diff options
Diffstat (limited to 'Utilities/cmcurl/lib/splay.c')
| -rw-r--r-- | Utilities/cmcurl/lib/splay.c | 267 |
1 files changed, 65 insertions, 202 deletions
diff --git a/Utilities/cmcurl/lib/splay.c b/Utilities/cmcurl/lib/splay.c index 9fb66c7..5bb7065 100644 --- a/Utilities/cmcurl/lib/splay.c +++ b/Utilities/cmcurl/lib/splay.c @@ -5,7 +5,7 @@ * | (__| |_| | _ <| |___ * \___|\___/|_| \_\_____| * - * Copyright (C) 1997 - 2006, Daniel Stenberg, <daniel@haxx.se>, et al. + * Copyright (C) 1997 - 2014, Daniel Stenberg, <daniel@haxx.se>, et al. * * This software is licensed as described in the file COPYING, which * you should have received as part of this distribution. The terms @@ -18,59 +18,62 @@ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY * KIND, either express or implied. * - * $Id$ ***************************************************************************/ -#include <stdio.h> -#include <stdlib.h> +#include "curl_setup.h" #include "splay.h" -#define compare(i,j) ((i)-(j)) - -/* Set this to a key value that will *NEVER* appear otherwise */ -#define KEY_NOTUSED -1 +/* + * This macro compares two node keys i and j and returns: + * + * negative value: when i is smaller than j + * zero : when i is equal to j + * positive when : when i is larger than j + */ +#define compare(i,j) Curl_splaycomparekeys((i),(j)) /* * Splay using the key i (which may or may not be in the tree.) The starting * root is t. */ -struct Curl_tree *Curl_splay(int i, struct Curl_tree *t) +struct Curl_tree *Curl_splay(struct timeval i, + struct Curl_tree *t) { struct Curl_tree N, *l, *r, *y; - int comp; + long comp; - if (t == NULL) + if(t == NULL) return t; N.smaller = N.larger = NULL; l = r = &N; - for (;;) { + for(;;) { comp = compare(i, t->key); - if (comp < 0) { - if (t->smaller == NULL) + if(comp < 0) { + if(t->smaller == NULL) break; - if (compare(i, t->smaller->key) < 0) { + if(compare(i, t->smaller->key) < 0) { y = t->smaller; /* rotate smaller */ t->smaller = y->larger; y->larger = t; t = y; - if (t->smaller == NULL) + if(t->smaller == NULL) break; } r->smaller = t; /* link smaller */ r = t; t = t->smaller; } - else if (comp > 0) { - if (t->larger == NULL) + else if(comp > 0) { + if(t->larger == NULL) break; - if (compare(i, t->larger->key) > 0) { + if(compare(i, t->larger->key) > 0) { y = t->larger; /* rotate larger */ t->larger = y->smaller; y->smaller = t; t = y; - if (t->larger == NULL) + if(t->larger == NULL) break; } l->larger = t; /* link larger */ @@ -90,17 +93,22 @@ struct Curl_tree *Curl_splay(int i, struct Curl_tree *t) } /* Insert key i into the tree t. Return a pointer to the resulting tree or - NULL if something went wrong. */ -struct Curl_tree *Curl_splayinsert(int i, + * NULL if something went wrong. + * + * @unittest: 1309 + */ +struct Curl_tree *Curl_splayinsert(struct timeval i, struct Curl_tree *t, struct Curl_tree *node) { - if (node == NULL) + static const struct timeval KEY_NOTUSED = {-1,-1}; /* will *NEVER* appear */ + + if(node == NULL) return t; - if (t != NULL) { + if(t != NULL) { t = Curl_splay(i,t); - if (compare(i, t->key)==0) { + if(compare(i, t->key)==0) { /* There already exists a node in the tree with the very same key. Build a linked list of nodes. We make the new 'node' struct the new master node and make the previous node the first one in the 'same' list. */ @@ -121,10 +129,10 @@ struct Curl_tree *Curl_splayinsert(int i, } } - if (t == NULL) { + if(t == NULL) { node->smaller = node->larger = NULL; } - else if (compare(i, t->key) < 0) { + else if(compare(i, t->key) < 0) { node->smaller = t->smaller; node->larger = t; t->smaller = NULL; @@ -141,63 +149,15 @@ struct Curl_tree *Curl_splayinsert(int i, return node; } -#if 0 -/* Deletes 'i' from the tree if it's there (with an exact match). Returns a - pointer to the resulting tree. - - Function not used in libcurl. -*/ -struct Curl_tree *Curl_splayremove(int i, struct Curl_tree *t, - struct Curl_tree **removed) -{ - struct Curl_tree *x; - - *removed = NULL; /* default to no removed */ - - if (t==NULL) - return NULL; - - t = Curl_splay(i,t); - if (compare(i, t->key) == 0) { /* found it */ - - /* FIRST! Check if there is a list with identical sizes */ - if((x = t->same)) { - /* there is, pick one from the list */ - - /* 'x' is the new root node */ - - x->key = t->key; - x->larger = t->larger; - x->smaller = t->smaller; - - *removed = t; - return x; /* new root */ - } - - if (t->smaller == NULL) { - x = t->larger; - } - else { - x = Curl_splay(i, t->smaller); - x->larger = t->larger; - } - *removed = t; - - return x; - } - else - return t; /* It wasn't there */ -} -#endif - /* Finds and deletes the best-fit node from the tree. Return a pointer to the - resulting tree. best-fit means the node with the given or lower number */ -struct Curl_tree *Curl_splaygetbest(int i, struct Curl_tree *t, + resulting tree. best-fit means the node with the given or lower key */ +struct Curl_tree *Curl_splaygetbest(struct timeval i, + struct Curl_tree *t, struct Curl_tree **removed) { struct Curl_tree *x; - if (!t) { + if(!t) { *removed = NULL; /* none removed since there was no root */ return NULL; } @@ -214,8 +174,8 @@ struct Curl_tree *Curl_splaygetbest(int i, struct Curl_tree *t, } } - if (compare(i, t->key) >= 0) { /* found it */ - /* FIRST! Check if there is a list with identical sizes */ + if(compare(i, t->key) >= 0) { /* found it */ + /* FIRST! Check if there is a list with identical keys */ x = t->same; if(x) { /* there is, pick one from the list */ @@ -230,7 +190,7 @@ struct Curl_tree *Curl_splaygetbest(int i, struct Curl_tree *t, return x; /* new root */ } - if (t->smaller == NULL) { + if(t->smaller == NULL) { x = t->larger; } else { @@ -249,43 +209,46 @@ struct Curl_tree *Curl_splaygetbest(int i, struct Curl_tree *t, /* Deletes the very node we point out from the tree if it's there. Stores a - pointer to the new resulting tree in 'newroot'. - - Returns zero on success and non-zero on errors! TODO: document error codes. - When returning error, it does not touch the 'newroot' pointer. - - NOTE: when the last node of the tree is removed, there's no tree left so - 'newroot' will be made to point to NULL. -*/ + * pointer to the new resulting tree in 'newroot'. + * + * Returns zero on success and non-zero on errors! TODO: document error codes. + * When returning error, it does not touch the 'newroot' pointer. + * + * NOTE: when the last node of the tree is removed, there's no tree left so + * 'newroot' will be made to point to NULL. + * + * @unittest: 1309 + */ int Curl_splayremovebyaddr(struct Curl_tree *t, - struct Curl_tree *remove, + struct Curl_tree *removenode, struct Curl_tree **newroot) { + static const struct timeval KEY_NOTUSED = {-1,-1}; /* will *NEVER* appear */ struct Curl_tree *x; - if (!t || !remove) + if(!t || !removenode) return 1; - if(KEY_NOTUSED == remove->key) { + if(compare(KEY_NOTUSED, removenode->key) == 0) { /* Key set to NOTUSED means it is a subnode within a 'same' linked list and thus we can unlink it easily. The 'smaller' link of a subnode links to the parent node. */ - if (remove->smaller == NULL) + if(removenode->smaller == NULL) return 3; - remove->smaller->same = remove->same; - if(remove->same) - remove->same->smaller = remove->smaller; + removenode->smaller->same = removenode->same; + if(removenode->same) + removenode->same->smaller = removenode->smaller; /* Ensures that double-remove gets caught. */ - remove->smaller = NULL; + removenode->smaller = NULL; /* voila, we're done! */ *newroot = t; /* return the same root */ return 0; } - t = Curl_splay(remove->key, t); + t = Curl_splay(removenode->key, t); /* First make sure that we got the same root node as the one we want to remove, as otherwise we might be trying to remove a node that @@ -294,7 +257,7 @@ int Curl_splayremovebyaddr(struct Curl_tree *t, We cannot just compare the keys here as a double remove in quick succession of a node with key != KEY_NOTUSED && same != NULL could return the same key but a different node. */ - if(t != remove) + if(t != removenode) return 2; /* Check if there is a list with identical sizes, as then we're trying to @@ -310,10 +273,10 @@ int Curl_splayremovebyaddr(struct Curl_tree *t, } else { /* Remove the root node */ - if (t->smaller == NULL) + if(t->smaller == NULL) x = t->larger; else { - x = Curl_splay(remove->key, t->smaller); + x = Curl_splay(removenode->key, t->smaller); x->larger = t->larger; } } @@ -323,103 +286,3 @@ int Curl_splayremovebyaddr(struct Curl_tree *t, return 0; } -#ifdef CURLDEBUG - -void Curl_splayprint(struct Curl_tree * t, int d, char output) -{ - struct Curl_tree *node; - int i; - int count; - if (t == NULL) - return; - - Curl_splayprint(t->larger, d+1, output); - for (i=0; i<d; i++) - if(output) - printf(" "); - - if(output) { - printf("%d[%d]", t->key, i); - } - - for(count=0, node = t->same; node; node = node->same, count++) - ; - - if(output) { - if(count) - printf(" [%d more]\n", count); - else - printf("\n"); - } - - Curl_splayprint(t->smaller, d+1, output); -} -#endif - -#ifdef TEST_SPLAY - -/*#define TEST2 */ -#define MAX 50 -#define TEST2 - -/* A sample use of these functions. Start with the empty tree, insert some - stuff into it, and then delete it */ -int main(int argc, char **argv) -{ - struct Curl_tree *root, *t; - void *ptrs[MAX]; - int adds=0; - int rc; - - long sizes[]={ - 50, 60, 50, 100, 60, 200, 120, 300, 400, 200, 256, 122, 60, 120, 200, 300, - 220, 80, 90, 50, 100, 60, 200, 120, 300, 400, 200, 256, 122, 60, 120, 200, - 300, 220, 80, 90, 50, 100, 60, 200, 120, 300, 400, 200, 256, 122, 60, 120, - 200, 300, 220, 80, 90}; - int i; - root = NULL; /* the empty tree */ - - for (i = 0; i < MAX; i++) { - int key; - ptrs[i] = t = (struct Curl_tree *)malloc(sizeof(struct Curl_tree)); - -#ifdef TEST2 - key = sizes[i]; -#elif defined(TEST1) - key = (541*i)%1023; -#elif defined(TEST3) - key = 100; -#endif - - t->payload = (void *)key; /* for simplicity */ - if(!t) { - puts("out of memory!"); - return 0; - } - root = Curl_splayinsert(key, root, t); - } - -#if 0 - puts("Result:"); - Curl_splayprint(root, 0, 1); -#endif - -#if 1 - for (i = 0; i < MAX; i++) { - int rem = (i+7)%MAX; - struct Curl_tree *r; - printf("Tree look:\n"); - Curl_splayprint(root, 0, 1); - printf("remove pointer %d, payload %d\n", rem, - (int)((struct Curl_tree *)ptrs[rem])->payload); - rc = Curl_splayremovebyaddr(root, (struct Curl_tree *)ptrs[rem], &root); - if(rc) - /* failed! */ - printf("remove %d failed!\n", rem); - } -#endif - - return 0; -} - -#endif /* TEST_SPLAY */ |