splay: add unit tests

The test code that was #ifdef'ed in the code was converted into unit
tests in test case 1309. I also removed the #if 0'ed code from splay.c

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
+
+
+
+