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