1 // Weak hash tables for making objects unique
3 #ifndef _CL_HASHUNIQWEAK_H
4 #define _CL_HASHUNIQWEAK_H
6 #include "cl_hashuniq.h"
10 // This is a hashuniq table in which an entry can be removed when the
11 // value is not referenced any more.
12 // Best example: string -> symbol uniquification. When a symbol is not
13 // referenced any more (except from the hash table itself), the (string,symbol)
14 // pair may be removed from the hash table.
15 // We don't remove unused entries immediately, only when the hash table
16 // wants to grow. This way the hash table also serves as a cache.
19 // - same as for hashuniq,
20 // - value_type must be a subclass of cl_[gc|rc][object|pointer].
21 // Note that since the reference counts are compared against 1, it doesn't
22 // make sense to have more than one weak hash table for the same value_type.
24 template <class key1_type, class value_type>
25 struct cl_heap_weak_hashtable_uniq : public cl_heap_hashtable_uniq <key1_type,value_type> {
27 void* operator new (size_t size) { return malloc_hook(size); }
29 void operator delete (void* ptr) { free_hook(ptr); }
32 cl_heap_weak_hashtable_uniq ()
33 : cl_heap_hashtable_uniq <key1_type,value_type> ()
35 this->_garcol_fun = garcol;
38 // Garbage collection.
39 // Before growing the table, we check whether we can remove unused
41 static bool garcol (cl_heap* _ht)
43 var cl_heap_weak_hashtable_uniq* ht = (cl_heap_weak_hashtable_uniq*)_ht;
44 // Now ht->_garcol_fun = garcol.
45 // It is not worth doing a garbage collection if the table
46 // is small, say, has fewer than 100 entries.
49 // Do a garbage collection.
51 for (long i = 0; i < ht->_size; i++)
52 if (ht->_entries[i].next >= 0) {
53 var value_type& v = ht->_entries[i].entry.val;
54 if (!v.pointer_p() || (v.heappointer->refcount == 1)) {
55 // This is hairy. We remove the entry and
56 // free the value after its refcount has
57 // dropped to zero. But in order to protect
58 // against too early destruction (depending on
59 // how the C++ compiler optimizes hashkey())
60 // we have to temporarily increase the refcount.
62 v.inc_pointer_refcount();
63 ht->remove(hashkey(v));
65 var cl_heap* p = v.heappointer;
66 if (!(--p->refcount == 0)) throw runtime_exception();
67 cl_free_heap_object(p);
73 // Unsuccessful. Let the table grow immediately.
75 else if (2*removed < ht->_count) {
76 // Table shrank by less than a factor of 1/1.5.
77 // Don't expand the table now, but expand it next time.
78 ht->_garcol_fun = garcol_nexttime;
81 // Table shrank much. Don't expand the table now,
82 // and try a GC next time.
86 static bool garcol_nexttime (cl_heap* _ht)
88 var cl_heap_weak_hashtable_uniq* ht = (cl_heap_weak_hashtable_uniq*)_ht;
89 // Now ht->_garcol_fun = garcol_nexttime.
90 ht->_garcol_fun = garcol;
97 #endif /* _CL_HASHUNIQWEAK_H */