2 * Dictionary Abstract Data Type
3 * Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net>
5 * Free Software License:
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.
25 * Blurb for inclusion into C++ translation units
32 typedef unsigned long dictcount_t
;
33 #define DICTCOUNT_T_MAX ULONG_MAX
36 * The dictionary is implemented as a red-black tree
39 typedef enum { dnode_red
, dnode_black
} dnode_color_t
;
41 typedef struct dnode_t
{
42 struct dnode_t
*dict_left
;
43 struct dnode_t
*dict_right
;
44 struct dnode_t
*dict_parent
;
45 dnode_color_t dict_color
;
50 typedef int (*dict_comp_t
)(const void *, const void *);
51 typedef dnode_t
*(*dnode_alloc_t
)(void *);
52 typedef void (*dnode_free_t
)(dnode_t
*, void *);
54 typedef struct dict_t
{
56 dictcount_t dict_nodecount
;
57 dictcount_t dict_maxcount
;
58 dict_comp_t dict_compare
;
59 dnode_alloc_t dict_allocnode
;
60 dnode_free_t dict_freenode
;
65 typedef void (*dnode_process_t
)(dict_t
*, dnode_t
*, void *);
67 typedef struct dict_load_t
{
72 extern dict_t
*dict_create(dictcount_t
, dict_comp_t
);
73 extern void dict_set_allocator(dict_t
*, dnode_alloc_t
, dnode_free_t
, void *);
74 extern void dict_destroy(dict_t
*);
75 extern void dict_free_nodes(dict_t
*);
76 extern void dict_free(dict_t
*);
77 extern dict_t
*dict_init(dict_t
*, dictcount_t
, dict_comp_t
);
78 extern void dict_init_like(dict_t
*, const dict_t
*);
79 extern int dict_verify(dict_t
*);
80 extern int dict_similar(const dict_t
*, const dict_t
*);
81 extern dnode_t
*dict_lookup(dict_t
*, const void *);
82 extern dnode_t
*dict_lower_bound(dict_t
*, const void *);
83 extern dnode_t
*dict_upper_bound(dict_t
*, const void *);
84 extern void dict_insert(dict_t
*, dnode_t
*, const void *);
85 extern dnode_t
*dict_delete(dict_t
*, dnode_t
*);
86 extern int dict_alloc_insert(dict_t
*, const void *, void *);
87 extern void dict_delete_free(dict_t
*, dnode_t
*);
88 extern dnode_t
*dict_first(dict_t
*);
89 extern dnode_t
*dict_last(dict_t
*);
90 extern dnode_t
*dict_next(dict_t
*, dnode_t
*);
91 extern dnode_t
*dict_prev(dict_t
*, dnode_t
*);
92 extern dictcount_t
dict_count(dict_t
*);
93 extern int dict_isempty(dict_t
*);
94 extern int dict_isfull(dict_t
*);
95 extern int dict_contains(dict_t
*, dnode_t
*);
96 extern void dict_allow_dupes(dict_t
*);
97 extern int dnode_is_in_a_dict(dnode_t
*);
98 extern dnode_t
*dnode_create(void *);
99 extern dnode_t
*dnode_init(dnode_t
*, void *);
100 extern void dnode_destroy(dnode_t
*);
101 extern void *dnode_get(dnode_t
*);
102 extern const void *dnode_getkey(dnode_t
*);
103 extern void dnode_put(dnode_t
*, void *);
104 extern void dict_process(dict_t
*, void *, dnode_process_t
);
105 extern void dict_load_begin(dict_load_t
*, dict_t
*);
106 extern void dict_load_next(dict_load_t
*, dnode_t
*, const void *);
107 extern void dict_load_end(dict_load_t
*);
108 extern void dict_merge(dict_t
*, dict_t
*);
110 #define dict_isfull(D) ((D)->dict_nodecount == (D)->dict_maxcount)
111 #define dict_count(D) ((D)->dict_nodecount)
112 #define dict_isempty(D) ((D)->dict_nodecount == 0)
113 #define dnode_get(N) ((N)->dict_data)
114 #define dnode_getkey(N) ((N)->dict_key)
115 #define dnode_put(N, X) ((N)->dict_data = (X))