1 /* treemap.c -*- coding: utf-8; -*-
2 *
3 * Copyright (c) 2010-2021 Takashi Kato <ktakashi@ymail.com>
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
22 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
23 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
24 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
25 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 *
28 * $Id: $
29 */
30 #define LIBSAGITTARIUS_BODY
31 #include "sagittarius/private/treemap.h"
32 #include "sagittarius/private/collection.h"
33 #include "sagittarius/private/error.h"
34 #include "sagittarius/private/pair.h"
35 #include "sagittarius/private/string.h"
36 #include "sagittarius/private/symbol.h"
37 #include "sagittarius/private/values.h"
38 #include "sagittarius/private/vm.h"
39 #include "sagittarius/private/writer.h"
40
treemap_print(SgObject obj,SgPort * port,SgWriteContext * ctx)41 static void treemap_print(SgObject obj, SgPort *port, SgWriteContext *ctx)
42 {
43 SgTreeMap *tm = SG_TREEMAP(obj);
44 Sg_Printf(port, UC("#<treemap %p (%d entries)>"), tm, tm->entryCount);
45 }
46
47 SG_DEFINE_BUILTIN_CLASS(Sg_TreeMapClass, treemap_print, NULL, NULL, NULL,
48 SG_CLASS_ORDERED_DICTIONARY_CPL);
49
make_treemap(int scm)50 static SgTreeMap* make_treemap(int scm)
51 {
52 SgTreeMap *tc = SG_NEW(SgTreeMap);
53 SG_SET_CLASS(tc, SG_CLASS_TREE_MAP);
54 if (scm) {
55 tc->schemep = TRUE;
56 }
57 tc->entryCount = 0;
58 return tc;
59 }
60
Sg_MakeGenericCTreeMap(SgTreeCompareProc * cmp,SgTreeSearchProc * search,SgTreeCopyProc * copy,SgTreeIterInitProc * iter,SgTreeRefProc * higher,SgTreeRefProc * lower,void * data)61 SgObject Sg_MakeGenericCTreeMap(SgTreeCompareProc *cmp,
62 SgTreeSearchProc *search,
63 SgTreeCopyProc *copy,
64 SgTreeIterInitProc *iter,
65 SgTreeRefProc *higher,
66 SgTreeRefProc *lower,
67 void *data)
68 {
69 SgTreeMap *tc = make_treemap(FALSE);
70 ASSERT(cmp && search && copy && iter);
71 SG_TREEMAP_C_PROC(tc, cmp) = cmp;
72 SG_TREEMAP_C_PROC(tc, search) = search;
73 SG_TREEMAP_C_PROC(tc, copy) = copy;
74 SG_TREEMAP_C_PROC(tc, iter) = iter;
75 SG_TREEMAP_C_PROC(tc, higher) = higher;
76 SG_TREEMAP_C_PROC(tc, lower) = lower;
77 tc->data = data;
78 tc->root = (intptr_t)NULL;
79 return SG_OBJ(tc);
80 }
81
82 /*
83 SgObject Sg_MakeGenericSchemeTreeMap(SgObject cmp,
84 SgObject ref,
85 SgObject set,
86 SgObject remove,
87 SgObject copy)
88 {
89 SgTreeMap *tc = make_treemap(TRUE);
90 SG_TREEMAP_SCM_PROC(tc, cmp) = cmp;
91 SG_TREEMAP_SCM_PROC(tc, ref) = ref;
92 SG_TREEMAP_SCM_PROC(tc, set) = set;
93 SG_TREEMAP_SCM_PROC(tc, remove) = remove;
94 SG_TREEMAP_SCM_PROC(tc, copy) = copy;
95 tc->root = (intptr_t)SG_FALSE;
96 return SG_OBJ(tc);
97 }
98 */
99
Sg_MakeDefaultTreeMap(SgTreeCompareProc * cmp)100 SgObject Sg_MakeDefaultTreeMap(SgTreeCompareProc *cmp)
101 {
102 return Sg_MakeRBTreeMap(cmp);
103 }
104
Sg_TreeMapCopy(const SgTreeMap * src)105 SgObject Sg_TreeMapCopy(const SgTreeMap *src)
106 {
107 return SG_TREEMAP_C_PROC(src, copy)(src);
108 }
109
Sg_TreeMapCoreSearch(SgTreeMap * tm,intptr_t key,SgDictOp op,int flags)110 SgTreeEntry* Sg_TreeMapCoreSearch(SgTreeMap *tm, intptr_t key,
111 SgDictOp op, int flags)
112 {
113 return SG_TREEMAP_C_PROC(tm, search)(tm, key, op);
114 }
115
116 /* These APIs are mere dispatchers. */
Sg_TreeMapRef(SgTreeMap * tm,SgObject key,SgObject fallback)117 SgObject Sg_TreeMapRef(SgTreeMap *tm, SgObject key,
118 SgObject fallback)
119 {
120 SgTreeEntry *e = Sg_TreeMapCoreSearch(tm, (intptr_t)key, SG_DICT_GET, 0);
121 if (!e) return fallback;
122 return SG_DICT_ENTRY_VALUE(e);
123 }
124
Sg_TreeMapSet(SgTreeMap * tm,SgObject key,SgObject value,int flags)125 SgObject Sg_TreeMapSet(SgTreeMap *tm, SgObject key, SgObject value,
126 int flags)
127 {
128 SgDictOp op = (flags & SG_DICT_NO_CREATE) ? SG_DICT_GET : SG_DICT_CREATE;
129 SgTreeEntry *e = Sg_TreeMapCoreSearch(tm, (intptr_t)key, op, 0);
130 if (!e) return SG_UNBOUND;
131 if (e->value) {
132 if (flags & SG_DICT_NO_OVERWRITE) return SG_DICT_ENTRY_VALUE(e);
133 else return SG_DICT_ENTRY_SET_VALUE(e, value);
134 } else {
135 return SG_DICT_ENTRY_SET_VALUE(e, value);
136 }
137 }
138
Sg_TreeMapDelete(SgTreeMap * tm,SgObject key)139 SgObject Sg_TreeMapDelete(SgTreeMap *tm, SgObject key)
140 {
141 return Sg_TreeMapCoreSearch(tm, (intptr_t)key, SG_DICT_DELETE, 0);
142 }
143
Sg_TreeMapClear(SgTreeMap * tm)144 void Sg_TreeMapClear(SgTreeMap *tm)
145 {
146 /* very simple :) */
147 tm->root = (SG_SCHEME_TREEMAP_P(tm)) ? (intptr_t)SG_FALSE : (intptr_t)NULL;
148 tm->entryCount = 0;
149 }
150
151 /* iterator */
Sg_TreeIterInit(SgTreeIter * iter,SgTreeMap * tm,SgTreeEntry * start)152 void Sg_TreeIterInit(SgTreeIter *iter,
153 SgTreeMap *tm, SgTreeEntry *start)
154 {
155 SG_TREEMAP_C_PROC(tm, iter)(iter, tm, start, TRUE);
156 }
157
Sg_TreeReverseIterInit(SgTreeIter * iter,SgTreeMap * tm,SgTreeEntry * start)158 void Sg_TreeReverseIterInit(SgTreeIter *iter,
159 SgTreeMap *tm, SgTreeEntry *start)
160 {
161 SG_TREEMAP_C_PROC(tm, iter)(iter, tm, start, FALSE);
162 }
163
164
Sg_TreeIterNext(SgTreeIter * iter)165 SgTreeEntry* Sg_TreeIterNext(SgTreeIter *iter)
166 {
167 return iter->next(iter);
168 }
169
Sg_TreeIterHasNext(SgTreeIter * iter)170 int Sg_TreeIterHasNext(SgTreeIter *iter)
171 {
172 return !iter->end;
173 }
174
keys_values(SgTreeMap * tm,SgObject * keys,SgObject * values)175 static void keys_values(SgTreeMap *tm, SgObject *keys, SgObject *values)
176 {
177 SgTreeIter itr;
178 SgTreeEntry *e;
179 SgObject kt = SG_NIL, vt = SG_NIL;
180 Sg_TreeIterInit(&itr, tm, NULL);
181 while ((e = Sg_TreeIterNext(&itr)) != NULL) {
182 if (keys) SG_APPEND1(*keys, kt, SG_OBJ(e->key));
183 if (values) SG_APPEND1(*values, vt, SG_OBJ(e->value));
184 }
185 }
186
Sg_TreeMapEntries(SgTreeMap * tm)187 SgObject Sg_TreeMapEntries(SgTreeMap *tm)
188 {
189 SgObject keys = SG_NIL, values = SG_NIL;
190 keys_values(tm, &keys, &values);
191 return Sg_Values2(keys, values);
192 }
193
Sg_TreeMapKeys(SgTreeMap * tm)194 SgObject Sg_TreeMapKeys(SgTreeMap *tm)
195 {
196 SgObject keys = SG_NIL;
197 keys_values(tm, &keys, NULL);
198 return keys;
199 }
200
Sg_TreeMapValues(SgTreeMap * tm)201 SgObject Sg_TreeMapValues(SgTreeMap *tm)
202 {
203 SgObject values = SG_NIL;
204 keys_values(tm, NULL, &values);
205 return values;
206 }
207
Sg_TreeMapHigherEntry(SgTreeMap * tm,SgObject key)208 SgTreeEntry* Sg_TreeMapHigherEntry(SgTreeMap *tm, SgObject key)
209 {
210 if (!SG_SCHEME_TREEMAP_P(tm) &&
211 SG_TREEMAP_C_PROC(tm, higher)) {
212 return SG_TREEMAP_C_PROC(tm, higher)(tm, (intptr_t)key);
213 }
214 Sg_ImplementationRestrictionViolation(SG_INTERN("treemap-higher"),
215 SG_MAKE_STRING("given treemap does not "
216 "support higher "
217 "navigation."),
218 tm);
219 return NULL; /* dummy */
220 }
221
Sg_TreeMapLowerEntry(SgTreeMap * tm,SgObject key)222 SgTreeEntry* Sg_TreeMapLowerEntry(SgTreeMap *tm, SgObject key)
223 {
224 if (!SG_SCHEME_TREEMAP_P(tm) &&
225 SG_TREEMAP_C_PROC(tm, lower)) {
226 return SG_TREEMAP_C_PROC(tm, lower)(tm, (intptr_t)key);
227 }
228 Sg_ImplementationRestrictionViolation(SG_INTERN("treemap-lower"),
229 SG_MAKE_STRING("given treemap does not "
230 "support lower "
231 "navigation."),
232 tm);
233 return NULL; /* dummy */
234 }
235
Sg_TreeMapFirstEntry(SgTreeMap * tm)236 SgTreeEntry* Sg_TreeMapFirstEntry(SgTreeMap *tm)
237 {
238 SgTreeIter itr;
239 Sg_TreeIterInit(&itr, tm, NULL);
240 return Sg_TreeIterNext(&itr);
241 }
242
Sg_TreeMapLastEntry(SgTreeMap * tm)243 SgTreeEntry* Sg_TreeMapLastEntry(SgTreeMap *tm)
244 {
245 SgTreeIter itr;
246 Sg_TreeReverseIterInit(&itr, tm, NULL);
247 return Sg_TreeIterNext(&itr);
248 }
249
Sg_TreeMapEq(SgTreeMap * a,SgTreeMap * b)250 int Sg_TreeMapEq(SgTreeMap *a, SgTreeMap *b)
251 {
252 SgTreeIter ai, bi;
253 SgTreeEntry *ae, *be;
254 if (a->entryCount != b->entryCount) return FALSE;
255 Sg_TreeIterInit(&ai, a, NULL);
256 Sg_TreeIterInit(&bi, b, NULL);
257 for (;;) {
258 ae = Sg_TreeIterNext(&ai);
259 be = Sg_TreeIterNext(&bi);
260 if (ae == NULL) {
261 if (be == NULL) return TRUE;
262 else return FALSE;
263 }
264 if (be == NULL) return FALSE;
265 if (ae->key != be->key || ae->value != be->value) return FALSE;
266 }
267 }
268