import "all.hff";

// KTraits:
//        :hash(K) u32
//        :eq(T, T) bool
struct Map<K, V, KTraits> {
   keys *K,
   vals *V,
   bitmap *u8,
   N int,
   count int,

   fn _iempty(self *Map, i int) bool {
      return (self.bitmap[i/8] & (1 << (i%8))) == 0;
   }

   fn get(self *Map, key K) *V {
      if self.N == 0 {
         return #null;
      }
      let i0 u32 = KTraits:hash(key);
      let i = i0 & (self.N - 1);
      do {
         if self->_iempty(i) {
            return #null;
         } else if KTraits:eq(self.keys[i], key) {
            return &self.vals[i];
         }
         i = (i + 1) & (self.N - 1);
      } while i != i0;
      assert(#f, "unreachable");
   }

   fn get_slot(self *Map, key K) *V {
      if self.keys == #null {
         assert(self.vals == #null and self.bitmap == #null and self.N == 0 and self.count == 0,
               "?");
         self.keys = xcalloc(self.N = 16, sizeof K);
         self.vals = xcalloc(self.N, sizeof V);
         self.bitmap = xcalloc(self.N / 8, 1);
      }

      if self.count == self.N / 2 {
         // rehash
      }
      let i0 u32 = KTraits:hash(key);
      let i = i0 & (self.N - 1);
      do {
         if self->_iempty(i) {
            self.bitmap[i/8] |= (1 << (i%8));
            ++self.count;
            self.vals[i] = {};
            return &self.vals[i];
         } else if KTraits:eq(self.keys[i], key) {
            return &self.vals[i];
         }
         i = (i + 1) & (self.N - 1);
      } while i != i0;
      assert(#f, "unreachable");
   }


   fn put(self *Map, key K, val V) void {
      *self->get_slot(key) = val;
   }

}