1 /* 2 * Dictionary Abstract Data Type 3 * Copyright (C) 1997 Kaz Kylheku <[email protected]> 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.22.2.6 2000/11/13 01:36:44 kaz Exp $ 18 * $Name: kazlib_1_20 $ 19 * The work has been modified. 20 */ 21 22 #ifndef DICT_H 23 #define DICT_H 24 25 #include <limits.h> 26 #ifdef KAZLIB_SIDEEFFECT_DEBUG 27 #include "sfx.h" 28 #endif 29 30 /* 31 * Blurb for inclusion into C++ translation units 32 */ 33 34 #ifdef __cplusplus 35 extern "C" { 36 #endif 37 38 typedef unsigned long dictcount_t; 39 #define DICTCOUNT_T_MAX ULONG_MAX 40 41 /* 42 * The dictionary is implemented as a red-black tree 43 */ 44 45 typedef enum { dnode_red, dnode_black } dnode_color_t; 46 47 typedef struct dnode_t { 48 #if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) 49 struct dnode_t *dict_left; 50 struct dnode_t *dict_right; 51 struct dnode_t *dict_parent; 52 dnode_color_t dict_color; 53 const void *dict_key; 54 void *dict_data; 55 #else 56 int dict_dummy; 57 #endif 58 } dnode_t; 59 60 typedef int (*dict_comp_t)(const void *, const void *, const void *); 61 typedef dnode_t *(*dnode_alloc_t)(void *); 62 typedef void (*dnode_free_t)(dnode_t *, void *); 63 64 typedef struct dict_t { 65 #if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) 66 dnode_t dict_nilnode; 67 dictcount_t dict_nodecount; 68 dictcount_t dict_maxcount; 69 dict_comp_t dict_compare; 70 dnode_alloc_t dict_allocnode; 71 dnode_free_t dict_freenode; 72 void *dict_context; 73 const void *cmp_ctx; 74 int dict_dupes; 75 #else 76 int dict_dummmy; 77 #endif 78 } dict_t; 79 80 typedef void (*dnode_process_t)(dict_t *, dnode_t *, void *); 81 82 typedef struct dict_load_t { 83 #if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) 84 dict_t *dict_dictptr; 85 dnode_t dict_nilnode; 86 #else 87 int dict_dummmy; 88 #endif 89 } dict_load_t; 90 91 extern dict_t *dict_create(dictcount_t, dict_comp_t); 92 extern void dict_set_allocator(dict_t *, dnode_alloc_t, dnode_free_t, void *); 93 extern void dict_set_cmp_context(dict_t *, const void *); 94 extern void dict_destroy(dict_t *); 95 extern void dict_free_nodes(dict_t *); 96 extern void dict_free(dict_t *); 97 extern dict_t *dict_init(dict_t *, dictcount_t, dict_comp_t); 98 extern void dict_init_like(dict_t *, const dict_t *); 99 extern int dict_verify(dict_t *); 100 extern int dict_similar(const dict_t *, const dict_t *); 101 extern dnode_t *dict_lookup(dict_t *, const void *); 102 extern dnode_t *dict_lower_bound(dict_t *, const void *); 103 extern dnode_t *dict_upper_bound(dict_t *, const void *); 104 extern void dict_insert(dict_t *, dnode_t *, const void *); 105 extern dnode_t *dict_delete(dict_t *, dnode_t *); 106 extern int dict_alloc_insert(dict_t *, const void *, void *); 107 extern void dict_delete_free(dict_t *, dnode_t *); 108 extern dnode_t *dict_first(dict_t *); 109 extern dnode_t *dict_last(dict_t *); 110 extern dnode_t *dict_next(dict_t *, dnode_t *); 111 extern dnode_t *dict_prev(dict_t *, dnode_t *); 112 extern dictcount_t dict_count(dict_t *); 113 extern int dict_isempty(dict_t *); 114 extern int dict_isfull(dict_t *); 115 extern int dict_contains(dict_t *, dnode_t *); 116 extern void dict_allow_dupes(dict_t *); 117 extern int dnode_is_in_a_dict(dnode_t *); 118 extern dnode_t *dnode_create(void *); 119 extern dnode_t *dnode_init(dnode_t *, void *); 120 extern void dnode_destroy(dnode_t *); 121 extern void *dnode_get(dnode_t *); 122 extern const void *dnode_getkey(dnode_t *); 123 extern void dnode_put(dnode_t *, void *); 124 extern void dict_process(dict_t *, void *, dnode_process_t); 125 extern void dict_load_begin(dict_load_t *, dict_t *); 126 extern void dict_load_next(dict_load_t *, dnode_t *, const void *); 127 extern void dict_load_end(dict_load_t *); 128 extern void dict_merge(dict_t *, dict_t *); 129 130 #if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) 131 #ifdef KAZLIB_SIDEEFFECT_DEBUG 132 #define dict_isfull(D) (SFX_CHECK(D)->dict_nodecount == (D)->dict_maxcount) 133 #else 134 #define dict_isfull(D) ((D)->dict_nodecount == (D)->dict_maxcount) 135 #endif 136 #define dict_count(D) ((D)->dict_nodecount) 137 #define dict_isempty(D) ((D)->dict_nodecount == 0) 138 #define dnode_get(N) ((N)->dict_data) 139 #define dnode_getkey(N) ((N)->dict_key) 140 #define dnode_put(N, X) ((N)->dict_data = (X)) 141 #endif 142 143 #ifdef __cplusplus 144 } 145 #endif 146 147 #endif 148