home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 6 File / 06-File.zip / mc454src.zip / mc-4.5.4.src / os2emx / src / glib / gtree.c < prev    next >
C/C++ Source or Header  |  1999-01-04  |  16KB  |  736 lines
  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 Library 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.  * Library General Public License for more details.
  13.  *
  14.  * You should have received a copy of the GNU Library 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.  * MT safe
  22.  */
  23.  
  24. #include "glib.h"
  25.  
  26.  
  27. typedef struct _GRealTree  GRealTree;
  28. typedef struct _GTreeNode  GTreeNode;
  29.  
  30. struct _GRealTree
  31. {
  32.   GTreeNode *root;
  33.   GCompareFunc key_compare;
  34. };
  35.  
  36. struct _GTreeNode
  37. {
  38.   gint balance;      /* height (left) - height (right) */
  39.   GTreeNode *left;   /* left subtree */
  40.   GTreeNode *right;  /* right subtree */
  41.   gpointer key;      /* key for this node */
  42.   gpointer value;    /* value stored at this node */
  43. };
  44.  
  45.  
  46. static GTreeNode* g_tree_node_new                   (gpointer        key,
  47.                              gpointer        value);
  48. static void       g_tree_node_destroy               (GTreeNode      *node);
  49. static GTreeNode* g_tree_node_insert                (GTreeNode      *node,
  50.                              GCompareFunc    compare,
  51.                              gpointer        key,
  52.                              gpointer        value,
  53.                              gint           *inserted);
  54. static GTreeNode* g_tree_node_remove                (GTreeNode      *node,
  55.                              GCompareFunc    compare,
  56.                              gpointer        key);
  57. static GTreeNode* g_tree_node_balance               (GTreeNode      *node);
  58. static GTreeNode* g_tree_node_remove_leftmost       (GTreeNode      *node,
  59.                              GTreeNode     **leftmost);
  60. static GTreeNode* g_tree_node_restore_left_balance  (GTreeNode      *node,
  61.                              gint            old_balance);
  62. static GTreeNode* g_tree_node_restore_right_balance (GTreeNode      *node,
  63.                              gint            old_balance);
  64. static gpointer   g_tree_node_lookup                (GTreeNode      *node,
  65.                              GCompareFunc    compare,
  66.                              gpointer        key);
  67. static gint       g_tree_node_count                 (GTreeNode      *node);
  68. static gint       g_tree_node_pre_order             (GTreeNode      *node,
  69.                              GTraverseFunc   traverse_func,
  70.                              gpointer        data);
  71. static gint       g_tree_node_in_order              (GTreeNode      *node,
  72.                              GTraverseFunc   traverse_func,
  73.                              gpointer        data);
  74. static gint       g_tree_node_post_order            (GTreeNode      *node,
  75.                              GTraverseFunc   traverse_func,
  76.                              gpointer        data);
  77. static gpointer   g_tree_node_search                (GTreeNode      *node,
  78.                              GSearchFunc     search_func,
  79.                              gpointer        data);
  80. static gint       g_tree_node_height                (GTreeNode      *node);
  81. static GTreeNode* g_tree_node_rotate_left           (GTreeNode      *node);
  82. static GTreeNode* g_tree_node_rotate_right          (GTreeNode      *node);
  83. static void       g_tree_node_check                 (GTreeNode      *node);
  84.  
  85.  
  86. G_LOCK_DECLARE_STATIC (g_tree_global);
  87. static GMemChunk *node_mem_chunk = NULL;
  88. static GTreeNode *node_free_list = NULL;
  89.  
  90.  
  91. static GTreeNode*
  92. g_tree_node_new (gpointer key,
  93.          gpointer value)
  94. {
  95.   GTreeNode *node;
  96.  
  97.   G_LOCK (g_tree_global);
  98.   if (node_free_list)
  99.     {
  100.       node = node_free_list;
  101.       node_free_list = node->right;
  102.     }
  103.   else
  104.     {
  105.       if (!node_mem_chunk)
  106.     node_mem_chunk = g_mem_chunk_new ("GLib GTreeNode mem chunk",
  107.                       sizeof (GTreeNode),
  108.                       1024,
  109.                       G_ALLOC_ONLY);
  110.  
  111.       node = g_chunk_new (GTreeNode, node_mem_chunk);
  112.    }
  113.   G_UNLOCK (g_tree_global);
  114.  
  115.   node->balance = 0;
  116.   node->left = NULL;
  117.   node->right = NULL;
  118.   node->key = key;
  119.   node->value = value;
  120.  
  121.   return node;
  122. }
  123.  
  124. static void
  125. g_tree_node_destroy (GTreeNode *node)
  126. {
  127.   if (node)
  128.     {
  129.       g_tree_node_destroy (node->right);
  130.       g_tree_node_destroy (node->left);
  131.       G_LOCK (g_tree_global);
  132.       node->right = node_free_list;
  133.       node_free_list = node;
  134.       G_UNLOCK (g_tree_global);
  135.    }
  136. }
  137.  
  138.  
  139. GTree*
  140. g_tree_new (GCompareFunc key_compare_func)
  141. {
  142.   GRealTree *rtree;
  143.  
  144.   g_return_val_if_fail (key_compare_func != NULL, NULL);
  145.  
  146.   rtree = g_new (GRealTree, 1);
  147.   rtree->root = NULL;
  148.   rtree->key_compare = key_compare_func;
  149.  
  150.   return (GTree*) rtree;
  151. }
  152.  
  153. void
  154. g_tree_destroy (GTree *tree)
  155. {
  156.   GRealTree *rtree;
  157.  
  158.   g_return_if_fail (tree != NULL);
  159.  
  160.   rtree = (GRealTree*) tree;
  161.  
  162.   g_tree_node_destroy (rtree->root);
  163.   g_free (rtree);
  164. }
  165.  
  166. void
  167. g_tree_insert (GTree    *tree,
  168.            gpointer  key,
  169.            gpointer  value)
  170. {
  171.   GRealTree *rtree;
  172.   gint inserted;
  173.  
  174.   g_return_if_fail (tree != NULL);
  175.  
  176.   rtree = (GRealTree*) tree;
  177.  
  178.   inserted = FALSE;
  179.   rtree->root = g_tree_node_insert (rtree->root, rtree->key_compare,
  180.                     key, value, &inserted);
  181. }
  182.  
  183. void
  184. g_tree_remove (GTree    *tree,
  185.            gpointer  key)
  186. {
  187.   GRealTree *rtree;
  188.  
  189.   g_return_if_fail (tree != NULL);
  190.  
  191.   rtree = (GRealTree*) tree;
  192.  
  193.   rtree->root = g_tree_node_remove (rtree->root, rtree->key_compare, key);
  194. }
  195.  
  196. gpointer
  197. g_tree_lookup (GTree    *tree,
  198.            gpointer  key)
  199. {
  200.   GRealTree *rtree;
  201.  
  202.   g_return_val_if_fail (tree != NULL, NULL);
  203.  
  204.   rtree = (GRealTree*) tree;
  205.  
  206.   return g_tree_node_lookup (rtree->root, rtree->key_compare, key);
  207. }
  208.  
  209. void
  210. g_tree_traverse (GTree         *tree,
  211.          GTraverseFunc  traverse_func,
  212.          GTraverseType  traverse_type,
  213.          gpointer       data)
  214. {
  215.   GRealTree *rtree;
  216.  
  217.   g_return_if_fail (tree != NULL);
  218.  
  219.   rtree = (GRealTree*) tree;
  220.  
  221.   g_return_if_fail (rtree->root != NULL);
  222.  
  223.   switch (traverse_type)
  224.     {
  225.     case G_PRE_ORDER:
  226.       g_tree_node_pre_order (rtree->root, traverse_func, data);
  227.       break;
  228.  
  229.     case G_IN_ORDER:
  230.       g_tree_node_in_order (rtree->root, traverse_func, data);
  231.       break;
  232.  
  233.     case G_POST_ORDER:
  234.       g_tree_node_post_order (rtree->root, traverse_func, data);
  235.       break;
  236.     
  237.     case G_LEVEL_ORDER:
  238.       g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
  239.       break;
  240.     }
  241. }
  242.  
  243. gpointer
  244. g_tree_search (GTree       *tree,
  245.            GSearchFunc  search_func,
  246.            gpointer     data)
  247. {
  248.   GRealTree *rtree;
  249.  
  250.   g_return_val_if_fail (tree != NULL, NULL);
  251.  
  252.   rtree = (GRealTree*) tree;
  253.  
  254.   if (rtree->root)
  255.     return g_tree_node_search (rtree->root, search_func, data);
  256.   return NULL;
  257. }
  258.  
  259. gint
  260. g_tree_height (GTree *tree)
  261. {
  262.   GRealTree *rtree;
  263.  
  264.   g_return_val_if_fail (tree != NULL, 0);
  265.  
  266.   rtree = (GRealTree*) tree;
  267.  
  268.   if (rtree->root)
  269.     return g_tree_node_height (rtree->root);
  270.   return 0;
  271. }
  272.  
  273. gint
  274. g_tree_nnodes (GTree *tree)
  275. {
  276.   GRealTree *rtree;
  277.  
  278.   g_return_val_if_fail (tree != NULL, 0);
  279.  
  280.   rtree = (GRealTree*) tree;
  281.  
  282.   if (rtree->root)
  283.     return g_tree_node_count (rtree->root);
  284.   return 0;
  285. }
  286.  
  287. static GTreeNode*
  288. g_tree_node_insert (GTreeNode    *node,
  289.             GCompareFunc  compare,
  290.             gpointer      key,
  291.             gpointer      value,
  292.             gint         *inserted)
  293. {
  294.   gint old_balance;
  295.   gint cmp;
  296.  
  297.   if (!node)
  298.     {
  299.       *inserted = TRUE;
  300.       return g_tree_node_new (key, value);
  301.     }
  302.  
  303.   cmp = (* compare) (key, node->key);
  304.   if (cmp == 0)
  305.     {
  306.       *inserted = FALSE;
  307.       node->value = value;
  308.       return node;
  309.     }
  310.  
  311.   if (cmp < 0)
  312.     {
  313.       if (node->left)
  314.     {
  315.       old_balance = node->left->balance;
  316.       node->left = g_tree_node_insert (node->left, compare, key, value, inserted);
  317.  
  318.       if ((old_balance != node->left->balance) && node->left->balance)
  319.         node->balance -= 1;
  320.     }
  321.       else
  322.     {
  323.       *inserted = TRUE;
  324.       node->left = g_tree_node_new (key, value);
  325.       node->balance -= 1;
  326.     }
  327.     }
  328.   else if (cmp > 0)
  329.     {
  330.       if (node->right)
  331.     {
  332.       old_balance = node->right->balance;
  333.       node->right = g_tree_node_insert (node->right, compare, key, value, inserted);
  334.  
  335.       if ((old_balance != node->right->balance) && node->right->balance)
  336.         node->balance += 1;
  337.     }
  338.       else
  339.     {
  340.       *inserted = TRUE;
  341.       node->right = g_tree_node_new (key, value);
  342.       node->balance += 1;
  343.     }
  344.     }
  345.  
  346.   if (*inserted)
  347.     {
  348.       if ((node->balance < -1) || (node->balance > 1))
  349.     node = g_tree_node_balance (node);
  350.     }
  351.  
  352.   return node;
  353. }
  354.  
  355. static GTreeNode*
  356. g_tree_node_remove (GTreeNode    *node,
  357.             GCompareFunc  compare,
  358.             gpointer      key)
  359. {
  360.   GTreeNode *new_root;
  361.   gint old_balance;
  362.   gint cmp;
  363.  
  364.   if (!node)
  365.     return NULL;
  366.  
  367.   cmp = (* compare) (key, node->key);
  368.   if (cmp == 0)
  369.     {
  370.       GTreeNode *garbage;
  371.  
  372.       garbage = node;
  373.  
  374.       if (!node->right)
  375.     {
  376.       node = node->left;
  377.     }
  378.       else
  379.     {
  380.       old_balance = node->right->balance;
  381.       node->right = g_tree_node_remove_leftmost (node->right, &new_root);
  382.       new_root->left = node->left;
  383.       new_root->right = node->right;
  384.       new_root->balance = node->balance;
  385.       node = g_tree_node_restore_right_balance (new_root, old_balance);
  386.     }
  387.  
  388.       G_LOCK (g_tree_global);
  389.       garbage->right = node_free_list;
  390.       node_free_list = garbage;
  391.       G_UNLOCK (g_tree_global);
  392.    }
  393.   else if (cmp < 0)
  394.     {
  395.       if (node->left)
  396.     {
  397.       old_balance = node->left->balance;
  398.       node->left = g_tree_node_remove (node->left, compare, key);
  399.       node = g_tree_node_restore_left_balance (node, old_balance);
  400.     }
  401.     }
  402.   else if (cmp > 0)
  403.     {
  404.       if (node->right)
  405.     {
  406.       old_balance = node->right->balance;
  407.       node->right = g_tree_node_remove (node->right, compare, key);
  408.       node = g_tree_node_restore_right_balance (node, old_balance);
  409.     }
  410.     }
  411.  
  412.   return node;
  413. }
  414.  
  415. static GTreeNode*
  416. g_tree_node_balance (GTreeNode *node)
  417. {
  418.   if (node->balance < -1)
  419.     {
  420.       if (node->left->balance > 0)
  421.     node->left = g_tree_node_rotate_left (node->left);
  422.       node = g_tree_node_rotate_right (node);
  423.     }
  424.   else if (node->balance > 1)
  425.     {
  426.       if (node->right->balance < 0)
  427.     node->right = g_tree_node_rotate_right (node->right);
  428.       node = g_tree_node_rotate_left (node);
  429.     }
  430.  
  431.   return node;
  432. }
  433.  
  434. static GTreeNode*
  435. g_tree_node_remove_leftmost (GTreeNode  *node,
  436.                  GTreeNode **leftmost)
  437. {
  438.   gint old_balance;
  439.  
  440.   if (!node->left)
  441.     {
  442.       *leftmost = node;
  443.       return node->right;
  444.     }
  445.  
  446.   old_balance = node->left->balance;
  447.   node->left = g_tree_node_remove_leftmost (node->left, leftmost);
  448.   return g_tree_node_restore_left_balance (node, old_balance);
  449. }
  450.  
  451. static GTreeNode*
  452. g_tree_node_restore_left_balance (GTreeNode *node,
  453.                   gint       old_balance)
  454. {
  455.   if (!node->left)
  456.     node->balance += 1;
  457.   else if ((node->left->balance != old_balance) &&
  458.        (node->left->balance == 0))
  459.     node->balance += 1;
  460.  
  461.   if (node->balance > 1)
  462.     return g_tree_node_balance (node);
  463.   return node;
  464. }
  465.  
  466. static GTreeNode*
  467. g_tree_node_restore_right_balance (GTreeNode *node,
  468.                    gint       old_balance)
  469. {
  470.   if (!node->right)
  471.     node->balance -= 1;
  472.   else if ((node->right->balance != old_balance) &&
  473.        (node->right->balance == 0))
  474.     node->balance -= 1;
  475.  
  476.   if (node->balance < -1)
  477.     return g_tree_node_balance (node);
  478.   return node;
  479. }
  480.  
  481. static gpointer
  482. g_tree_node_lookup (GTreeNode    *node,
  483.             GCompareFunc  compare,
  484.             gpointer      key)
  485. {
  486.   gint cmp;
  487.  
  488.   if (!node)
  489.     return NULL;
  490.  
  491.   cmp = (* compare) (key, node->key);
  492.   if (cmp == 0)
  493.     return node->value;
  494.  
  495.   if (cmp < 0)
  496.     {
  497.       if (node->left)
  498.     return g_tree_node_lookup (node->left, compare, key);
  499.     }
  500.   else if (cmp > 0)
  501.     {
  502.       if (node->right)
  503.     return g_tree_node_lookup (node->right, compare, key);
  504.     }
  505.  
  506.   return NULL;
  507. }
  508.  
  509. static gint
  510. g_tree_node_count (GTreeNode *node)
  511. {
  512.   gint count;
  513.  
  514.   count = 1;
  515.   if (node->left)
  516.     count += g_tree_node_count (node->left);
  517.   if (node->right)
  518.     count += g_tree_node_count (node->right);
  519.  
  520.   return count;
  521. }
  522.  
  523. static gint
  524. g_tree_node_pre_order (GTreeNode     *node,
  525.                GTraverseFunc  traverse_func,
  526.                gpointer       data)
  527. {
  528.   if ((*traverse_func) (node->key, node->value, data))
  529.     return TRUE;
  530.   if (node->left)
  531.     {
  532.       if (g_tree_node_pre_order (node->left, traverse_func, data))
  533.     return TRUE;
  534.     }
  535.   if (node->right)
  536.     {
  537.       if (g_tree_node_pre_order (node->right, traverse_func, data))
  538.     return TRUE;
  539.     }
  540.  
  541.   return FALSE;
  542. }
  543.  
  544. static gint
  545. g_tree_node_in_order (GTreeNode     *node,
  546.               GTraverseFunc  traverse_func,
  547.               gpointer       data)
  548. {
  549.   if (node->left)
  550.     {
  551.       if (g_tree_node_in_order (node->left, traverse_func, data))
  552.     return TRUE;
  553.     }
  554.   if ((*traverse_func) (node->key, node->value, data))
  555.     return TRUE;
  556.   if (node->right)
  557.     {
  558.       if (g_tree_node_in_order (node->right, traverse_func, data))
  559.     return TRUE;
  560.     }
  561.  
  562.   return FALSE;
  563. }
  564.  
  565. static gint
  566. g_tree_node_post_order (GTreeNode     *node,
  567.             GTraverseFunc  traverse_func,
  568.             gpointer       data)
  569. {
  570.   if (node->left)
  571.     {
  572.       if (g_tree_node_post_order (node->left, traverse_func, data))
  573.     return TRUE;
  574.     }
  575.   if (node->right)
  576.     {
  577.       if (g_tree_node_post_order (node->right, traverse_func, data))
  578.     return TRUE;
  579.     }
  580.   if ((*traverse_func) (node->key, node->value, data))
  581.     return TRUE;
  582.  
  583.   return FALSE;
  584. }
  585.  
  586. static gpointer
  587. g_tree_node_search (GTreeNode   *node,
  588.             GSearchFunc  search_func,
  589.             gpointer     data)
  590. {
  591.   gint dir;
  592.  
  593.   if (!node)
  594.     return NULL;
  595.  
  596.   do {
  597.     dir = (* search_func) (node->key, data);
  598.     if (dir == 0)
  599.       return node->value;
  600.  
  601.     if (dir < 0)
  602.       node = node->left;
  603.     else if (dir > 0)
  604.       node = node->right;
  605.   } while (node && (dir != 0));
  606.  
  607.   return NULL;
  608. }
  609.  
  610. static gint
  611. g_tree_node_height (GTreeNode *node)
  612. {
  613.   gint left_height;
  614.   gint right_height;
  615.  
  616.   if (node)
  617.     {
  618.       left_height = 0;
  619.       right_height = 0;
  620.  
  621.       if (node->left)
  622.     left_height = g_tree_node_height (node->left);
  623.  
  624.       if (node->right)
  625.     right_height = g_tree_node_height (node->right);
  626.  
  627.       return MAX (left_height, right_height) + 1;
  628.     }
  629.  
  630.   return 0;
  631. }
  632.  
  633. static GTreeNode*
  634. g_tree_node_rotate_left (GTreeNode *node)
  635. {
  636.   GTreeNode *left;
  637.   GTreeNode *right;
  638.   gint a_bal;
  639.   gint b_bal;
  640.  
  641.   left = node->left;
  642.   right = node->right;
  643.  
  644.   node->right = right->left;
  645.   right->left = node;
  646.  
  647.   a_bal = node->balance;
  648.   b_bal = right->balance;
  649.  
  650.   if (b_bal <= 0)
  651.     {
  652.       if (a_bal >= 1)
  653.     right->balance = b_bal - 1;
  654.       else
  655.     right->balance = a_bal + b_bal - 2;
  656.       node->balance = a_bal - 1;
  657.     }
  658.   else
  659.     {
  660.       if (a_bal <= b_bal)
  661.     right->balance = a_bal - 2;
  662.       else
  663.     right->balance = b_bal - 1;
  664.       node->balance = a_bal - b_bal - 1;
  665.     }
  666.  
  667.   return right;
  668. }
  669.  
  670. static GTreeNode*
  671. g_tree_node_rotate_right (GTreeNode *node)
  672. {
  673.   GTreeNode *left;
  674.   GTreeNode *right;
  675.   gint a_bal;
  676.   gint b_bal;
  677.  
  678.   left = node->left;
  679.   right = node->right;
  680.  
  681.   node->left = left->right;
  682.   left->right = node;
  683.  
  684.   a_bal = node->balance;
  685.   b_bal = left->balance;
  686.  
  687.   if (b_bal <= 0)
  688.     {
  689.       if (b_bal > a_bal)
  690.     left->balance = b_bal + 1;
  691.       else
  692.     left->balance = a_bal + 2;
  693.       node->balance = a_bal - b_bal + 1;
  694.     }
  695.   else
  696.     {
  697.       if (a_bal <= -1)
  698.     left->balance = b_bal + 1;
  699.       else
  700.     left->balance = a_bal + b_bal + 2;
  701.       node->balance = a_bal + 1;
  702.     }
  703.  
  704.   return left;
  705. }
  706.  
  707. static void
  708. g_tree_node_check (GTreeNode *node)
  709. {
  710.   gint left_height;
  711.   gint right_height;
  712.   gint balance;
  713.   
  714.   if (node)
  715.     {
  716.       left_height = 0;
  717.       right_height = 0;
  718.       
  719.       if (node->left)
  720.     left_height = g_tree_node_height (node->left);
  721.       if (node->right)
  722.     right_height = g_tree_node_height (node->right);
  723.       
  724.       balance = right_height - left_height;
  725.       if (balance != node->balance)
  726.     g_log (g_log_domain_glib, G_LOG_LEVEL_INFO,
  727.            "g_tree_node_check: failed: %d ( %d )\n",
  728.            balance, node->balance);
  729.       
  730.       if (node->left)
  731.     g_tree_node_check (node->left);
  732.       if (node->right)
  733.     g_tree_node_check (node->right);
  734.     }
  735. }
  736.