-
-def cal_hash(name):
- """Calculate the same hash value that Mesa will calculate in C."""
- return functools.reduce(
- lambda h, c: (h * PRIME_FACTOR + ord(c)) & U32_MASK, name, 0)
+class StringIntMapEntry(object):
+ def __init__(self, string, num):
+ self.string = string
+ self.num = num
+
+ # Calculate the same hash value that we will calculate in C.
+ h = 0
+ for c in string:
+ h = ((h * PRIME_FACTOR) + ord(c)) & U32_MASK
+ self.hash = h
+
+ self.offset = None
+
+def round_to_pow2(x):
+ return 2**int(math.ceil(math.log(x, 2)))
+
+class StringIntMap(object):
+ def __init__(self):
+ self.baked = False
+ self.strings = dict()
+
+ def add_string(self, string, num):
+ assert not self.baked
+ assert string not in self.strings
+ assert 0 <= num < 2**31
+ self.strings[string] = StringIntMapEntry(string, num)
+
+ def bake(self):
+ self.sorted_strings = \
+ sorted(self.strings.values(), key=lambda x: x.string)
+ offset = 0
+ for entry in self.sorted_strings:
+ entry.offset = offset
+ offset += len(entry.string) + 1
+
+ # Save off some values that we'll need in C
+ self.hash_size = round_to_pow2(len(self.strings) * 1.25)
+ self.hash_mask = self.hash_size - 1
+ self.prime_factor = PRIME_FACTOR
+ self.prime_step = PRIME_STEP
+
+ self.mapping = [-1] * self.hash_size
+ self.collisions = [0] * 10
+ for idx, s in enumerate(self.sorted_strings):
+ level = 0
+ h = s.hash
+ while self.mapping[h & self.hash_mask] >= 0:
+ h = h + PRIME_STEP
+ level = level + 1
+ self.collisions[min(level, 9)] += 1
+ self.mapping[h & self.hash_mask] = idx
projects / mesa.git / blobdiff