Debian Codegraph @

src/gauche/treemap.h

raw
1 /*
2 * treemap.h - general library of balanced trees
3 *
4 * Copyright (c) 2000-2024 Shiro Kawai <[email protected]>
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * 3. Neither the name of the authors nor the names of its contributors
18 * may be used to endorse or promote products derived from this
19 * software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34 /* This file is included from gauche.h */
35
36 /*
37 * Provides ScmTreeCore, a raw red-black tree implementation,
38 * and ScmTreeMap, ScmObj wrapper of ScmTreeCore.
39 */
40
41 #ifndef GAUCHE_TREEMAP_H
42 #define GAUCHE_TREEMAP_H
43
44 /*================================================================
45 * ScmTreeCore
46 */
47
48 typedef struct ScmTreeCoreRec ScmTreeCore;
49
50 typedef int ScmTreeCoreCompareProc(ScmTreeCore*, intptr_t, intptr_t);
51
52 /* A general tree map for internal use. This is NOT a Scheme object. */
53
54 struct ScmTreeCoreRec {
55 ScmDictEntry *root;
56 ScmTreeCoreCompareProc *cmp;
57 int num_entries;
58 void *data;
59 };
60
61 #define SCM_TREE_CORE_DATA(core) ((core)->data)
62
63 /* The tree iterator is bidirectional. We need to keep both next and
64 prev entries in case if the 'current' entry is deleted during traversal.
65 NULL in n and/or p means iter is at the far end.
66 The initial state is exceptional, since we don't know which way the
67 cursor would go. So 'prev' pointer points to the max node (hence
68 going backwards start from max node) and 'next' pointer points to the
69 min node (so going fowards start from min node).
70
71 p c n
72 cur-1 cur cur+1 normal state
73 NULL min min+1 cursor at the lowest end
74 NULL NULL min cursor exhausted (when going backwards)
75 max-1 max NULL cursor at the highest end
76 max NULL NULL cursor exhausted (when goind forwards)
77 max NULL min special initial state
78
79 NULL cur NULL edge case: map only has one entry
80 NULL NULL NULL edge case: map has no entries
81 */
82 typedef struct ScmTreeIterRec {
83 ScmTreeCore *t;
84 ScmDictEntry *c; /* current */
85 ScmDictEntry *n; /* next */
86 ScmDictEntry *p; /* prev */
87 } ScmTreeIter;
88
89 /*
90 * Initializers
91 */
92 SCM_EXTERN void Scm_TreeCoreInit(ScmTreeCore *tc,
93 ScmTreeCoreCompareProc *cmp,
94 void *data);
95 SCM_EXTERN void Scm_TreeCoreCopy(ScmTreeCore *dst,
96 const ScmTreeCore *src);
97 SCM_EXTERN void Scm_TreeCoreClear(ScmTreeCore *tc);
98
99 /*
100 * Accessors
101 */
102 SCM_EXTERN ScmDictEntry *Scm_TreeCoreSearch(ScmTreeCore *tc,
103 intptr_t key,
104 ScmDictOp op);
105
106 SCM_EXTERN ScmDictEntry *Scm_TreeCoreClosestEntries(ScmTreeCore *tc,
107 intptr_t key,
108 ScmDictEntry **lo,
109 ScmDictEntry **hi);
110
111 SCM_EXTERN ScmDictEntry *Scm_TreeCoreNextEntry(ScmTreeCore *tc, intptr_t key);
112 SCM_EXTERN ScmDictEntry *Scm_TreeCorePrevEntry(ScmTreeCore *tc, intptr_t key);
113
114 typedef enum ScmTreeCoreBoundOp {
115 SCM_TREE_CORE_MIN,
116 SCM_TREE_CORE_MAX
117 } ScmTreeCoreBoundOp;
118
119 SCM_EXTERN ScmDictEntry *Scm_TreeCoreGetBound(ScmTreeCore *tc,
120 ScmTreeCoreBoundOp op);
121 SCM_EXTERN ScmDictEntry *Scm_TreeCorePopBound(ScmTreeCore *tc,
122 ScmTreeCoreBoundOp op);
123
124 SCM_EXTERN int Scm_TreeCoreNumEntries(ScmTreeCore *tc);
125
126 SCM_EXTERN int Scm_TreeCoreEq(ScmTreeCore *a, ScmTreeCore *b);
127
128 /*
129 * Iterators
130 */
131 SCM_EXTERN void Scm_TreeIterInit(ScmTreeIter *iter,
132 ScmTreeCore *tc,
133 ScmDictEntry *start);
134 SCM_EXTERN ScmDictEntry *Scm_TreeIterNext(ScmTreeIter *iter);
135 SCM_EXTERN ScmDictEntry *Scm_TreeIterPrev(ScmTreeIter *iter);
136 SCM_EXTERN ScmDictEntry *Scm_TreeIterCurrent(ScmTreeIter *iter);
137 SCM_EXTERN int Scm_TreeIterAtEnd(ScmTreeIter *iter);
138
139 /* for debug */
140 SCM_EXTERN void Scm_TreeCoreCheckConsistency(ScmTreeCore *tc);
141 SCM_EXTERN void Scm_TreeCoreDump(ScmTreeCore *tc, ScmPort *out);
142
143 /*================================================================
144 * ScmTreeMap
145 */
146
147 /* We store ScmComparator in core.data if the treemap is created
148 in the Scheme world. See make-tree-map in lib/gauche/treeutil.scm */
149 struct ScmTreeMapRec {
150 SCM_HEADER;
151 ScmTreeCore core;
152 };
153
154 SCM_CLASS_DECL(Scm_TreeMapClass);
155 #define SCM_CLASS_TREE_MAP (&Scm_TreeMapClass)
156
157 #define SCM_TREE_MAP(obj) ((ScmTreeMap*)(obj))
158 #define SCM_TREE_MAP_P(obj) SCM_XTYPEP(obj, SCM_CLASS_TREE_MAP)
159
160 #define SCM_TREE_MAP_CORE(obj) (&SCM_TREE_MAP(obj)->core)
161 #define SCM_TREE_MAP_DATA(obj) SCM_TREE_CORE_DATA(SCM_TRE_MAP_CORE(obj))
162
163 SCM_EXTERN ScmObj Scm_MakeTreeMap(ScmTreeCoreCompareProc *cmp,
164 void *data);
165 SCM_EXTERN ScmObj Scm_TreeMapCopy(const ScmTreeMap *src);
166
167 SCM_EXTERN ScmObj Scm_TreeMapRef(ScmTreeMap *tm, ScmObj key,
168 ScmObj fallback);
169 SCM_EXTERN ScmObj Scm_TreeMapSet(ScmTreeMap *tm, ScmObj key, ScmObj value,
170 int flags);
171 SCM_EXTERN ScmObj Scm_TreeMapDelete(ScmTreeMap *tm, ScmObj key);
172
173 /* For debug */
174 SCM_EXTERN void Scm_TreeMapDump(ScmTreeMap *tm, ScmPort *out);
175
176 #endif /* GAUCHE_TREEMAP_H */