include/aatree.h

   1 /*
   2  * PgBouncer - Lightweight connection pooler for PostgreSQL.
   3  *
   4  * Copyright (c) 2007-2009  Marko Kreen, Skype Technologies OÜ
   5  *
   6  * Permission to use, copy, modify, and/or distribute this software for any
   7  * purpose with or without fee is hereby granted, provided that the above
   8  * copyright notice and this permission notice appear in all copies.
   9  *
  10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  */
  18
  19 typedef struct Node Node;
  20 typedef struct Tree Tree;
  21
  22 typedef int (*tree_cmp_f)(long, Node *node);
  23 typedef void (*tree_walker_f)(Node *n, void *arg);
  24
  25 /*
  26  * Tree header, for storing helper functions.
  27  */
  28 struct Tree {
  29         Node *root;
  30         int count;
  31         tree_cmp_f node_cmp;
  32         tree_walker_f release_cb;
  33 };
  34
  35 /*
  36  * Tree node.
  37  */
  38 struct Node {
  39         Node *left;     /* smaller values */
  40         Node *right;    /* larger values */
  41         int level;      /* number of black nodes to leaf */
  42 };
  43
  44 /*
  45  * walk order
  46  */
  47 enum TreeWalkType {
  48         WALK_IN_ORDER = 0, /* left->self->right */
  49         WALK_PRE_ORDER = 1, /* self->left->right */
  50         WALK_POST_ORDER = 2, /* left->right->self */
  51 };
  52
  53 void tree_init(Tree *tree, tree_cmp_f cmpfn, tree_walker_f release_cb);
  54 Node *tree_search(Tree *tree, long value);
  55 void tree_insert(Tree *tree, long value, Node *node);
  56 void tree_remove(Tree *tree, long value);
  57 void tree_walk(Tree *tree, enum TreeWalkType wtype, tree_walker_f walker, void *arg);
  58 void tree_destroy(Tree *tree);
  59