1 /***************************************************************************
2 * _ _ ____ _
3 * Project ___| | | | _ \| |
4 * / __| | | | |_) | |
5 * | (__| |_| | _ <| |___
6 * \___|\___/|_| \_\_____|
7 *
8 * Copyright (C) 1998 - 2018, 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.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
unit_setup(void)28 static CURLcode unit_setup(void)
29 {
30 return CURLE_OK;
31 }
32
unit_stop(void)33 static void unit_stop(void)
34 {
35
36 }
37
splayprint(struct Curl_tree * t,int d,char output)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
143