lib/splay.c

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