1 files changed, 63 insertions, 0 deletions
diff --git a/src/idxmap.hff b/src/idxmap.hff
new file mode 100644
index 0000000..7e5f066
--- /dev/null
+++ b/src/idxmap.hff
@@ -0,0 +1,63 @@
+import "util.hff";
+import "common.hff";
+
+// Round x up to power of 2
+fn roundup2(x u32) u32 {
+   x--;
+   x |= x >> 1;
+   x |= x >> 2;
+   x |= x >> 4;
+   x |= x >> 8;
+   x |= x >> 16;
+   x++;
+   return x;
+}
+
+// Assume for less than this number of fields just doing a linear search is faster
+// than the IdxMap overhead (arbitrarily chosen).
+def IDXMAP_MIN_WORTHIT = 12;
+
+// A map of names to indeces for aggregates' (and bitfields') fields lookup.
+// Assumes a pointer to the field name is the first element of each
+// field structure (true for AggField and BitFField).
+struct IdxMap {
+   idxs *u16,
+   N u16,
+
+   def EMPTY = 0xFFFF;
+   fn init(this *IdxMap, n usize, fields *const void, fieldstride usize) void {
+      assert(n < EMPTY, "too many indeces");
+      this.N = roundup2(n * 2);
+      this.idxs = xcalloc(this.N, sizeof u16);
+      memset(this.idxs, 0xFF, this.N * sizeof u16);
+      for let i = 0z; i < n; ++i {
+         let name *const u8 = *as(**const u8)fields;
+         fields += fieldstride;
+         let h = cwhash32(as(uptrint)name);
+         let hidx = h & (this.N - 1);
+         for ;; {
+            if this.idxs[hidx] == EMPTY {
+               this.idxs[hidx] = i;
+               break;
+            }
+            hidx = (hidx + 1) & (this.N - 1);
+         }
+      }
+   }
+
+   fn find(this *const IdxMap, name *const u8, fields *void, fieldstride usize) *void {
+      let h = cwhash32(as(uptrint)name);
+      let hidx = h & (this.N - 1);
+      for ;; {
+         if this.idxs[hidx] == EMPTY {
+            return #null;
+         }
+         let idx = this.idxs[hidx];
+         let fname *const u8 = *as(**const u8)(fields + (idx * fieldstride));
+         if name == fname {
+            return fields + (idx * fieldstride);
+         }
+         hidx = (hidx + 1) & (this.N - 1);
+      }
+   }
+}