]>
Commit | Line | Data |
---|---|---|
eb5d44eb | 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 | * | |
eb5d44eb | 17 | */ |
18 | ||
19 | #ifndef DICT_H | |
20 | #define DICT_H | |
21 | ||
22 | #include <limits.h> | |
eb5d44eb | 23 | |
24 | /* | |
25 | * Blurb for inclusion into C++ translation units | |
26 | */ | |
27 | ||
28 | #ifdef __cplusplus | |
ffe543af | 29 | extern "C" { |
eb5d44eb | 30 | #endif |
31 | ||
ffe543af | 32 | typedef unsigned long dictcount_t; |
eb5d44eb | 33 | #define DICTCOUNT_T_MAX ULONG_MAX |
34 | ||
35 | /* | |
36 | * The dictionary is implemented as a red-black tree | |
37 | */ | |
38 | ||
ffe543af | 39 | typedef enum { dnode_red, dnode_black } dnode_color_t; |
eb5d44eb | 40 | |
ffe543af | 41 | typedef struct dnode_t { |
d62a17ae | 42 | struct dnode_t *dict_left; |
43 | struct dnode_t *dict_right; | |
44 | struct dnode_t *dict_parent; | |
45 | dnode_color_t dict_color; | |
46 | const void *dict_key; | |
47 | void *dict_data; | |
ffe543af | 48 | } dnode_t; |
eb5d44eb | 49 | |
ffe543af | 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 *); | |
eb5d44eb | 53 | |
ffe543af | 54 | typedef struct dict_t { |
d62a17ae | 55 | dnode_t dict_nilnode; |
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; | |
61 | void *dict_context; | |
62 | int dict_dupes; | |
ffe543af | 63 | } dict_t; |
eb5d44eb | 64 | |
ffe543af | 65 | typedef void (*dnode_process_t)(dict_t *, dnode_t *, void *); |
eb5d44eb | 66 | |
ffe543af | 67 | typedef struct dict_load_t { |
d62a17ae | 68 | dict_t *dict_dictptr; |
69 | dnode_t dict_nilnode; | |
ffe543af | 70 | } dict_load_t; |
71 | ||
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 *); | |
eb5d44eb | 109 | |
eb5d44eb | 110 | #define dict_isfull(D) ((D)->dict_nodecount == (D)->dict_maxcount) |
eb5d44eb | 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)) | |
eb5d44eb | 116 | |
117 | #ifdef __cplusplus | |
118 | } | |
119 | #endif | |
120 | ||
121 | #endif |