include/gsl/gsl_bst_rb.h

0001 /* bst/gsl_bst_rb.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_RB_H__
0021 #define __GSL_BST_RB_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_RB_MAX_HEIGHT
0039 #define GSL_BST_RB_MAX_HEIGHT 48
0040 #endif
0041
0042 /* red-black node */
0043 struct gsl_bst_rb_node
0044 {
0045   struct gsl_bst_rb_node *rb_link[2]; /* subtrees */
0046   void *rb_data;                      /* pointer to data */
0047   unsigned char rb_color;             /* color */
0048 };
0049
0050 /* red-black tree data structure */
0051 typedef struct
0052 {
0053   struct gsl_bst_rb_node *rb_root;   /* tree's root */
0054   gsl_bst_cmp_function *rb_compare;  /* comparison function */
0055   void *rb_param;                    /* extra argument to |rb_compare| */
0056   const gsl_bst_allocator *rb_alloc; /* memory allocator */
0057   size_t rb_count;                   /* number of items in tree */
0058   unsigned long rb_generation;       /* generation number */
0059 } gsl_bst_rb_table;
0060
0061 /* red-black traverser structure */
0062 typedef struct
0063 {
0064   const gsl_bst_rb_table *rb_table;  /* tree being traversed */
0065   struct gsl_bst_rb_node *rb_node;   /* current node in tree */
0066   struct gsl_bst_rb_node *rb_stack[GSL_BST_RB_MAX_HEIGHT];
0067                                      /* all the nodes above |rb_node| */
0068   size_t rb_height;                  /* number of nodes in |rb_parent| */
0069   unsigned long rb_generation;       /* generation number */
0070 } gsl_bst_rb_traverser;
0071
0072 __END_DECLS
0073
0074 #endif /* __GSL_BST_RB_H__ */