glib/gtree.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19
  20 /*
  21  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  22  * file for a list of people on the GLib Team.  See the ChangeLog
  23  * files for a list of changes.  These files are distributed with
  24  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  25  */
  26
  27 /*
  28  * MT safe
  29  */
  30
  31 #include "config.h"
  32
  33 #include "glib.h"
  34 #include "galias.h"
  35
  36 #undef G_TREE_DEBUG
  37
  38 #define MAX_IN_DEGREE 3
  39 #define TABLE_SIZE (MAX_IN_DEGREE+1) /* This is the minimum size required so
  40                                         that you only have a constant number of
  41                                         nodes fill up their tables and
  42                                         require a new node to be created at
  43                                         a time. */
  44
  45 typedef struct _GTreeRootVersion   GTreeRootVersion;
  46 typedef struct _GTreeNodeVersion   GTreeNodeVersion;
  47 typedef struct _GTreeNodeData      GTreeNodeData;
  48 typedef struct _GTreeNode          GTreeNode;
  49
  50 struct _GTreeRootVersion
  51 {
  52   GTreeNode *root;
  53   guint      version;
  54 };
  55
  56 struct _GTree
  57 {
  58   GTreeRootVersion *r; /* versioned root nodes of the tree.  r[0] is
  59                           the highest (latest) version.  then r[1]..r[nr-1] are
  60                           older versions in ascending order.  Use first_v(),
  61                           next_v() and prev_v() to traverse the list. */
  62   guint             nr;
  63   GCompareDataFunc  key_compare;
  64   GDestroyNotify    key_destroy_func;
  65   GDestroyNotify    value_destroy_func;
  66   gpointer          key_compare_data;
  67   guint             nnodes;
  68   gint              ref_count;
  69   guint             version;
  70 };
  71
  72 struct _GTreeNodeVersion
  73 {
  74   guint      version;
  75   GTreeNode *left;        /* left subtree */
  76   GTreeNode *right;       /* right subtree */
  77   GTreeNode *parent;      /* parent node */
  78 };
  79
  80 struct _GTreeNodeData
  81 {
  82   gpointer   key;         /* key for this node */
  83   gpointer   value;       /* value stored at this node */
  84   gint       ref_count;
  85   guint8     stolen;      /* true if the node is stolen instead of removed */
  86 };
  87
  88 struct _GTreeNode
  89 {
  90   GTreeNodeData    *data; /* the node's permanent data */
  91   GTreeNodeVersion *v;    /* versions of pointers for the node.  v[0] is the
  92                              highest (latest) version.  then v[1]..v[nv-1] are
  93                              older versions in ascending order.  Use first_v(),
  94                              next_v() and prev_v() to traverse the list. */
  95   guint             nv;   /* number of versions stored in this node */
  96 };
  97
  98 static GTreeNode* g_tree_node_new                   (GTree           *tree,
  99                                                      gpointer         key,
 100                                                      gpointer         value);
 101 static guint      g_tree_priority                   (GTreeNode       *node);
 102 static void       g_tree_insert_internal            (GTree           *tree,
 103                                                      gpointer         key,
 104                                                      gpointer         value,
 105                                                      gboolean         replace);
 106 static gboolean   g_tree_remove_internal            (GTree           *tree,
 107                                                      gconstpointer    key,
 108                                                      gboolean         steal);
 109 static GTreeNode *g_tree_find_node                  (GTree           *tree,
 110                                                      gconstpointer    key,
 111                                                      GTreeSearchType  search_type,
 112                                                      guint            version);
 113 static gint       g_tree_node_pre_order             (GTreeNode       *node,
 114                                                      GTraverseFunc    traverse_func,
 115                                                      gpointer         data);
 116 static gint       g_tree_node_in_order              (GTreeNode       *node,
 117                                                      GTraverseFunc    traverse_func,
 118                                                      gpointer         data);
 119 static gint       g_tree_node_post_order            (GTreeNode       *node,
 120                                                      GTraverseFunc    traverse_func,
 121                                                      gpointer         data);
 122 static gpointer   g_tree_node_search                (GTreeNode       *node,
 123                                                      GCompareFunc     search_func,
 124                                                      gconstpointer    data,
 125                                                      GTreeSearchType  search_type,
 126                                                      guint            version);
 127 static gint       g_tree_node_height                (GTreeNode       *node);
 128 static GTreeNode* g_tree_node_rotate_left           (GTree           *tree,
 129                                                      GTreeNode       *node);
 130 static GTreeNode* g_tree_node_rotate_right          (GTree           *tree,
 131                                                      GTreeNode       *node);
 132 #ifdef G_TREE_DEBUG
 133 static void       g_tree_node_check                 (GTreeNode       *node,
 134                                                      guint            version);
 135 #endif
 136
 137 static GTreeNode*
 138 g_tree_node_new (GTree   *tree,
 139                  gpointer key,
 140                  gpointer value)
 141 {
 142   GTreeNode *node = g_slice_new (GTreeNode);
 143
 144   node->data = g_slice_new(GTreeNodeData);
 145   node->data->key = key;
 146   node->data->value = value;
 147   node->data->ref_count = 1;
 148   node->data->stolen = FALSE;
 149
 150   /* for the version 0, only allocate one set of pointers for a node,
 151      so that we don't use a lot more memory when persistence isn't even
 152      being used */
 153   node->v = g_slice_alloc(sizeof(GTreeNodeVersion) *
 154                           (tree->version == 0 ? 1 : TABLE_SIZE));
 155   node->nv = 1;
 156
 157   node->v[0].version = tree->version;
 158   node->v[0].left = NULL;
 159   node->v[0].right = NULL;
 160   node->v[0].parent = NULL;
 161
 162   return node;
 163 }
 164
 165 static gboolean
 166 g_tree_node_data_unref (GTree *tree,
 167                         GTreeNode *node)
 168 {
 169   /* free the node's data if it's the last node which is using it. just
 170      because the version of the node was created in the latest version
 171      of the tree, doesn't mean there aren't older versions around still */
 172   if (g_atomic_int_dec_and_test (&node->data->ref_count))
 173     {
 174       if (!node->data->stolen)
 175         {
 176           if (tree->key_destroy_func)
 177             tree->key_destroy_func (node->data->key);
 178           if (tree->value_destroy_func)
 179             tree->value_destroy_func (node->data->value);
 180         }
 181       g_slice_free (GTreeNodeData, node->data);
 182       return TRUE;
 183     }
 184   return FALSE;
 185 }
 186
 187 static gboolean
 188 g_tree_node_free (GTree     *tree,
 189                   GTreeNode *node)
 190 {
 191   gboolean data_free;
 192
 193   if (node->data)
 194     data_free = g_tree_node_data_unref (tree, node);
 195   else
 196     data_free = FALSE;
 197
 198   g_slice_free1 (sizeof(GTreeNodeVersion) *
 199                  (node->v[0].version == 0 ? 1 : TABLE_SIZE),
 200                  node->v);
 201   node->v = NULL;
 202   node->data = NULL;
 203   g_slice_free (GTreeNode, node);
 204
 205   return data_free;
 206 }
 207
 208 /**
 209  * g_tree_new:
 210  * @key_compare_func: the function used to order the nodes in the #GTree.
 211  *   It should return values similar to the standard strcmp() function -
 212  *   0 if the two arguments are equal, a negative value if the first argument
 213  *   comes before the second, or a positive value if the first argument comes
 214  *   after the second.
 215  *
 216  * Creates a new #GTree.
 217  *
 218  * Return value: a new #GTree.
 219  **/
 220 GTree*
 221 g_tree_new (GCompareFunc key_compare_func)
 222 {
 223   g_return_val_if_fail (key_compare_func != NULL, NULL);
 224
 225   return g_tree_new_full ((GCompareDataFunc) key_compare_func, NULL,
 226                           NULL, NULL);
 227 }
 228
 229 /**
 230  * g_tree_new_with_data:
 231  * @key_compare_func: qsort()-style comparison function.
 232  * @key_compare_data: data to pass to comparison function.
 233  *
 234  * Creates a new #GTree with a comparison function that accepts user data.
 235  * See g_tree_new() for more details.
 236  *
 237  * Return value: a new #GTree.
 238  **/
 239 GTree*
 240 g_tree_new_with_data (GCompareDataFunc key_compare_func,
 241                       gpointer         key_compare_data)
 242 {
 243   g_return_val_if_fail (key_compare_func != NULL, NULL);
 244
 245   return g_tree_new_full (key_compare_func, key_compare_data,
 246                           NULL, NULL);
 247 }
 248
 249 /**
 250  * g_tree_new_full:
 251  * @key_compare_func: qsort()-style comparison function.
 252  * @key_compare_data: data to pass to comparison function.
 253  * @key_destroy_func: a function to free the memory allocated for the key
 254  *   used when removing the entry from the #GTree or %NULL if you don't
 255  *   want to supply such a function.
 256  * @value_destroy_func: a function to free the memory allocated for the
 257  *   value used when removing the entry from the #GTree or %NULL if you
 258  *   don't want to supply such a function.
 259  *
 260  * Creates a new #GTree like g_tree_new() and allows to specify functions
 261  * to free the memory allocated for the key and value that get called when
 262  * removing the entry from the #GTree.
 263  *
 264  * Return value: a new #GTree.
 265  **/
 266 GTree*
 267 g_tree_new_full (GCompareDataFunc key_compare_func,
 268                  gpointer         key_compare_data,
 269                  GDestroyNotify   key_destroy_func,
 270                  GDestroyNotify   value_destroy_func)
 271 {
 272   GTree *tree;
 273
 274   g_return_val_if_fail (key_compare_func != NULL, NULL);
 275
 276   tree = g_slice_new (GTree);
 277   tree->r                  = g_new(GTreeRootVersion, 1);
 278   tree->nr                 = 1;
 279   tree->key_compare        = key_compare_func;
 280   tree->key_destroy_func   = key_destroy_func;
 281   tree->value_destroy_func = value_destroy_func;
 282   tree->key_compare_data   = key_compare_data;
 283   tree->nnodes             = 0;
 284   tree->ref_count          = 1;
 285   tree->version            = 0;
 286
 287   tree->r[0].root          = NULL;
 288   tree->r[0].version       = 0;
 289
 290   return tree;
 291 }
 292
 293 /* finds the largest version in the array, that is <= the query version */
 294 static inline GTreeRootVersion *
 295 g_tree_root_find_version (GTree *tree,
 296                           guint  version)
 297 {
 298   GTreeRootVersion *const v = tree->r;
 299   const guint nv = tree->nr;
 300   GTreeRootVersion *l, *r;
 301   static GTreeRootVersion none = {
 302     .root = NULL,
 303     .version = 0
 304   };
 305
 306   if (v[0].version <= version)
 307     return v;
 308
 309   l = v+1;
 310   r = v+(nv-1);
 311   while (l <= r) /* binary search */
 312     {
 313       GTreeRootVersion *const m = l + (r - l) / 2;
 314       if (version == m->version)
 315         return m;
 316       else if (version < m->version)
 317         r = m-1;
 318       else
 319         l = m+1;
 320     }
 321   /* If searching earlier than the first root in the tree, r will be off
 322      the start of the list (in the first position in the array) */
 323   g_assert (r == v || r->version < version);
 324   /* When searching for the second last root (the last position in the array),
 325      l will be off the end of the list */
 326   g_assert (l == v+nv || l->version > version);
 327   if (r == v)
 328     return &none;
 329   else
 330     return r;
 331 }
 332
 333 static inline GTreeNodeVersion *
 334 g_tree_node_find_version(GTreeNode *node,
 335                          guint      version)
 336 {
 337   GTreeNodeVersion *const v = node->v;
 338   const guint nv = node->nv;
 339   GTreeNodeVersion *n;
 340
 341   /* note: we never search for a version smaller than the smallest
 342      version in the array */
 343
 344   if (v[0].version <= version)
 345     return v;
 346
 347   /* there are at most TABLE_SIZE things to look through, which is small,
 348      so just scan through them from largest version to smallest */
 349   for (n = v+(nv-1); n != v; --n)
 350     if (n->version <= version)
 351       break;
 352   /* searched for something smaller than the lowest version in the node */
 353   g_assert (n != v);
 354   return n;
 355 }
 356
 357 static inline GTreeNode *
 358 g_tree_first_node (GTree *tree,
 359                    guint  version)
 360 {
 361   GTreeNode *tmp;
 362   GTreeNodeVersion *tmpv;
 363   GTreeRootVersion *rv;
 364
 365   rv = g_tree_root_find_version (tree, version);
 366   if (!rv->root)
 367     return NULL;
 368
 369   tmpv = g_tree_node_find_version (tmp = rv->root, version);
 370
 371   while (tmpv->left)
 372     tmpv = g_tree_node_find_version (tmp = tmpv->left, version);
 373
 374   return tmp;
 375 }
 376
 377 static inline GTreeNode *
 378 g_tree_node_previous (GTreeNode *node,
 379                       guint      version)
 380 {
 381   GTreeNode *tmp;
 382   GTreeNodeVersion *nodev, *tmpv;
 383
 384   nodev = g_tree_node_find_version (node, version);
 385
 386   if (nodev->left)
 387     {
 388       tmpv = g_tree_node_find_version (tmp = nodev->left, version);
 389       while (tmpv->right)
 390         tmpv = g_tree_node_find_version (tmp = tmpv->right, version);
 391     }
 392   else
 393     {
 394       tmp = nodev->parent;
 395       while (tmp)
 396         {
 397           tmpv = g_tree_node_find_version (tmp, version);
 398           if (tmpv->right == node)
 399               break;
 400           node = tmp;
 401           tmp = tmpv->parent;
 402         }
 403     }
 404   return tmp;
 405 }
 406
 407 static inline GTreeNode *
 408 g_tree_node_next (GTreeNode *node,
 409                   guint      version)
 410 {
 411   GTreeNode *tmp;
 412   GTreeNodeVersion *nodev, *tmpv;
 413
 414   nodev = g_tree_node_find_version (node, version);
 415
 416   if (nodev->right)
 417     {
 418       tmpv = g_tree_node_find_version (tmp = nodev->right, version);
 419       while (tmpv->left)
 420         tmpv = g_tree_node_find_version (tmp = tmpv->left, version);
 421     }
 422   else
 423     {
 424       tmp = nodev->parent;
 425       while (tmp)
 426         {
 427           tmpv = g_tree_node_find_version (tmp, version);
 428           if (tmpv->left == node)
 429               break;
 430           node = tmp;
 431           tmp = tmpv->parent;
 432         }
 433     }
 434   return tmp;
 435 }
 436
 437 static inline void
 438 g_tree_node_free_all (GTree *tree, GTreeNode *node)
 439 {
 440   guint i;
 441
 442   if (!node)
 443     return;
 444
 445   for (i = 0; i < node->nv; ++i)
 446     {
 447       g_tree_node_free_all (tree, node->v[i].parent);
 448       g_tree_node_free_all (tree, node->v[i].left);
 449       g_tree_node_free_all (tree, node->v[i].right);
 450     }
 451
 452   g_tree_node_free (tree, node);
 453 }
 454
 455 static inline GTreeNode *
 456 g_tree_node_decompose (GTree     *tree,
 457                        GTreeNode *node)
 458 {
 459   guint i;
 460
 461   if (!node || !node->data)
 462     return NULL;
 463
 464   g_tree_node_data_unref (tree, node);
 465   node->data = NULL;
 466
 467   for (i = 0; i < node->nv; ++i)
 468     {
 469       node->v[i].parent = g_tree_node_decompose (tree, node->v[i].parent);
 470       node->v[i].left = g_tree_node_decompose (tree, node->v[i].left);
 471       node->v[i].right = g_tree_node_decompose (tree, node->v[i].right);
 472     }
 473
 474   return node;
 475 }
 476
 477 static void
 478 g_tree_remove_all (GTree *tree)
 479 {
 480   guint i;
 481
 482   g_return_if_fail (tree != NULL);
 483
 484   /* decompose the graph into individual trees rooted at the various
 485      root pointers in the graph, so that there are no cycles while we are
 486      freeing them */
 487   for (i = 0; i < tree->nr; ++i)
 488     tree->r[i].root = g_tree_node_decompose (tree, tree->r[i].root);
 489
 490   /* free everything */
 491   for (i = 0; i < tree->nr; ++i)
 492     g_tree_node_free_all (tree, tree->r[i].root);
 493
 494   tree->r[0].root = NULL;
 495   tree->r[0].version = tree->version = 0;
 496   tree->nnodes = 0;
 497 }
 498
 499 /**
 500  * g_tree_ref:
 501  * @tree: a #GTree.
 502  *
 503  * Increments the reference count of @tree by one.  It is safe to call
 504  * this function from any thread.
 505  *
 506  * Return value: the passed in #GTree.
 507  *
 508  * Since: 2.22
 509  **/
 510 GTree *
 511 g_tree_ref (GTree *tree)
 512 {
 513   g_return_val_if_fail (tree != NULL, NULL);
 514
 515   g_atomic_int_inc (&tree->ref_count);
 516
 517   return tree;
 518 }
 519
 520 /**
 521  * g_tree_unref:
 522  * @tree: a #GTree.
 523  *
 524  * Decrements the reference count of @tree by one.  If the reference count
 525  * drops to 0, all keys and values will be destroyed (if destroy
 526  * functions were specified) and all memory allocated by @tree will be
 527  * released.
 528  *
 529  * It is safe to call this function from any thread.
 530  *
 531  * Since: 2.22
 532  **/
 533 void
 534 g_tree_unref (GTree *tree)
 535 {
 536   g_return_if_fail (tree != NULL);
 537
 538   if (g_atomic_int_dec_and_test (&tree->ref_count))
 539     {
 540       g_tree_remove_all (tree);
 541       g_free (tree->r);
 542       g_slice_free (GTree, tree);
 543     }
 544 }
 545
 546 /**
 547  * g_tree_destroy:
 548  * @tree: a #GTree.
 549  *
 550  * Removes all keys and values from the #GTree and decreases its
 551  * reference count by one. If keys and/or values are dynamically
 552  * allocated, you should either free them first or create the #GTree
 553  * using g_tree_new_full().  In the latter case the destroy functions
 554  * you supplied will be called on all keys and values before destroying
 555  * the #GTree.
 556  **/
 557 void
 558 g_tree_destroy (GTree *tree)
 559 {
 560   g_return_if_fail (tree != NULL);
 561
 562   g_tree_remove_all (tree);
 563   g_tree_unref (tree);
 564 }
 565
 566 /**
 567  * g_tree_current_version:
 568  * @tree: a #GTree
 569  *
 570  * Returns the current version number of the #GTree.  Inserting or deleting
 571  * keys will affect the current version, but not change earlier versions.
 572  *
 573  * Returns: the current version number of the #GTree.
 574  **/
 575 guint
 576 g_tree_current_version (GTree *tree)
 577 {
 578   return tree->version;
 579 }
 580
 581 /**
 582  * g_tree_next_version:
 583  * @tree: a #GTree
 584  *
 585  * Increments the version number of the tree.  Inserting or deleting keys will
 586  * affect the new version of the tree, but not change earlier versions.
 587  *
 588  * Returns: the new current version number of the #GTree.
 589  **/
 590 guint
 591 g_tree_next_version (GTree *tree)
 592 {
 593   g_assert (tree->version+1 != 0);
 594   return ++tree->version;
 595 }
 596
 597 /* Given the length of the array of versions, return the index of the
 598    first (oldest) version, or @n if there is none. */
 599 #define first_v(n) ((n) > 1 ? 1 : 0)
 600
 601 /* Given a current index, and the length of the array of versions, return
 602    the index of the next (newer) version, or @n if there is none. */
 603 #define next_v(i, n) \
 604   ((i) == 0 ? (n) : /* it was the last version, return something invalid */ \
 605    ((i) == (n)-1 ? 0 : /* it was the second last, return the last */        \
 606     (i)+1)) /* it was somewhere else in the array, return the next */
 607
 608 /* Given a current index, and the length of the array of versions, return
 609    the index of the previous (older) version, or @n if there is none. */
 610 #define prev_v(i, n) \
 611   ((i) == 0 ? (n)-1 : /* it was the last version, return the second last */ \
 612    ((i) == 1 ? (n) : /* it was the first, return something invalid */       \
 613     (i)-1)); /* it was somewhere else in the array, return the previous */
 614
 615 static guint
 616 g_tree_node_delete_versions (GTree     *tree,
 617                              GTreeNode *node,
 618                              guint      pnext,
 619                              guint      version)
 620 {
 621   guint rm, i, nv, next, nextv, lnext, rnext, ret;
 622
 623   if (!node)
 624     return 0;
 625
 626   nv = node->nv;
 627
 628   ret = 0;
 629   rm = 0;
 630   for (i = first_v (nv); i < nv && node->v[i].version <= version; i = next)
 631     {
 632       next = next_v (i, nv);
 633
 634       if (next < nv)
 635         nextv = node->v[next].version - 1;
 636       else
 637         nextv = version;
 638
 639       if (next < nv && node->v[i].left &&
 640           node->v[next].left == node->v[i].left &&
 641           (!pnext || node->v[next].version <= pnext))
 642         lnext = node->v[next].version;
 643       else if (next == nv || node->v[next].version > pnext)
 644         lnext = pnext;
 645       else
 646         lnext = 0;
 647       lnext = g_tree_node_delete_versions (tree, node->v[i].left, lnext,
 648                                            nextv);
 649
 650       if (next < nv && node->v[i].right &&
 651           node->v[next].right == node->v[i].right &&
 652           (!pnext || node->v[next].version <= pnext))
 653         rnext = node->v[next].version;
 654       else if (next == nv || node->v[next].version > pnext)
 655         rnext = pnext;
 656       else
 657         rnext = 0;
 658       rnext = g_tree_node_delete_versions (tree, node->v[i].right, rnext,
 659                                            nextv);
 660
 661       /* smallest non-zero of pnext, rnext, and lnext (or zero if all 3 are) */
 662       nextv = MIN ((pnext ? pnext : (lnext ? lnext : rnext)),
 663                    MIN ((lnext ? lnext : (rnext ? rnext : pnext)),
 664                         (rnext ? rnext : (lnext ? lnext : pnext))));
 665
 666       if (nextv && (next == nv || node->v[next].version > nextv))
 667         { /* leave this one behind as there are more pointers coming here */
 668           ret = node->v[i].version = nextv;
 669           break;
 670         }
 671
 672       ++rm;
 673     }
 674
 675   /* remove the first 'rm' versioned pointers from the node, they are <=
 676      'version' */
 677   for (i = 1; rm && i+rm < nv; ++i)
 678     node->v[i] = node->v[i+rm];
 679   node->nv -= rm;
 680
 681   /* if we removed the last version inside the node, then we can free it */
 682   if (node->nv == 0)
 683     {
 684       g_tree_node_free (tree, node);
 685       node = NULL;
 686     }
 687
 688   /* if we saved a version here, then it's because a child still needs it
 689      or the parent still needs it.  if the child needs it, then we will
 690      still have a pointer back to the parent, so it needs to also know.  so
 691      either way the parent needs it.
 692      if we did not save a version, but the parent needs us to stick around for
 693      something, then we can let it know that we did
 694   */
 695   if (!ret && node && pnext)
 696     {
 697       g_assert (node->v[first_v (node->nv)].version == pnext);
 698       ret = pnext;
 699     }
 700
 701   return ret;
 702 }
 703
 704 /**
 705  * g_tree_delete_versions:
 706  * @tree: a #GTree.
 707  * @version: the highest version to delete.
 708  *
 709  * Deletes all versions in the #GTree which are at most @version.  You can not
 710  * delete the latest version of the #GTree, so @version must be less than the
 711  * value returned by g_tree_current_version().
 712
 713  * Deleting a version from the #GTree frees all resources used that are not
 714  * needed for later versions in the #GTree.  All elements which have been
 715  * removed from the tree in a version no later than @version will be freed,
 716  * and if you supplied a @key_destroy_func or @value_destroy_func when
 717  * creating the #GTree, any such nodes will have their keys and values
 718  * freed using these functions (unless it was removed from the #GTree by
 719  * g_tree_steal(), in which case the key and value is not freed).
 720  **/
 721 void
 722 g_tree_delete_versions (GTree *tree,
 723                         guint  version)
 724 {
 725   guint rm, i, l, keep, next;
 726
 727   g_return_if_fail (tree != NULL);
 728   g_return_if_fail (version < tree->version);
 729
 730   if (version < tree->r[first_v (tree->nr)].version)
 731     return;
 732
 733   rm = 0;
 734   keep = i = first_v (tree->nr);
 735   next = next_v (i, tree->nr);
 736   while (i < tree->nr && tree->r[i].version < version + 1)
 737     {
 738       guint nextv, v;
 739
 740       if (next == tree->nr || tree->r[next].version > version + 1)
 741         nextv = version + 1;
 742       else if (next < tree->nr && tree->r[next].root == tree->r[i].root)
 743         nextv = tree->r[next].version;
 744       else
 745         nextv = 0;
 746
 747       if (next < tree->nr && tree->r[next].version <= version)
 748         v = tree->r[next].version - 1;
 749       else
 750         v = version;
 751
 752       l = g_tree_node_delete_versions (tree, tree->r[i].root, nextv, v);
 753       g_assert (l == 0 || l > v);
 754
 755       if (l > v)
 756         tree->r[i].version = l;
 757       else
 758         {
 759           ++rm;
 760           keep = next;
 761         }
 762
 763       i = next;
 764       next = next_v (i, tree->nr);
 765     }
 766
 767   if (rm)
 768     {
 769       guint j;
 770       for (j = first_v (tree->nr - rm);
 771            j < tree->nr - rm;
 772            j = next_v (j, tree->nr - rm), keep = next_v (keep, tree->nr))
 773         {
 774           tree->r[j] = tree->r[keep];
 775         }
 776     }
 777
 778   tree->nr -= rm;
 779   tree->r = g_renew(GTreeRootVersion, tree->r, tree->nr);
 780
 781 #ifdef G_TREE_DEBUG
 782   {
 783     guint i;
 784     for (i = 0; i <= tree->version; ++i)
 785       g_tree_node_check (g_tree_root_find_version (tree, i)->root, i);
 786   }
 787 #endif
 788 }
 789
 790 /* Make a new root pointer if the current one is not for the current version
 791    of the tree */
 792 static void
 793 g_tree_root_next_version (GTree *tree)
 794 {
 795   g_assert(tree->r[0].version <= tree->version);
 796
 797   if (tree->r[0].version < tree->version)
 798     {
 799       /* add a new version of the root */
 800       tree->nr++;
 801       tree->r = g_renew(GTreeRootVersion, tree->r, tree->nr);
 802       /* copy the latest version from r[0] */
 803       tree->r[tree->nr-1] = tree->r[0];
 804       tree->r[0].version = tree->version;
 805     }
 806 }
 807
 808 /* add a new version of pointers to a node.  return TRUE if ok, and FALSE
 809    if there is no room to do so. */
 810 static inline GTreeNode *
 811 g_tree_node_add_version (GTree     *tree,
 812                          GTreeNode *node)
 813 {
 814   if (!node)
 815     return NULL;
 816
 817   /* node already has the current version */
 818   if (node->v[0].version == tree->version)
 819     return node;
 820   /* if we filled the node's pointer table and need to make a new GTreeNode */
 821   else if (node->v[0].version == 0 || node->nv >= TABLE_SIZE)
 822     {
 823       GTreeNode *newnode = g_slice_new(GTreeNode);
 824       newnode->v = g_slice_alloc(sizeof(GTreeNodeVersion) * TABLE_SIZE);
 825       newnode->data = node->data;
 826       g_atomic_int_inc (&newnode->data->ref_count);
 827       newnode->v[0] = node->v[0]; /* copy the latest version to here */
 828       newnode->v[0].version = tree->version;
 829       newnode->nv = 1;
 830       return newnode;
 831     }
 832   /* there is space left in the node's pointer table for a new version */
 833   else
 834     {
 835       node->nv++;
 836       /* copy the latest version from v[0] */
 837       node->v[node->nv-1] = node->v[0];
 838       node->v[0].version = tree->version;
 839       return node;
 840     }
 841 }
 842
 843 static inline void
 844 g_tree_node_fix_incoming (GTree     *tree,
 845                           GTreeNode *oldnode,
 846                           GTreeNode *newnode)
 847 {
 848   GTreeNode *oldparent, *oldleft, *oldright;
 849   GTreeNode *newparent, *newleft, *newright;
 850
 851   if (oldnode == newnode) return;
 852
 853   g_assert (oldnode != NULL);
 854   g_assert (newnode != NULL);
 855
 856   /* find incoming edges to the old version of the node */
 857   oldparent = newnode->v[0].parent;
 858   if (oldparent && oldparent->v[0].left != oldnode &&
 859       oldparent->v[0].right != oldnode)
 860     oldparent = NULL;
 861   oldleft = newnode->v[0].left;
 862   if (oldleft && oldleft->v[0].parent != oldnode)
 863     oldleft = NULL;
 864   oldright = newnode->v[0].right;
 865   if (oldright && oldright->v[0].parent != oldnode)
 866     oldright = NULL;
 867
 868   /* add new pointers for nodes that point to me, possibly creating new
 869      versions of the nodes */
 870   newparent = g_tree_node_add_version (tree, oldparent);
 871   newleft = g_tree_node_add_version (tree, oldleft);
 872   newright = g_tree_node_add_version (tree, oldright);
 873
 874   /* 1. update my pointers to point to the new versions (if a prev node
 875      points to me, then i'm its next node, and its my parent or
 876      it is the rightmost node in my left subtree. case a, i update my
 877      pointer to it already.  case b, if it's my left child i update
 878      my pointer to it already, otherwise i don't have a pointer to it,
 879      because i do have a left subtree.
 880   */
 881   if (newparent != oldparent)
 882     newnode->v[0].parent = newparent;
 883   if (newleft != oldleft)
 884     newnode->v[0].left = newleft;
 885   if (newright != oldright)
 886     newnode->v[0].right = newright;
 887
 888   /* 2. update my incoming nodes to point back to the new version of me */
 889   if (newparent)
 890     {
 891       if (newparent->v[0].left == oldnode)
 892         newparent->v[0].left = newnode;
 893       else
 894         newparent->v[0].right = newnode;
 895     }
 896   if (newleft)
 897     newleft->v[0].parent = newnode;
 898   if (newright)
 899     newright->v[0].parent = newnode;
 900
 901   /* 3. recurse on each of the incoming nodes if they had to create a new
 902      version */
 903   g_tree_node_fix_incoming (tree, oldparent, newparent);
 904   g_tree_node_fix_incoming (tree, oldleft, newleft);
 905   g_tree_node_fix_incoming (tree, oldright, newright);
 906
 907   /* 4. if this was the root node, then the root pointer into the tree needs
 908      be updated */
 909   if (tree->r[0].root == oldnode)
 910     {
 911       g_tree_root_next_version (tree);
 912       tree->r[0].root = newnode;
 913     }
 914 }
 915
 916 /* You must call this on a node before you start changing its pointers,
 917    or you might be changing an old (permanent) version of the node */
 918 static GTreeNode*
 919 g_tree_node_next_version (GTree     *tree,
 920                           GTreeNode *oldnode)
 921 {
 922   GTreeNode *newnode;
 923
 924   if (!oldnode)
 925     return NULL;
 926
 927   g_assert(oldnode->v[0].version <= tree->version);
 928
 929   newnode = g_tree_node_add_version (tree, oldnode);
 930   g_tree_node_fix_incoming (tree, oldnode, newnode);
 931   return newnode;
 932 }
 933
 934 /**
 935  * g_tree_insert:
 936  * @tree: a #GTree.
 937  * @key: the key to insert.
 938  * @value: the value corresponding to the key.
 939  *
 940  * Inserts a key/value pair into a #GTree. If the given key already exists
 941  * in the #GTree its corresponding value is set to the new value. If you
 942  * supplied a value_destroy_func when creating the #GTree, the old value is
 943  * freed using that function. If you supplied a @key_destroy_func when
 944  * creating the #GTree, the passed key is freed using that function.
 945  *
 946  * The tree is automatically 'balanced' as new key/value pairs are added,
 947  * so that the distance from the root to every leaf is small.
 948  **/
 949 void
 950 g_tree_insert (GTree    *tree,
 951                gpointer  key,
 952                gpointer  value)
 953 {
 954   g_return_if_fail (tree != NULL);
 955
 956   g_tree_insert_internal (tree, key, value, FALSE);
 957
 958 #ifdef G_TREE_DEBUG
 959   {
 960     guint i;
 961     for (i = 0; i <= tree->version; ++i)
 962       g_tree_node_check (g_tree_root_find_version (tree, i)->root, i);
 963   }
 964 #endif
 965 }
 966
 967 /**
 968  * g_tree_replace:
 969  * @tree: a #GTree.
 970  * @key: the key to insert.
 971  * @value: the value corresponding to the key.
 972  *
 973  * Inserts a new key and value into a #GTree similar to g_tree_insert().
 974  * The difference is that if the key already exists in the #GTree, it gets
 975  * replaced by the new key. If you supplied a @value_destroy_func when
 976  * creating the #GTree, the old value is freed using that function. If you
 977  * supplied a @key_destroy_func when creating the #GTree, the old key is
 978  * freed using that function.
 979  *
 980  * The tree is automatically 'balanced' as new key/value pairs are added,
 981  * so that the distance from the root to every leaf is small.
 982  **/
 983 void
 984 g_tree_replace (GTree    *tree,
 985                 gpointer  key,
 986                 gpointer  value)
 987 {
 988   g_return_if_fail (tree != NULL);
 989
 990   g_tree_insert_internal (tree, key, value, TRUE);
 991
 992 #ifdef G_TREE_DEBUG
 993   {
 994     guint i;
 995     for (i = 0; i <= tree->version; ++i)
 996       g_tree_node_check (g_tree_root_find_version (tree, i)->root, i);
 997   }
 998 #endif
 999 }
1000
1001 /*
1002  * Implementation of a treap
1003  *
1004  * (Copied from gsequence.c)
1005  */
1006 static guint
1007 g_tree_priority (GTreeNode *node)
1008 {
1009   guint key = GPOINTER_TO_UINT (node->data);
1010
1011   /* This hash function is based on one found on Thomas Wang's
1012    * web page at
1013    *
1014    *    http://www.concentric.net/~Ttwang/tech/inthash.htm
1015    *
1016    */
1017   key = (key << 15) - key - 1;
1018   key = key ^ (key >> 12);
1019   key = key + (key << 2);
1020   key = key ^ (key >> 4);
1021   key = key + (key << 3) + (key << 11);
1022   key = key ^ (key >> 16);
1023
1024   /* We rely on 0 being less than all other priorities */
1025   return key? key : 1;
1026 }
1027
1028 /* Internal insert routine.  Always inserts into the current version of the
1029    tree. */
1030 static void
1031 g_tree_insert_internal (GTree    *tree,
1032                         gpointer  key,
1033                         gpointer  value,
1034                         gboolean  replace)
1035 {
1036   GTreeNode *node, *child;
1037
1038   g_return_if_fail (tree != NULL);
1039
1040   if (!tree->r[0].root)
1041     {
1042       g_tree_root_next_version (tree);
1043       tree->r[0].root = g_tree_node_new (tree, key, value);
1044       tree->nnodes++;
1045       return;
1046     }
1047
1048   node = tree->r[0].root;
1049
1050   while (1)
1051     {
1052       gint cmp = tree->key_compare (key, node->data->key,
1053                                     tree->key_compare_data);
1054
1055       if (cmp == 0)
1056         {
1057           if (tree->value_destroy_func)
1058             tree->value_destroy_func (node->data->value);
1059
1060           node->data->value = value;
1061
1062           if (replace)
1063             {
1064               if (tree->key_destroy_func)
1065                 tree->key_destroy_func (node->data->key);
1066
1067               node->data->key = key;
1068             }
1069           else
1070             {
1071               /* free the passed key */
1072               if (tree->key_destroy_func)
1073                 tree->key_destroy_func (key);
1074             }
1075
1076           return;
1077         }
1078       else if (cmp < 0)
1079         {
1080           if (node->v[0].left)
1081               node = node->v[0].left;
1082           else
1083             {
1084               child = g_tree_node_new (tree, key, value);
1085               node = g_tree_node_next_version (tree, node);
1086
1087               child->v[0].parent = node;
1088               node->v[0].left = child;
1089
1090               tree->nnodes++;
1091
1092               break;
1093             }
1094         }
1095       else
1096         {
1097           if (node->v[0].right)
1098               node = node->v[0].right;
1099           else
1100             {
1101               child = g_tree_node_new (tree, key, value);
1102               node = g_tree_node_next_version (tree, node);
1103
1104               child->v[0].parent = node;
1105               node->v[0].right = child;
1106
1107               tree->nnodes++;
1108
1109               break;
1110             }
1111         }
1112     }
1113
1114   /* rotate the new node up until the heap property is restored */
1115   node = child;
1116   while (node->v[0].parent &&
1117          g_tree_priority (node) < g_tree_priority (node->v[0].parent))
1118     {
1119       GTreeNode *sp, *p;
1120
1121       /* we'll be changing both of these nodes */
1122       p = g_tree_node_next_version (tree, node->v[0].parent);
1123       sp = g_tree_node_next_version (tree, p->v[0].parent);
1124
1125       if (p->v[0].left == node)
1126         node = g_tree_node_rotate_right (tree, p);
1127       else
1128         node = g_tree_node_rotate_left (tree, p);
1129
1130       if (!sp)
1131         {
1132           g_tree_root_next_version (tree);
1133           tree->r[0].root = node;
1134         }
1135       else if (sp->v[0].left == p)
1136         sp->v[0].left = node;
1137       else
1138         sp->v[0].right = node;
1139     }
1140 }
1141
1142 /**
1143  * g_tree_remove:
1144  * @tree: a #GTree.
1145  * @key: the key to remove.
1146  *
1147  * Removes a key/value pair from a #GTree.
1148  *
1149  * If the #GTree was created using g_tree_new_full(), the key and value
1150  * are freed using the supplied destroy functions, otherwise you have to
1151  * make sure that any dynamically allocated values are freed yourself.
1152  * Note that if the key existed in
1153  * earlier versions of the tree (g_tree_next_version() has been called since
1154  * it was inserted), then it cannot be removed from the tree. *
1155  * If the key does not exist in the #GTree, the function does nothing.
1156  *
1157  * Returns: %TRUE if the key was found and able to be removed
1158  *   (prior to 2.8, this function returned nothing)
1159  **/
1160 gboolean
1161 g_tree_remove (GTree         *tree,
1162                gconstpointer  key)
1163 {
1164   gboolean removed;
1165
1166   g_return_val_if_fail (tree != NULL, FALSE);
1167
1168   removed = g_tree_remove_internal (tree, key, FALSE);
1169
1170 #ifdef G_TREE_DEBUG
1171   {
1172     guint i;
1173     for (i = 0; i <= tree->version; ++i)
1174       g_tree_node_check (g_tree_root_find_version (tree, i)->root, i);
1175   }
1176 #endif
1177
1178   return removed;
1179 }
1180
1181 /**
1182  * g_tree_steal:
1183  * @tree: a #GTree.
1184  * @key: the key to remove.
1185  *
1186  * Removes a key and its associated value from a #GTree without calling
1187  * the key and value destroy functions.  Note that if the key existed in
1188  * earlier versions of the tree (g_tree_next_version() has been called since
1189  * it was inserted), then it cannot be removed from the tree until all
1190  * versions containing the node are removed from the tree, by calling
1191  * g_tree_delete_versions().  However, if the node is removed from the current
1192  * version of the tree with g_tree_steal() then the key and value destroy
1193  * functions will not be called once the last version of the key/value pair
1194  * is removed.
1195  * If the key does not exist in the #GTree, the function does nothing.
1196  *
1197  * Returns: %TRUE if the key was found and able to be removed
1198  *   (prior to 2.8, this function returned nothing)
1199  **/
1200 gboolean
1201 g_tree_steal (GTree         *tree,
1202               gconstpointer  key)
1203 {
1204   gboolean removed;
1205
1206   g_return_val_if_fail (tree != NULL, FALSE);
1207
1208   removed = g_tree_remove_internal (tree, key, TRUE);
1209
1210 #ifdef G_TREE_DEBUG
1211   {
1212     guint i;
1213     for (i = 0; i <= tree->version; ++i)
1214       g_tree_node_check (g_tree_root_find_version (tree, i)->root, i);
1215   }
1216 #endif
1217
1218   return removed;
1219 }
1220
1221 /* internal remove routine */
1222 static gboolean
1223 g_tree_remove_internal (GTree         *tree,
1224                         gconstpointer  key,
1225                         gboolean       steal)
1226 {
1227   GTreeNode *node, *parent;
1228   gboolean is_leftchild;
1229   gboolean data_free;
1230
1231   g_return_val_if_fail (tree != NULL, FALSE);
1232
1233   if (!tree->r[0].root)
1234     return FALSE;
1235
1236   node = tree->r[0].root;
1237   parent = NULL;
1238   is_leftchild = FALSE;
1239
1240   while (1)
1241     {
1242       gint cmp = tree->key_compare (key, node->data->key,
1243                                     tree->key_compare_data);
1244
1245       if (cmp == 0)
1246         break;
1247       else if (cmp < 0)
1248         {
1249           if (!node->v[0].left)
1250             return FALSE;
1251
1252           parent = node;
1253           is_leftchild = TRUE;
1254           node = node->v[0].left;
1255         }
1256       else
1257         {
1258           if (!node->v[0].right)
1259             return FALSE;
1260
1261           parent = node;
1262           is_leftchild = FALSE;
1263           node = node->v[0].right;
1264         }
1265     }
1266
1267   /* rotate the node down the tree, maintaining the heap property */
1268   while (node->v[0].left || node->v[0].right)
1269     {
1270       /* we're changing this node, make sure our pointer will stay valid
1271          when we rotate it */
1272       node = g_tree_node_next_version (tree, node);
1273       /* getting the next version for the node may change where its parent
1274          lies, so get a new pointer for it, from the node */
1275       parent = node->v[0].parent;
1276
1277       if (!node->v[0].left ||
1278           (node->v[0].right &&
1279            g_tree_priority (node->v[0].left) >
1280            g_tree_priority (node->v[0].right)))
1281         {
1282           /* rotate the right child up */
1283           if (!parent)
1284             {
1285               g_tree_root_next_version (tree);
1286               parent = tree->r[0].root =
1287                 g_tree_node_rotate_left (tree, node);
1288             }
1289           else
1290             {
1291               parent = g_tree_node_next_version (tree, parent);
1292               if (is_leftchild)
1293                 parent = parent->v[0].left =
1294                   g_tree_node_rotate_left (tree, node);
1295               else
1296                 parent = parent->v[0].right =
1297                   g_tree_node_rotate_left (tree, node);
1298             }
1299           is_leftchild = TRUE;
1300         }
1301       else
1302         {
1303           /* rotate the left child up */
1304           if (!parent)
1305             {
1306               g_tree_root_next_version (tree);
1307               parent = tree->r[0].root =
1308                 g_tree_node_rotate_right (tree, node);
1309             }
1310           else
1311             {
1312               parent = g_tree_node_next_version (tree, parent);
1313               if (is_leftchild)
1314                 parent = parent->v[0].left =
1315                   g_tree_node_rotate_right (tree, node);
1316               else
1317                 parent = parent->v[0].right =
1318                   g_tree_node_rotate_right (tree, node);
1319             }
1320           is_leftchild = FALSE;
1321         }
1322     }
1323
1324   /* remove any pointers to the node in the treap */
1325   if (!parent)
1326     {
1327       g_tree_root_next_version (tree);
1328       tree->r[0].root = NULL;
1329     }
1330   else
1331     {
1332       /* make a new version of the parent to cut the child off.
1333          making a new version of the parent may make a new version of
1334          the node being deleted, which is the one we'd want to free then
1335          instead, so update the node pointer */
1336       parent = g_tree_node_next_version (tree, parent);
1337       if (is_leftchild)
1338         {
1339           node = parent->v[0].left;
1340           parent->v[0].left = NULL;
1341         }
1342       else
1343         {
1344           node = parent->v[0].right;
1345           parent->v[0].right = NULL;
1346         }
1347     }
1348
1349   tree->nnodes--;
1350
1351   if (node->v[0].version == tree->version)
1352     {
1353       /* remove the entry from the node's pointer table */
1354       node->v[0] = node->v[node->nv-1];
1355       --node->nv;
1356     }
1357
1358   node->data->stolen = steal;
1359   data_free = FALSE;
1360
1361   /* only really delete the node if it was only in the current version,
1362      otherwise it needs to be remembered */
1363   if (node->nv == 0)
1364     data_free = g_tree_node_free (tree, node);
1365
1366   return data_free;
1367 }
1368
1369 /**
1370  * g_tree_lookup:
1371  * @tree: a #GTree.
1372  * @key: the key to look up.
1373  *
1374  * Gets the value corresponding to the given key. Since a #GTree is
1375  * automatically balanced as key/value pairs are added, key lookup is very
1376  * fast.
1377  *
1378  * Return value: the value corresponding to the key, or %NULL if the key was
1379  * not found.
1380  **/
1381 gpointer
1382 g_tree_lookup (GTree         *tree,
1383                gconstpointer  key)
1384 {
1385   return g_tree_lookup_related (tree, key, G_TREE_SEARCH_EXACT, tree->version);
1386 }
1387
1388 /**
1389  * g_tree_lookup_related:
1390  * @tree: a #GTree.
1391  * @key: the key to look up.
1392  * @search_type: the search behavior if the @key is not present in the #GTree,
1393  *   one of %G_TREE_SEARCH_EXACT, %G_TREE_SEARCH_SUCCESSOR, and
1394  *   %G_TREE_SEARCH_PREDECESSOR.
1395  * @version: the version of the tree within which to search.  If
1396  *   g_tree_next_version() has not been used, then this is 0.
1397  *
1398  * Gets a value corresponding to the given key.
1399  *
1400  * If the given @key is present in the tree, then its corresponding value is
1401  * always returned.  If it is not, then the @search_type will define the
1402  * function's behavior.  If @search_type is %G_TREE_SEARCH_EXACT, the
1403  * function will return %NULL if the @key is not found.  If @search_type is
1404  * %G_TREE_SEARCH_SUCCESSOR, the function will find the next larger key that
1405  * is present in the tree and return its value, or %NULL if there are no keys
1406  * larger than @key in the tree.  If @search_type is
1407  * %G_TREE_SEARCH_PREDECESSOR, the function will find the next smaller key that
1408  * is present in the tree and return its value, or %NULL if there are no keys
1409  * smaller than @key in the tree.
1410  * Since a #GTree is
1411  * automatically balanced as key/value pairs are added, key lookup is very
1412  * fast.
1413  *
1414  * Return value: the value corresponding to the found key, or %NULL if no
1415  * matching key was found.
1416  **/
1417 gpointer
1418 g_tree_lookup_related  (GTree          *tree,
1419                         gconstpointer   key,
1420                         GTreeSearchType search_type,
1421                         guint           version)
1422 {
1423   GTreeNode *node;
1424
1425   g_return_val_if_fail (tree != NULL, NULL);
1426   g_return_val_if_fail (version <= tree->version, NULL);
1427
1428   node = g_tree_find_node (tree, key, search_type, version);
1429
1430   return node ? node->data->value : NULL;
1431 }
1432
1433 /**
1434  * g_tree_lookup_extended:
1435  * @tree: a #GTree.
1436  * @lookup_key: the key to look up.
1437  * @orig_key: returns the original key.
1438  * @value: returns the value associated with the key.
1439  *
1440  * Looks up a key in the #GTree, returning the original key and the
1441  * associated value and a #gboolean which is %TRUE if the key was found. This
1442  * is useful if you need to free the memory allocated for the original key,
1443  * for example before calling g_tree_remove().
1444  *
1445  * Return value: %TRUE if the key was found in the #GTree.
1446  **/
1447 gboolean
1448 g_tree_lookup_extended (GTree         *tree,
1449                         gconstpointer  lookup_key,
1450                         gpointer      *orig_key,
1451                         gpointer      *value)
1452 {
1453   GTreeNode *node;
1454
1455   g_return_val_if_fail (tree != NULL, FALSE);
1456
1457   node = g_tree_find_node (tree, lookup_key, G_TREE_SEARCH_EXACT, tree->version);
1458
1459   if (node)
1460     {
1461       if (orig_key)
1462         *orig_key = node->data->key;
1463       if (value)
1464         *value = node->data->value;
1465       return TRUE;
1466     }
1467   else
1468     return FALSE;
1469 }
1470
1471 /**
1472  * g_tree_foreach:
1473  * @tree: a #GTree.
1474  * @func: the function to call for each node visited. If this function
1475  *   returns %TRUE, the traversal is stopped.
1476  * @user_data: user data to pass to the function.
1477  *
1478  * Calls the given function for each of the key/value pairs in the #GTree.
1479  * The function is passed the key and value of each pair, and the given
1480  * @data parameter. The tree is traversed in sorted order.
1481  *
1482  * The tree may not be modified while iterating over it (you can't
1483  * add/remove items). To remove all items matching a predicate, you need
1484  * to add each item to a list in your #GTraverseFunc as you walk over
1485  * the tree, then walk the list and remove each item.
1486  **/
1487 void
1488 g_tree_foreach (GTree         *tree,
1489                 GTraverseFunc  func,
1490                 gpointer       user_data)
1491 {
1492   GTreeNode *node;
1493
1494   g_return_if_fail (tree != NULL);
1495
1496   if (!tree->r[0].root)
1497     return;
1498
1499   node = g_tree_first_node (tree, tree->version);
1500
1501   while (node)
1502     {
1503       if ((*func) (node->data->key, node->data->value, user_data))
1504         break;
1505
1506       node = g_tree_node_next (node, tree->version);
1507     }
1508 }
1509
1510 /**
1511  * g_tree_traverse:
1512  * @tree: a #GTree.
1513  * @traverse_func: the function to call for each node visited. If this
1514  *   function returns %TRUE, the traversal is stopped.
1515  * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
1516  *   %G_PRE_ORDER and %G_POST_ORDER.
1517  * @user_data: user data to pass to the function.
1518  *
1519  * Calls the given function for each node in the #GTree.
1520  *
1521  * Deprecated:2.2: The order of a balanced tree is somewhat arbitrary. If you
1522  * just want to visit all nodes in sorted order, use g_tree_foreach()
1523  * instead. If you really need to visit nodes in a different order, consider
1524  * using an <link linkend="glib-N-ary-Trees">N-ary Tree</link>.
1525  **/
1526 void
1527 g_tree_traverse (GTree         *tree,
1528                  GTraverseFunc  traverse_func,
1529                  GTraverseType  traverse_type,
1530                  gpointer       user_data)
1531 {
1532   g_return_if_fail (tree != NULL);
1533
1534   if (!tree->r[0].root)
1535     return;
1536
1537   switch (traverse_type)
1538     {
1539     case G_PRE_ORDER:
1540       g_tree_node_pre_order (tree->r[0].root, traverse_func, user_data);
1541       break;
1542
1543     case G_IN_ORDER:
1544       g_tree_node_in_order (tree->r[0].root, traverse_func, user_data);
1545       break;
1546
1547     case G_POST_ORDER:
1548       g_tree_node_post_order (tree->r[0].root, traverse_func, user_data);
1549       break;
1550
1551     case G_LEVEL_ORDER:
1552       g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
1553       break;
1554     }
1555 }
1556
1557 /**
1558  * g_tree_search:
1559  * @tree: a #GTree.
1560  * @search_func: a function used to search the #GTree.
1561  * @user_data: the data passed as the second argument to the @search_func
1562  * function.
1563  *
1564  * Searches a #GTree using @search_func.
1565  *
1566  * The @search_func is called with a pointer to the key of a key/value pair in
1567  * the tree, and the passed in @user_data. If @search_func returns 0 for a
1568  * key/value pair, then g_tree_search_func() will return the value of that
1569  * pair. If @search_func returns -1,  searching will proceed among the
1570  * key/value pairs that have a smaller key; if @search_func returns 1,
1571  * searching will proceed among the key/value pairs that have a larger key.
1572  *
1573  * Return value: the value corresponding to the found key, or %NULL if the key
1574  * was not found.
1575  **/
1576 gpointer
1577 g_tree_search (GTree         *tree,
1578                GCompareFunc   search_func,
1579                gconstpointer  user_data)
1580 {
1581   return g_tree_search_related (tree, search_func, user_data,
1582                                 G_TREE_SEARCH_EXACT);
1583 }
1584
1585 /**
1586  * g_tree_search_related:
1587  * @tree: a #GTree.
1588  * @search_func: a function used to search the #GTree.
1589  * @user_data: the data passed as the second argument to the @search_func
1590  * @search_type: the search behavior if the @key is not present in the #GTree,
1591  *   one of %G_TREE_SEARCH_EXACT, %G_TREE_SEARCH_SUCCESSOR, and
1592  *   %G_TREE_SEARCH_PREDECESSOR.
1593  *
1594  * Searches a #GTree using @search_func.
1595  *
1596  * The @search_func is called with a pointer to the key of a key/value pair in
1597  * the tree, and the passed in @user_data. If @search_func returns 0 for a
1598  * key/value pair, then g_tree_search_func() will return the value of that
1599  * pair. If @search_func returns -1,  searching will proceed among the
1600  * key/value pairs that have a smaller key; if @search_func returns 1,
1601  * searching will proceed among the key/value pairs that have a larger key.
1602  * If @search_func never returns 0 before searching the entire height of the
1603  * tree, then the @search_type will define what the function returns.
1604  * If @search_type is %G_TREE_SEARCH_EXACT, the
1605  * function will return %NULL.  If @search_type is
1606  * %G_TREE_SEARCH_SUCCESSOR, the function will return the value corresponding
1607  * to the last key at which @search_func returned -1.  This key would be the
1608  * successor to the element being searched for. If @search_type is
1609  * %G_TREE_SEARCH_PREDECESSOR, the function return the value corresponding
1610  * to the last key at which @search_func returned 1.  This key would be the
1611  * predecessor to the element being searched for.
1612  *
1613  * Return value: the value corresponding to the found key, or %NULL if no
1614  * matching key was found.
1615  **/
1616 gpointer
1617 g_tree_search_related (GTree          *tree,
1618                        GCompareFunc    search_func,
1619                        gconstpointer   user_data,
1620                        GTreeSearchType search_type)
1621 {
1622   g_return_val_if_fail (tree != NULL, NULL);
1623
1624   return g_tree_node_search (tree->r[0].root,
1625                              search_func, user_data, search_type,
1626                              tree->version);
1627 }
1628
1629 static gint
1630 g_tree_node_height(GTreeNode *node)
1631 {
1632   gint l = 0, r = 0;
1633   if (node == NULL) return 0;
1634   if (node->v[0].left) l = g_tree_node_height (node->v[0].left);
1635   if (node->v[0].right) r = g_tree_node_height (node->v[0].right);
1636   return 1 + MAX(l, r);
1637 }
1638
1639 /**
1640  * g_tree_height:
1641  * @tree: a #GTree.
1642  *
1643  * Gets the height of a #GTree.
1644  *
1645  * If the #GTree contains no nodes, the height is 0.
1646  * If the #GTree contains only one root node the height is 1.
1647  * If the root node has children the height is 2, etc.
1648  *
1649  * Return value: the height of the #GTree.
1650  **/
1651 gint
1652 g_tree_height (GTree *tree)
1653 {
1654   g_return_val_if_fail (tree != NULL, 0);
1655
1656   return g_tree_node_height (tree->r[0].root);
1657 }
1658
1659 /**
1660  * g_tree_nnodes:
1661  * @tree: a #GTree.
1662  *
1663  * Gets the number of nodes in the current version of a #GTree.
1664  *
1665  * Return value: the number of nodes in the latest version of the #GTree.
1666  **/
1667 gint
1668 g_tree_nnodes (GTree *tree)
1669 {
1670   g_return_val_if_fail (tree != NULL, 0);
1671
1672   return tree->nnodes;
1673 }
1674
1675 static GTreeNode *
1676 g_tree_find_node (GTree           *tree,
1677                   gconstpointer    key,
1678                   GTreeSearchType  search_type,
1679                   guint            version)
1680 {
1681   GTreeNode *node, *remember;
1682   GTreeRootVersion *rv;
1683   gint cmp;
1684
1685   rv = g_tree_root_find_version (tree, version);
1686   node = rv->root;
1687   if (!node)
1688     return NULL;
1689
1690   remember = NULL;
1691   while (1)
1692     {
1693       cmp = tree->key_compare (key, node->data->key, tree->key_compare_data);
1694       if (cmp == 0)
1695         return node;
1696       else if (cmp < 0)
1697         {
1698           GTreeNodeVersion *nodev = g_tree_node_find_version (node, version);
1699           if (search_type == G_TREE_SEARCH_SUCCESSOR)
1700             remember = node;
1701           if (!nodev->left)
1702             return remember;
1703
1704           node = nodev->left;
1705         }
1706       else
1707         {
1708           GTreeNodeVersion *nodev = g_tree_node_find_version (node, version);
1709           if (search_type == G_TREE_SEARCH_PREDECESSOR)
1710             remember = node;
1711           if (!nodev->right)
1712             return remember;
1713
1714           node = nodev->right;
1715         }
1716     }
1717 }
1718
1719 static gint
1720 g_tree_node_pre_order (GTreeNode     *node,
1721                        GTraverseFunc  traverse_func,
1722                        gpointer       data)
1723 {
1724   if ((*traverse_func) (node->data->key, node->data->value, data))
1725     return TRUE;
1726
1727   if (node->v[0].left)
1728     {
1729       if (g_tree_node_pre_order (node->v[0].left, traverse_func, data))
1730         return TRUE;
1731     }
1732
1733   if (node->v[0].right)
1734     {
1735       if (g_tree_node_pre_order (node->v[0].right, traverse_func, data))
1736         return TRUE;
1737     }
1738
1739   return FALSE;
1740 }
1741
1742 static gint
1743 g_tree_node_in_order (GTreeNode     *node,
1744                       GTraverseFunc  traverse_func,
1745                       gpointer       data)
1746 {
1747   if (node->v[0].left)
1748     {
1749       if (g_tree_node_in_order (node->v[0].left, traverse_func, data))
1750         return TRUE;
1751     }
1752
1753   if ((*traverse_func) (node->data->key, node->data->value, data))
1754     return TRUE;
1755
1756   if (node->v[0].right)
1757     {
1758       if (g_tree_node_in_order (node->v[0].right, traverse_func, data))
1759         return TRUE;
1760     }
1761
1762   return FALSE;
1763 }
1764
1765 static gint
1766 g_tree_node_post_order (GTreeNode     *node,
1767                         GTraverseFunc  traverse_func,
1768                         gpointer       data)
1769 {
1770   if (node->v[0].left)
1771     {
1772       if (g_tree_node_post_order (node->v[0].left, traverse_func, data))
1773         return TRUE;
1774     }
1775
1776   if (node->v[0].right)
1777     {
1778       if (g_tree_node_post_order (node->v[0].right, traverse_func, data))
1779         return TRUE;
1780     }
1781
1782   if ((*traverse_func) (node->data->key, node->data->value, data))
1783     return TRUE;
1784
1785   return FALSE;
1786 }
1787
1788 static gpointer
1789 g_tree_node_search (GTreeNode       *node,
1790                     GCompareFunc     search_func,
1791                     gconstpointer    data,
1792                     GTreeSearchType  search_type,
1793                     guint            version)
1794 {
1795   gint dir;
1796   GTreeNode *remember;
1797
1798   if (!node)
1799     return NULL;
1800
1801   remember = NULL;
1802   while (1)
1803     {
1804       dir = (* search_func) (node->data->key, data);
1805       if (dir == 0)
1806         return node->data->value;
1807       else if (dir < 0)
1808         {
1809           GTreeNodeVersion *nodev = g_tree_node_find_version (node, version);
1810           if (search_type == G_TREE_SEARCH_SUCCESSOR)
1811             remember = node;
1812           if (!nodev->left)
1813             return remember;
1814
1815           node = nodev->left;
1816         }
1817       else
1818         {
1819           GTreeNodeVersion *nodev = g_tree_node_find_version (node, version);
1820           if (search_type == G_TREE_SEARCH_PREDECESSOR)
1821             remember = node;
1822           if (!nodev->right)
1823             return remember;
1824
1825           node = nodev->right;
1826         }
1827     }
1828 }
1829
1830 static GTreeNode*
1831 g_tree_node_rotate_left (GTree     *tree,
1832                          GTreeNode *node)
1833 {
1834   GTreeNode *right;
1835
1836   g_assert (node->v[0].version == tree->version);
1837
1838   right = g_tree_node_next_version (tree, node->v[0].right);
1839
1840   if (right->v[0].left)
1841     {
1842       node->v[0].right = g_tree_node_next_version (tree, right->v[0].left);
1843       node->v[0].right->v[0].parent = node;
1844     }
1845   else
1846       node->v[0].right = NULL;
1847   right->v[0].left = node;
1848   right->v[0].parent = node->v[0].parent;
1849   node->v[0].parent = right;
1850
1851   return right;
1852 }
1853
1854 static GTreeNode*
1855 g_tree_node_rotate_right (GTree     *tree,
1856                           GTreeNode *node)
1857 {
1858   GTreeNode *left;
1859
1860   g_assert (node->v[0].version == tree->version);
1861
1862   left = g_tree_node_next_version (tree, node->v[0].left);
1863
1864   if (left->v[0].right)
1865     {
1866       node->v[0].left = g_tree_node_next_version (tree, left->v[0].right);
1867       node->v[0].left->v[0].parent = node;
1868     }
1869   else
1870     node->v[0].left = NULL;
1871   left->v[0].right = node;
1872   left->v[0].parent = node->v[0].parent;
1873   node->v[0].parent = left;
1874
1875   return left;
1876 }
1877
1878 #ifdef G_TREE_DEBUG
1879 static void
1880 g_tree_node_check (GTreeNode *node,
1881                    guint      version)
1882 {
1883   GTreeNodeVersion *nv, *tmpv;
1884
1885   if (node)
1886     {
1887       nv = g_tree_node_find_version (node, version);
1888
1889       g_assert (nv->left == NULL || nv->left != nv->right);
1890
1891       if (nv->left)
1892         {
1893           tmpv = g_tree_node_find_version (nv->left, version);
1894           g_assert (tmpv->parent == node);
1895         }
1896
1897       if (nv->right)
1898         {
1899           tmpv = g_tree_node_find_version (nv->right, version);
1900           g_assert (tmpv->parent == node);
1901         }
1902
1903       if (nv->parent)
1904         {
1905           tmpv = g_tree_node_find_version (nv->parent, version);
1906           g_assert (tmpv->left == node || tmpv->right == node);
1907         }
1908
1909       if (nv->left)
1910         g_tree_node_check (nv->left, version);
1911       if (nv->right)
1912         g_tree_node_check (nv->right, version);
1913     }
1914 }
1915
1916 static void
1917 g_tree_node_dump (GTreeNode *node,
1918                   guint      version,
1919                   gint       indent)
1920 {
1921   GTreeNodeVersion *nv = g_tree_node_find_version (node, version);
1922
1923   g_print ("%*s%c\n", indent, "", *(char *)node->data->key);
1924
1925   if (nv->left)
1926     g_tree_node_dump (nv->left, version, indent + 2);
1927   else if ((node = g_tree_node_previous (node, version)))
1928     g_print ("%*s<%c\n", indent + 2, "", *(char *)node->data->key);
1929
1930   if (nv->right)
1931     g_tree_node_dump (nv->right, version, indent + 2);
1932   else if ((node = g_tree_node_next (node, version)))
1933     g_print ("%*s>%c\n", indent + 2, "", *(char *)node->data->key);
1934 }
1935
1936
1937 void
1938 g_tree_dump (GTree *tree,
1939              guint  version)
1940 {
1941   GTreeRootVersion *rv = g_tree_root_find_version (tree, version);
1942   if (rv->root)
1943     g_tree_node_dump (rv->root, version, 0);
1944 }
1945 #endif
1946
1947
1948 #define __G_TREE_C__
1949 #include "galiasdef.c"
1950