1 /*************************************************************************** 2 * _ _ ____ _ 3 * Project ___| | | | _ \| | 4 * / __| | | | |_) | | 5 * | (__| |_| | _ <| |___ 6 * \___|\___/|_| \_\_____| 7 * 8 * Copyright (C) 1998 - 2011, 2017, Daniel Stenberg, <daniel (at) 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.haxx.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 ***************************************************************************/ 22 #include "curlcheck.h" 23 24 #include "splay.h" 25 26 27 static CURLcode unit_setup(void) 28 { 29 return CURLE_OK; 30 } 31 32 static void unit_stop(void) 33 { 34 35 } 36 37 static void splayprint(struct Curl_tree * t, int d, char output) 38 { 39 struct Curl_tree *node; 40 int i; 41 int count; 42 if(t == NULL) 43 return; 44 45 splayprint(t->larger, d + 1, output); 46 for(i = 0; i<d; i++) 47 if(output) 48 printf(" "); 49 50 if(output) { 51 printf("%ld.%ld[%d]", (long)t->key.tv_sec, 52 (long)t->key.tv_usec, i); 53 } 54 55 for(count = 0, node = t->samen; node != t; node = node->samen, count++) 56 ; 57 58 if(output) { 59 if(count) 60 printf(" [%d more]\n", count); 61 else 62 printf("\n"); 63 } 64 65 splayprint(t->smaller, d + 1, output); 66 } 67 68 UNITTEST_START 69 70 /* number of nodes to add to the splay tree */ 71 #define NUM_NODES 50 72 73 struct Curl_tree *root, *removed; 74 struct Curl_tree nodes[NUM_NODES*3]; 75 int rc; 76 int i, j; 77 struct curltime tv_now = {0, 0}; 78 root = NULL; /* the empty tree */ 79 80 /* add nodes */ 81 for(i = 0; i < NUM_NODES; i++) { 82 struct curltime key; 83 size_t payload; 84 85 key.tv_sec = 0; 86 key.tv_usec = (541*i)%1023; 87 payload = (size_t) key.tv_usec; 88 89 nodes[i].payload = (void *)payload; /* for simplicity */ 90 root = Curl_splayinsert(key, root, &nodes[i]); 91 } 92 93 puts("Result:"); 94 splayprint(root, 0, 1); 95 96 for(i = 0; i < NUM_NODES; i++) { 97 int rem = (i + 7)%NUM_NODES; 98 printf("Tree look:\n"); 99 splayprint(root, 0, 1); 100 printf("remove pointer %d, payload %ld\n", rem, 101 (long)(nodes[rem].payload)); 102 rc = Curl_splayremovebyaddr(root, &nodes[rem], &root); 103 if(rc) { 104 /* failed! */ 105 printf("remove %d failed!\n", rem); 106 fail("remove"); 107 } 108 } 109 110 fail_unless(root == NULL, "tree not empty after removing all nodes"); 111 112 /* rebuild tree */ 113 for(i = 0; i < NUM_NODES; i++) { 114 struct curltime key; 115 116 key.tv_sec = 0; 117 key.tv_usec = (541*i)%1023; 118 119 /* add some nodes with the same key */ 120 for(j = 0; j <= i % 3; j++) { 121 size_t payload = key.tv_usec*10 + j; 122 nodes[i * 3 + j].payload = (void *)payload; /* for simplicity */ 123 root = Curl_splayinsert(key, root, &nodes[i * 3 + j]); 124 } 125 } 126 127 removed = NULL; 128 for(i = 0; i <= 1100; i += 100) { 129 printf("Removing nodes not larger than %d\n", i); 130 tv_now.tv_usec = i; 131 root = Curl_splaygetbest(tv_now, root, &removed); 132 while(removed != NULL) { 133 printf("removed payload %ld[%ld]\n", (long)(removed->payload) / 10, 134 (long)(removed->payload) % 10); 135 root = Curl_splaygetbest(tv_now, root, &removed); 136 } 137 } 138 139 fail_unless(root == NULL, "tree not empty when it should be"); 140 141 UNITTEST_STOP 142 143 144 145 146
