1 // Weak hash tables with 1 key and a value
3 #ifndef _CL_HASH1WEAK_H
4 #define _CL_HASH1WEAK_H
6 #include "base/hash/cl_hash1.h"
10 // This is a hash table in which an entry can be removed when a user-defined
11 // condition is fulfilled (e.g. the value is not referenced any more).
12 // We don't remove unused entries immediately, only when the hash table
13 // wants to grow. This way the hash table also serves as a cache.
16 // - same as for hash1,
17 // - key1_type must be a subclass of cl_gc[object|pointer],
18 // - value_type must be a subclass of cl_[gc|rc][object|pointer],
19 // - function maygc_htentry(const cl_htentry1<key1_type,value_type>&);
20 // must be filled in at runtime.
22 template <class key1_type, class value_type>
23 struct cl_heap_weak_hashtable_1 : public cl_heap_hashtable_1 <key1_type,value_type> {
25 void* operator new (size_t size) { return malloc_hook(size); }
27 void operator delete (void* ptr) { free_hook(ptr); }
29 // Function which tells when an unused entry may be garbage collected.
30 bool (* const _maygc_htentry) (const cl_htentry1<key1_type,value_type>&);
32 cl_heap_weak_hashtable_1 (bool (*maygc_htentry) (const cl_htentry1<key1_type,value_type>&))
33 : cl_heap_hashtable_1 <key1_type,value_type> (),
34 _maygc_htentry (maygc_htentry)
36 this->_garcol_fun = cl_heap_weak_hashtable_1<key1_type,value_type>::garcol;
39 // Garbage collection.
40 // Before growing the table, we check whether we can remove unused
42 static bool garcol (cl_heap* _ht)
44 var cl_heap_weak_hashtable_1* ht = (cl_heap_weak_hashtable_1*)_ht;
45 // Now ht->_garcol_fun = garcol.
46 // It is not worth doing a garbage collection if the table
47 // is small, say, has fewer than 100 entries.
50 // Do a garbage collection.
52 for (long i = 0; i < ht->_size; i++)
53 if (ht->_entries[i].next >= 0) {
54 var cl_htentry1<key1_type,value_type>& entry = ht->_entries[i].entry;
55 if (ht->_maygc_htentry(entry)) {
56 // This is hairy. We remove the entry and
57 // free the value after its refcount has
58 // dropped to zero. But in order to protect
59 // against too early destruction
60 // we have to temporarily increase the refcount.
61 if (entry.val.pointer_p())
62 entry.val.inc_pointer_refcount();
63 ht->remove(entry.key);
64 if (entry.val.pointer_p()) {
65 var cl_heap* p = entry.val.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 = cl_heap_weak_hashtable_1<key1_type,value_type>::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_1* ht = (cl_heap_weak_hashtable_1*)_ht;
89 // Now ht->_garcol_fun = garcol_nexttime.
90 ht->_garcol_fun = cl_heap_weak_hashtable_1<key1_type,value_type>::garcol;
97 #endif /* _CL_HASH1WEAK_H */