import "common.hff";
import "util.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 h u32 = KTraits:hash(key);
      let i = h & (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 != h;
      assert(#f, "unreachable1");
   }

   fn _reallockvb(self *Map) void {
      // keys, vals, bitmap are in a contiguous memory allocation,
      // XXX ^ alignment
      let p = xcalloc((self.N * (sizeof K + sizeof V)) + (self.N / 8), 1);
      self.keys = p;
      self.vals = as(*V)(self.keys + self.N);
      self.bitmap = as(*u8)(self.vals + self.N);
   }

   fn _rehash(self *Map, newN int) void {
      let oldks = self.keys,
          oldvs = self.vals,
          oldbmp = self.bitmap;
      self.N *= 2;
      self->_reallockvb();
      for let i = 0; i < self.N / 2; ++i {
         let k = oldks[i],
             v = oldvs[i],
             b = (oldbmp[i/8] & (1 << (i%8))) != 0;
         if (b) {
            let h u32 = KTraits:hash(k);
            let j = h & (self.N - 1);
            for ;; {
               if self->_iempty(j) {
                  self.keys[j] = k;
                  self.vals[j] = v;
                  self.bitmap[j/8] |= 1 << (j%8);
                  break;
               } else if KTraits:eq(self.keys[j], k) {
                  assert(#f, "unreachable2");
               }
               j = (j + 1) & (self.N - 1);
            }

         }
      }
      free(oldks);
   }

   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.N = 16;
         _reallockvb(self);
      }

      if self.count == self.N / 2 {
         self->_rehash(self.N * 2);
      }

      let h u32 = KTraits:hash(key);
      let i = h & (self.N - 1);
      do {
         if self->_iempty(i) {
            self.bitmap[i/8] |= (1 << (i%8));
            ++self.count;
            self.keys[i] = key;
            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 != h;
      assert(#f, "unreachable3");
   }


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

   fn clear(self *Map) void {
      free(self.keys);
      *self = {};
   }

}

defmacro map_each(v, k, map, &body) [
   let $m = (map);
   for let $i = 0; $i < $m.N; ++$i {
      if $m->_iempty($i) {
         continue;
      }
      let k = $m.keys[$i];
      let v = $m.vals[$i];
      body;
   }
]