]>
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 | * | |
ffe543af | 17 | * $Id: dict.h,v 1.3 2005/09/25 12:04:25 hasso Exp $ |
eb5d44eb | 18 | * $Name: $ |
19 | */ | |
20 | ||
21 | #ifndef DICT_H | |
22 | #define DICT_H | |
23 | ||
24 | #include <limits.h> | |
eb5d44eb | 25 | |
26 | /* | |
27 | * Blurb for inclusion into C++ translation units | |
28 | */ | |
29 | ||
30 | #ifdef __cplusplus | |
ffe543af | 31 | extern "C" { |
eb5d44eb | 32 | #endif |
33 | ||
ffe543af | 34 | typedef unsigned long dictcount_t; |
eb5d44eb | 35 | #define DICTCOUNT_T_MAX ULONG_MAX |
36 | ||
37 | /* | |
38 | * The dictionary is implemented as a red-black tree | |
39 | */ | |
40 | ||
ffe543af | 41 | typedef enum { dnode_red, dnode_black } dnode_color_t; |
eb5d44eb | 42 | |
ffe543af | 43 | typedef struct dnode_t { |
d62a17ae | 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; | |
ffe543af | 50 | } dnode_t; |
eb5d44eb | 51 | |
ffe543af | 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 *); | |
eb5d44eb | 55 | |
ffe543af | 56 | typedef struct dict_t { |
d62a17ae | 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; | |
ffe543af | 65 | } dict_t; |
eb5d44eb | 66 | |
ffe543af | 67 | typedef void (*dnode_process_t)(dict_t *, dnode_t *, void *); |
eb5d44eb | 68 | |
ffe543af | 69 | typedef struct dict_load_t { |
d62a17ae | 70 | dict_t *dict_dictptr; |
71 | dnode_t dict_nilnode; | |
ffe543af | 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 *); | |
eb5d44eb | 111 | |
eb5d44eb | 112 | #define dict_isfull(D) ((D)->dict_nodecount == (D)->dict_maxcount) |
eb5d44eb | 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)) | |
eb5d44eb | 118 | |
119 | #ifdef __cplusplus | |
120 | } | |
121 | #endif | |
122 | ||
123 | #endif |