Debian Codegraph @

src/weak.c

raw
1 /*
2 * weak.c - weak vectors and tables
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 #define LIBGAUCHE_BODY
35 #include "gauche.h"
36 #include "gauche/priv/configP.h"
37
38 /*=============================================================
39 * Weak vector
40 *
41 * A weak vector is like a vector of Scheme objects, except
42 * it doesn't prevent the referenced objects to be garbage-collected.
43 * Internally, it is implemented using "disappearing link" feature
44 * of Boehm GC; when the referenced object is collected, the pointer
45 * in the vector is set to NULL.
46 * It is important to keep track of whether the entry of the vector
47 * is registered as a disappearing link or not, for you can't register
48 * the same location more than once.
49 */
50
51 static void weakvector_print(ScmObj obj, ScmPort *port, ScmWriteContext *ctx)
52 {
53 ScmWeakVector *v = SCM_WEAK_VECTOR(obj);
54 ScmObj *ptrs = (ScmObj*)v->pointers;
55 Scm_Printf(port, "#,(<weak-vector> %d", v->size);
56 for (ScmSmallInt i=0; i<v->size; i++) {
57 SCM_PUTC(' ', port);
58 if (ptrs[i]) {
59 Scm_Write(ptrs[i], SCM_OBJ(port), Scm_WriteContextMode(ctx));
60 } else {
61 Scm_Write(SCM_FALSE, SCM_OBJ(port), Scm_WriteContextMode(ctx));
62 }
63 }
64 SCM_PUTC(')', port);
65 }
66
67 static void weakvector_finalize(ScmObj obj, void *data SCM_UNUSED)
68 {
69 ScmWeakVector *v = SCM_WEAK_VECTOR(obj);
70 ScmObj *p = (ScmObj*)v->pointers;
71 for (ScmSmallInt i=0; i<v->size; i++) {
72 if (p[i]==NULL || SCM_PTRP(p[i])) {
73 GC_unregister_disappearing_link((void **)&p[i]);
74 }
75 p[i] = SCM_FALSE; /* safety */
76 }
77 }
78
79 SCM_DEFINE_BUILTIN_CLASS(Scm_WeakVectorClass, weakvector_print,
80 NULL, NULL, NULL,
81 SCM_CLASS_SEQUENCE_CPL);
82
83 ScmObj Scm_MakeWeakVector(ScmSmallInt size)
84 {
85 ScmWeakVector *v = SCM_NEW(ScmWeakVector);
86
87 SCM_SET_CLASS(v, SCM_CLASS_WEAK_VECTOR);
88 v->size = size;
89 /* Allocate pointer array by ATOMIC, so that GC won't trace the
90 pointers in it. */
91 ScmObj *p = SCM_NEW_ATOMIC2(ScmObj*, size * sizeof(ScmObj));
92 for (ScmSmallInt i=0; i<size; i++) p[i] = SCM_FALSE;
93 v->pointers = (void*)p;
94 Scm_RegisterFinalizer(SCM_OBJ(v), weakvector_finalize, NULL);
95 return SCM_OBJ(v);
96 }
97
98 ScmObj Scm_WeakVectorRef(ScmWeakVector *v, ScmSmallInt index, ScmObj fallback)
99 {
100 if (index < 0 || index >= v->size) {
101 if (SCM_UNBOUNDP(fallback)) {
102 Scm_Error("argument out of range: %ld", index);
103 } else {
104 return fallback;
105 }
106 }
107 ScmObj *p = (ScmObj*)v->pointers;
108 if (p[index] == NULL) {
109 if (SCM_UNBOUNDP(fallback)) return SCM_FALSE;
110 else return fallback;
111 } else {
112 return p[index];
113 }
114 }
115
116 ScmObj Scm_WeakVectorSet(ScmWeakVector *v, ScmSmallInt index, ScmObj value)
117 {
118 if (index < 0 || index >= v->size) {
119 Scm_Error("argument out of range: %ld", index);
120 }
121 ScmObj *p = (ScmObj*)v->pointers;
122
123 /* unregister the location if it was registered before */
124 if (p[index] == NULL || SCM_PTRP(p[index])) {
125 GC_unregister_disappearing_link((void **)&p[index]);
126 }
127
128 p[index] = value;
129 /* register the location if the value is a heap object */
130 if (SCM_PTRP(value)) {
131 GC_general_register_disappearing_link((void **)&p[index], (void *)value);
132 }
133 return SCM_UNDEFINED;
134 }
135
136 /*=============================================================
137 * Weak box
138 */
139
140 /* Weak box is not an ScmObj. It provides a packaged 'weak pointer'
141 feature to C. */
142
143 /* ptr points to the target object weakly.
144 Registered flag becomes TRUE whenever ptr points to a GC_malloced object,
145 thus &wbox->ptr is registered as a disappearing link.
146 Note that we can distinguish a box that containing NULL pointer, and
147 a box whose target has been GCed and hence ptr is cleared---in the
148 former case registered is FALSE, while in the latter case it is TRUE. */
149 struct ScmWeakBoxRec {
150 void *ptr;
151 int registered;
152 };
153
154 static void wbox_setvalue(ScmWeakBox *wbox, void *value)
155 {
156 void *base = GC_base((void *)value);
157 wbox->ptr = value;
158 if (base != NULL) {
159 GC_general_register_disappearing_link((void *)&wbox->ptr, base);
160 wbox->registered = TRUE;
161 } else {
162 wbox->registered = FALSE;
163 }
164 }
165
166
167 ScmWeakBox *Scm_MakeWeakBox(void *value)
168 {
169 ScmWeakBox *wbox = SCM_NEW_ATOMIC(ScmWeakBox);
170 wbox_setvalue(wbox, value);
171 return wbox;
172 }
173
174 int Scm_WeakBoxEmptyP(ScmWeakBox *wbox)
175 {
176 return (wbox->registered && wbox->ptr == NULL);
177 }
178
179 void Scm_WeakBoxSet(ScmWeakBox *wbox, void *newvalue)
180 {
181 if (wbox->registered) {
182 GC_unregister_disappearing_link((void *)&wbox->ptr);
183 wbox->registered = FALSE;
184 }
185 wbox_setvalue(wbox, newvalue);
186 }
187
188 void *Scm_WeakBoxRef(ScmWeakBox *wbox)
189 {
190 return wbox->ptr; /* NB: if NULL is retured, you can't know
191 whether box has been containing NULL or
192 the target is GCed. You have to call
193 Scm_WeakBoxEmptyP to check that.
194 IMPORTANT: If you call EmptyP before
195 calling Ref, there is a hazard that the
196 target is GCed between the two calls.
197 ALWAYS call Ref first and keep the
198 result in the register, so that it won't
199 be GCed. */
200 }
201
202 /*=============================================================
203 * Weak Hash Table
204 */
205
206 /* The table can be created with weak key (key can be GC-ed), weak value
207 * (value can be GC-ed), or weak key&value (both key and value can be
208 * GC-ed).
209 *
210 * If a value is GC-ed, the entry returns the default value specified
211 * at the hash table creation time.
212 *
213 * If a key is GC-ed, the entry becomes inaccessible---from outside it
214 * looks as if the entry is deleted. We don't immediately delete the entry
215 * at the time we found its key has been GC-ed, since the caller may not
216 * expect the table is modified. Instead we flag the table and delete
217 * those entries when the table is modified.
218 */
219
220 #define MARK_GONE_ENTRY(ht, e) (ht->goneEntries++)
221
222
223 static void weakhash_print(ScmObj obj, ScmPort *port,
224 ScmWriteContext *ctx SCM_UNUSED)
225 {
226 ScmWeakHashTable *ht = SCM_WEAK_HASH_TABLE(obj);
227 char *type = "";
228
229 switch (ht->type) {
230 case SCM_HASH_EQ: type = "eq?"; break;
231 case SCM_HASH_EQV: type = "eqv?"; break;
232 case SCM_HASH_EQUAL: type = "equal?"; break;
233 case SCM_HASH_STRING: type = "string=?"; break;
234 case SCM_HASH_GENERAL: type = "general"; break;
235 default: Scm_Panic("something wrong with a hash table");
236 }
237 /* should we also print weakness info? */
238 Scm_Printf(port, "#<weak-hash-table %s %p>", type, ht);
239 }
240
241 SCM_DEFINE_BUILTIN_CLASS(Scm_WeakHashTableClass, weakhash_print,
242 NULL, NULL, NULL,
243 SCM_CLASS_DICTIONARY_CPL);
244
245 /* Custom hasher & comparer for key-weak table, in which we insert
246 one indirection to the real key via WeakBox. */
247 static u_long weak_key_hash(const ScmHashCore *hc, intptr_t key)
248 {
249 ScmWeakHashTable *wh = SCM_WEAK_HASH_TABLE(hc->data);
250 ScmWeakBox *box = (ScmWeakBox *)key;
251 intptr_t realkey = (intptr_t)Scm_WeakBoxRef(box);
252 if (Scm_WeakBoxEmptyP(box)) {
253 /* There IS a small possibility that the real key has already been
254 GCed. We return an arbitrary value (0 here); the entry won't
255 match anyway. */
256 return 0;
257 } else {
258 u_long k= wh->hashfn(hc, realkey);
259 return k;
260 }
261 }
262
263
264 static int weak_key_compare(const ScmHashCore *hc, intptr_t key,
265 intptr_t entrykey)
266 {
267 ScmWeakHashTable *wh = SCM_WEAK_HASH_TABLE(hc->data);
268 ScmWeakBox *box = (ScmWeakBox *)entrykey;
269 intptr_t realkey = (intptr_t)Scm_WeakBoxRef(box);
270 if (Scm_WeakBoxEmptyP(box)) {
271 return FALSE;
272 } else {
273 return wh->cmpfn(hc, key, realkey);
274 }
275 }
276
277 /* Scan through */
278 #if 0
279 static void weak_hash_cleanup(ScmWeakHashTable *wh)
280 {
281 }
282 #endif
283
284
285 ScmObj Scm_MakeWeakHashTableSimple(ScmHashType type,
286 ScmWeakness weakness,
287 int initSize,
288 ScmObj defaultValue)
289 {
290 ScmWeakHashTable *wh = SCM_NEW(ScmWeakHashTable);
291 SCM_SET_CLASS(wh, SCM_CLASS_WEAK_HASH_TABLE);
292 wh->weakness = weakness;
293 wh->type = type;
294 wh->defaultValue = defaultValue;
295 wh->goneEntries = 0;
296
297 if (weakness & SCM_WEAK_KEY) {
298 if (!Scm_HashCoreTypeToProcs(type, &wh->hashfn, &wh->cmpfn)) {
299 Scm_Error("[internal error] Scm_MakeWeakHashTableSimple: unsupported type: %d", type);
300 }
301 Scm_HashCoreInitGeneral(&wh->core, weak_key_hash, weak_key_compare,
302 initSize, wh);
303 } else {
304 Scm_HashCoreInitSimple(&wh->core, type, initSize, wh);
305 }
306 return SCM_OBJ(wh);
307 }
308
309 ScmObj Scm_WeakHashTableCopy(ScmWeakHashTable *src)
310 {
311 ScmWeakHashTable *wh = SCM_NEW(ScmWeakHashTable);
312 SCM_SET_CLASS(wh, SCM_CLASS_WEAK_HASH_TABLE);
313
314 wh->weakness = src->weakness;
315 wh->type = src->type;
316 wh->defaultValue = src->defaultValue;
317 wh->hashfn = src->hashfn;
318 wh->cmpfn = src->cmpfn;
319 wh->goneEntries = 0;
320 Scm_HashCoreCopy(&wh->core, &src->core);
321 return SCM_OBJ(wh);
322 }
323
324 ScmObj Scm_WeakHashTableRef(ScmWeakHashTable *ht, ScmObj key, ScmObj fallback)
325 {
326 ScmDictEntry *e = Scm_HashCoreSearch(SCM_WEAK_HASH_TABLE_CORE(ht),
327 (intptr_t)key, SCM_DICT_GET);
328 if (!e) return fallback;
329 if (ht->weakness & SCM_WEAK_VALUE) {
330 void *val = Scm_WeakBoxRef((ScmWeakBox*)e->value);
331 if (Scm_WeakBoxEmptyP((ScmWeakBox*)e->value)) return ht->defaultValue;
332 SCM_ASSERT(val != NULL);
333 return SCM_OBJ(val);
334 } else {
335 return SCM_DICT_VALUE(e);
336 }
337 }
338
339 ScmObj Scm_WeakHashTableSet(ScmWeakHashTable *ht, ScmObj key, ScmObj value,
340 int flags)
341 {
342 intptr_t proxy;
343
344 if (ht->weakness&SCM_WEAK_KEY) {
345 proxy = (intptr_t)Scm_MakeWeakBox(key);
346 } else {
347 proxy = (intptr_t)key;
348 }
349
350 ScmDictEntry *e = Scm_HashCoreSearch(
351 SCM_WEAK_HASH_TABLE_CORE(ht), proxy,
352 (flags&SCM_DICT_NO_CREATE)?SCM_DICT_GET:SCM_DICT_CREATE);
353 if (!e) return SCM_UNBOUND;
354 if (ht->weakness&SCM_WEAK_VALUE) {
355 if (flags&SCM_DICT_NO_OVERWRITE) {
356 if (e->value) {
357 void *val = Scm_WeakBoxRef((ScmWeakBox*)e->value);
358 if (!Scm_WeakBoxEmptyP((ScmWeakBox*)e->value))
359 return SCM_OBJ(val);
360 }
361 }
362 e->value = (intptr_t)Scm_MakeWeakBox(value);
363 return value;
364 } else {
365 if (flags&SCM_DICT_NO_OVERWRITE && e->value) {
366 return SCM_DICT_VALUE(e);
367 }
368 (void)SCM_DICT_SET_VALUE(e, value);
369 return value;
370 }
371 }
372
373 ScmObj Scm_WeakHashTableDelete(ScmWeakHashTable *ht, ScmObj key)
374 {
375 ScmDictEntry *e = Scm_HashCoreSearch(SCM_WEAK_HASH_TABLE_CORE(ht),
376 (intptr_t)key, SCM_DICT_DELETE);
377 if (e && e->value) {
378 if (ht->weakness&SCM_WEAK_VALUE) {
379 void *val = Scm_WeakBoxRef((ScmWeakBox*)e->value);
380 if (!Scm_WeakBoxEmptyP((ScmWeakBox*)e->value))
381 return SCM_OBJ(val);
382 else
383 return SCM_UNBOUND;
384 } else {
385 return SCM_DICT_VALUE(e);
386 }
387 } else {
388 return SCM_UNBOUND;
389 }
390 }
391
392 void Scm_WeakHashIterInit(ScmWeakHashIter *iter, ScmWeakHashTable *ht)
393 {
394 Scm_HashIterInit(&iter->iter, SCM_WEAK_HASH_TABLE_CORE(ht));
395 iter->table = ht;
396 }
397
398 int Scm_WeakHashIterNext(ScmWeakHashIter *iter, ScmObj *key, ScmObj *value)
399 {
400 for (;;) {
401 ScmDictEntry *e = Scm_HashIterNext(&iter->iter);
402 if (e == NULL) return FALSE;
403 if (iter->table->weakness & SCM_WEAK_KEY) {
404 ScmWeakBox *box = (ScmWeakBox*)e->key;
405 ScmObj realkey = SCM_OBJ(Scm_WeakBoxRef(box));
406 if (Scm_WeakBoxEmptyP(box)) {
407 MARK_GONE_ENTRY(iter->table, e);
408 continue;
409 }
410 *key = realkey;
411 } else {
412 *key = (ScmObj)e->key;
413 }
414
415 if (iter->table->weakness & SCM_WEAK_VALUE) {
416 ScmWeakBox *box = (ScmWeakBox*)e->value;
417 ScmObj realval = SCM_OBJ(Scm_WeakBoxRef(box));
418 if (Scm_WeakBoxEmptyP(box)) {
419 *value = iter->table->defaultValue;
420 } else {
421 *value = realval;
422 }
423 } else {
424 *value = (ScmObj)e->value;
425 }
426 return TRUE;
427 }
428 }
429
430 ScmObj Scm_WeakHashTableKeys(ScmWeakHashTable *table)
431 {
432 ScmWeakHashIter iter;
433 ScmObj h = SCM_NIL, t = SCM_NIL, k, v;
434 Scm_WeakHashIterInit(&iter, table);
435 while (Scm_WeakHashIterNext(&iter, &k, &v)) {
436 SCM_APPEND1(h, t, k);
437 }
438 return h;
439 }
440
441 ScmObj Scm_WeakHashTableValues(ScmWeakHashTable *table)
442 {
443 ScmWeakHashIter iter;
444 ScmObj h = SCM_NIL, t = SCM_NIL, k, v;
445 Scm_WeakHashIterInit(&iter, table);
446 while (Scm_WeakHashIterNext(&iter, &k, &v)) {
447 SCM_APPEND1(h, t, v);
448 }
449 return h;
450 }