1 // Weak hash tables with 2 keys and a value
3 #ifndef _CL_HASH2WEAK_H
4 #define _CL_HASH2WEAK_H
8 // This is a hash table in which an entry can be removed when a user-defined
9 // condition is fulfilled (e.g. the value is not referenced any more).
10 // We don't remove unused entries immediately, only when the hash table
11 // wants to grow. This way the hash table also serves as a cache.
14 // - same as for hash2,
15 // - key1_type and key2_type must be subclasses of cl_gc[object|pointer],
16 // - value_type must be a subclass of cl_[gc|rc][object|pointer],
17 // - function maygc_htentry(const cl_htentry2<key1_type,key2_type,value_type>&);
18 // must be filled in at runtime.
20 template <class key1_type, class key2_type, class value_type>
21 struct cl_heap_weak_hashtable_2 : public cl_heap_hashtable_2 <key1_type,key2_type,value_type> {
23 void* operator new (size_t size) { return cl_malloc_hook(size); }
25 void operator delete (void* ptr) { cl_free_hook(ptr); }
27 // Function which tells when an unused entry may be garbage collected.
28 cl_boolean (* const _maygc_htentry) (const cl_htentry2<key1_type,key2_type,value_type>&);
30 cl_heap_weak_hashtable_2 (cl_boolean (*maygc_htentry) (const cl_htentry2<key1_type,key2_type,value_type>&))
31 : cl_heap_hashtable_2 <key1_type,key2_type,value_type> (),
32 _maygc_htentry (maygc_htentry)
37 // Garbage collection.
38 // Before growing the table, we check whether we can remove unused
40 static cl_boolean garcol (cl_heap* _ht)
42 var cl_heap_weak_hashtable_2* ht = (cl_heap_weak_hashtable_2*)_ht;
43 // Now ht->_garcol_fun = garcol.
44 // It is not worth doing a garbage collection if the table
45 // is small, say, has fewer than 100 entries.
48 // Do a garbage collection.
50 for (long i = 0; i < ht->_size; i++)
51 if (ht->_entries[i].next >= 0) {
52 var cl_htentry2<key1_type,key2_type,value_type>& entry = ht->_entries[i].entry;
53 if (ht->_maygc_htentry(entry)) {
54 // This is hairy. We remove the entry and
55 // free the value after its refcount has
56 // dropped to zero. But in order to protect
57 // against too early destruction
58 // we have to temporarily increase the refcount.
59 if (entry.val.pointer_p())
60 entry.val.inc_pointer_refcount();
61 ht->remove(entry.key1,entry.key2);
62 if (entry.val.pointer_p()) {
63 var cl_heap* p = entry.val.heappointer;
64 if (!(--p->refcount == 0)) cl_abort();
65 cl_free_heap_object(p);
71 // Unsuccessful. Let the table grow immediately.
73 else if (2*removed < ht->_count) {
74 // Table shrank by less than a factor of 1/1.5.
75 // Don't expand the table now, but expand it next time.
76 ht->_garcol_fun = garcol_nexttime;
79 // Table shrank much. Don't expand the table now,
80 // and try a GC next time.
84 static cl_boolean garcol_nexttime (cl_heap* _ht)
86 var cl_heap_weak_hashtable_2* ht = (cl_heap_weak_hashtable_2*)_ht;
87 // Now ht->_garcol_fun = garcol_nexttime.
88 ht->_garcol_fun = garcol;
93 #endif /* _CL_HASH2WEAK_H */