1 #include "inthash.h"
2 #include "ml_macros.h"
3 #include <gc/gc.h>
4
inthash_new()5 inthash_t *inthash_new() {
6 return new(inthash_t);
7 }
8
9 #define INDEX_SHIFT 6
10 #define INCR_SHIFT 8
11
12
13 #ifndef ASM_INTHASH_SEARCH
inthash_search(const inthash_t * Map,uintptr_t Key)14 void *inthash_search(const inthash_t *Map, uintptr_t Key) {
15 if (!Map->Size) return NULL;
16 uintptr_t *Keys = Map->Keys;
17 size_t Mask = Map->Size - 1;
18 size_t Index = (Key >> INDEX_SHIFT) & Mask;
19 if (Keys[Index] == Key) return Map->Values[Index];
20 if (Keys[Index] < Key) return NULL;
21 size_t Incr = (Key >> INCR_SHIFT) | 1;
22 do {
23 Index = (Index + Incr) & Mask;
24 if (Keys[Index] == Key) return Map->Values[Index];
25 } while (Keys[Index] > Key);
26 return NULL;
27 }
28
inthash_search2(const inthash_t * Map,uintptr_t Key)29 inthash_result_t inthash_search2(const inthash_t *Map, uintptr_t Key) {
30 if (!Map->Size) return (inthash_result_t){NULL, 0};
31 uintptr_t *Keys = Map->Keys;
32 size_t Mask = Map->Size - 1;
33 size_t Index = (Key >> INDEX_SHIFT) & Mask;
34 if (Keys[Index] == Key) return (inthash_result_t){Map->Values[Index], 1};
35 if (Keys[Index] < Key) return (inthash_result_t){NULL, 0};
36 size_t Incr = (Key >> INCR_SHIFT) | 1;
37 do {
38 Index = (Index + Incr) & Mask;
39 if (Keys[Index] == Key) return (inthash_result_t){Map->Values[Index], 1};
40 } while (Keys[Index] > Key);
41 return (inthash_result_t){NULL, 0};
42 }
43 #endif
44
inthash_nodes_sort(uintptr_t * KeyA,uintptr_t * KeyB,void ** ValueA,void ** ValueB)45 static void inthash_nodes_sort(uintptr_t *KeyA, uintptr_t *KeyB, void **ValueA, void **ValueB) {
46 uintptr_t *KeyA1 = KeyA, *KeyB1 = KeyB;
47 uintptr_t KeyTemp = *KeyA;
48 uintptr_t KeyPivot = *KeyB;
49 void **ValueA1 = ValueA, **ValueB1 = ValueB;
50 void *ValueTemp = *ValueA;
51 void *ValuePivot = *ValueB;
52 while (KeyA1 < KeyB1) {
53 if (KeyTemp > KeyPivot) {
54 *KeyA1 = KeyTemp;
55 ++KeyA1;
56 KeyTemp = *KeyA1;
57 *ValueA1 = ValueTemp;
58 ++ValueA1;
59 ValueTemp = *ValueA1;
60 } else {
61 *KeyB1 = KeyTemp;
62 --KeyB1;
63 KeyTemp = *KeyB1;
64 *ValueB1 = ValueTemp;
65 --ValueB1;
66 ValueTemp = *ValueB1;
67 }
68 }
69 *KeyA1 = KeyPivot;
70 *ValueA1 = ValuePivot;
71 if (KeyA1 - KeyA > 1) inthash_nodes_sort(KeyA, KeyA1 - 1, ValueA, ValueA1 - 1);
72 if (KeyB - KeyB1 > 1) inthash_nodes_sort(KeyB1 + 1, KeyB, ValueB1 + 1, ValueB);
73 }
74
75 #define INITIAL_SIZE 8
76
inthash_insert(inthash_t * Map,uintptr_t Key,void * Value)77 void *inthash_insert(inthash_t *Map, uintptr_t Key, void *Value) {
78 uintptr_t *Keys = Map->Keys;
79 void **Values = Map->Values;
80 if (!Keys) {
81 Keys = Map->Keys = anew(uintptr_t, INITIAL_SIZE);
82 Values = Map->Values = anew(void *, INITIAL_SIZE);
83 Map->Size = INITIAL_SIZE;
84 Map->Space = INITIAL_SIZE - 1;
85 size_t Index = (Key >> INDEX_SHIFT) & (INITIAL_SIZE - 1);
86 Keys[Index] = Key;
87 Values[Index] = Value;
88 return NULL;
89 }
90 size_t Mask = Map->Size - 1;
91 size_t Index = (Key >> INDEX_SHIFT) & Mask;
92 size_t Incr = (Key >> INCR_SHIFT) | 1;
93 for (;;) {
94 if (Keys[Index] == Key) {
95 void *Old = Values[Index];
96 Values[Index] = Value;
97 return Old;
98 }
99 if (Keys[Index] < Key) break;
100 Index = (Index + Incr) & Mask;
101 }
102 if (--Map->Space > (Map->Size >> 2)) {
103 uintptr_t Key1 = Keys[Index];
104 void *Value1 = Values[Index];
105 Keys[Index] = Key;
106 Values[Index] = Value;
107 while (Key1) {
108 Incr = (Key1 >> INCR_SHIFT) | 1;
109 while (Keys[Index] > Key1) Index = (Index + Incr) & Mask;
110 uintptr_t Key2 = Keys[Index];
111 void *Value2 = Values[Index];
112 Keys[Index] = Key1;
113 Values[Index] = Value1;
114 Key1 = Key2;
115 Value1 = Value2;
116 }
117 } else {
118 while (Keys[Index]) Index = (Index + 1) & Mask;
119 Keys[Index] = Key;
120 Values[Index] = Value;
121 inthash_nodes_sort(Keys, Keys + Mask, Values, Values + Mask);
122 size_t Size2 = 2 * Map->Size;
123 Mask = Size2 - 1;
124 uintptr_t *Keys2 = anew(uintptr_t, Size2);
125 void **Values2 = anew(void *, Size2);
126 for (int I = 0; Keys[I]; ++I) {
127 uintptr_t Key2 = Keys[I];
128 void *Value2 = Values[I];
129 size_t Index2 = (Key2 >> INDEX_SHIFT) & Mask;
130 size_t Incr2 = (Key2 >> INCR_SHIFT) | 1;
131 while (Keys2[Index2]) Index2 = (Index2 + Incr2) & Mask;
132 Keys2[Index2] = Key2;
133 Values2[Index2] = Value2;
134 }
135 Map->Keys = Keys2;
136 Map->Values = Values2;
137 Map->Space += Map->Size;
138 Map->Size = Size2;
139 }
140 return NULL;
141 }
142