1 /***************************************************************************
2 * _ _ ____ _
3 * Project ___| | | | _ \| |
4 * / __| | | | |_) | |
5 * | (__| |_| | _ <| |___
6 * \___|\___/|_| \_\_____|
7 *
8 * Copyright (C) 1997 - 2008, 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 http://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 * $Id: splay.c,v 1.12 2008-12-20 21:48:34 bagder Exp $
22 ***************************************************************************/
23
24 #include "setup.h"
25
26 #include "splay.h"
27
28 /*
29 * This macro compares two node keys i and j and returns:
30 *
31 * negative value: when i is smaller than j
32 * zero : when i is equal to j
33 * positive when : when i is larger than j
34 */
35 #define compare(i,j) Curl_splaycomparekeys((i),(j))
36
37 /*
38 * Splay using the key i (which may or may not be in the tree.) The starting
39 * root is t.
40 */
Curl_splay(struct timeval i,struct Curl_tree * t)41 struct Curl_tree *Curl_splay(struct timeval i,
42 struct Curl_tree *t)
43 {
44 struct Curl_tree N, *l, *r, *y;
45 long comp;
46
47 if(t == NULL)
48 return t;
49 N.smaller = N.larger = NULL;
50 l = r = &N;
51
52 for (;;) {
53 comp = compare(i, t->key);
54 if(comp < 0) {
55 if(t->smaller == NULL)
56 break;
57 if(compare(i, t->smaller->key) < 0) {
58 y = t->smaller; /* rotate smaller */
59 t->smaller = y->larger;
60 y->larger = t;
61 t = y;
62 if(t->smaller == NULL)
63 break;
64 }
65 r->smaller = t; /* link smaller */
66 r = t;
67 t = t->smaller;
68 }
69 else if(comp > 0) {
70 if(t->larger == NULL)
71 break;
72 if(compare(i, t->larger->key) > 0) {
73 y = t->larger; /* rotate larger */
74 t->larger = y->smaller;
75 y->smaller = t;
76 t = y;
77 if(t->larger == NULL)
78 break;
79 }
80 l->larger = t; /* link larger */
81 l = t;
82 t = t->larger;
83 }
84 else
85 break;
86 }
87
88 l->larger = t->smaller; /* assemble */
89 r->smaller = t->larger;
90 t->smaller = N.larger;
91 t->larger = N.smaller;
92
93 return t;
94 }
95
96 /* Insert key i into the tree t. Return a pointer to the resulting tree or
97 NULL if something went wrong. */
Curl_splayinsert(struct timeval i,struct Curl_tree * t,struct Curl_tree * node)98 struct Curl_tree *Curl_splayinsert(struct timeval i,
99 struct Curl_tree *t,
100 struct Curl_tree *node)
101 {
102 static struct timeval KEY_NOTUSED = {-1,-1}; /* key that will *NEVER* appear */
103
104 if(node == NULL)
105 return t;
106
107 if(t != NULL) {
108 t = Curl_splay(i,t);
109 if(compare(i, t->key)==0) {
110 /* There already exists a node in the tree with the very same key. Build
111 a linked list of nodes. We make the new 'node' struct the new master
112 node and make the previous node the first one in the 'same' list. */
113
114 node->same = t;
115 node->key = i;
116 node->smaller = t->smaller;
117 node->larger = t->larger;
118
119 t->smaller = node; /* in the sub node for this same key, we use the
120 smaller pointer to point back to the master
121 node */
122
123 t->key = KEY_NOTUSED; /* and we set the key in the sub node to NOTUSED
124 to quickly identify this node as a subnode */
125
126 return node; /* new root node */
127 }
128 }
129
130 if(t == NULL) {
131 node->smaller = node->larger = NULL;
132 }
133 else if(compare(i, t->key) < 0) {
134 node->smaller = t->smaller;
135 node->larger = t;
136 t->smaller = NULL;
137
138 }
139 else {
140 node->larger = t->larger;
141 node->smaller = t;
142 t->larger = NULL;
143 }
144 node->key = i;
145
146 node->same = NULL; /* no identical node (yet) */
147 return node;
148 }
149
150 #if 0
151 /* Deletes 'i' from the tree if it's there (with an exact match). Returns a
152 pointer to the resulting tree.
153
154 Function not used in libcurl.
155 */
156 struct Curl_tree *Curl_splayremove(struct timeval i,
157 struct Curl_tree *t,
158 struct Curl_tree **removed)
159 {
160 struct Curl_tree *x;
161
162 *removed = NULL; /* default to no removed */
163
164 if(t==NULL)
165 return NULL;
166
167 t = Curl_splay(i,t);
168 if(compare(i, t->key) == 0) { /* found it */
169
170 /* FIRST! Check if there is a list with identical sizes */
171 if((x = t->same) != NULL) {
172 /* there is, pick one from the list */
173
174 /* 'x' is the new root node */
175
176 x->key = t->key;
177 x->larger = t->larger;
178 x->smaller = t->smaller;
179
180 *removed = t;
181 return x; /* new root */
182 }
183
184 if(t->smaller == NULL) {
185 x = t->larger;
186 }
187 else {
188 x = Curl_splay(i, t->smaller);
189 x->larger = t->larger;
190 }
191 *removed = t;
192
193 return x;
194 }
195 else
196 return t; /* It wasn't there */
197 }
198 #endif
199
200 /* Finds and deletes the best-fit node from the tree. Return a pointer to the
201 resulting tree. best-fit means the node with the given or lower key */
Curl_splaygetbest(struct timeval i,struct Curl_tree * t,struct Curl_tree ** removed)202 struct Curl_tree *Curl_splaygetbest(struct timeval i,
203 struct Curl_tree *t,
204 struct Curl_tree **removed)
205 {
206 struct Curl_tree *x;
207
208 if(!t) {
209 *removed = NULL; /* none removed since there was no root */
210 return NULL;
211 }
212
213 t = Curl_splay(i,t);
214 if(compare(i, t->key) < 0) {
215 /* too big node, try the smaller chain */
216 if(t->smaller)
217 t=Curl_splay(t->smaller->key, t);
218 else {
219 /* fail */
220 *removed = NULL;
221 return t;
222 }
223 }
224
225 if(compare(i, t->key) >= 0) { /* found it */
226 /* FIRST! Check if there is a list with identical keys */
227 x = t->same;
228 if(x) {
229 /* there is, pick one from the list */
230
231 /* 'x' is the new root node */
232
233 x->key = t->key;
234 x->larger = t->larger;
235 x->smaller = t->smaller;
236
237 *removed = t;
238 return x; /* new root */
239 }
240
241 if(t->smaller == NULL) {
242 x = t->larger;
243 }
244 else {
245 x = Curl_splay(i, t->smaller);
246 x->larger = t->larger;
247 }
248 *removed = t;
249
250 return x;
251 }
252 else {
253 *removed = NULL; /* no match */
254 return t; /* It wasn't there */
255 }
256 }
257
258
259 /* Deletes the very node we point out from the tree if it's there. Stores a
260 pointer to the new resulting tree in 'newroot'.
261
262 Returns zero on success and non-zero on errors! TODO: document error codes.
263 When returning error, it does not touch the 'newroot' pointer.
264
265 NOTE: when the last node of the tree is removed, there's no tree left so
266 'newroot' will be made to point to NULL.
267 */
Curl_splayremovebyaddr(struct Curl_tree * t,struct Curl_tree * removenode,struct Curl_tree ** newroot)268 int Curl_splayremovebyaddr(struct Curl_tree *t,
269 struct Curl_tree *removenode,
270 struct Curl_tree **newroot)
271 {
272 static struct timeval KEY_NOTUSED = {-1,-1}; /* key that will *NEVER* appear */
273 struct Curl_tree *x;
274
275 if(!t || !removenode)
276 return 1;
277
278 if(compare(KEY_NOTUSED, removenode->key) == 0) {
279 /* Key set to NOTUSED means it is a subnode within a 'same' linked list
280 and thus we can unlink it easily. The 'smaller' link of a subnode
281 links to the parent node. */
282 if(removenode->smaller == NULL)
283 return 3;
284
285 removenode->smaller->same = removenode->same;
286 if(removenode->same)
287 removenode->same->smaller = removenode->smaller;
288
289 /* Ensures that double-remove gets caught. */
290 removenode->smaller = NULL;
291
292 /* voila, we're done! */
293 *newroot = t; /* return the same root */
294 return 0;
295 }
296
297 t = Curl_splay(removenode->key, t);
298
299 /* First make sure that we got the same root node as the one we want
300 to remove, as otherwise we might be trying to remove a node that
301 isn't actually in the tree.
302
303 We cannot just compare the keys here as a double remove in quick
304 succession of a node with key != KEY_NOTUSED && same != NULL
305 could return the same key but a different node. */
306 if(t != removenode)
307 return 2;
308
309 /* Check if there is a list with identical sizes, as then we're trying to
310 remove the root node of a list of nodes with identical keys. */
311 x = t->same;
312 if(x) {
313 /* 'x' is the new root node, we just make it use the root node's
314 smaller/larger links */
315
316 x->key = t->key;
317 x->larger = t->larger;
318 x->smaller = t->smaller;
319 }
320 else {
321 /* Remove the root node */
322 if(t->smaller == NULL)
323 x = t->larger;
324 else {
325 x = Curl_splay(removenode->key, t->smaller);
326 x->larger = t->larger;
327 }
328 }
329
330 *newroot = x; /* store new root pointer */
331
332 return 0;
333 }
334
335 #ifdef CURLDEBUG
336
Curl_splayprint(struct Curl_tree * t,int d,char output)337 void Curl_splayprint(struct Curl_tree * t, int d, char output)
338 {
339 struct Curl_tree *node;
340 int i;
341 int count;
342 if(t == NULL)
343 return;
344
345 Curl_splayprint(t->larger, d+1, output);
346 for (i=0; i<d; i++)
347 if(output)
348 fprintf(stderr, " ");
349
350 if(output) {
351 #ifdef TEST_SPLAY
352 fprintf(stderr, "%ld[%d]", (long)t->key.tv_usec, i);
353 #else
354 fprintf(stderr, "%ld.%ld[%d]", (long)t->key.tv_sec, (long)t->key.tv_usec, i);
355 #endif
356 }
357
358 for(count=0, node = t->same; node; node = node->same, count++)
359 ;
360
361 if(output) {
362 if(count)
363 fprintf(stderr, " [%d more]\n", count);
364 else
365 fprintf(stderr, "\n");
366 }
367
368 Curl_splayprint(t->smaller, d+1, output);
369 }
370 #endif
371
372 #ifdef TEST_SPLAY
373
374 /*#define TEST2 */
375 #define MAX 50
376 #define TEST2
377
378 /* A sample use of these functions. Start with the empty tree, insert some
379 stuff into it, and then delete it */
main(int argc,argv_item_t argv[])380 int main(int argc, argv_item_t argv[])
381 {
382 struct Curl_tree *root, *t;
383 void *ptrs[MAX];
384 int adds=0;
385 int rc;
386
387 static const long sizes[]={
388 50, 60, 50, 100, 60, 200, 120, 300, 400, 200, 256, 122, 60, 120, 200, 300,
389 220, 80, 90, 50, 100, 60, 200, 120, 300, 400, 200, 256, 122, 60, 120, 200,
390 300, 220, 80, 90, 50, 100, 60, 200, 120, 300, 400, 200, 256, 122, 60, 120,
391 200, 300, 220, 80, 90};
392 int i;
393 root = NULL; /* the empty tree */
394
395 for (i = 0; i < MAX; i++) {
396 struct timeval key;
397 ptrs[i] = t = malloc(sizeof(struct Curl_tree));
398
399 key.tv_sec = 0;
400 #ifdef TEST2
401 key.tv_usec = sizes[i];
402 #elif defined(TEST1)
403 key.tv_usec = (541*i)%1023;
404 #elif defined(TEST3)
405 key.tv_usec = 100;
406 #endif
407
408 t->payload = (void *)key.tv_usec; /* for simplicity */
409 if(!t) {
410 puts("out of memory!");
411 return 0;
412 }
413 root = Curl_splayinsert(key, root, t);
414 }
415
416 #if 0
417 puts("Result:");
418 Curl_splayprint(root, 0, 1);
419 #endif
420
421 #if 1
422 for (i = 0; i < MAX; i++) {
423 int rem = (i+7)%MAX;
424 struct Curl_tree *r;
425 printf("Tree look:\n");
426 Curl_splayprint(root, 0, 1);
427 printf("remove pointer %d, payload %ld\n", rem,
428 (long)((struct Curl_tree *)ptrs[rem])->payload);
429 rc = Curl_splayremovebyaddr(root, (struct Curl_tree *)ptrs[rem], &root);
430 if(rc)
431 /* failed! */
432 printf("remove %d failed!\n", rem);
433 }
434 #endif
435
436 return 0;
437 }
438
439 #endif /* TEST_SPLAY */
440