util/X86LINUX64/include/gsl/gsl_bst_avl.h

   1 /* bst/gsl_bst_avl.h
   2  *
   3  * Copyright (C) 2018 Patrick Alken
   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 (at
   8  * your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * 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, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  18  */
  19
  20 #ifndef __GSL_BST_AVL_H__
  21 #define __GSL_BST_AVL_H__
  22
  23 #include <stdlib.h>
  24 #include <gsl/gsl_bst_types.h>
  25
  26 #undef __BEGIN_DECLS
  27 #undef __END_DECLS
  28 #ifdef __cplusplus
  29 # define __BEGIN_DECLS extern "C" {
  30 # define __END_DECLS }
  31 #else
  32 # define __BEGIN_DECLS /* empty */
  33 # define __END_DECLS /* empty */
  34 #endif
  35
  36 __BEGIN_DECLS
  37
  38 #ifndef GSL_BST_AVL_MAX_HEIGHT
  39 #define GSL_BST_AVL_MAX_HEIGHT 32
  40 #endif
  41
  42 /* AVL node */
  43 struct gsl_bst_avl_node
  44 {
  45   struct gsl_bst_avl_node *avl_link[2]; /* subtrees */
  46   void *avl_data;                       /* pointer to data */
  47   signed char avl_balance;              /* balance factor */
  48 };
  49
  50 /* tree data structure */
  51 typedef struct
  52 {
  53   struct gsl_bst_avl_node *avl_root;          /* tree's root */
  54   gsl_bst_cmp_function *avl_compare;          /* comparison function */
  55   void *avl_param;                            /* extra argument to |avl_compare| */
  56   const gsl_bst_allocator *avl_alloc;         /* memory allocator */
  57   size_t avl_count;                           /* number of items in tree */
  58   unsigned long avl_generation;               /* generation number */
  59 } gsl_bst_avl_table;
  60
  61 /* AVL traverser structure */
  62 typedef struct
  63 {
  64   const gsl_bst_avl_table *avl_table;                         /* tree being traversed */
  65   struct gsl_bst_avl_node *avl_node;                          /* current node in tree */
  66   struct gsl_bst_avl_node *avl_stack[GSL_BST_AVL_MAX_HEIGHT]; /* all the nodes above |avl_node| */
  67   size_t avl_height;                                          /* number of nodes in |avl_parent| */
  68   unsigned long avl_generation;                               /* generation number */
  69 } gsl_bst_avl_traverser;
  70
  71 __END_DECLS
  72
  73 #endif /* __GSL_BST_AVL_H__ */