Annotation of embedaddon/quagga/isisd/dict.h, revision 1.1.1.1
1.1 misho 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: *
17: * $Id: dict.h,v 1.3 2005/09/25 12:04:25 hasso Exp $
18: * $Name: $
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
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>