"Fossies" - the Fresh Open Source Software Archive

Member "gretl-2020e/lib/src/gretl_btree.c" (29 Aug 2019, 8318 Bytes) of package /linux/misc/gretl-2020e.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "gretl_btree.c" see the Fossies "Dox" file reference documentation.

    1 /*
    2  *  gretl -- Gnu Regression, Econometrics and Time-series Library
    3  *  Copyright (C) 2001 Allin Cottrell and Riccardo "Jack" Lucchetti
    4  *
    5  *  This program is free software: you can redistribute it and/or modify
    6  *  it under the terms of the GNU General Public License as published by
    7  *  the Free Software Foundation, either version 3 of the License, or
    8  *  (at your option) any later version.
    9  *
   10  *  This program is distributed in the hope that it will be useful,
   11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   13  *  GNU General Public License for more details.
   14  *
   15  *  You should have received a copy of the GNU General Public License
   16  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
   17  *
   18  */
   19 
   20 /* The code here is a simplified version of GLib's GTree, modified
   21    such that we can use doubles for key and value rather than
   22    pointers; this gives us a means of setting up fast lookup for
   23    the hansl replace() function as applied to series or matrices.
   24    See glib/gtree.c at https://github.com/GNOME/glib for the
   25    original code, which is under the GNU Lesser General Public
   26    License, version 2.1 or higher.
   27 
   28    We could have used the unmodified GTree API (replacing the
   29    doubles by pointers-to-doubles) but it turns out that this
   30    simplified version is a good deal faster for the purpose.
   31 */
   32 
   33 #include <glib.h>
   34 #include <math.h>
   35 #include "gretl_btree.h"
   36 
   37 #define MAX_BTREE_HEIGHT 40
   38 
   39 typedef struct _BTreeNode  BTreeNode;
   40 
   41 struct _BTree {
   42     BTreeNode *root;
   43     guint nnodes;
   44 };
   45 
   46 struct _BTreeNode {
   47     gdouble key;        /* key for this node */
   48     gdouble value;      /* value stored at this node */
   49     BTreeNode *left;    /* left subtree */
   50     BTreeNode *right;   /* right subtree */
   51     gint8 balance;      /* height (right) - height (left) */
   52     guint8 left_child;
   53     guint8 right_child;
   54 };
   55 
   56 static BTreeNode *btree_node_rotate_left (BTreeNode *node);
   57 static BTreeNode *btree_node_rotate_right (BTreeNode *node);
   58 
   59 static BTreeNode *btree_node_new (gdouble key,
   60                   gdouble value)
   61 {
   62     BTreeNode *node = g_slice_new(BTreeNode);
   63 
   64     node->balance = 0;
   65     node->left = NULL;
   66     node->right = NULL;
   67     node->left_child = FALSE;
   68     node->right_child = FALSE;
   69     node->key = key;
   70     node->value = value;
   71 
   72     return node;
   73 }
   74 
   75 static gint key_compare (gdouble a, gdouble b)
   76 {
   77     /* Handle NaNs in matrices? Let NaN be "bigger" than
   78        anything else, and in this context let it compare
   79        equal to itself.
   80     */
   81     if (isnan(a)) {
   82     return isnan(b) ? 0 : 1;
   83     } else if (isnan(b)) {
   84     return -1;
   85     }
   86 
   87     return a - b > 0 ? 1 : a == b ? 0 : -1;
   88 }
   89 
   90 BTree *gretl_btree_new (void)
   91 {
   92     BTree *tree = g_slice_new(BTree);
   93 
   94     tree->root = NULL;
   95     tree->nnodes = 0;
   96 
   97     return tree;
   98 }
   99 
  100 static inline BTreeNode *btree_first_node (BTree *tree)
  101 {
  102     BTreeNode *tmp;
  103 
  104     if (!tree->root) {
  105     return NULL;
  106     }
  107 
  108     tmp = tree->root;
  109 
  110     while (tmp->left_child) {
  111     tmp = tmp->left;
  112     }
  113 
  114     return tmp;
  115 }
  116 
  117 static inline BTreeNode *btree_node_previous (BTreeNode *node)
  118 {
  119     BTreeNode *tmp = node->left;
  120 
  121     if (node->left_child) {
  122     while (tmp->right_child) {
  123         tmp = tmp->right;
  124     }
  125     }
  126 
  127     return tmp;
  128 }
  129 
  130 static inline BTreeNode *btree_node_next (BTreeNode *node)
  131 {
  132     BTreeNode *tmp = node->right;
  133 
  134     if (node->right_child) {
  135     while (tmp->left_child) {
  136         tmp = tmp->left;
  137     }
  138     }
  139 
  140     return tmp;
  141 }
  142 
  143 static void btree_remove_all (BTree *tree)
  144 {
  145     BTreeNode *node, *next;
  146 
  147     g_return_if_fail(tree != NULL);
  148 
  149     node = btree_first_node(tree);
  150 
  151     while (node) {
  152     next = btree_node_next(node);
  153     g_slice_free(BTreeNode, node);
  154     node = next;
  155     }
  156 
  157     tree->root = NULL;
  158     tree->nnodes = 0;
  159 }
  160 
  161 void gretl_btree_destroy (BTree *tree)
  162 {
  163     g_return_if_fail(tree != NULL);
  164 
  165     btree_remove_all(tree);
  166     g_slice_free(BTree, tree);
  167 }
  168 
  169 static BTreeNode *btree_node_balance (BTreeNode *node)
  170 {
  171     if (node->balance < -1) {
  172     if (node->left->balance > 0) {
  173         node->left = btree_node_rotate_left(node->left);
  174     }
  175     node = btree_node_rotate_right(node);
  176     } else if (node->balance > 1) {
  177     if (node->right->balance < 0) {
  178         node->right = btree_node_rotate_right(node->right);
  179     }
  180     node = btree_node_rotate_left(node);
  181     }
  182 
  183     return node;
  184 }
  185 
  186 void gretl_btree_insert (BTree *tree,
  187              gdouble key,
  188              gdouble value)
  189 {
  190     BTreeNode *node;
  191     BTreeNode *path[MAX_BTREE_HEIGHT];
  192     int idx;
  193 
  194     g_return_if_fail(tree != NULL);
  195 
  196     if (!tree->root) {
  197     tree->root = btree_node_new(key, value);
  198     tree->nnodes++;
  199     return;
  200     }
  201 
  202     idx = 0;
  203     path[idx++] = NULL;
  204     node = tree->root;
  205 
  206     while (1) {
  207     int cmp = key_compare(key, node->key);
  208 
  209     if (cmp == 0) {
  210         node->value = value;
  211         return;
  212     } else if (cmp < 0) {
  213         if (node->left_child) {
  214         path[idx++] = node;
  215         node = node->left;
  216         } else {
  217         BTreeNode *child = btree_node_new(key, value);
  218 
  219         child->left = node->left;
  220         child->right = node;
  221         node->left = child;
  222         node->left_child = TRUE;
  223         node->balance -= 1;
  224 
  225         tree->nnodes++;
  226         break;
  227         }
  228     } else {
  229         if (node->right_child) {
  230         path[idx++] = node;
  231         node = node->right;
  232         } else {
  233         BTreeNode *child = btree_node_new(key, value);
  234 
  235         child->right = node->right;
  236         child->left = node;
  237         node->right = child;
  238         node->right_child = TRUE;
  239         node->balance += 1;
  240 
  241         tree->nnodes++;
  242         break;
  243         }
  244     }
  245     }
  246 
  247     /* restore balance */
  248     while (1) {
  249     BTreeNode *bparent = path[--idx];
  250     gboolean left_node = (bparent && node == bparent->left);
  251 
  252     g_assert(!bparent || bparent->left == node || bparent->right == node);
  253 
  254     if (node->balance < -1 || node->balance > 1) {
  255         node = btree_node_balance (node);
  256         if (bparent == NULL) {
  257         tree->root = node;
  258         } else if (left_node) {
  259         bparent->left = node;
  260         } else {
  261         bparent->right = node;
  262         }
  263     }
  264 
  265     if (node->balance == 0 || bparent == NULL) {
  266         break;
  267     }
  268 
  269     if (left_node) {
  270         bparent->balance -= 1;
  271     } else {
  272         bparent->balance += 1;
  273     }
  274 
  275     node = bparent;
  276     }
  277 }
  278 
  279 static BTreeNode *btree_find_node (BTree *tree,
  280                    gdouble key)
  281 {
  282     BTreeNode *node = tree->root;
  283     gint cmp;
  284 
  285     if (!node) {
  286     return NULL;
  287     }
  288 
  289     while (1) {
  290     cmp = key_compare(key, node->key);
  291     if (cmp == 0) {
  292         return node;
  293     } else if (cmp < 0) {
  294         if (!node->left_child) {
  295         return NULL;
  296         }
  297         node = node->left;
  298         } else {
  299         if (!node->right_child) {
  300         return NULL;
  301         }
  302         node = node->right;
  303     }
  304     }
  305 }
  306 
  307 gdouble gretl_btree_lookup (BTree *tree,
  308                 gdouble key)
  309 {
  310     BTreeNode *node;
  311 
  312     g_return_val_if_fail(tree != NULL, key);
  313 
  314     node = btree_find_node(tree, key);
  315 
  316     return node ? node->value : key;
  317 }
  318 
  319 void gretl_btree_minmax (BTree *tree,
  320              gdouble *keymin,
  321              gdouble *keymax)
  322 {
  323     BTreeNode *L, *R;
  324 
  325     g_return_if_fail(tree != NULL);
  326 
  327     L = R = tree->root;
  328 
  329     while (L) {
  330     *keymin = L->key;
  331     L = L->left;
  332     }
  333 
  334     while (R) {
  335     *keymax = R->key;
  336     R = R->right;
  337     }
  338 }
  339 
  340 static BTreeNode *btree_node_rotate_left (BTreeNode *node)
  341 {
  342     BTreeNode *right;
  343     gint a_bal, b_bal;
  344 
  345     right = node->right;
  346 
  347     if (right->left_child) {
  348     node->right = right->left;
  349     } else {
  350     node->right_child = FALSE;
  351     right->left_child = TRUE;
  352     }
  353     right->left = node;
  354 
  355     a_bal = node->balance;
  356     b_bal = right->balance;
  357 
  358     if (b_bal <= 0) {
  359     if (a_bal >= 1) {
  360         right->balance = b_bal - 1;
  361     } else {
  362         right->balance = a_bal + b_bal - 2;
  363     }
  364     node->balance = a_bal - 1;
  365     } else {
  366     if (a_bal <= b_bal) {
  367         right->balance = a_bal - 2;
  368     } else {
  369         right->balance = b_bal - 1;
  370     }
  371     node->balance = a_bal - b_bal - 1;
  372     }
  373 
  374     return right;
  375 }
  376 
  377 static BTreeNode *btree_node_rotate_right (BTreeNode *node)
  378 {
  379     BTreeNode *left;
  380     gint a_bal, b_bal;
  381 
  382     left = node->left;
  383 
  384     if (left->right_child) {
  385     node->left = left->right;
  386     } else {
  387     node->left_child = FALSE;
  388     left->right_child = TRUE;
  389     }
  390     left->right = node;
  391 
  392     a_bal = node->balance;
  393     b_bal = left->balance;
  394 
  395     if (b_bal <= 0) {
  396     if (b_bal > a_bal) {
  397         left->balance = b_bal + 1;
  398     } else {
  399         left->balance = a_bal + 2;
  400     }
  401     node->balance = a_bal - b_bal + 1;
  402     } else {
  403     if (a_bal <= -1) {
  404         left->balance = b_bal + 1;
  405     } else {
  406         left->balance = a_bal + b_bal + 2;
  407     }
  408     node->balance = a_bal + 1;
  409     }
  410 
  411     return left;
  412 }