include/gsl/gsl_bst_avl.h

0001 /* bst/gsl_bst_avl.h
0002  *
0003  * Copyright (C) 2018 Patrick Alken
0004  *
0005  * This program is free software; you can redistribute it and/or modify
0006  * it under the terms of the GNU General Public License as published by
0007  * the Free Software Foundation; either version 3 of the License, or (at
0008  * your option) any later version.
0009  *
0010  * This program is distributed in the hope that it will be useful, but
0011  * WITHOUT ANY WARRANTY; without even the implied warranty of
0012  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
0013  * General Public License for more details.
0014  *
0015  * You should have received a copy of the GNU General Public License
0016  * along with this program; if not, write to the Free Software
0017  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
0018  */
0019
0020 #ifndef __GSL_BST_AVL_H__
0021 #define __GSL_BST_AVL_H__
0022
0023 #include <stdlib.h>
0024 #include <gsl/gsl_bst_types.h>
0025
0026 #undef __BEGIN_DECLS
0027 #undef __END_DECLS
0028 #ifdef __cplusplus
0029 # define __BEGIN_DECLS extern "C" {
0030 # define __END_DECLS }
0031 #else
0032 # define __BEGIN_DECLS /* empty */
0033 # define __END_DECLS /* empty */
0034 #endif
0035
0036 __BEGIN_DECLS
0037
0038 #ifndef GSL_BST_AVL_MAX_HEIGHT
0039 #define GSL_BST_AVL_MAX_HEIGHT 32
0040 #endif
0041
0042 /* AVL node */
0043 struct gsl_bst_avl_node
0044 {
0045   struct gsl_bst_avl_node *avl_link[2]; /* subtrees */
0046   void *avl_data;                       /* pointer to data */
0047   signed char avl_balance;              /* balance factor */
0048 };
0049
0050 /* tree data structure */
0051 typedef struct
0052 {
0053   struct gsl_bst_avl_node *avl_root;          /* tree's root */
0054   gsl_bst_cmp_function *avl_compare;          /* comparison function */
0055   void *avl_param;                            /* extra argument to |avl_compare| */
0056   const gsl_bst_allocator *avl_alloc;         /* memory allocator */
0057   size_t avl_count;                           /* number of items in tree */
0058   unsigned long avl_generation;               /* generation number */
0059 } gsl_bst_avl_table;
0060
0061 /* AVL traverser structure */
0062 typedef struct
0063 {
0064   const gsl_bst_avl_table *avl_table;                         /* tree being traversed */
0065   struct gsl_bst_avl_node *avl_node;                          /* current node in tree */
0066   struct gsl_bst_avl_node *avl_stack[GSL_BST_AVL_MAX_HEIGHT]; /* all the nodes above |avl_node| */
0067   size_t avl_height;                                          /* number of nodes in |avl_parent| */
0068   unsigned long avl_generation;                               /* generation number */
0069 } gsl_bst_avl_traverser;
0070
0071 __END_DECLS
0072
0073 #endif /* __GSL_BST_AVL_H__ */