unit1309.c 3.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144
  1. /***************************************************************************
  2. * _ _ ____ _
  3. * Project ___| | | | _ \| |
  4. * / __| | | | |_) | |
  5. * | (__| |_| | _ <| |___
  6. * \___|\___/|_| \_\_____|
  7. *
  8. * Copyright (C) 1998 - 2022, Daniel Stenberg, <daniel@haxx.se>, et al.
  9. *
  10. * This software is licensed as described in the file COPYING, which
  11. * you should have received as part of this distribution. The terms
  12. * are also available at https://curl.se/docs/copyright.html.
  13. *
  14. * You may opt to use, copy, modify, merge, publish, distribute and/or sell
  15. * copies of the Software, and permit persons to whom the Software is
  16. * furnished to do so, under the terms of the COPYING file.
  17. *
  18. * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  19. * KIND, either express or implied.
  20. *
  21. * SPDX-License-Identifier: curl
  22. *
  23. ***************************************************************************/
  24. #include "curlcheck.h"
  25. #include "splay.h"
  26. #include "warnless.h"
  27. static CURLcode unit_setup(void)
  28. {
  29. return CURLE_OK;
  30. }
  31. static void unit_stop(void)
  32. {
  33. }
  34. static void splayprint(struct Curl_tree *t, int d, char output)
  35. {
  36. struct Curl_tree *node;
  37. int i;
  38. int count;
  39. if(!t)
  40. return;
  41. splayprint(t->larger, d + 1, output);
  42. for(i = 0; i<d; i++)
  43. if(output)
  44. printf(" ");
  45. if(output) {
  46. printf("%ld.%ld[%d]", (long)t->key.tv_sec,
  47. (long)t->key.tv_usec, i);
  48. }
  49. for(count = 0, node = t->samen; node != t; node = node->samen, count++)
  50. ;
  51. if(output) {
  52. if(count)
  53. printf(" [%d more]\n", count);
  54. else
  55. printf("\n");
  56. }
  57. splayprint(t->smaller, d + 1, output);
  58. }
  59. UNITTEST_START
  60. /* number of nodes to add to the splay tree */
  61. #define NUM_NODES 50
  62. struct Curl_tree *root, *removed;
  63. struct Curl_tree nodes[NUM_NODES*3];
  64. size_t storage[NUM_NODES*3];
  65. int rc;
  66. int i, j;
  67. struct curltime tv_now = {0, 0};
  68. root = NULL; /* the empty tree */
  69. /* add nodes */
  70. for(i = 0; i < NUM_NODES; i++) {
  71. struct curltime key;
  72. key.tv_sec = 0;
  73. key.tv_usec = (541*i)%1023;
  74. storage[i] = key.tv_usec;
  75. nodes[i].payload = &storage[i];
  76. root = Curl_splayinsert(key, root, &nodes[i]);
  77. }
  78. puts("Result:");
  79. splayprint(root, 0, 1);
  80. for(i = 0; i < NUM_NODES; i++) {
  81. int rem = (i + 7)%NUM_NODES;
  82. printf("Tree look:\n");
  83. splayprint(root, 0, 1);
  84. printf("remove pointer %d, payload %zu\n", rem,
  85. *(size_t *)nodes[rem].payload);
  86. rc = Curl_splayremove(root, &nodes[rem], &root);
  87. if(rc) {
  88. /* failed! */
  89. printf("remove %d failed!\n", rem);
  90. fail("remove");
  91. }
  92. }
  93. fail_unless(root == NULL, "tree not empty after removing all nodes");
  94. /* rebuild tree */
  95. for(i = 0; i < NUM_NODES; i++) {
  96. struct curltime key;
  97. key.tv_sec = 0;
  98. key.tv_usec = (541*i)%1023;
  99. /* add some nodes with the same key */
  100. for(j = 0; j <= i % 3; j++) {
  101. storage[i * 3 + j] = key.tv_usec*10 + j;
  102. nodes[i * 3 + j].payload = &storage[i * 3 + j];
  103. root = Curl_splayinsert(key, root, &nodes[i * 3 + j]);
  104. }
  105. }
  106. removed = NULL;
  107. for(i = 0; i <= 1100; i += 100) {
  108. printf("Removing nodes not larger than %d\n", i);
  109. tv_now.tv_usec = i;
  110. root = Curl_splaygetbest(tv_now, root, &removed);
  111. while(removed) {
  112. printf("removed payload %zu[%zu]\n",
  113. (*(size_t *)removed->payload) / 10,
  114. (*(size_t *)removed->payload) % 10);
  115. root = Curl_splaygetbest(tv_now, root, &removed);
  116. }
  117. }
  118. fail_unless(root == NULL, "tree not empty when it should be");
  119. UNITTEST_STOP