aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lib/splay.c179
-rw-r--r--tests/data/test13091457
-rw-r--r--tests/unit/Makefile.inc3
-rw-r--r--tests/unit/unit1309.c113
4 files changed, 1586 insertions, 166 deletions
diff --git a/lib/splay.c b/lib/splay.c
index ce8a8a57b..b6664e6df 100644
--- a/lib/splay.c
+++ b/lib/splay.c
@@ -93,7 +93,10 @@ struct Curl_tree *Curl_splay(struct timeval i,
}
/* Insert key i into the tree t. Return a pointer to the resulting tree or
- NULL if something went wrong. */
+ * NULL if something went wrong.
+ *
+ * @unittest: 1309
+ */
struct Curl_tree *Curl_splayinsert(struct timeval i,
struct Curl_tree *t,
struct Curl_tree *node)
@@ -146,56 +149,6 @@ struct Curl_tree *Curl_splayinsert(struct timeval 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(struct timeval 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) != NULL) {
- /* 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 key */
struct Curl_tree *Curl_splaygetbest(struct timeval i,
@@ -256,14 +209,16 @@ struct Curl_tree *Curl_splaygetbest(struct timeval i,
/* 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 *removenode,
struct Curl_tree **newroot)
@@ -331,109 +286,3 @@ int Curl_splayremovebyaddr(struct Curl_tree *t,
return 0;
}
-#ifdef DEBUGBUILD
-
-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)
- fprintf(stderr, " ");
-
- if(output) {
-#ifdef TEST_SPLAY
- fprintf(stderr, "%ld[%d]", (long)t->key.tv_usec, i);
-#else
- fprintf(stderr, "%ld.%ld[%d]", (long)t->key.tv_sec,
- (long)t->key.tv_usec, i);
-#endif
- }
-
- for(count=0, node = t->same; node; node = node->same, count++)
- ;
-
- if(output) {
- if(count)
- fprintf(stderr, " [%d more]\n", count);
- else
- fprintf(stderr, "\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, argv_item_t argv[])
-{
- struct Curl_tree *root, *t;
- void *ptrs[MAX];
- int adds=0;
- int rc;
-
- static const 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++) {
- struct timeval key;
- ptrs[i] = t = malloc(sizeof(struct Curl_tree));
- if(!t) {
- puts("out of memory!");
- return 0;
- }
-
- key.tv_sec = 0;
-#ifdef TEST2
- key.tv_usec = sizes[i];
-#elif defined(TEST1)
- key.tv_usec = (541*i)%1023;
-#elif defined(TEST3)
- key.tv_usec = 100;
-#endif
-
- t->payload = (void *)key.tv_usec; /* for simplicity */
- 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 %ld\n", rem,
- (long)((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 */
diff --git a/tests/data/test1309 b/tests/data/test1309
new file mode 100644
index 000000000..c2f67ff10
--- /dev/null
+++ b/tests/data/test1309
@@ -0,0 +1,1457 @@
+<testcase>
+<info>
+<keywords>
+unittest
+splay
+</keywords>
+</info>
+
+#
+# Client-side
+<client>
+<server>
+none
+</server>
+<features>
+unittest
+</features>
+ <name>
+splay unit tests
+ </name>
+<tool>
+unit1309
+</tool>
+</client>
+
+<verify>
+<stdout>
+Result:
+ 0.1013[3]
+ 0.1003[2]
+ 0.954[3]
+ 0.944[1]
+0.934[0]
+ 0.895[1]
+ 0.885[4]
+ 0.875[3]
+ 0.836[4]
+ 0.826[7]
+ 0.816[6]
+ 0.777[5]
+ 0.767[9]
+ 0.757[8]
+ 0.718[7]
+ 0.708[10]
+ 0.698[9]
+ 0.659[8]
+ 0.649[9]
+ 0.639[10]
+ 0.600[12]
+ 0.590[13]
+ 0.580[11]
+ 0.541[6]
+ 0.531[9]
+ 0.521[10]
+ 0.472[8]
+ 0.462[9]
+ 0.413[7]
+ 0.403[2]
+ 0.393[3]
+ 0.354[5]
+ 0.344[4]
+ 0.334[5]
+ 0.295[7]
+ 0.285[6]
+ 0.275[7]
+ 0.236[9]
+ 0.226[8]
+ 0.216[9]
+ 0.177[11]
+ 0.167[12]
+ 0.157[10]
+ 0.118[11]
+ 0.108[13]
+ 0.98[12]
+ 0.59[13]
+ 0.49[15]
+ 0.39[14]
+ 0.0[15]
+Tree look:
+ 0.1013[3]
+ 0.1003[2]
+ 0.954[3]
+ 0.944[1]
+0.934[0]
+ 0.895[1]
+ 0.885[4]
+ 0.875[3]
+ 0.836[4]
+ 0.826[7]
+ 0.816[6]
+ 0.777[5]
+ 0.767[9]
+ 0.757[8]
+ 0.718[7]
+ 0.708[10]
+ 0.698[9]
+ 0.659[8]
+ 0.649[9]
+ 0.639[10]
+ 0.600[12]
+ 0.590[13]
+ 0.580[11]
+ 0.541[6]
+ 0.531[9]
+ 0.521[10]
+ 0.472[8]
+ 0.462[9]
+ 0.413[7]
+ 0.403[2]
+ 0.393[3]
+ 0.354[5]
+ 0.344[4]
+ 0.334[5]
+ 0.295[7]
+ 0.285[6]
+ 0.275[7]
+ 0.236[9]
+ 0.226[8]
+ 0.216[9]
+ 0.177[11]
+ 0.167[12]
+ 0.157[10]
+ 0.118[11]
+ 0.108[13]
+ 0.98[12]
+ 0.59[13]
+ 0.49[15]
+ 0.39[14]
+ 0.0[15]
+remove pointer 7, payload 718
+Tree look:
+ 0.1013[5]
+ 0.1003[4]
+ 0.954[5]
+ 0.944[3]
+ 0.934[2]
+ 0.895[1]
+ 0.885[4]
+ 0.875[3]
+ 0.836[2]
+ 0.826[5]
+ 0.816[4]
+ 0.777[3]
+ 0.767[5]
+ 0.757[4]
+0.708[0]
+ 0.698[2]
+ 0.659[3]
+ 0.649[4]
+ 0.639[5]
+ 0.600[7]
+ 0.590[8]
+ 0.580[6]
+ 0.541[1]
+ 0.531[5]
+ 0.521[6]
+ 0.472[4]
+ 0.462[5]
+ 0.413[3]
+ 0.403[2]
+ 0.393[3]
+ 0.354[5]
+ 0.344[4]
+ 0.334[5]
+ 0.295[7]
+ 0.285[6]
+ 0.275[7]
+ 0.236[9]
+ 0.226[8]
+ 0.216[9]
+ 0.177[11]
+ 0.167[12]
+ 0.157[10]
+ 0.118[11]
+ 0.108[13]
+ 0.98[12]
+ 0.59[13]
+ 0.49[15]
+ 0.39[14]
+ 0.0[15]
+remove pointer 8, payload 236
+Tree look:
+ 0.1013[7]
+ 0.1003[6]
+ 0.954[7]
+ 0.944[5]
+ 0.934[4]
+ 0.895[3]
+ 0.885[6]
+ 0.875[5]
+ 0.836[4]
+ 0.826[7]
+ 0.816[6]
+ 0.777[5]
+ 0.767[7]
+ 0.757[6]
+ 0.708[2]
+ 0.698[3]
+ 0.659[4]
+ 0.649[5]
+ 0.639[6]
+ 0.600[8]
+ 0.590[9]
+ 0.580[7]
+ 0.541[1]
+ 0.531[6]
+ 0.521[7]
+ 0.472[5]
+ 0.462[6]
+ 0.413[4]
+ 0.403[3]
+ 0.393[2]
+ 0.354[5]
+ 0.344[4]
+ 0.334[3]
+ 0.295[6]
+ 0.285[5]
+ 0.275[4]
+0.226[0]
+ 0.216[1]
+ 0.177[3]
+ 0.167[4]
+ 0.157[2]
+ 0.118[3]
+ 0.108[5]
+ 0.98[4]
+ 0.59[5]
+ 0.49[7]
+ 0.39[6]
+ 0.0[7]
+remove pointer 9, payload 777
+Tree look:
+ 0.1013[6]
+ 0.1003[5]
+ 0.954[6]
+ 0.944[4]
+ 0.934[3]
+ 0.895[2]
+ 0.885[4]
+ 0.875[3]
+ 0.836[1]
+ 0.826[3]
+ 0.816[2]
+0.767[0]
+ 0.757[2]
+ 0.708[1]
+ 0.698[3]
+ 0.659[4]
+ 0.649[5]
+ 0.639[6]
+ 0.600[8]
+ 0.590[9]
+ 0.580[7]
+ 0.541[2]
+ 0.531[8]
+ 0.521[9]
+ 0.472[7]
+ 0.462[8]
+ 0.413[6]
+ 0.403[5]
+ 0.393[4]
+ 0.354[7]
+ 0.344[6]
+ 0.334[5]
+ 0.295[8]
+ 0.285[7]
+ 0.275[6]
+ 0.226[3]
+ 0.216[4]
+ 0.177[6]
+ 0.167[7]
+ 0.157[5]
+ 0.118[6]
+ 0.108[8]
+ 0.98[7]
+ 0.59[8]
+ 0.49[10]
+ 0.39[9]
+ 0.0[10]
+remove pointer 10, payload 295
+Tree look:
+ 0.1013[8]
+ 0.1003[7]
+ 0.954[8]
+ 0.944[6]
+ 0.934[5]
+ 0.895[4]
+ 0.885[6]
+ 0.875[5]
+ 0.836[3]
+ 0.826[5]
+ 0.816[4]
+ 0.767[2]
+ 0.757[3]
+ 0.708[1]
+ 0.698[3]
+ 0.659[4]
+ 0.649[5]
+ 0.639[6]
+ 0.600[8]
+ 0.590[9]
+ 0.580[7]
+ 0.541[2]
+ 0.531[8]
+ 0.521[9]
+ 0.472[7]
+ 0.462[8]
+ 0.413[6]
+ 0.403[5]
+ 0.393[4]
+ 0.354[6]
+ 0.344[5]
+ 0.334[3]
+0.285[0]
+ 0.275[2]
+ 0.226[1]
+ 0.216[2]
+ 0.177[4]
+ 0.167[5]
+ 0.157[3]
+ 0.118[4]
+ 0.108[6]
+ 0.98[5]
+ 0.59[6]
+ 0.49[8]
+ 0.39[7]
+ 0.0[8]
+remove pointer 11, payload 836
+Tree look:
+ 0.1013[5]
+ 0.1003[4]
+ 0.954[5]
+ 0.944[3]
+ 0.934[2]
+ 0.895[1]
+ 0.885[3]
+ 0.875[2]
+0.826[0]
+ 0.816[2]
+ 0.767[1]
+ 0.757[3]
+ 0.708[2]
+ 0.698[5]
+ 0.659[6]
+ 0.649[7]
+ 0.639[8]
+ 0.600[10]
+ 0.590[11]
+ 0.580[9]
+ 0.541[4]
+ 0.531[10]
+ 0.521[11]
+ 0.472[9]
+ 0.462[10]
+ 0.413[8]
+ 0.403[7]
+ 0.393[6]
+ 0.354[8]
+ 0.344[7]
+ 0.334[5]
+ 0.285[3]
+ 0.275[5]
+ 0.226[4]
+ 0.216[5]
+ 0.177[7]
+ 0.167[8]
+ 0.157[6]
+ 0.118[7]
+ 0.108[9]
+ 0.98[8]
+ 0.59[9]
+ 0.49[11]
+ 0.39[10]
+ 0.0[11]
+remove pointer 12, payload 354
+Tree look:
+ 0.1013[7]
+ 0.1003[6]
+ 0.954[7]
+ 0.944[5]
+ 0.934[4]
+ 0.895[3]
+ 0.885[5]
+ 0.875[4]
+ 0.826[2]
+ 0.816[3]
+ 0.767[1]
+ 0.757[3]
+ 0.708[2]
+ 0.698[4]
+ 0.659[5]
+ 0.649[6]
+ 0.639[7]
+ 0.600[9]
+ 0.590[10]
+ 0.580[8]
+ 0.541[3]
+ 0.531[8]
+ 0.521[9]
+ 0.472[7]
+ 0.462[8]
+ 0.413[6]
+ 0.403[5]
+ 0.393[4]
+0.344[0]
+ 0.334[1]
+ 0.285[2]
+ 0.275[4]
+ 0.226[3]
+ 0.216[4]
+ 0.177[6]
+ 0.167[7]
+ 0.157[5]
+ 0.118[6]
+ 0.108[8]
+ 0.98[7]
+ 0.59[8]
+ 0.49[10]
+ 0.39[9]
+ 0.0[10]
+remove pointer 13, payload 895
+Tree look:
+ 0.1013[4]
+ 0.1003[3]
+ 0.954[4]
+ 0.944[2]
+ 0.934[1]
+0.885[0]
+ 0.875[2]
+ 0.826[1]
+ 0.816[3]
+ 0.767[2]
+ 0.757[5]
+ 0.708[4]
+ 0.698[6]
+ 0.659[7]
+ 0.649[8]
+ 0.639[9]
+ 0.600[11]
+ 0.590[12]
+ 0.580[10]
+ 0.541[5]
+ 0.531[10]
+ 0.521[11]
+ 0.472[9]
+ 0.462[10]
+ 0.413[8]
+ 0.403[7]
+ 0.393[6]
+ 0.344[3]
+ 0.334[4]
+ 0.285[5]
+ 0.275[7]
+ 0.226[6]
+ 0.216[7]
+ 0.177[9]
+ 0.167[10]
+ 0.157[8]
+ 0.118[9]
+ 0.108[11]
+ 0.98[10]
+ 0.59[11]
+ 0.49[13]
+ 0.39[12]
+ 0.0[13]
+remove pointer 14, payload 413
+Tree look:
+ 0.1013[6]
+ 0.1003[5]
+ 0.954[6]
+ 0.944[4]
+ 0.934[3]
+ 0.885[2]
+ 0.875[3]
+ 0.826[1]
+ 0.816[3]
+ 0.767[2]
+ 0.757[5]
+ 0.708[4]
+ 0.698[5]
+ 0.659[6]
+ 0.649[7]
+ 0.639[8]
+ 0.600[10]
+ 0.590[11]
+ 0.580[9]
+ 0.541[3]
+ 0.531[5]
+ 0.521[6]
+ 0.472[4]
+ 0.462[5]
+0.403[0]
+ 0.393[2]
+ 0.344[1]
+ 0.334[2]
+ 0.285[3]
+ 0.275[5]
+ 0.226[4]
+ 0.216[5]
+ 0.177[7]
+ 0.167[8]
+ 0.157[6]
+ 0.118[7]
+ 0.108[9]
+ 0.98[8]
+ 0.59[9]
+ 0.49[11]
+ 0.39[10]
+ 0.0[11]
+remove pointer 15, payload 954
+Tree look:
+ 0.1013[2]
+ 0.1003[1]
+0.944[0]
+ 0.934[1]
+ 0.885[3]
+ 0.875[4]
+ 0.826[2]
+ 0.816[5]
+ 0.767[4]
+ 0.757[7]
+ 0.708[6]
+ 0.698[7]
+ 0.659[8]
+ 0.649[9]
+ 0.639[10]
+ 0.600[12]
+ 0.590[13]
+ 0.580[11]
+ 0.541[5]
+ 0.531[7]
+ 0.521[8]
+ 0.472[6]
+ 0.462[7]
+ 0.403[3]
+ 0.393[5]
+ 0.344[4]
+ 0.334[5]
+ 0.285[6]
+ 0.275[8]
+ 0.226[7]
+ 0.216[8]
+ 0.177[10]
+ 0.167[11]
+ 0.157[9]
+ 0.118[10]
+ 0.108[12]
+ 0.98[11]
+ 0.59[12]
+ 0.49[14]
+ 0.39[13]
+ 0.0[14]
+remove pointer 16, payload 472
+Tree look:
+ 0.1013[4]
+ 0.1003[3]
+ 0.944[2]
+ 0.934[1]
+ 0.885[3]
+ 0.875[4]
+ 0.826[2]
+ 0.816[5]
+ 0.767[4]
+ 0.757[6]
+ 0.708[5]
+ 0.698[6]
+ 0.659[7]
+ 0.649[8]
+ 0.639[9]
+ 0.600[11]
+ 0.590[12]
+ 0.580[10]
+ 0.541[3]
+ 0.531[4]
+ 0.521[5]
+0.462[0]
+ 0.403[1]
+ 0.393[3]
+ 0.344[2]
+ 0.334[3]
+ 0.285[4]
+ 0.275[6]
+ 0.226[5]
+ 0.216[6]
+ 0.177[8]
+ 0.167[9]
+ 0.157[7]
+ 0.118[8]
+ 0.108[10]
+ 0.98[9]
+ 0.59[10]
+ 0.49[12]
+ 0.39[11]
+ 0.0[12]
+remove pointer 17, payload 1013
+Tree look:
+0.1003[0]
+ 0.944[2]
+ 0.934[1]
+ 0.885[4]
+ 0.875[5]
+ 0.826[3]
+ 0.816[6]
+ 0.767[5]
+ 0.757[7]
+ 0.708[6]
+ 0.698[7]
+ 0.659[8]
+ 0.649[9]
+ 0.639[10]
+ 0.600[12]
+ 0.590[13]
+ 0.580[11]
+ 0.541[4]
+ 0.531[5]
+ 0.521[6]
+ 0.462[2]
+ 0.403[3]
+ 0.393[5]
+ 0.344[4]
+ 0.334[5]
+ 0.285[6]
+ 0.275[8]
+ 0.226[7]
+ 0.216[8]
+ 0.177[10]
+ 0.167[11]
+ 0.157[9]
+ 0.118[10]
+ 0.108[12]
+ 0.98[11]
+ 0.59[12]
+ 0.49[14]
+ 0.39[13]
+ 0.0[14]
+remove pointer 18, payload 531
+Tree look:
+ 0.1003[2]
+ 0.944[3]
+ 0.934[1]
+ 0.885[4]
+ 0.875[5]
+ 0.826[3]
+ 0.816[5]
+ 0.767[4]
+ 0.757[6]
+ 0.708[5]
+ 0.698[6]
+ 0.659[7]
+ 0.649[8]
+ 0.639[9]
+ 0.600[11]
+ 0.590[12]
+ 0.580[10]
+ 0.541[2]
+0.521[0]
+ 0.462[1]
+ 0.403[2]
+ 0.393[4]
+ 0.344[3]
+ 0.334[4]
+ 0.285[5]
+ 0.275[7]
+ 0.226[6]
+ 0.216[7]
+ 0.177[9]
+ 0.167[10]
+ 0.157[8]
+ 0.118[9]
+ 0.108[11]
+ 0.98[10]
+ 0.59[11]
+ 0.49[13]
+ 0.39[12]
+ 0.0[13]
+remove pointer 19, payload 49
+Tree look:
+ 0.1003[4]
+ 0.944[5]
+ 0.934[3]
+ 0.885[6]
+ 0.875[7]
+ 0.826[5]
+ 0.816[7]
+ 0.767[6]
+ 0.757[8]
+ 0.708[7]
+ 0.698[8]
+ 0.659[9]
+ 0.649[10]
+ 0.639[11]
+ 0.600[13]
+ 0.590[14]
+ 0.580[12]
+ 0.541[4]
+ 0.521[2]
+ 0.462[1]
+ 0.403[3]
+ 0.393[4]
+ 0.344[2]
+ 0.334[4]
+ 0.285[3]
+ 0.275[6]
+ 0.226[5]
+ 0.216[4]
+ 0.177[7]
+ 0.167[8]
+ 0.157[6]
+ 0.118[5]
+ 0.108[8]
+ 0.98[7]
+ 0.59[6]
+0.39[0]
+ 0.0[1]
+remove pointer 20, payload 590
+Tree look:
+ 0.1003[2]
+ 0.944[3]
+ 0.934[1]
+ 0.885[4]
+ 0.875[5]
+ 0.826[3]
+ 0.816[4]
+ 0.767[2]
+ 0.757[5]
+ 0.708[4]
+ 0.698[3]
+ 0.659[5]
+ 0.649[4]
+ 0.639[5]
+ 0.600[6]
+0.580[0]
+ 0.541[2]
+ 0.521[1]
+ 0.462[2]
+ 0.403[5]
+ 0.393[6]
+ 0.344[4]
+ 0.334[6]
+ 0.285[5]
+ 0.275[8]
+ 0.226[7]
+ 0.216[6]
+ 0.177[9]
+ 0.167[10]
+ 0.157[8]
+ 0.118[7]
+ 0.108[10]
+ 0.98[9]
+ 0.59[8]
+ 0.39[3]
+ 0.0[4]
+remove pointer 21, payload 108
+Tree look:
+ 0.1003[4]
+ 0.944[5]
+ 0.934[3]
+ 0.885[6]
+ 0.875[7]
+ 0.826[5]
+ 0.816[6]
+ 0.767[4]
+ 0.757[7]
+ 0.708[6]
+ 0.698[5]
+ 0.659[7]
+ 0.649[6]
+ 0.639[7]
+ 0.600[8]
+ 0.580[2]
+ 0.541[3]
+ 0.521[1]
+ 0.462[2]
+ 0.403[5]
+ 0.393[6]
+ 0.344[4]
+ 0.334[5]
+ 0.285[3]
+ 0.275[7]
+ 0.226[6]
+ 0.216[5]
+ 0.177[7]
+ 0.167[8]
+ 0.157[6]
+ 0.118[4]
+0.98[0]
+ 0.59[2]
+ 0.39[1]
+ 0.0[2]
+remove pointer 22, payload 649
+Tree look:
+ 0.1003[3]
+ 0.944[4]
+ 0.934[2]
+ 0.885[4]
+ 0.875[5]
+ 0.826[3]
+ 0.816[4]
+ 0.767[1]
+ 0.757[4]
+ 0.708[3]
+ 0.698[2]
+ 0.659[3]
+0.639[0]
+ 0.600[2]
+ 0.580[1]
+ 0.541[3]
+ 0.521[2]
+ 0.462[4]
+ 0.403[7]
+ 0.393[8]
+ 0.344[6]
+ 0.334[7]
+ 0.285[5]
+ 0.275[9]
+ 0.226[8]
+ 0.216[7]
+ 0.177[9]
+ 0.167[10]
+ 0.157[8]
+ 0.118[6]
+ 0.98[3]
+ 0.59[5]
+ 0.39[4]
+ 0.0[5]
+remove pointer 23, payload 167
+Tree look:
+ 0.1003[5]
+ 0.944[6]
+ 0.934[4]
+ 0.885[6]
+ 0.875[7]
+ 0.826[5]
+ 0.816[6]
+ 0.767[3]
+ 0.757[6]
+ 0.708[5]
+ 0.698[4]
+ 0.659[5]
+ 0.639[2]
+ 0.600[3]
+ 0.580[1]
+ 0.541[3]
+ 0.521[2]
+ 0.462[4]
+ 0.403[6]
+ 0.393[7]
+ 0.344[5]
+ 0.334[6]
+ 0.285[3]
+ 0.275[6]
+ 0.226[5]
+ 0.216[4]
+ 0.177[5]
+0.157[0]
+ 0.118[1]
+ 0.98[2]
+ 0.59[4]
+ 0.39[3]
+ 0.0[4]
+remove pointer 24, payload 708
+Tree look:
+ 0.1003[3]
+ 0.944[4]
+ 0.934[2]
+ 0.885[4]
+ 0.875[5]
+ 0.826[3]
+ 0.816[4]
+ 0.767[1]
+ 0.757[2]
+0.698[0]
+ 0.659[2]
+ 0.639[1]
+ 0.600[3]
+ 0.580[2]
+ 0.541[5]
+ 0.521[4]
+ 0.462[6]
+ 0.403[8]
+ 0.393[9]
+ 0.344[7]
+ 0.334[8]
+ 0.285[5]
+ 0.275[8]
+ 0.226[7]
+ 0.216[6]
+ 0.177[7]
+ 0.157[3]
+ 0.118[4]
+ 0.98[5]
+ 0.59[7]
+ 0.39[6]
+ 0.0[7]
+remove pointer 25, payload 226
+Tree look:
+ 0.1003[5]
+ 0.944[6]
+ 0.934[4]
+ 0.885[6]
+ 0.875[7]
+ 0.826[5]
+ 0.816[6]
+ 0.767[3]
+ 0.757[4]
+ 0.698[2]
+ 0.659[3]
+ 0.639[1]
+ 0.600[3]
+ 0.580[2]
+ 0.541[5]
+ 0.521[4]
+ 0.462[5]
+ 0.403[7]
+ 0.393[8]
+ 0.344[6]
+ 0.334[7]
+ 0.285[3]
+ 0.275[4]
+0.216[0]
+ 0.177[2]
+ 0.157[1]
+ 0.118[2]
+ 0.98[3]
+ 0.59[5]
+ 0.39[4]
+ 0.0[5]
+remove pointer 26, payload 767
+Tree look:
+ 0.1003[2]
+ 0.944[3]
+ 0.934[1]
+ 0.885[3]
+ 0.875[4]
+ 0.826[2]
+ 0.816[3]
+0.757[0]
+ 0.698[1]
+ 0.659[3]
+ 0.639[2]
+ 0.600[5]
+ 0.580[4]
+ 0.541[7]
+ 0.521[6]
+ 0.462[7]
+ 0.403[9]
+ 0.393[10]
+ 0.344[8]
+ 0.334[9]
+ 0.285[5]
+ 0.275[6]
+ 0.216[3]
+ 0.177[5]
+ 0.157[4]
+ 0.118[5]
+ 0.98[6]
+ 0.59[8]
+ 0.39[7]
+ 0.0[8]
+remove pointer 27, payload 285
+Tree look:
+ 0.1003[4]
+ 0.944[5]
+ 0.934[3]
+ 0.885[5]
+ 0.875[6]
+ 0.826[4]
+ 0.816[5]
+ 0.757[2]
+ 0.698[1]
+ 0.659[3]
+ 0.639[2]
+ 0.600[4]
+ 0.580[3]
+ 0.541[5]
+ 0.521[4]
+ 0.462[5]
+ 0.403[7]
+ 0.393[8]
+ 0.344[6]
+ 0.334[7]
+0.275[0]
+ 0.216[1]
+ 0.177[3]
+ 0.157[2]
+ 0.118[3]
+ 0.98[4]
+ 0.59[6]
+ 0.39[5]
+ 0.0[6]
+remove pointer 28, payload 826
+Tree look:
+ 0.1003[2]
+ 0.944[3]
+ 0.934[1]
+ 0.885[2]
+ 0.875[3]
+0.816[0]
+ 0.757[1]
+ 0.698[2]
+ 0.659[5]
+ 0.639[4]
+ 0.600[6]
+ 0.580[5]
+ 0.541[7]
+ 0.521[6]
+ 0.462[7]
+ 0.403[9]
+ 0.393[10]
+ 0.344[8]
+ 0.334[9]
+ 0.275[3]
+ 0.216[4]
+ 0.177[6]
+ 0.157[5]
+ 0.118[6]
+ 0.98[7]
+ 0.59[9]
+ 0.39[8]
+ 0.0[9]
+remove pointer 29, payload 344
+Tree look:
+ 0.1003[4]
+ 0.944[5]
+ 0.934[3]
+ 0.885[4]
+ 0.875[5]
+ 0.816[2]
+ 0.757[1]
+ 0.698[2]
+ 0.659[5]
+ 0.639[4]
+ 0.600[5]
+ 0.580[3]
+ 0.541[6]
+ 0.521[5]
+ 0.462[4]
+ 0.403[5]
+ 0.393[6]
+0.334[0]
+ 0.275[1]
+ 0.216[2]
+ 0.177[4]
+ 0.157[3]
+ 0.118[4]
+ 0.98[5]
+ 0.59[7]
+ 0.39[6]
+ 0.0[7]
+remove pointer 30, payload 885
+Tree look:
+ 0.1003[2]
+ 0.944[3]
+ 0.934[1]
+0.875[0]
+ 0.816[1]
+ 0.757[2]
+ 0.698[4]
+ 0.659[7]
+ 0.639[6]
+ 0.600[7]
+ 0.580[5]
+ 0.541[8]
+ 0.521[7]
+ 0.462[6]
+ 0.403[7]
+ 0.393[8]
+ 0.334[3]
+ 0.275[4]
+ 0.216[5]
+ 0.177[7]
+ 0.157[6]
+ 0.118[7]
+ 0.98[8]
+ 0.59[10]
+ 0.39[9]
+ 0.0[10]
+remove pointer 31, payload 403
+Tree look:
+ 0.1003[4]
+ 0.944[5]
+ 0.934[3]
+ 0.875[2]
+ 0.816[1]
+ 0.757[2]
+ 0.698[4]
+ 0.659[6]
+ 0.639[5]
+ 0.600[6]
+ 0.580[3]
+ 0.541[6]
+ 0.521[5]
+ 0.462[4]
+0.393[0]
+ 0.334[1]
+ 0.275[2]
+ 0.216[3]
+ 0.177[5]
+ 0.157[4]
+ 0.118[5]
+ 0.98[6]
+ 0.59[8]
+ 0.39[7]
+ 0.0[8]
+remove pointer 32, payload 944
+Tree look:
+ 0.1003[1]
+0.934[0]
+ 0.875[2]
+ 0.816[1]
+ 0.757[3]
+ 0.698[5]
+ 0.659[7]
+ 0.639[6]
+ 0.600[7]
+ 0.580[4]
+ 0.541[7]
+ 0.521[6]
+ 0.462[5]
+ 0.393[2]
+ 0.334[3]
+ 0.275[4]
+ 0.216[5]
+ 0.177[7]
+ 0.157[6]
+ 0.118[7]
+ 0.98[8]
+ 0.59[10]
+ 0.39[9]
+ 0.0[10]
+remove pointer 33, payload 462
+Tree look:
+ 0.1003[3]
+ 0.934[2]
+ 0.875[3]
+ 0.816[1]
+ 0.757[3]
+ 0.698[4]
+ 0.659[6]
+ 0.639[5]
+ 0.600[6]
+ 0.580[2]
+ 0.541[4]
+ 0.521[3]
+0.393[0]
+ 0.334[1]
+ 0.275[2]
+ 0.216[3]
+ 0.177[5]
+ 0.157[4]
+ 0.118[5]
+ 0.98[6]
+ 0.59[8]
+ 0.39[7]
+ 0.0[8]
+remove pointer 34, payload 1003
+Tree look:
+0.934[0]
+ 0.875[2]
+ 0.816[1]
+ 0.757[4]
+ 0.698[5]
+ 0.659[7]
+ 0.639[6]
+ 0.600[7]
+ 0.580[3]
+ 0.541[5]
+ 0.521[4]
+ 0.393[2]
+ 0.334[3]
+ 0.275[4]
+ 0.216[5]
+ 0.177[7]
+ 0.157[6]
+ 0.118[7]
+ 0.98[8]
+ 0.59[10]
+ 0.39[9]
+ 0.0[10]
+remove pointer 35, payload 521
+Tree look:
+ 0.934[2]
+ 0.875[3]
+ 0.816[1]
+ 0.757[3]
+ 0.698[4]
+ 0.659[6]
+ 0.639[5]
+ 0.600[6]
+ 0.580[2]
+ 0.541[3]
+0.393[0]
+ 0.334[1]
+ 0.275[2]
+ 0.216[3]
+ 0.177[5]
+ 0.157[4]
+ 0.118[5]
+ 0.98[6]
+ 0.59[8]
+ 0.39[7]
+ 0.0[8]
+remove pointer 36, payload 39
+Tree look:
+ 0.934[4]
+ 0.875[5]
+ 0.816[3]
+ 0.757[5]
+ 0.698[6]
+ 0.659[8]
+ 0.639[7]
+ 0.600[8]
+ 0.580[4]
+ 0.541[5]
+ 0.393[2]
+ 0.334[1]
+ 0.275[3]
+ 0.216[2]
+ 0.177[5]
+ 0.157[4]
+ 0.118[3]
+ 0.98[4]
+ 0.59[5]
+0.0[0]
+remove pointer 37, payload 580
+Tree look:
+ 0.934[2]
+ 0.875[3]
+ 0.816[1]
+ 0.757[2]
+ 0.698[3]
+ 0.659[5]
+ 0.639[4]
+ 0.600[5]
+0.541[0]
+ 0.393[1]
+ 0.334[2]
+ 0.275[5]
+ 0.216[4]
+ 0.177[7]
+ 0.157[6]
+ 0.118[5]
+ 0.98[6]
+ 0.59[7]
+ 0.0[3]
+remove pointer 38, payload 98
+Tree look:
+ 0.934[4]
+ 0.875[5]
+ 0.816[3]
+ 0.757[4]
+ 0.698[5]
+ 0.659[7]
+ 0.639[6]
+ 0.600[7]
+ 0.541[2]
+ 0.393[1]
+ 0.334[2]
+ 0.275[5]
+ 0.216[4]
+ 0.177[6]
+ 0.157[5]
+ 0.118[3]
+0.59[0]
+ 0.0[1]
+remove pointer 39, payload 639
+Tree look:
+ 0.934[3]
+ 0.875[4]
+ 0.816[2]
+ 0.757[1]
+ 0.698[2]
+ 0.659[3]
+0.600[0]
+ 0.541[1]
+ 0.393[2]
+ 0.334[4]
+ 0.275[7]
+ 0.216[6]
+ 0.177[8]
+ 0.157[7]
+ 0.118[5]
+ 0.59[3]
+ 0.0[4]
+remove pointer 40, payload 157
+Tree look:
+ 0.934[5]
+ 0.875[6]
+ 0.816[4]
+ 0.757[3]
+ 0.698[4]
+ 0.659[5]
+ 0.600[2]
+ 0.541[1]
+ 0.393[2]
+ 0.334[3]
+ 0.275[5]
+ 0.216[4]
+ 0.177[5]
+0.118[0]
+ 0.59[1]
+ 0.0[2]
+remove pointer 41, payload 698
+Tree look:
+ 0.934[3]
+ 0.875[4]
+ 0.816[2]
+ 0.757[1]
+0.659[0]
+ 0.600[1]
+ 0.541[2]
+ 0.393[4]
+ 0.334[5]
+ 0.275[7]
+ 0.216[6]
+ 0.177[7]
+ 0.118[3]
+ 0.59[4]
+ 0.0[5]
+remove pointer 42, payload 216
+Tree look:
+ 0.934[5]
+ 0.875[6]
+ 0.816[4]
+ 0.757[3]
+ 0.659[2]
+ 0.600[1]
+ 0.541[2]
+ 0.393[4]
+ 0.334[3]
+ 0.275[4]
+0.177[0]
+ 0.118[1]
+ 0.59[2]
+ 0.0[3]
+remove pointer 43, payload 757
+Tree look:
+ 0.934[2]
+ 0.875[3]
+ 0.816[1]
+0.659[0]
+ 0.600[1]
+ 0.541[3]
+ 0.393[5]
+ 0.334[4]
+ 0.275[5]
+ 0.177[2]
+ 0.118[3]
+ 0.59[4]
+ 0.0[5]
+remove pointer 44, payload 275
+Tree look:
+ 0.934[4]
+ 0.875[5]
+ 0.816[3]
+ 0.659[2]
+ 0.600[1]
+ 0.541[3]
+ 0.393[4]
+ 0.334[2]
+0.177[0]
+ 0.118[1]
+ 0.59[2]
+ 0.0[3]
+remove pointer 45, payload 816
+Tree look:
+ 0.934[1]
+ 0.875[2]
+0.659[0]
+ 0.600[1]
+ 0.541[4]
+ 0.393[5]
+ 0.334[3]
+ 0.177[2]
+ 0.118[3]
+ 0.59[4]
+ 0.0[5]
+remove pointer 46, payload 334
+Tree look:
+ 0.934[3]
+ 0.875[4]
+ 0.659[2]
+ 0.600[1]
+ 0.541[2]
+ 0.393[3]
+0.177[0]
+ 0.118[1]
+ 0.59[2]
+ 0.0[3]
+remove pointer 47, payload 875
+Tree look:
+ 0.934[1]
+0.659[0]
+ 0.600[1]
+ 0.541[3]
+ 0.393[4]
+ 0.177[2]
+ 0.118[3]
+ 0.59[4]
+ 0.0[5]
+remove pointer 48, payload 393
+Tree look:
+ 0.934[3]
+ 0.659[2]
+ 0.600[1]
+ 0.541[2]
+0.177[0]
+ 0.118[1]
+ 0.59[2]
+ 0.0[3]
+remove pointer 49, payload 934
+Tree look:
+0.659[0]
+ 0.600[1]
+ 0.541[3]
+ 0.177[2]
+ 0.118[3]
+ 0.59[4]
+ 0.0[5]
+remove pointer 0, payload 0
+Tree look:
+ 0.659[1]
+0.600[0]
+ 0.541[3]
+ 0.177[2]
+ 0.118[1]
+ 0.59[2]
+remove pointer 1, payload 541
+Tree look:
+ 0.659[2]
+ 0.600[1]
+0.177[0]
+ 0.118[1]
+ 0.59[2]
+remove pointer 2, payload 59
+Tree look:
+ 0.659[3]
+ 0.600[2]
+ 0.177[1]
+0.118[0]
+remove pointer 3, payload 600
+Tree look:
+ 0.659[1]
+0.177[0]
+ 0.118[1]
+remove pointer 4, payload 118
+Tree look:
+ 0.659[1]
+0.177[0]
+remove pointer 5, payload 659
+Tree look:
+0.177[0]
+remove pointer 6, payload 177
+</stdout>
+</verify>
+
+</testcase>
diff --git a/tests/unit/Makefile.inc b/tests/unit/Makefile.inc
index f1d66989a..257e2a61c 100644
--- a/tests/unit/Makefile.inc
+++ b/tests/unit/Makefile.inc
@@ -6,7 +6,7 @@ UNITFILES = curlcheck.h \
# These are all unit test programs
UNITPROGS = unit1300 unit1301 unit1302 unit1303 unit1304 unit1305 unit1307 \
- unit1308
+ unit1308 unit1309
unit1300_SOURCES = unit1300.c $(UNITFILES)
unit1301_SOURCES = unit1301.c $(UNITFILES)
@@ -16,3 +16,4 @@ unit1304_SOURCES = unit1304.c $(UNITFILES)
unit1305_SOURCES = unit1305.c $(UNITFILES)
unit1307_SOURCES = unit1307.c $(UNITFILES)
unit1308_SOURCES = unit1308.c $(UNITFILES)
+unit1309_SOURCES = unit1309.c $(UNITFILES)
diff --git a/tests/unit/unit1309.c b/tests/unit/unit1309.c
new file mode 100644
index 000000000..6581642e8
--- /dev/null
+++ b/tests/unit/unit1309.c
@@ -0,0 +1,113 @@
+/***************************************************************************
+ * _ _ ____ _
+ * Project ___| | | | _ \| |
+ * / __| | | | |_) | |
+ * | (__| |_| | _ <| |___
+ * \___|\___/|_| \_\_____|
+ *
+ * Copyright (C) 1998 - 2011, 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
+ * are also available at http://curl.haxx.se/docs/copyright.html.
+ *
+ * You may opt to use, copy, modify, merge, publish, distribute and/or sell
+ * copies of the Software, and permit persons to whom the Software is
+ * furnished to do so, under the terms of the COPYING file.
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
+ * KIND, either express or implied.
+ *
+ ***************************************************************************/
+#include "curlcheck.h"
+
+#include "splay.h"
+
+
+static CURLcode unit_setup(void)
+{
+ return CURLE_OK;
+}
+
+static void unit_stop(void)
+{
+
+}
+
+static void splayprint(struct Curl_tree * t, int d, char output)
+{
+ struct Curl_tree *node;
+ int i;
+ int count;
+ if(t == NULL)
+ return;
+
+ splayprint(t->larger, d+1, output);
+ for(i=0; i<d; i++)
+ if(output)
+ printf(" ");
+
+ if(output) {
+ printf("%ld.%ld[%d]", (long)t->key.tv_sec,
+ (long)t->key.tv_usec, i);
+ }
+
+ for(count=0, node = t->same; node; node = node->same, count++)
+ ;
+
+ if(output) {
+ if(count)
+ printf(" [%d more]\n", count);
+ else
+ printf("\n");
+ }
+
+ splayprint(t->smaller, d+1, output);
+}
+
+UNITTEST_START
+
+/* number of nodes to add to the splay tree */
+#define NUM_NODES 50
+
+ struct Curl_tree *root, *t;
+ void *ptrs[NUM_NODES];
+ int rc;
+ int i;
+ root = NULL; /* the empty tree */
+
+ for(i = 0; i < NUM_NODES; i++) {
+ struct timeval key;
+ ptrs[i] = t = malloc(sizeof(struct Curl_tree));
+ if(!t) {
+ puts("out of memory!");
+ return 0;
+ }
+
+ key.tv_sec = 0;
+ key.tv_usec = (541*i)%1023;
+
+ t->payload = (void *)key.tv_usec; /* for simplicity */
+ root = Curl_splayinsert(key, root, t);
+ }
+
+ puts("Result:");
+ splayprint(root, 0, 1);
+
+ for(i = 0; i < NUM_NODES; i++) {
+ int rem = (i+7)%NUM_NODES;
+ printf("Tree look:\n");
+ splayprint(root, 0, 1);
+ printf("remove pointer %d, payload %ld\n", rem,
+ (long)((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);
+ }
+
+UNITTEST_STOP
+
+
+
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 06:29:40 +0000