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