src/base/hash/cl_hashuniqweak.h

   1 // Weak hash tables for making objects unique
   2
   3 #ifndef _CL_HASHUNIQWEAK_H
   4 #define _CL_HASHUNIQWEAK_H
   5
   6 #include "cl_hashuniq.h"
   7
   8 // This is a hashuniq table in which an entry can be removed when the
   9 // value is not referenced any more.
  10 // Best example: string -> symbol uniquification. When a symbol is not
  11 // referenced any more (except from the hash table itself), the (string,symbol)
  12 // pair may be removed from the hash table.
  13 // We don't remove unused entries immediately, only when the hash table
  14 // wants to grow. This way the hash table also serves as a cache.
  15
  16 // Requirements:
  17 // - same as for hashuniq,
  18 // - value_type must be a subclass of cl_[gc|rc][object|pointer].
  19 // Note that since the reference counts are compared against 1, it doesn't
  20 // make sense to have more than one weak hash table for the same value_type.
  21
  22 template <class key1_type, class value_type>
  23 struct cl_heap_weak_hashtable_uniq : public cl_heap_hashtable_uniq <key1_type,value_type> {
  24         // Allocation.
  25         void* operator new (size_t size) { return cl_malloc_hook(size); }
  26         // Deallocation.
  27         void operator delete (void* ptr) { cl_free_hook(ptr); }
  28 public:
  29         // Constructor.
  30         cl_heap_weak_hashtable_uniq ()
  31                 : cl_heap_hashtable_uniq <key1_type,value_type> ()
  32         {
  33                 _garcol_fun = garcol;
  34         }
  35 private:
  36         // Garbage collection.
  37         // Before growing the table, we check whether we can remove unused
  38         // entries.
  39         static cl_boolean garcol (cl_heap* _ht)
  40         {
  41                 var cl_heap_weak_hashtable_uniq* ht = (cl_heap_weak_hashtable_uniq*)_ht;
  42                 // Now ht->_garcol_fun = garcol.
  43                 // It is not worth doing a garbage collection if the table
  44                 // is small, say, has fewer than 100 entries.
  45                 if (ht->_count < 100)
  46                         return cl_false;
  47                 // Do a garbage collection.
  48                 var long removed = 0;
  49                 for (long i = 0; i < ht->_size; i++)
  50                     if (ht->_entries[i].next >= 0) {
  51                         var value_type& v = ht->_entries[i].entry.val;
  52                         if (!v.pointer_p() || (v.heappointer->refcount == 1)) {
  53                                 // This is hairy. We remove the entry and
  54                                 // free the value after its refcount has
  55                                 // dropped to zero. But in order to protect
  56                                 // against too early destruction (depending on
  57                                 // how the C++ compiler optimizes hashkey())
  58                                 // we have to temporarily increase the refcount.
  59                                 if (v.pointer_p())
  60                                         v.inc_pointer_refcount();
  61                                 ht->remove(hashkey(v));
  62                                 if (v.pointer_p()) {
  63                                         var cl_heap* p = v.heappointer;
  64                                         if (!(--p->refcount == 0)) cl_abort();
  65                                         cl_free_heap_object(p);
  66                                 }
  67                                 removed++;
  68                         }
  69                     }
  70                 if (removed == 0)
  71                         // Unsuccessful. Let the table grow immediately.
  72                         return cl_false;
  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;
  77                         return cl_true;
  78                 } else {
  79                         // Table shrank much. Don't expand the table now,
  80                         // and try a GC next time.
  81                         return cl_true;
  82                 }
  83         }
  84         static cl_boolean garcol_nexttime (cl_heap* _ht)
  85         {
  86                 var cl_heap_weak_hashtable_uniq* ht = (cl_heap_weak_hashtable_uniq*)_ht;
  87                 // Now ht->_garcol_fun = garcol_nexttime.
  88                 ht->_garcol_fun = garcol;
  89                 return cl_false;
  90         }
  91 };
  92
  93 #endif /* _CL_HASHUNIQWEAK_H */