Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Browse code

This commit was manufactured by cvs2svn to create tag 'REL_1_2_19'.

  • Loading branch information...
commit f1d38574a10ca206a31cf62b98cee0fa99393fbc 2 parents 8812bd4 + 0b607f7
cvs2svn authored

Showing 2 changed files with 477 additions and 0 deletions. Show diff stats Hide diff stats

  1. +409 0 src/misc/avl_tree.c
  2. +68 0 src/misc/avl_tree.h
409 src/misc/avl_tree.c
... ... @@ -0,0 +1,409 @@
  1 +/* ----------------------------------------------------------------------
  2 + * avl_tree.c
  3 + *
  4 + * AVL style self balancing tree support.
  5 + *
  6 + * Copyright (c) 2007-2009, PostgreSQL Global Development Group
  7 + * Author: Jan Wieck, Afilias USA INC.
  8 + *
  9 + * $Id: avl_tree.c,v 1.3 2009-08-17 17:25:50 devrim Exp $
  10 + * ----------------------------------------------------------------------
  11 + */
  12 +
  13 +#include "avl_tree.h"
  14 +
  15 +/* ----
  16 + * local function declarations
  17 + * ----
  18 + */
  19 +static AVLnode *avl_makenode(void);
  20 +static void avl_reset_node(AVLnode *node, AVLfreefunc *freefunc);
  21 +static int avl_insertinto(AVLtree *tree, AVLnode **node,
  22 + void *cdata, AVLnode **result);
  23 +static void avl_rotate_left(AVLnode **node);
  24 +static void avl_rotate_right(AVLnode **node);
  25 +
  26 +
  27 +/* ----
  28 + * avl_init() -
  29 + *
  30 + * Initilize an AVL tree structure.
  31 + *
  32 + * compfunc is a user supplied tri-state comparision function that compares
  33 + * two tree elements and returns <0, 0 or >0 (like strcmp).
  34 + *
  35 + * If freefunc is specified, it is called to free no longer used elements.
  36 + * Note that the element will not immediately be free'd on avl_delete(),
  37 + * but only on a avl_delete, avl_insert sequence using the same key.
  38 + * ----
  39 + */
  40 +void
  41 +avl_init(AVLtree *tree, AVLcompfunc *compfunc, AVLfreefunc *freefunc)
  42 +{
  43 + tree->root = NULL;
  44 + tree->compfunc = compfunc;
  45 + tree->freefunc = freefunc;
  46 +}
  47 +
  48 +
  49 +/* ----
  50 + * avl_reset() -
  51 + *
  52 + * Reset an AVL tree to empty. This will call the user defined
  53 + * free function for all elements in the tree, destroy all nodes
  54 + * and declare the tree empty again.
  55 + * ----
  56 + */
  57 +void
  58 +avl_reset(AVLtree *tree)
  59 +{
  60 + avl_reset_node(tree->root, tree->freefunc);
  61 + tree->root = NULL;
  62 +}
  63 +
  64 +
  65 +/* ----
  66 + * avl_reset_node() -
  67 + *
  68 + * avl_reset()'s workhorse.
  69 + * ----
  70 + */
  71 +void
  72 +avl_reset_node(AVLnode *node, AVLfreefunc *freefunc)
  73 +{
  74 + if (node == NULL)
  75 + return;
  76 +
  77 + avl_reset_node(node->lnode, freefunc);
  78 + avl_reset_node(node->rnode, freefunc);
  79 +
  80 + if (freefunc != NULL)
  81 + freefunc(node->cdata);
  82 + free(node);
  83 +}
  84 +
  85 +
  86 +/* ----
  87 + * avl_insert() -
  88 + *
  89 + * Insert an element into an AVL tree. On return AVL_DATA(node) might
  90 + * point to an existing entry with the same key. If the caller replaces
  91 + * the entry, it must free the existing one since AVL will no longer
  92 + * keep track of it.
  93 + * ----
  94 + */
  95 +AVLnode *
  96 +avl_insert(AVLtree *tree, void *cdata)
  97 +{
  98 + AVLnode *result;
  99 + int depth;
  100 +
  101 + /*
  102 + * If this is an empty tree, create the root node.
  103 + */
  104 + if (tree->root == NULL)
  105 + return (tree->root = avl_makenode());
  106 +
  107 + /*
  108 + * Traverse the tree to find the insert point.
  109 + */
  110 + result = NULL;
  111 + depth = avl_insertinto(tree, &(tree->root), cdata, &result);
  112 + return result;
  113 +}
  114 +
  115 +
  116 +/* ----
  117 + * avl_lookup() -
  118 + *
  119 + * Search for an existing key in the tree.
  120 + * ----
  121 + */
  122 +AVLnode *
  123 +avl_lookup(AVLtree *tree, void *cdata)
  124 +{
  125 + AVLnode *node;
  126 + int cmp;
  127 +
  128 + node = tree->root;
  129 + while (node != NULL)
  130 + {
  131 + cmp = tree->compfunc(cdata, node->cdata);
  132 + if (cmp == 0)
  133 + {
  134 + /*
  135 + * Found the node. If it is marked deleted, return NULL anyway.
  136 + * Otherwise return this node.
  137 + */
  138 + if (node->deleted)
  139 + return NULL;
  140 + return node;
  141 + }
  142 +
  143 + /*
  144 + * Search on ...
  145 + */
  146 + if (cmp < 0)
  147 + node = node->lnode;
  148 + else
  149 + node = node->rnode;
  150 + }
  151 +
  152 + /*
  153 + * No such element found
  154 + */
  155 + return NULL;
  156 +}
  157 +
  158 +
  159 +/* ----
  160 + * avl_delete() -
  161 + *
  162 + * Mark a given element as deleted. Subsequent lookups for the element
  163 + * will return NULL. Note that the caller should NOT free the memory
  164 + * of the element, as it is AVL's property altogether after the delete.
  165 + *
  166 + * avl_delete() returns 1 on success, 0 if no such element was found.
  167 + * ----
  168 + */
  169 +int
  170 +avl_delete(AVLtree *tree, void *cdata)
  171 +{
  172 + AVLnode *node;
  173 +
  174 + if ((node = avl_lookup(tree, cdata)) == NULL)
  175 + return 0;
  176 +
  177 + node->deleted = 1;
  178 + return 1;
  179 +}
  180 +
  181 +
  182 +/* ----
  183 + * avl_insertinto() -
  184 + *
  185 + * The heart of avl_insert().
  186 + * ----
  187 + */
  188 +static int
  189 +avl_insertinto(AVLtree *tree, AVLnode **node,
  190 + void *cdata, AVLnode **result)
  191 +{
  192 + int cmp;
  193 +
  194 + /*
  195 + * Compare the node at hand with the new elements key.
  196 + */
  197 + cmp = (tree->compfunc) (cdata, (*node)->cdata);
  198 +
  199 + if (cmp > 0)
  200 + {
  201 + /*
  202 + * New element is > than node. Insert to the right.
  203 + */
  204 + if ((*node)->rnode == NULL)
  205 + {
  206 + /*
  207 + * Right side of current node is empty. Create a new node there
  208 + * and return new maximum depth. Note that this can only be 1
  209 + * because otherwise this node would have been unbalanced before.
  210 + */
  211 + (*node)->rnode = *result = avl_makenode();
  212 + (*node)->rdepth = 1;
  213 + return 1;
  214 + }
  215 +
  216 + /*
  217 + * Right hand node exists. Recurse into that and remember the new
  218 + * right hand side depth.
  219 + */
  220 + (*node)->rdepth = avl_insertinto(tree, &((*node)->rnode),
  221 + cdata, result) + 1;
  222 +
  223 + /*
  224 + * A right hand side insert can unbalance this node only to the right.
  225 + */
  226 + if (AVL_BALANCE(*node) > 1)
  227 + {
  228 + if (AVL_BALANCE((*node)->rnode) > 0)
  229 + {
  230 + /*
  231 + * RR situation, rebalance the tree by left rotating this
  232 + * node.
  233 + */
  234 + avl_rotate_left(node);
  235 + }
  236 + else
  237 + {
  238 + /*
  239 + * RL situation, rebalance the tree by first right rotating
  240 + * the right hand side, then left rotating this node.
  241 + */
  242 + avl_rotate_right(&((*node)->rnode));
  243 + avl_rotate_left(node);
  244 + }
  245 + }
  246 +
  247 + return AVL_MAXDEPTH(*node);
  248 + }
  249 + else if (cmp < 0)
  250 + {
  251 + /*
  252 + * New element is < than node. Insert to the left.
  253 + */
  254 + if ((*node)->lnode == NULL)
  255 + {
  256 + /*
  257 + * Left side of current node is empty. Create a new node there and
  258 + * return new maximum depth. Note that this can only be 1 because
  259 + * otherwise this node would have been unbalanced before.
  260 + */
  261 + (*node)->lnode = *result = avl_makenode();
  262 + (*node)->ldepth = 1;
  263 + return AVL_MAXDEPTH(*node);
  264 + }
  265 +
  266 + /*
  267 + * Left hand node exists. Recurse into that and remember the new left
  268 + * hand side depth.
  269 + */
  270 + (*node)->ldepth = avl_insertinto(tree, &((*node)->lnode),
  271 + cdata, result) + 1;
  272 +
  273 + /*
  274 + * A left hand side insert can unbalance this node only to the left.
  275 + */
  276 + if (AVL_BALANCE(*node) < -1)
  277 + {
  278 + if (AVL_BALANCE((*node)->lnode) < 0)
  279 + {
  280 + /*
  281 + * LL situation, rebalance the tree by right rotating this
  282 + * node.
  283 + */
  284 + avl_rotate_right(node);
  285 + }
  286 + else
  287 + {
  288 + /*
  289 + * LR situation, rebalance the tree by first left rotating the
  290 + * left node, then right rotating this node.
  291 + */
  292 + avl_rotate_left(&((*node)->lnode));
  293 + avl_rotate_right(node);
  294 + }
  295 + }
  296 +
  297 + return AVL_MAXDEPTH(*node);
  298 + }
  299 + else
  300 + {
  301 + /*
  302 + * The new element is equal to this node. If it is marked for
  303 + * deletion, free the user element data now. The caller is supposed to
  304 + * replace it with a new element having the the key.
  305 + */
  306 + if ((*node)->deleted && tree->freefunc != NULL)
  307 + {
  308 + (tree->freefunc) ((*node)->cdata);
  309 + (*node)->cdata = NULL;
  310 + (*node)->deleted = 0;
  311 + }
  312 + *result = *node;
  313 + return AVL_MAXDEPTH(*node);
  314 + }
  315 +}
  316 +
  317 +
  318 +/* ----
  319 + * avl_makenode() -
  320 + *
  321 + * Create a new empty node.
  322 + * ----
  323 + */
  324 +static AVLnode *
  325 +avl_makenode(void)
  326 +{
  327 + AVLnode *new;
  328 +
  329 + new = (AVLnode *) malloc(sizeof(AVLnode));
  330 + memset(new, 0, sizeof(AVLnode));
  331 +
  332 + return new;
  333 +}
  334 +
  335 +
  336 +/* ----
  337 + * avl_rotate_left() -
  338 + *
  339 + * Rebalance a node to the left.
  340 + * ----
  341 + */
  342 +static void
  343 +avl_rotate_left(AVLnode **node)
  344 +{
  345 + AVLnode *rtmp;
  346 +
  347 + /*
  348 + * save right node
  349 + */
  350 + rtmp = (*node)->rnode;
  351 +
  352 + /*
  353 + * move right nodes left side to this nodes right
  354 + */
  355 + (*node)->rnode = rtmp->lnode;
  356 + if (rtmp->lnode != NULL)
  357 + (*node)->rdepth = AVL_MAXDEPTH(rtmp->lnode) + 1;
  358 + else
  359 + (*node)->rdepth = 0;
  360 +
  361 + /*
  362 + * Move this node to right nodes left side
  363 + */
  364 + rtmp->lnode = *node;
  365 + rtmp->ldepth = AVL_MAXDEPTH(*node) + 1;
  366 +
  367 + /*
  368 + * Let parent point to right node
  369 + */
  370 + *node = rtmp;
  371 +}
  372 +
  373 +
  374 +/* ----
  375 + * avl_rotate_right() -
  376 + *
  377 + * Rebalance a node to the right.
  378 + * ----
  379 + */
  380 +static void
  381 +avl_rotate_right(AVLnode **node)
  382 +{
  383 + AVLnode *ltmp;
  384 +
  385 + /*
  386 + * save left node
  387 + */
  388 + ltmp = (*node)->lnode;
  389 +
  390 + /*
  391 + * move left nodes right side to this nodes left
  392 + */
  393 + (*node)->lnode = ltmp->rnode;
  394 + if (ltmp->rnode != NULL)
  395 + (*node)->ldepth = AVL_MAXDEPTH(ltmp->rnode) + 1;
  396 + else
  397 + (*node)->ldepth = 0;
  398 +
  399 + /*
  400 + * Move this node to left nodes right side
  401 + */
  402 + ltmp->rnode = *node;
  403 + ltmp->rdepth = AVL_MAXDEPTH(*node) + 1;
  404 +
  405 + /*
  406 + * Let parent point to left node
  407 + */
  408 + *node = ltmp;
  409 +}
68 src/misc/avl_tree.h
... ... @@ -0,0 +1,68 @@
  1 +/* ----------------------------------------------------------------------
  2 + * avl_tree.h
  3 + *
  4 + * Declarations for AVL style balanced tree support.
  5 + *
  6 + * Copyright (c) 2003-2009, PostgreSQL Global Development Group
  7 + * Author: Jan Wieck, Afilias USA INC.
  8 + *
  9 + * $Id: avl_tree.h,v 1.3 2009-08-17 17:25:50 devrim Exp $
  10 + * ----------------------------------------------------------------------
  11 + */
  12 +
  13 +#ifndef _AVL_TREE_H_INCLUDED_
  14 +#define _AVL_TREE_H_INCLUDED_
  15 +
  16 +/* ----
  17 + * Callback function type declarations
  18 + * ----
  19 + */
  20 +typedef int (AVLcompfunc) (void *, void *);
  21 +typedef void (AVLfreefunc) (void *);
  22 +
  23 +
  24 +/* ----
  25 + * Data structures
  26 + * ----
  27 + */
  28 +typedef struct AVLnode_s
  29 +{
  30 + struct AVLnode_s *lnode,
  31 + *rnode;
  32 + int ldepth,
  33 + rdepth;
  34 + void *cdata;
  35 + int deleted;
  36 +} AVLnode;
  37 +
  38 +typedef struct AVLtree_s
  39 +{
  40 + AVLnode *root;
  41 + AVLcompfunc *compfunc;
  42 + AVLfreefunc *freefunc;
  43 +} AVLtree;
  44 +
  45 +/* ----
  46 + * Macros
  47 + * ----
  48 + */
  49 +#define AVL_DATA(n) (n)->cdata
  50 +#define AVL_SETDATA(n,p) ((n)->cdata = (p))
  51 +#define AVL_MAXDEPTH(n) (((n)->ldepth > (n)->rdepth) ? (n)->ldepth : (n)->rdepth)
  52 +#define AVL_BALANCE(n) ((n)->rdepth - (n)->ldepth)
  53 +
  54 +#define AVL_INITIALIZER(cmp,free) {NULL, (cmp), (free)}
  55 +
  56 +
  57 +/* ----
  58 + * Public functions
  59 + * ----
  60 + */
  61 +void avl_init(AVLtree *tree, AVLcompfunc *compfunc,
  62 + AVLfreefunc *freefunc);
  63 +void avl_reset(AVLtree *tree);
  64 +AVLnode *avl_insert(AVLtree *tree, void *cdata);
  65 +AVLnode *avl_lookup(AVLtree *tree, void *cdata);
  66 +int avl_delete(AVLtree *tree, void *cdata);
  67 +
  68 +#endif /* _AVL_TREE_H_INCLUDED_ */

0 comments on commit f1d3857

Please sign in to comment.
Something went wrong with that request. Please try again.