Utilities/cmcurl/splay.c

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