1 // Weak hash tables with 1 key and a value 2 3 #ifndef _CL_HASH1WEAK_H 4 #define _CL_HASH1WEAK_H 5 6 #include "base/hash/cl_hash1.h" 7 8 namespace cln { 9 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. 14 15 // Requirements: 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. 21 22 template <class key1_type, class value_type> 23 struct cl_heap_weak_hashtable_1 : public cl_heap_hashtable_1 <key1_type,value_type> { 24 // Allocation. newcl_heap_weak_hashtable_125 void* operator new (size_t size) { return malloc_hook(size); } 26 // Deallocation. deletecl_heap_weak_hashtable_127 void operator delete (void* ptr) { free_hook(ptr); } 28 public: 29 // Function which tells when an unused entry may be garbage collected. 30 bool (* const _maygc_htentry) (const cl_htentry1<key1_type,value_type>&); 31 // Constructor. cl_heap_weak_hashtable_1cl_heap_weak_hashtable_132 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) 35 { 36 this->_garcol_fun = cl_heap_weak_hashtable_1<key1_type,value_type>::garcol; 37 } 38 private: 39 // Garbage collection. 40 // Before growing the table, we check whether we can remove unused 41 // entries. garcolcl_heap_weak_hashtable_142 static bool garcol (cl_heap* _ht) 43 { 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. 48 if (ht->_count < 100) 49 return false; 50 // Do a garbage collection. 51 var intptr_t removed = 0; 52 for (intptr_t 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); 68 } 69 removed++; 70 } 71 } 72 if (removed == 0) 73 // Unsuccessful. Let the table grow immediately. 74 return false; 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; 79 return true; 80 } else { 81 // Table shrank much. Don't expand the table now, 82 // and try a GC next time. 83 return true; 84 } 85 } garcol_nexttimecl_heap_weak_hashtable_186 static bool garcol_nexttime (cl_heap* _ht) 87 { 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; 91 return false; 92 } 93 }; 94 95 } // namespace cln 96 97 #endif /* _CL_HASH1WEAK_H */ 98