"Fossies" - the Fresh Open Source Software Archive

Member "inotify-tools-3.20.11.0/libinotifytools/src/redblack.h" (13 Nov 2020, 6052 Bytes) of package /linux/privat/inotify-tools-3.20.11.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "redblack.h" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 3.20.2.2_vs_3.20.11.0.

    1 /*
    2  * RCS $Id: redblack.h,v 1.9 2003/10/24 01:31:21 damo Exp $
    3  */
    4 
    5 /*
    6    Redblack balanced tree algorithm
    7    Copyright (C) Damian Ivereigh 2000
    8 
    9    This program is free software; you can redistribute it and/or modify
   10    it under the terms of the GNU Lesser General Public License as published by
   11    the Free Software Foundation; either version 2.1 of the License, or
   12    (at your option) any later version. See the file COPYING for details.
   13 
   14    This program is distributed in the hope that it will be useful,
   15    but WITHOUT ANY WARRANTY; without even the implied warranty of
   16    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   17    GNU General Public License for more details.
   18 
   19    You should have received a copy of the GNU Lesser General Public License
   20    along with this program; if not, write to the Free Software
   21    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
   22  */
   23 
   24 /* Header file for redblack.c, should be included by any code that 
   25 ** uses redblack.c since it defines the functions 
   26 */ 
   27  
   28 /* Stop multiple includes */
   29 #ifndef _REDBLACK_H
   30 #define _REDBLACK_H
   31 
   32 #ifndef RB_CUSTOMIZE
   33 /*
   34  * Without customization, the data member in the tree nodes is a void
   35  * pointer, and you need to pass in a comparison function to be
   36  * applied at runtime.  With customization, you specify the data type
   37  * as the macro RB_ENTRY(data_t) (has to be a macro because compilers
   38  * gag on typdef void) and the name of the compare function as the
   39  * value of the macro RB_CMP. Because the comparison function is
   40  * compiled in, RB_CMP only needs to take two arguments.  If your
   41  * content type is not a pointer, define INLINE to get direct access.
   42  */
   43 #define rbdata_t    void
   44 #define RB_CMP(s, t, e) (*rbinfo->rb_cmp)(s, t, e)
   45 #undef RB_INLINE
   46 #define RB_ENTRY(name)  rb##name
   47 #endif /* RB_CUSTOMIZE */
   48 
   49 #ifndef RB_STATIC
   50 #define RB_STATIC
   51 #endif
   52 
   53 /* Modes for rblookup */
   54 #define RB_NONE -1      /* None of those below */
   55 #define RB_LUEQUAL 0    /* Only exact match */
   56 #define RB_LUGTEQ 1     /* Exact match or greater */
   57 #define RB_LULTEQ 2     /* Exact match or less */
   58 #define RB_LULESS 3     /* Less than key (not equal to) */
   59 #define RB_LUGREAT 4    /* Greater than key (not equal to) */
   60 #define RB_LUNEXT 5     /* Next key after current */
   61 #define RB_LUPREV 6     /* Prev key before current */
   62 #define RB_LUFIRST 7    /* First key in index */
   63 #define RB_LULAST 8     /* Last key in index */
   64 
   65 /* For rbwalk - pinched from search.h */
   66 typedef enum
   67 {
   68   preorder,
   69   postorder,
   70   endorder,
   71   leaf
   72 }
   73 VISIT;
   74 
   75 struct RB_ENTRY(lists) { 
   76 const struct RB_ENTRY(node) *rootp; 
   77 const struct RB_ENTRY(node) *nextp; 
   78 }; 
   79  
   80 #define RBLIST struct RB_ENTRY(lists) 
   81 
   82 struct RB_ENTRY(tree) {
   83 #ifndef RB_CUSTOMIZE
   84         /* comparison routine */
   85 int (*rb_cmp)(const void *, const void *, const void *);
   86         /* config data to be passed to rb_cmp */
   87 const void *rb_config;
   88         /* root of tree */
   89 #endif /* RB_CUSTOMIZE */
   90 struct RB_ENTRY(node) *rb_root;
   91 };
   92 
   93 #ifndef RB_CUSTOMIZE
   94 RB_STATIC struct RB_ENTRY(tree) *rbinit(int (*)(const void *, const void *, const void *),
   95          const void *);
   96 #else
   97 RB_STATIC struct RB_ENTRY(tree) *RB_ENTRY(init)(void);
   98 #endif /* RB_CUSTOMIZE */
   99 
  100 #ifndef no_delete
  101 RB_STATIC const RB_ENTRY(data_t) *RB_ENTRY(delete)(const RB_ENTRY(data_t) *, struct RB_ENTRY(tree) *);
  102 #endif
  103 
  104 #ifndef no_find
  105 RB_STATIC const RB_ENTRY(data_t) *RB_ENTRY(find)(const RB_ENTRY(data_t) *, struct RB_ENTRY(tree) *);
  106 #endif
  107 
  108 #ifndef no_lookup
  109 RB_STATIC const RB_ENTRY(data_t) *RB_ENTRY(lookup)(int, const RB_ENTRY(data_t) *, struct RB_ENTRY(tree) *);
  110 #endif
  111 
  112 #ifndef no_search
  113 RB_STATIC const RB_ENTRY(data_t) *RB_ENTRY(search)(const RB_ENTRY(data_t) *, struct RB_ENTRY(tree) *);
  114 #endif
  115 
  116 #ifndef no_destroy
  117 RB_STATIC void RB_ENTRY(destroy)(struct RB_ENTRY(tree) *);
  118 #endif
  119 
  120 #ifndef no_walk
  121 RB_STATIC void RB_ENTRY(walk)(const struct RB_ENTRY(tree) *,
  122         void (*)(const RB_ENTRY(data_t) *, const VISIT, const int, void *),
  123         void *); 
  124 #endif
  125 
  126 #ifndef no_readlist
  127 RB_STATIC RBLIST *RB_ENTRY(openlist)(const struct RB_ENTRY(tree) *); 
  128 RB_STATIC const RB_ENTRY(data_t) *RB_ENTRY(readlist)(RBLIST *); 
  129 RB_STATIC void RB_ENTRY(closelist)(RBLIST *); 
  130 #endif
  131 
  132 /* Some useful macros */
  133 #define rbmin(rbinfo) RB_ENTRY(lookup)(RB_LUFIRST, NULL, (rbinfo))
  134 #define rbmax(rbinfo) RB_ENTRY(lookup)(RB_LULAST, NULL, (rbinfo))
  135 
  136 #endif /* _REDBLACK_H */
  137 
  138 /*
  139  *
  140  * $Log: redblack.h,v $
  141  * Revision 1.9  2003/10/24 01:31:21  damo
  142  * Patches from Eric Raymond: %prefix is implemented.  Various other small
  143  * changes avoid stepping on global namespaces and improve the documentation.
  144  *
  145  * Revision 1.8  2003/10/23 04:18:47  damo
  146  * Fixed up the rbgen stuff ready for the 1.3 release
  147  *
  148  * Revision 1.7  2002/08/26 03:11:40  damo
  149  * Fixed up a bunch of compiler warnings when compiling example4
  150  *
  151  * Tidies up the Makefile.am & Specfile.
  152  *
  153  * Renamed redblack to rbgen
  154  *
  155  * Revision 1.6  2002/08/26 01:03:35  damo
  156  * Patch from Eric Raymond to change the way the library is used:-
  157  *
  158  * Eric's idea is to convert libredblack into a piece of in-line code
  159  * generated by another program. This should be faster, smaller and easier
  160  * to use.
  161  *
  162  * This is the first check-in of his code before I start futzing with it!
  163  *
  164  * Revision 1.5  2002/01/30 07:54:53  damo
  165  * Fixed up the libtool versioning stuff (finally)
  166  * Fixed bug 500600 (not detecting a NULL return from malloc)
  167  * Fixed bug 509485 (no longer needs search.h)
  168  * Cleaned up debugging section
  169  * Allow multiple inclusions of redblack.h
  170  * Thanks to Matthias Andree for reporting (and fixing) these
  171  *
  172  * Revision 1.4  2000/06/06 14:43:43  damo
  173  * Added all the rbwalk & rbopenlist stuff. Fixed up malloc instead of sbrk.
  174  * Added two new examples
  175  *
  176  * Revision 1.3  2000/05/24 06:45:27  damo
  177  * Converted everything over to using const
  178  * Added a new example1.c file to demonstrate the worst case scenario
  179  * Minor fixups of the spec file
  180  *
  181  * Revision 1.2  2000/05/24 06:17:10  damo
  182  * Fixed up the License (now the LGPL)
  183  *
  184  * Revision 1.1  2000/05/24 04:15:53  damo
  185  * Initial import of files. Versions are now all over the place. Oh well
  186  *
  187  */
  188