source: trunk/src/zAVLTree.c @ 481

Last change on this file since 481 was 481, checked in by katerina, 6 years ago

Enhancements and fixes for tickets #374, #375, #376, #377, #378, and #379.

File size: 14.4 KB
Line 
1/*
2 * zAVLTree.c: Source code for zAVLTrees.
3 * Copyright (C) 1998,2001  Michael H. Buselli
4 * This is version 0.1.3 (alpha).
5 * Generated from $Id: xAVLTree.c.sh,v 1.5 2001/06/07 06:58:28 cosine Exp $
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Library General Public
9 * License as published by the Free Software Foundation; either
10 * version 2 of the License, or (at your option) any later version.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15 * Library General Public License for more details.
16 *
17 * You should have received a copy of the GNU Library General Public
18 * License along with this library; if not, write to the Free
19 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
20 *
21 * The author of this library can be reached at the following address:
22 * Michael H. Buselli
23 * 30051 N. Waukegan Rd. Apt. 103
24 * Lake Bluff, IL  60044-5412
25 *
26 * Or you can send email to <cosine@cosine.org>.
27 * The official web page for this product is:
28 * http://www.cosine.org/project/AVLTree/
29 */
30
31#include <stdlib.h>
32#include <string.h>
33#include "zAVLTree.h"
34
35/* Interface for handling "string only" items rw 2014-06-26
36 */
37static zAVLKey zstring_key (void const * arg)
38{
39  return (zAVLKey) arg;
40}
41
42char * dummy_zfree_string;
43#ifdef __clang__
44char * dummy_zfree_str;
45#endif
46
47static void zfree_string (void * inptr)
48{
49#ifdef __clang__
50  dummy_zfree_str = (char *) inptr;
51#else
52  char * str = (char *) inptr;
53#endif
54
55  /* Take the address to circumvent gcc 4.9 optimizer bug */
56  dummy_zfree_string = (char *) &inptr;
57
58#ifdef __clang__
59  dummy_zfree_str[0] = '\0';
60  free (dummy_zfree_str);
61#else
62  str[0] = '\0';
63  free (inptr);
64#endif
65  return;
66}
67void zAVL_string_reset (zAVLTree * tree)
68{
69  if (tree)
70    zAVLFreeTree (tree, zfree_string);
71  return;
72}
73int zAVL_string_set (zAVLTree ** tree, const char * key)
74{
75  if (tree && key)
76    {
77      zAVLTree * itree = (*tree);
78      if (!itree)
79        {
80          itree = zAVLAllocTree (zstring_key, zAVL_KEY_STRING);
81          if (!itree) 
82            {
83              return -1;
84            }
85        }
86      *tree = itree;
87      return zAVLInsert (itree, strdup(key));
88    }
89  return -1;
90}
91char * zAVL_string_get (zAVLTree * tree, const char * key)
92{
93  /* zAVLSearch() checks for NULL tree
94   */
95  if (key)
96    {
97      return ((char *) zAVLSearch (tree, key));
98    }
99  return NULL;
100}
101void zAVL_string_del (zAVLTree * tree, const char * key)
102{
103  /* zAVLSearch() checks for NULL tree
104   */
105  if (key)
106    {
107      char * item = ((char *) zAVLSearch (tree, key));
108      if (item)
109        {
110          zAVLDelete(tree, key);
111          zfree_string(item);
112        }
113    }
114  return;
115}
116
117
118
119/* Wed Nov 23 17:57:42 CET 2005 rw: introduce third argument in
120 * zAVLCloseSearchNode() to avoid redundant strcmp
121 */
122static zAVLNode *zAVLCloseSearchNode (zAVLTree const *avltree, zAVLKey key,
123                                      int * ok);
124static void zAVLRebalanceNode (zAVLTree *avltree, zAVLNode *avlnode);
125static void zAVLFreeBranch (zAVLNode *avlnode, void (freeitem)(void *item));
126static void zAVLFillVacancy (zAVLTree *avltree,
127        zAVLNode *origparent, zAVLNode **superparent,
128        zAVLNode *left, zAVLNode *right);
129
130#define MAX(x, y)      ((x) > (y) ? (x) : (y))
131#define MIN(x, y)      ((x) < (y) ? (x) : (y))
132#define L_DEPTH(n)     ((n)->left ? (n)->left->depth : 0)
133#define R_DEPTH(n)     ((n)->right ? (n)->right->depth : 0)
134#define CALC_DEPTH(n)  (MAX(L_DEPTH(n), R_DEPTH(n)) + 1)
135
136#define ZAVL_OK 1
137#define ZAVL_NO 0
138
139/* The comparison function. Was a macro, but this allows for more
140 * flexibility (non-string keys). The key is a (void *) now, and
141 * the type is stored in the zAVLTree struct. Oct 21, 2011, rw
142 */
143static int zAVLKey_cmp(const zAVLTree * tree, zAVLKey a, zAVLKey b)
144{
145  if (tree->keytype == zAVL_KEY_STRING)
146    {
147      return (strcmp((const char*)a, (const char *)b));
148    }
149  else /* zAVL_KEY_INT */
150    {
151      const int x = *((const int *)a);
152      const int y = *((const int *)b);
153
154      if      (x > y) return  1;
155      else if (x < y) return -1;
156      else return 0;
157    }
158}
159
160/*
161 * AVLAllocTree:
162 * Allocate memory for a new AVL tree and set the getkey function for
163 * that tree.  The getkey function should take an item and return an
164 * AVLKey that is to be used for indexing this object in the AVL tree.
165 * On success, a pointer to the malloced AVLTree is returned.  If there
166 * was a malloc failure, then NULL is returned.
167 */
168zAVLTree *zAVLAllocTree (zAVLKey (*getkey)(void const *item), int keytype)
169{
170  zAVLTree *rc;
171
172  rc = calloc(1, sizeof(zAVLTree));
173  if (rc == NULL)
174    return NULL;
175
176  rc->top = NULL;
177  rc->count = 0;
178  rc->getkey = getkey;
179  rc->keytype = keytype;
180  return rc;
181}
182
183
184/*
185 * AVLFreeTree:
186 * Free all memory used by this AVL tree.  If freeitem is not NULL, then
187 * it is assumed to be a destructor for the items reference in the AVL
188 * tree, and they are deleted as well.
189 */
190void zAVLFreeTree (zAVLTree *avltree, void (freeitem)(void *item))
191{
192  if (NULL == avltree)  /* R.W. Mon Nov 19 21:15:44 CET 2001 */
193    return;
194  if (avltree->top)
195    zAVLFreeBranch(avltree->top, freeitem);
196  free(avltree);
197}
198
199
200/*
201 * AVLInsert:
202 * Create a new node and insert an item there.
203 *
204 * Returns  0 on success,
205 *         -1 on malloc failure,
206 *          3 if duplicate key.
207 */
208int zAVLInsert (zAVLTree *avltree, void *item)
209{
210  zAVLNode *newnode;
211  zAVLNode *node;
212  zAVLNode *balnode;
213  zAVLNode *nextbalnode;
214  int       ok;
215
216  newnode = calloc(1, sizeof(zAVLNode));
217  if (newnode == NULL)
218    return -1;
219
220  newnode->key = avltree->getkey(item);
221  newnode->item = item;
222  newnode->depth = 1;
223  newnode->left = NULL;
224  newnode->right = NULL;
225  newnode->parent = NULL;
226
227  if (avltree->top != NULL) {
228    node = zAVLCloseSearchNode(avltree, newnode->key, &ok);
229
230    if (ok == ZAVL_OK) { /* exists already */
231      free(newnode);
232      return 3;
233    }
234
235    newnode->parent = node;
236
237    if (zAVLKey_cmp(avltree, newnode->key, node->key) < 0) {
238      node->left = newnode;
239      node->depth = CALC_DEPTH(node);
240    }
241
242    else {
243      node->right = newnode;
244      node->depth = CALC_DEPTH(node);
245    }
246
247    for (balnode = node->parent; balnode; balnode = nextbalnode) {
248      nextbalnode = balnode->parent;
249      zAVLRebalanceNode(avltree, balnode);
250    }
251  }
252
253  else {
254    avltree->top = newnode;
255  }
256
257  avltree->count++;
258  return 0;
259}
260
261
262/*
263 * zAVLSearch:
264 * Return a pointer to the item with the given key in the AVL tree.  If
265 * no such item is in the tree, then NULL is returned.
266 */
267void *zAVLSearch (zAVLTree const *avltree, zAVLKey key)
268{
269  zAVLNode *node;
270  int       ok;
271
272  if (NULL == avltree)  /* R.W. Mon Nov 19 21:15:44 CET 2001 */
273    return NULL;
274
275  node = zAVLCloseSearchNode(avltree, key, &ok);
276
277  if (node && ok == ZAVL_OK)
278    return node->item;
279
280  return NULL;
281}
282
283
284/*
285 * zAVLDelete:
286 * Deletes the node with the given key.  Does not delete the item at
287 * that key.  Returns 0 on success and -1 if a node with the given key
288 * does not exist.
289 */
290int zAVLDelete (zAVLTree *avltree, zAVLKey key)
291{
292  zAVLNode *avlnode;
293  zAVLNode *origparent;
294  zAVLNode **superparent;
295  int        ok;
296
297  avlnode = zAVLCloseSearchNode(avltree, key, &ok);
298  if (avlnode == NULL || ok == ZAVL_NO) /* does not exist */
299    return -1;
300
301  origparent = avlnode->parent;
302
303  if (origparent) {
304    if (zAVLKey_cmp(avltree, avlnode->key, avlnode->parent->key) < 0)
305      superparent = &(avlnode->parent->left);
306    else
307      superparent = &(avlnode->parent->right);
308  }
309  else
310    superparent = &(avltree->top);
311
312  zAVLFillVacancy(avltree, origparent, superparent,
313                  avlnode->left, avlnode->right);
314  free(avlnode);
315  avltree->count--;
316  return 0;
317}
318
319
320/*
321 * zAVLFirst:
322 * Initializes an zAVLCursor object and returns the item with the lowest
323 * key in the zAVLTree.
324 */
325void *zAVLFirst (zAVLCursor *avlcursor, zAVLTree const *avltree)
326{
327  const zAVLNode *avlnode;
328
329  if (NULL == avltree)  /* R.W. Mon Nov 19 21:15:44 CET 2001 */
330    return NULL;
331
332  avlcursor->avltree = avltree;
333
334  if (avltree->top == NULL) {
335    avlcursor->curnode = NULL;
336    return NULL;
337  }
338
339  for (avlnode = avltree->top;
340       avlnode->left != NULL;
341       avlnode = avlnode->left);
342  avlcursor->curnode = avlnode;
343  return avlnode->item;
344}
345
346
347/*
348 * zAVLNext:
349 * Called after an zAVLFirst() call, this returns the item with the least
350 * key that is greater than the last item returned either by zAVLFirst()
351 * or a previous invokation of this function.
352 */
353void *zAVLNext (zAVLCursor *avlcursor)
354{
355  const zAVLNode *avlnode;
356
357  avlnode = avlcursor->curnode;
358
359  if (avlnode->right != NULL) {
360    for (avlnode = avlnode->right;
361         avlnode->left != NULL;
362         avlnode = avlnode->left);
363    avlcursor->curnode = avlnode;
364    return avlnode->item;
365  }
366
367  while (avlnode->parent && avlnode->parent->left != avlnode) {
368    avlnode = avlnode->parent;
369  }
370
371  if (avlnode->parent == NULL) {
372    avlcursor->curnode = NULL;
373    return NULL;
374  }
375
376  avlcursor->curnode = avlnode->parent;
377  return avlnode->parent->item;
378}
379
380
381/*
382 * zAVLCloseSearchNode:
383 * Return a pointer to the node closest to the given key.
384 * Returns NULL if the AVL tree is empty.
385 */
386static zAVLNode *zAVLCloseSearchNode (zAVLTree const *avltree, zAVLKey key, 
387                                      int * ok)
388{
389  zAVLNode *node;
390
391  *ok = ZAVL_NO;
392
393  node = avltree->top;
394
395  if (!node)
396    return NULL;
397
398  for (;;) {
399    if (!zAVLKey_cmp(avltree, node->key, key))
400      {
401        *ok = ZAVL_OK;
402        return node;
403      }
404
405    if (zAVLKey_cmp(avltree, node->key, key) < 0) {
406      if (node->right)
407        node = node->right;
408      else
409        return node;
410    }
411
412    else {
413      if (node->left)
414        node = node->left;
415      else
416        return node;
417    }
418  }
419}
420
421
422/*
423 * zAVLRebalanceNode:
424 * Rebalances the AVL tree if one side becomes too heavy.  This function
425 * assumes that both subtrees are AVL trees with consistant data.  This
426 * function has the additional side effect of recalculating the depth of
427 * the tree at this node.  It should be noted that at the return of this
428 * function, if a rebalance takes place, the top of this subtree is no
429 * longer going to be the same node.
430 */
431static void zAVLRebalanceNode (zAVLTree *avltree, zAVLNode *avlnode)
432{
433  long depthdiff;
434  zAVLNode *child;
435  zAVLNode *gchild;
436  zAVLNode *origparent;
437  zAVLNode **superparent;
438
439  origparent = avlnode->parent;
440
441  if (origparent) {
442    if (zAVLKey_cmp(avltree, avlnode->key, avlnode->parent->key) < 0)
443      superparent = &(avlnode->parent->left);
444    else
445      superparent = &(avlnode->parent->right);
446  }
447  else
448    superparent = &(avltree->top);
449
450  depthdiff = R_DEPTH(avlnode) - L_DEPTH(avlnode);
451
452  if (depthdiff <= -2 && avlnode->left) {
453    child = avlnode->left;
454
455    if (L_DEPTH(child) >= R_DEPTH(child)) {
456      avlnode->left = child->right;
457      if (avlnode->left != NULL)
458        avlnode->left->parent = avlnode;
459      avlnode->depth = CALC_DEPTH(avlnode);
460      child->right = avlnode;
461      if (child->right != NULL)
462        child->right->parent = child;
463      child->depth = CALC_DEPTH(child);
464      *superparent = child;
465      child->parent = origparent;
466    }
467
468    else {
469      gchild = child->right;
470      if (gchild)
471        {
472          avlnode->left = gchild->right;
473          if (avlnode->left != NULL)
474            avlnode->left->parent = avlnode;
475          avlnode->depth = CALC_DEPTH(avlnode);
476          child->right = gchild->left;
477          if (child->right != NULL)
478            child->right->parent = child;
479          child->depth = CALC_DEPTH(child);
480          gchild->right = avlnode;
481          if (gchild->right != NULL)
482            gchild->right->parent = gchild;
483          gchild->left = child;
484          if (gchild->left != NULL)
485            gchild->left->parent = gchild;
486          gchild->depth = CALC_DEPTH(gchild);
487          *superparent = gchild;
488          gchild->parent = origparent;
489        }
490    }
491  }
492
493  else if (depthdiff >= 2 && avlnode->right) {
494    child = avlnode->right;
495
496    if (R_DEPTH(child) >= L_DEPTH(child)) {
497      avlnode->right = child->left;
498      if (avlnode->right != NULL)
499        avlnode->right->parent = avlnode;
500      avlnode->depth = CALC_DEPTH(avlnode);
501      child->left = avlnode;
502      if (child->left != NULL)
503        child->left->parent = child;
504      child->depth = CALC_DEPTH(child);
505      *superparent = child;
506      child->parent = origparent;
507    }
508
509    else {
510      gchild = child->left;
511      if (gchild)
512        {
513          avlnode->right = gchild->left;
514          if (avlnode->right != NULL)
515            avlnode->right->parent = avlnode;
516          avlnode->depth = CALC_DEPTH(avlnode);
517          child->left = gchild->right;
518          if (child->left != NULL)
519            child->left->parent = child;
520          child->depth = CALC_DEPTH(child);
521          gchild->left = avlnode;
522          if (gchild->left != NULL)
523            gchild->left->parent = gchild;
524          gchild->right = child;
525          if (gchild->right != NULL)
526            gchild->right->parent = gchild;
527          gchild->depth = CALC_DEPTH(gchild);
528          *superparent = gchild;
529          gchild->parent = origparent;
530        }
531    }
532  }
533
534  else {
535    avlnode->depth = CALC_DEPTH(avlnode);
536  }
537}
538
539
540/*
541 * zAVLFreeBranch:
542 * Free memory used by this node and its item.  If the freeitem argument
543 * is not NULL, then that function is called on the items to free their
544 * memory as well.  In other words, the freeitem function is a
545 * destructor for the items in the tree.
546 */
547static void zAVLFreeBranch (zAVLNode *avlnode, void (freeitem)(void *item))
548{
549  if (avlnode->left)
550    zAVLFreeBranch(avlnode->left, freeitem);
551  if (avlnode->right)
552    zAVLFreeBranch(avlnode->right, freeitem);
553  if (freeitem) {
554    freeitem(avlnode->item);
555    avlnode->item = NULL;
556  }
557  free(avlnode);
558}
559
560
561/*
562 * zAVLFillVacancy:
563 * Given a vacancy in the AVL tree by it's parent, children, and parent
564 * component pointer, fill that vacancy.
565 */
566static void zAVLFillVacancy (zAVLTree *avltree,
567                             zAVLNode *origparent, zAVLNode **superparent,
568                             zAVLNode *left, zAVLNode *right)
569{
570  zAVLNode *avlnode;
571  zAVLNode *balnode;
572  zAVLNode *nextbalnode;
573
574  if (left == NULL) {
575    if (right)
576      right->parent = origparent;
577
578    *superparent = right;
579    balnode = origparent;
580  }
581
582  else {
583    for (avlnode = left; avlnode->right != NULL; avlnode = avlnode->right);
584
585    if (avlnode == left) {
586      balnode = avlnode;
587    }
588    else {
589      balnode = avlnode->parent;
590      balnode->right = avlnode->left;
591      if (balnode->right != NULL)
592        balnode->right->parent = balnode;
593      avlnode->left = left;
594      left->parent = avlnode;
595    }
596
597    avlnode->right = right;
598    if (right != NULL)
599      right->parent = avlnode;
600    *superparent = avlnode;
601    avlnode->parent = origparent;
602  }
603
604  for (; balnode; balnode = nextbalnode) {
605    nextbalnode = balnode->parent;
606    zAVLRebalanceNode(avltree, balnode);
607  }
608}
Note: See TracBrowser for help on using the repository browser.