123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743 |
- /*
- * This program is free software: you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation, either version 3 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program. If not, see <http://www.gnu.org/licenses/>.
- *
- * SPDX-License-Identifier: GPL-3.0+
- * License-Filename: LICENSE
- *
- */
- #ifdef HAVE_CONFIG_H
- #include "config.h"
- #endif
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include "splay-tree.h"
- /* forward decl. */
- static struct splay_tree_node_n *splay (splay_tree sp, splay_tree_key key);
- /* delete whole sp tree */
- splay_tree
- splay_tree_delete (splay_tree sp)
- {
- splay_tree_node spn = (splay_tree_node) 0;
- splay_tree_node spn2 = (splay_tree_node) 0;
- if (sp == (splay_tree) 0)
- {
- return ((splay_tree) 0);
- }
- /* if there is data */
- if (sp->root)
- {
- /* for every node, this does not cause stack smashing */
- spn = splay_tree_min (sp);
- while (spn)
- {
- spn2 = splay_tree_successor (sp, spn->key);
- splay_tree_remove (sp, spn->key);
- spn = spn2;
- }
- }
- /* wipe the pointers in the struct to make valgrind happy */
- sp->root = (splay_tree_node) 0;
- /* The comparision function. */
- sp->comp = (splay_tree_compare_fn) 0;
- /* The deallocate-key function. NULL if no cleanup is necessary. */
- sp->delete_key = (splay_tree_delete_key_fn) 0;
- /* The deallocate-value function. NULL if no cleanup is necessary. */
- sp->delete_value = (splay_tree_delete_value_fn) 0;
- free ((void *) sp);
- return ((splay_tree) 0);
- }
- /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
- DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
- values. */
- splay_tree
- splay_tree_new (splay_tree_compare_fn compare_fn,
- splay_tree_delete_key_fn delete_key_fn,
- splay_tree_delete_value_fn delete_value_fn)
- {
- splay_tree sp = (splay_tree) 0;
- /* there must be a compare function, the free() functions are optional */
- if (compare_fn == (splay_tree_compare_fn) 0)
- {
- return ((splay_tree) 0);
- }
- sp = (splay_tree) calloc (1, sizeof (struct splay_tree_t));
- if (sp == (splay_tree) 0)
- {
- return ((splay_tree) 0);
- }
- /* set root node to use and the functions */
- sp->root = (splay_tree_node) 0;
- sp->comp = compare_fn;
- sp->delete_key = delete_key_fn;
- sp->delete_value = delete_value_fn;
- return ((splay_tree) sp);
- }
- /* Insert a new node (associating KEY with DATA) into SP. If a
- previous node with the indicated KEY exists, its data is not replaced
- with the new value. */
- void
- splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value)
- {
- splay_tree_node spn = (splay_tree_node) 0;
- int comparison = 0;
- if (sp == (splay_tree) 0)
- {
- /* no tree */
- return;
- }
- spn = splay_tree_lookup (sp, key);
- if (spn != (splay_tree_node) 0)
- {
- /* did already exist */
- return;
- }
- /* Create a new node, and insert it at the root. */
- spn = (splay_tree_node) calloc (1, sizeof (struct splay_tree_node_n));
- if (spn == (splay_tree_node) 0)
- {
- /* shouldnothappen */
- return;
- }
- /* set node data */
- spn->key = key;
- spn->value = value;
- if (sp->root == (splay_tree_node) 0)
- {
- /* first entry */
- sp->root = spn;
- return;
- }
- /* add in tree */
- comparison = (*sp->comp) (sp->root->key, key);
- if (comparison < 0)
- {
- spn->left = sp->root;
- spn->right = spn->left->right;
- spn->left->right = (splay_tree_node) 0;
- }
- else
- {
- /* > or == */
- spn->right = sp->root;
- spn->left = spn->right->left;
- spn->right->left = (splay_tree_node) 0;
- }
- sp->root = spn;
- return;
- }
- /* insert and allow duplicates of key */
- void
- splay_tree_insert_duplicates (splay_tree sp, splay_tree_key key,
- splay_tree_value value)
- {
- if (sp == (splay_tree) 0)
- {
- /* no tree */
- return;
- }
- splay_tree_insert (sp, key, value);
- return;
- }
- /* Remove KEY from SP. It is not an error if it did not exist. */
- void
- splay_tree_remove (splay_tree sp, splay_tree_key key)
- {
- splay_tree_node spn = (splay_tree_node) 0;
- splay_tree_node node = (splay_tree_node) 0;
- splay_tree_node left = (splay_tree_node) 0;
- splay_tree_node right = (splay_tree_node) 0;
- if (sp == (splay_tree) 0)
- {
- /* no tree */
- return;
- }
- if (sp->root == (splay_tree_node) 0)
- {
- /* no data */
- return;
- }
- spn = splay_tree_lookup (sp, key);
- if (spn == (splay_tree_node) 0)
- {
- return;
- }
- /* found entry to delete now in spn */
- node = sp->root;
- left = sp->root->left;
- right = sp->root->right;
- /* One of the children is now the root. Doesn't matter much
- which, so long as we preserve the properties of the tree. */
- if (left)
- {
- sp->root = left;
- /* If there was a right child as well, hang it off the
- right-most leaf of the left child. */
- if (right)
- {
- while (left->right)
- {
- left = left->right;
- }
- left->right = right;
- }
- }
- else
- {
- sp->root = right;
- }
- /* free() key if needed */
- if (sp->delete_key)
- {
- /* avoid free(0) */
- if (node->key)
- {
- (*sp->delete_key) (node->key);
- }
- node->key = (splay_tree_key) 0;
- }
- /* free() value if needed */
- if (sp->delete_value)
- {
- /* avoid free(0) */
- if (node->value)
- {
- (*sp->delete_value) (node->value);
- }
- node->value = (splay_tree_value) 0;
- }
- /* free() node itself and wipe the pointers */
- node->left = (splay_tree_node) 0;
- node->right = (splay_tree_node) 0;
- free ((void *) node);
- return;
- }
- /* Lookup KEY in SP, returning VALUE if present, and NULL
- otherwise. */
- splay_tree_node
- splay_tree_lookup (splay_tree sp, splay_tree_key key)
- {
- splay_tree_node spn = (splay_tree_node) 0;
- if (sp == (splay_tree) 0)
- {
- /* no tree */
- return ((splay_tree_node) 0);
- }
- if (sp->root == (splay_tree_node) 0)
- {
- /* no data */
- return ((splay_tree_node) 0);
- }
- if ((*sp->comp) (sp->root->key, key) == 0)
- {
- /* found */
- return ((splay_tree_node) sp->root);
- }
- spn = splay (sp, key);
- if (spn)
- {
- if ((*sp->comp) (sp->root->key, key) == 0)
- {
- /* found */
- return ((splay_tree_node) sp->root);
- }
- }
- /* not found */
- return ((splay_tree_node) 0);
- }
- /* Call FN, passing it the DATA, for every node in SP, following an
- in-order traversal. If FN every returns a non-zero value, the
- iteration ceases immediately, and the value is returned.
- Otherwise, this function returns 0.
- */
- int
- splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data)
- {
- splay_tree_node spn = (splay_tree_node) 0;
- splay_tree_key spnkey = (splay_tree_key) 0;
- int status = 0;
- /* <nil> splaytree */
- if (sp == (splay_tree) 0)
- {
- return (0);
- }
- /* no data */
- if (sp->root == (splay_tree_node) 0)
- {
- return (0);
- }
- /* no routine() to run */
- if (fn == (splay_tree_foreach_fn) 0)
- {
- return (0);
- }
- /* */
- status = 0;
- spn = splay_tree_min (sp);
- while (spn)
- {
- /* save key if spn disappears */
- spnkey = spn->key;
- status = (*fn) (spn, data);
- if (status)
- {
- break;
- }
- spn = splay_tree_successor (sp, spnkey);
- }
- /* set if callback() routine set it otherwise 0 */
- return (status);
- }
- /* Return the node in SP with the smallest key. */
- splay_tree_node
- splay_tree_min (splay_tree sp)
- {
- splay_tree_node n = (splay_tree_node) 0;
- /* <nil> splaytree */
- if (sp == (splay_tree) 0)
- {
- return ((splay_tree_node) 0);
- }
- /* no data */
- if (sp->root == (splay_tree_node) 0)
- {
- return ((splay_tree_node) 0);
- }
- n = sp->root;
- /* scan l */
- while (n->left)
- {
- n = n->left;
- }
- return ((splay_tree_node) n);
- }
- /* Return the node in SP with the highest key. */
- splay_tree_node
- splay_tree_max (splay_tree sp)
- {
- splay_tree_node n = (splay_tree_node) 0;
- /* <nil> splaytree */
- if (sp == (splay_tree) 0)
- {
- return ((splay_tree_node) 0);
- }
- /* no data */
- if (sp->root == (splay_tree_node) 0)
- {
- return ((splay_tree_node) 0);
- }
- n = sp->root;
- /* scan l */
- while (n->right)
- {
- n = n->right;
- }
- return ((splay_tree_node) n);
- }
- /* return 1 if splay tree has data, otherwise 0 */
- int
- splay_tree_has_data (splay_tree sp)
- {
- if (sp == (splay_tree) 0)
- {
- return (0);
- }
- if (sp->root)
- {
- return (1);
- }
- else
- {
- return (0);
- }
- }
- /* Return the immediate successor KEY, or NULL if there is no
- successor. KEY need not be present in the tree. */
- splay_tree_node
- splay_tree_successor (splay_tree sp, splay_tree_key key)
- {
- int comparison = 0;
- splay_tree_node node = (splay_tree_node) 0;
- if (sp == (splay_tree) 0)
- {
- /* no tree */
- return ((splay_tree_node) 0);
- }
- /* If the tree is empty, there is certainly no successor. */
- if (sp->root == (splay_tree_node) 0)
- {
- return ((splay_tree_node) 0);
- }
- /* Splay the tree around KEY. That will leave either the KEY
- itself, its predecessor, or its successor at the root. */
- node = splay (sp, key);
- if (node == (splay_tree_node) 0)
- {
- return ((splay_tree_node) 0);
- }
- /* */
- comparison = (*sp->comp) (sp->root->key, key);
- /* If the successor is at the root, just return it. */
- if (comparison > 0)
- {
- return ((splay_tree_node) sp->root);
- }
- /* Otherwise, find the leftmost element of the right subtree. */
- node = sp->root->right;
- if (node)
- {
- while (node->left)
- {
- node = node->left;
- }
- }
- return ((splay_tree_node) node);
- }
- /* free() wrappers to free key/value */
- void
- splay_tree_free_value (splay_tree_value value)
- {
- if (value)
- {
- free ((void *) value);
- }
- return;
- }
- void
- splay_tree_free_key (splay_tree_key key)
- {
- if (key)
- {
- free ((void *) key);
- }
- return;
- }
- /* Splay-tree comparison function, treating the keys as ints. */
- int
- splay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2)
- {
- if ((int) k1 < (int) k2)
- {
- return ((int) -1);
- }
- else if ((int) k1 > (int) k2)
- {
- return (1);
- }
- else
- {
- return (0);
- }
- }
- /* Splay-tree comparison function, treating the keys as pointers.
- Note this is possibly not portable on all systems according to standards
- and may have undefined results. there seems no good solution for this.
- (a char datatype does not have to be a single byte in c for example)
- */
- int
- splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2)
- {
- /* 0==0 */
- if ((k1 == (splay_tree_key) 0) && (k2 == (splay_tree_key) 0))
- {
- return (0);
- }
- /* possible undefined results at this, says the c standard. has to be understood as (signed char *) */
- if ((char *) k1 < (char *) k2)
- {
- return ((int) -1);
- }
- else if ((char *) k1 > (char *) k2)
- {
- return (1);
- }
- else
- {
- return (0);
- }
- }
- /* Comparison function for a splay tree in which the keys are strings.
- K1 and K2 have the dynamic type "const char *". Returns <0, 0, or
- >0 to indicate whether K1 is less than, equal to, or greater than
- K2, respectively.
- similar issues here when as compare pointers and c portable src.
- */
- int
- splay_tree_compare_strings (splay_tree_key k1, splay_tree_key k2)
- {
- const char *s1 = (const char *) k1;
- const char *s2 = (const char *) k2;
- int ret = 0;
- if ((k1 == (splay_tree_key) 0) && (k2 == (splay_tree_key) 0))
- {
- return (0);
- }
- if (s1 == (const char *) 0)
- {
- /* to avoid crashes only */
- return (0);
- }
- if (s2 == (const char *) 0)
- {
- /* to avoid crashes only */
- return (0);
- }
- /* check if same pointer. possible not portable c. */
- if (s1 == s2)
- {
- return (0);
- }
- ret = strcmp (s1, s2);
- return ((int) ret);
- }
- /* */
- static struct splay_tree_node_n *
- splay (splay_tree sp, splay_tree_key key)
- {
- struct splay_tree_node_n *t = (struct splay_tree_node_n *) 0;
- struct splay_tree_node_n *l = (struct splay_tree_node_n *) 0;
- struct splay_tree_node_n *r = (struct splay_tree_node_n *) 0;
- struct splay_tree_node_n *y = (struct splay_tree_node_n *) 0;
- int comparevalue = 0;
- int comparevalue2 = 0;
- struct splay_tree_node_n tmp = {
- /* The key. */
- (splay_tree_key) 0,
- /* The value. */
- (splay_tree_value) 0,
- /* The left and right children, respectively. */
- (struct splay_tree_node_n *) 0, /* left */
- (struct splay_tree_node_n *) 0 /* right */
- };
- /* no tree */
- if (sp == (splay_tree) 0)
- {
- return ((struct splay_tree_node_n *) 0);
- }
- /* no data in root. return 0 */
- if (sp->root == (struct splay_tree_node_n *) 0)
- {
- return ((struct splay_tree_node_n *) 0);
- }
- /* current root */
- t = sp->root;
- tmp.left = (struct splay_tree_node_n *) 0;
- tmp.right = (struct splay_tree_node_n *) 0;
- l = &tmp;
- r = &tmp;
- labelstart:
- /* */
- comparevalue = (*sp->comp) (key, t->key);
- if (comparevalue < 0)
- {
- if (t->left == (struct splay_tree_node_n *) 0)
- {
- goto labelend;
- }
- /* */
- comparevalue2 = (*sp->comp) (key, t->left->key);
- if (comparevalue2 < 0)
- {
- y = t->left;
- t->left = y->right;
- y->right = t;
- t = y;
- if (t->left == (struct splay_tree_node_n *) 0)
- {
- goto labelend;
- }
- }
- /* */
- r->left = t;
- r = t;
- t = t->left;
- }
- else if (comparevalue > 0)
- {
- if (t->right == (struct splay_tree_node_n *) 0)
- {
- goto labelend;
- }
- /* */
- comparevalue2 = (*sp->comp) (key, t->right->key);
- if (comparevalue2 > 0)
- {
- /* */
- y = t->right;
- t->right = y->left;
- y->left = t;
- t = y;
- if (t->right == (struct splay_tree_node_n *) 0)
- {
- goto labelend;
- }
- }
- /* */
- l->right = t;
- l = t;
- t = t->right;
- }
- else
- {
- /* here if (comparevalue == 0) */
- goto labelend;
- }
- goto labelstart;
- labelend:
- l->right = t->left;
- r->left = t->right;
- t->left = tmp.right;
- t->right = tmp.left;
- sp->root = t;
- return ((struct splay_tree_node_n *) t);
- }
- /* end */
|