src/base/hash/cl_hash2weak.h

   1 // Weak hash tables with 2 keys and a value
   2
   3 #ifndef _CL_HASH2WEAK_H
   4 #define _CL_HASH2WEAK_H
   5
   6 #include "cl_hash2.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 hash2,
  17 // - key1_type and key2_type must be subclasses of cl_gc[object|pointer],
  18 // - value_type must be a subclass of cl_[gc|rc][object|pointer],
  19 // - function maygc_htentry(const cl_htentry2<key1_type,key2_type,value_type>&);
  20 //   must be filled in at runtime.
  21
  22 template <class key1_type, class key2_type, class value_type>
  23 struct cl_heap_weak_hashtable_2 : public cl_heap_hashtable_2 <key1_type,key2_type,value_type> {
  24         // Allocation.
  25         void* operator new (size_t size) { return malloc_hook(size); }
  26         // Deallocation.
  27         void operator delete (void* ptr) { free_hook(ptr); }
  28 public:
  29         // Function which tells when an unused entry may be garbage collected.
  30         cl_boolean (* const _maygc_htentry) (const cl_htentry2<key1_type,key2_type,value_type>&);
  31         // Constructor.
  32         cl_heap_weak_hashtable_2 (cl_boolean (*maygc_htentry) (const cl_htentry2<key1_type,key2_type,value_type>&))
  33                 : cl_heap_hashtable_2 <key1_type,key2_type,value_type> (),
  34                   _maygc_htentry (maygc_htentry)
  35         {
  36                 this->_garcol_fun = garcol;
  37         }
  38 private:
  39         // Garbage collection.
  40         // Before growing the table, we check whether we can remove unused
  41         // entries.
  42         static cl_boolean garcol (cl_heap* _ht)
  43         {
  44                 var cl_heap_weak_hashtable_2* ht = (cl_heap_weak_hashtable_2*)_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 cl_false;
  50                 // Do a garbage collection.
  51                 var long removed = 0;
  52                 for (long i = 0; i < ht->_size; i++)
  53                     if (ht->_entries[i].next >= 0) {
  54                         var cl_htentry2<key1_type,key2_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.key1,entry.key2);
  64                                 if (entry.val.pointer_p()) {
  65                                         var cl_heap* p = entry.val.heappointer;
  66                                         if (!(--p->refcount == 0)) cl_abort();
  67                                         cl_free_heap_object(p);
  68                                 }
  69                                 removed++;
  70                         }
  71                     }
  72                 if (removed == 0)
  73                         // Unsuccessful. Let the table grow immediately.
  74                         return cl_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 = garcol_nexttime;
  79                         return cl_true;
  80                 } else {
  81                         // Table shrank much. Don't expand the table now,
  82                         // and try a GC next time.
  83                         return cl_true;
  84                 }
  85         }
  86         static cl_boolean garcol_nexttime (cl_heap* _ht)
  87         {
  88                 var cl_heap_weak_hashtable_2* ht = (cl_heap_weak_hashtable_2*)_ht;
  89                 // Now ht->_garcol_fun = garcol_nexttime.
  90                 ht->_garcol_fun = cl_heap_weak_hashtable_2<key1_type,key2_type,value_type>::garcol;
  91                 return cl_false;
  92         }
  93 };
  94
  95 }  // namespace cln
  96
  97 #endif /* _CL_HASH2WEAK_H */