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.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
34extern "C" {
35#endif
36
37typedef 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
44typedef enum { dnode_red, dnode_black } dnode_color_t;
45
46typedef 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
59typedef int (*dict_comp_t)(const void *, const void *);
60typedef dnode_t *(*dnode_alloc_t)(void *);
61typedef void (*dnode_free_t)(dnode_t *, void *);
62
63typedef 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
78typedef void (*dnode_process_t)(dict_t *, dnode_t *, void *);
79
80typedef 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
89extern dict_t *dict_create(dictcount_t, dict_comp_t);
90extern void dict_set_allocator(dict_t *, dnode_alloc_t, dnode_free_t, void *);
91extern void dict_destroy(dict_t *);
92extern void dict_free_nodes(dict_t *);
93extern void dict_free(dict_t *);
94extern dict_t *dict_init(dict_t *, dictcount_t, dict_comp_t);
95extern void dict_init_like(dict_t *, const dict_t *);
96extern int dict_verify(dict_t *);
97extern int dict_similar(const dict_t *, const dict_t *);
98extern dnode_t *dict_lookup(dict_t *, const void *);
99extern dnode_t *dict_lower_bound(dict_t *, const void *);
100extern dnode_t *dict_upper_bound(dict_t *, const void *);
101extern void dict_insert(dict_t *, dnode_t *, const void *);
102extern dnode_t *dict_delete(dict_t *, dnode_t *);
103extern int dict_alloc_insert(dict_t *, const void *, void *);
104extern void dict_delete_free(dict_t *, dnode_t *);
105extern dnode_t *dict_first(dict_t *);
106extern dnode_t *dict_last(dict_t *);
107extern dnode_t *dict_next(dict_t *, dnode_t *);
108extern dnode_t *dict_prev(dict_t *, dnode_t *);
109extern dictcount_t dict_count(dict_t *);
110extern int dict_isempty(dict_t *);
111extern int dict_isfull(dict_t *);
112extern int dict_contains(dict_t *, dnode_t *);
113extern void dict_allow_dupes(dict_t *);
114extern int dnode_is_in_a_dict(dnode_t *);
115extern dnode_t *dnode_create(void *);
116extern dnode_t *dnode_init(dnode_t *, void *);
117extern void dnode_destroy(dnode_t *);
118extern void *dnode_get(dnode_t *);
119extern const void *dnode_getkey(dnode_t *);
120extern void dnode_put(dnode_t *, void *);
121extern void dict_process(dict_t *, void *, dnode_process_t);
122extern void dict_load_begin(dict_load_t *, dict_t *);
123extern void dict_load_next(dict_load_t *, dnode_t *, const void *);
124extern void dict_load_end(dict_load_t *);
125extern 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