src/idxmap.hff


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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);
      }
   }
}