| 1 |
/*************************************************************************** |
| 2 |
* _ _ ____ _ |
| 3 |
* Project ___| | | | _ \| | |
| 4 |
* / __| | | | |_) | | |
| 5 |
* | (__| |_| | _ <| |___ |
| 6 |
* \___|\___/|_| \_\_____| |
| 7 |
* |
| 8 |
* Copyright (C) 1998 - 2018, Daniel Stenberg, <[email protected]>, 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 |
#include "warnless.h" |
| 26 |
|
| 27 |
|
| 28 |
static CURLcode unit_setup(void) |
| 29 |
{ |
| 30 |
return CURLE_OK; |
| 31 |
} |
| 32 |
|
| 33 |
static void unit_stop(void) |
| 34 |
{ |
| 35 |
|
| 36 |
} |
| 37 |
|
| 38 |
static void splayprint(struct Curl_tree * t, int d, char output) |
| 39 |
{ |
| 40 |
struct Curl_tree *node; |
| 41 |
int i; |
| 42 |
int count; |
| 43 |
if(t == NULL) |
| 44 |
return; |
| 45 |
|
| 46 |
splayprint(t->larger, d + 1, output); |
| 47 |
for(i = 0; i<d; i++) |
| 48 |
if(output) |
| 49 |
printf(" "); |
| 50 |
|
| 51 |
if(output) { |
| 52 |
printf("%ld.%ld[%d]", (long)t->key.tv_sec, |
| 53 |
(long)t->key.tv_usec, i); |
| 54 |
} |
| 55 |
|
| 56 |
for(count = 0, node = t->samen; node != t; node = node->samen, count++) |
| 57 |
; |
| 58 |
|
| 59 |
if(output) { |
| 60 |
if(count) |
| 61 |
printf(" [%d more]\n", count); |
| 62 |
else |
| 63 |
printf("\n"); |
| 64 |
} |
| 65 |
|
| 66 |
splayprint(t->smaller, d + 1, output); |
| 67 |
} |
| 68 |
|
| 69 |
UNITTEST_START |
| 70 |
|
| 71 |
/* number of nodes to add to the splay tree */ |
| 72 |
#define NUM_NODES 50 |
| 73 |
|
| 74 |
struct Curl_tree *root, *removed; |
| 75 |
struct Curl_tree nodes[NUM_NODES*3]; |
| 76 |
size_t storage[NUM_NODES*3]; |
| 77 |
int rc; |
| 78 |
int i, j; |
| 79 |
struct curltime tv_now = {0, 0}; |
| 80 |
root = NULL; /* the empty tree */ |
| 81 |
|
| 82 |
/* add nodes */ |
| 83 |
for(i = 0; i < NUM_NODES; i++) { |
| 84 |
struct curltime key; |
| 85 |
|
| 86 |
key.tv_sec = 0; |
| 87 |
key.tv_usec = (541*i)%1023; |
| 88 |
storage[i] = key.tv_usec; |
| 89 |
nodes[i].payload = &storage[i]; |
| 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 %zu\n", rem, |
| 101 |
*(size_t *)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 |
storage[i * 3 + j] = key.tv_usec*10 + j; |
| 122 |
nodes[i * 3 + j].payload = &storage[i * 3 + j]; |
| 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 %zu[%zu]\n", |
| 134 |
(*(size_t *)removed->payload) / 10, |
| 135 |
(*(size_t *)removed->payload) % 10); |
| 136 |
root = Curl_splaygetbest(tv_now, root, &removed); |
| 137 |
} |
| 138 |
} |
| 139 |
|
| 140 |
fail_unless(root == NULL, "tree not empty when it should be"); |
| 141 |
|
| 142 |
UNITTEST_STOP |