Utilities/cmcurl-7.19.0/lib/splay.c

   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.1.1.1 2008-09-23 16:32:05 hoffman 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  */
  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. */
  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 */
 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 */
 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
 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       printf("  ");
 349
 350   if(output) {
 351 #ifdef TEST_SPLAY
 352     printf("%ld[%d]", (long)t->key.tv_usec, i);
 353 #else
 354     printf("%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       printf(" [%d more]\n", count);
 364     else
 365       printf("\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 */
 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 = (struct Curl_tree *)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 */