isisd/dict.h

   1 /*
   2  * Dictionary Abstract Data Type
   3  * Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net>
   4  *
   5  * Free Software License:
   6  *
   7  * All rights are reserved by the author, with the following exceptions:
   8  * Permission is granted to freely reproduce and distribute this software,
   9  * possibly in exchange for a fee, provided that this copyright notice appears
  10  * intact. Permission is also granted to adapt this software to produce
  11  * derivative works, as long as the modified versions carry this copyright
  12  * notice and additional notices stating that the work has been modified.
  13  * This source code may be translated into executable form and incorporated
  14  * into proprietary software; there is no requirement for such software to
  15  * contain a copyright notice related to this source.
  16  *
  17  * $Id: dict.h,v 1.3 2005/09/25 12:04:25 hasso Exp $
  18  * $Name:  $
  19  */
  20
  21 #ifndef DICT_H
  22 #define DICT_H
  23
  24 #include <limits.h>
  25
  26 /*
  27  * Blurb for inclusion into C++ translation units
  28  */
  29
  30 #ifdef __cplusplus
  31 extern "C" {
  32 #endif
  33
  34 typedef unsigned long dictcount_t;
  35 #define DICTCOUNT_T_MAX ULONG_MAX
  36
  37 /*
  38  * The dictionary is implemented as a red-black tree
  39  */
  40
  41 typedef enum { dnode_red, dnode_black } dnode_color_t;
  42
  43 typedef struct dnode_t {
  44     struct dnode_t *dict_left;
  45     struct dnode_t *dict_right;
  46     struct dnode_t *dict_parent;
  47     dnode_color_t dict_color;
  48     const void *dict_key;
  49     void *dict_data;
  50 } dnode_t;
  51
  52 typedef int (*dict_comp_t)(const void *, const void *);
  53 typedef dnode_t *(*dnode_alloc_t)(void *);
  54 typedef void (*dnode_free_t)(dnode_t *, void *);
  55
  56 typedef struct dict_t {
  57     dnode_t dict_nilnode;
  58     dictcount_t dict_nodecount;
  59     dictcount_t dict_maxcount;
  60     dict_comp_t dict_compare;
  61     dnode_alloc_t dict_allocnode;
  62     dnode_free_t dict_freenode;
  63     void *dict_context;
  64     int dict_dupes;
  65 } dict_t;
  66
  67 typedef void (*dnode_process_t)(dict_t *, dnode_t *, void *);
  68
  69 typedef struct dict_load_t {
  70     dict_t *dict_dictptr;
  71     dnode_t dict_nilnode;
  72 } dict_load_t;
  73
  74 extern dict_t *dict_create(dictcount_t, dict_comp_t);
  75 extern void dict_set_allocator(dict_t *, dnode_alloc_t, dnode_free_t, void *);
  76 extern void dict_destroy(dict_t *);
  77 extern void dict_free_nodes(dict_t *);
  78 extern void dict_free(dict_t *);
  79 extern dict_t *dict_init(dict_t *, dictcount_t, dict_comp_t);
  80 extern void dict_init_like(dict_t *, const dict_t *);
  81 extern int dict_verify(dict_t *);
  82 extern int dict_similar(const dict_t *, const dict_t *);
  83 extern dnode_t *dict_lookup(dict_t *, const void *);
  84 extern dnode_t *dict_lower_bound(dict_t *, const void *);
  85 extern dnode_t *dict_upper_bound(dict_t *, const void *);
  86 extern void dict_insert(dict_t *, dnode_t *, const void *);
  87 extern dnode_t *dict_delete(dict_t *, dnode_t *);
  88 extern int dict_alloc_insert(dict_t *, const void *, void *);
  89 extern void dict_delete_free(dict_t *, dnode_t *);
  90 extern dnode_t *dict_first(dict_t *);
  91 extern dnode_t *dict_last(dict_t *);
  92 extern dnode_t *dict_next(dict_t *, dnode_t *);
  93 extern dnode_t *dict_prev(dict_t *, dnode_t *);
  94 extern dictcount_t dict_count(dict_t *);
  95 extern int dict_isempty(dict_t *);
  96 extern int dict_isfull(dict_t *);
  97 extern int dict_contains(dict_t *, dnode_t *);
  98 extern void dict_allow_dupes(dict_t *);
  99 extern int dnode_is_in_a_dict(dnode_t *);
 100 extern dnode_t *dnode_create(void *);
 101 extern dnode_t *dnode_init(dnode_t *, void *);
 102 extern void dnode_destroy(dnode_t *);
 103 extern void *dnode_get(dnode_t *);
 104 extern const void *dnode_getkey(dnode_t *);
 105 extern void dnode_put(dnode_t *, void *);
 106 extern void dict_process(dict_t *, void *, dnode_process_t);
 107 extern void dict_load_begin(dict_load_t *, dict_t *);
 108 extern void dict_load_next(dict_load_t *, dnode_t *, const void *);
 109 extern void dict_load_end(dict_load_t *);
 110 extern void dict_merge(dict_t *, dict_t *);
 111
 112 #define dict_isfull(D) ((D)->dict_nodecount == (D)->dict_maxcount)
 113 #define dict_count(D) ((D)->dict_nodecount)
 114 #define dict_isempty(D) ((D)->dict_nodecount == 0)
 115 #define dnode_get(N) ((N)->dict_data)
 116 #define dnode_getkey(N) ((N)->dict_key)
 117 #define dnode_put(N, X) ((N)->dict_data = (X))
 118
 119 #ifdef __cplusplus
 120 }
 121 #endif
 122
 123 #endif