lib/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$
  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   l->larger = r->smaller = NULL;
  84
  85   l->larger = t->smaller;                                /* assemble */
  86   r->smaller = t->larger;
  87   t->smaller = N.larger;
  88   t->larger = N.smaller;
  89
  90   return t;
  91 }
  92
  93 /* Insert key i into the tree t.  Return a pointer to the resulting tree or
  94    NULL if something went wrong. */
  95 struct Curl_tree *Curl_splayinsert(int i,
  96                                    struct Curl_tree *t,
  97                                    struct Curl_tree *node)
  98 {
  99   if (node == NULL)
 100     return t;
 101
 102   if (t != NULL) {
 103     t = Curl_splay(i,t);
 104     if (compare(i, t->key)==0) {
 105       /* There already exists a node in the tree with the very same key. Build
 106          a linked list of nodes. We make the new 'node' struct the new master
 107          node and make the previous node the first one in the 'same' list. */
 108
 109       node->same = t;
 110       node->key = i;
 111       node->smaller = t->smaller;
 112       node->larger = t->larger;
 113
 114       t->smaller = node; /* in the sub node for this same key, we use the
 115                             smaller pointer to point back to the master
 116                             node */
 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     remove->smaller->same = remove->same;
 274     if(remove->same)
 275       remove->same->smaller = remove->smaller;
 276     /* voila, we're done! */
 277     *newroot = t; /* return the same root */
 278     return 0;
 279   }
 280
 281   t = Curl_splay(remove->key, t);
 282
 283   /* First make sure that we got a root node witht he same key as the one we
 284      want to remove, as otherwise we might be trying to remove a node that
 285      isn't actually in the tree. */
 286   if(t->key != remove->key)
 287     return 2;
 288
 289   /* Check if there is a list with identical sizes, as then we're trying to
 290      remove the root node of a list of nodes with identical keys. */
 291   x = t->same;
 292   if(x) {
 293     /* 'x' is the new root node, we just make it use the root node's
 294        smaller/larger links */
 295
 296     x->key = t->key;
 297     x->larger = t->larger;
 298     x->smaller = t->smaller;
 299   }
 300   else {
 301     /* Remove the root node */
 302     if (t->smaller == NULL)
 303       x = t->larger;
 304     else {
 305       x = Curl_splay(remove->key, t->smaller);
 306       x->larger = t->larger;
 307     }
 308   }
 309
 310   *newroot = x; /* store new root pointer */
 311
 312   return 0;
 313 }
 314
 315 #ifdef CURLDEBUG
 316
 317 void Curl_splayprint(struct Curl_tree * t, int d, char output)
 318 {
 319   struct Curl_tree *node;
 320   int i;
 321   int count;
 322   if (t == NULL)
 323     return;
 324
 325   Curl_splayprint(t->larger, d+1, output);
 326   for (i=0; i<d; i++)
 327     if(output)
 328       printf("  ");
 329
 330   if(output) {
 331     printf("%d[%d]", t->key, i);
 332   }
 333
 334   for(count=0, node = t->same; node; node = node->same, count++)
 335     ;
 336
 337   if(output) {
 338     if(count)
 339       printf(" [%d more]\n", count);
 340     else
 341       printf("\n");
 342   }
 343
 344   Curl_splayprint(t->smaller, d+1, output);
 345 }
 346 #endif
 347
 348 #ifdef TEST_SPLAY
 349
 350 /*#define TEST2 */
 351 #define MAX 50
 352 #define TEST2
 353
 354 /* A sample use of these functions.  Start with the empty tree, insert some
 355    stuff into it, and then delete it */
 356 int main(int argc, char **argv)
 357 {
 358   struct Curl_tree *root, *t;
 359   void *ptrs[MAX];
 360   int adds=0;
 361   int rc;
 362
 363   long sizes[]={
 364     50, 60, 50, 100, 60, 200, 120, 300, 400, 200, 256, 122, 60, 120, 200, 300,
 365     220, 80, 90, 50, 100, 60, 200, 120, 300, 400, 200, 256, 122, 60, 120, 200,
 366     300, 220, 80, 90, 50, 100, 60, 200, 120, 300, 400, 200, 256, 122, 60, 120,
 367     200, 300, 220, 80, 90};
 368   int i;
 369   root = NULL;              /* the empty tree */
 370
 371   for (i = 0; i < MAX; i++) {
 372     int key;
 373     ptrs[i] = t = (struct Curl_tree *)malloc(sizeof(struct Curl_tree));
 374
 375 #ifdef TEST2
 376     key = sizes[i];
 377 #elif defined(TEST1)
 378     key = (541*i)%1023;
 379 #elif defined(TEST3)
 380     key = 100;
 381 #endif
 382
 383     t->payload = (void *)key; /* for simplicity */
 384     if(!t) {
 385       puts("out of memory!");
 386       return 0;
 387     }
 388     root = Curl_splayinsert(key, root, t);
 389   }
 390
 391 #if 0
 392   puts("Result:");
 393   Curl_splayprint(root, 0, 1);
 394 #endif
 395
 396 #if 1
 397   for (i = 0; i < MAX; i++) {
 398     int rem = (i+7)%MAX;
 399     struct Curl_tree *r;
 400     printf("Tree look:\n");
 401     Curl_splayprint(root, 0, 1);
 402     printf("remove pointer %d, payload %d\n", rem,
 403            (int)((struct Curl_tree *)ptrs[rem])->payload);
 404     rc = Curl_splayremovebyaddr(root, (struct Curl_tree *)ptrs[rem], &root);
 405     if(rc)
 406       /* failed! */
 407       printf("remove %d failed!\n", rem);
 408   }
 409 #endif
 410
 411   return 0;
 412 }
 413
 414 #endif /* TEST_SPLAY */