1 force_inline
Link(int & m,Hash & hh,int ii)2 void IndexCommon::Link(int& m, Hash& hh, int ii)
3 {
4 if(m < 0)
5 m = hh.prev = hh.next = ii;
6 else {
7 hh.next = m;
8 hh.prev = hash[m].prev;
9 hash[hh.prev].next = ii;
10 hash[m].prev = ii;
11 }
12 }
13
14 force_inline
Link(int ii,dword sh)15 void IndexCommon::Link(int ii, dword sh)
16 {
17 Link(map[sh & mask], hash[ii], ii);
18 }
19
20 force_inline
Del(int & m,Hash & hh,int ii)21 void IndexCommon::Del(int& m, Hash& hh, int ii)
22 { // unlink from m
23 if(ii == m) { // this is item pointed by map
24 if(hh.next == ii) { // this is the only item in the bucket
25 m = -1; // bucket is now empty
26 return;
27 }
28 m = hh.next; // move bucket pointer to the next item
29 }
30 hash[hh.next].prev = hh.prev; // unlink
31 hash[hh.prev].next = hh.next;
32 }
33
34 template <typename T>
35 never_inline
ReallocHash(int n)36 void Index<T>::ReallocHash(int n)
37 { // realloc hash to have the same capacity as key, copy n elements from previous alloc
38 if(key.GetAlloc()) {
39 size_t sz = key.GetAlloc() * sizeof(Hash);
40 if(!MemoryTryRealloc(hash, sz)) {
41 Hash *h = (Hash *)MemoryAlloc(sz);
42 if(hash) {
43 if(n)
44 memcpy_t(h, hash, n);
45 MemoryFree(hash);
46 }
47 hash = h;
48 }
49 }
50 else {
51 MemoryFree(hash);
52 hash = NULL;
53 }
54 }
55
56 template <typename T>
57 never_inline
FixHash(bool makemap)58 void Index<T>::FixHash(bool makemap)
59 {
60 ReallocHash(0);
61 unlinked = -1;
62 for(int i = 0; i < key.GetCount(); i++)
63 hash[i].hash = Smear(key[i]);
64 if(makemap)
65 MakeMap(key.GetCount());
66 else
67 Remap(key.GetCount());
68 }
69
70 template <typename T>
71 template <typename U>
72 never_inline
GrowAdd(U && k,dword sh)73 void Index<T>::GrowAdd(U&& k, dword sh)
74 {
75 int n = key.GetCount();
76 key.GrowAdd(std::forward<U>(k));
77 ReallocHash(n);
78 }
79
80 template <typename T>
81 template <typename U>
AddS(int & m,U && k,dword sh)82 void Index<T>::AddS(int& m, U&& k, dword sh)
83 {
84 int ii = key.GetCount();
85 if(ii >= key.GetAlloc())
86 GrowAdd(std::forward<U>(k), sh);
87 else
88 new(key.Rdd()) T(std::forward<U>(k));
89 Hash& hh = hash[ii];
90 hh.hash = sh;
91 if(ii >= (int)mask)
92 GrowMap(key.GetCount());
93 else
94 Link(m, hh, ii);
95 }
96
97 template <typename T>
98 template <typename U>
AddS(U && k,dword sh)99 void Index<T>::AddS(U&& k, dword sh)
100 {
101 AddS(map[sh & mask], std::forward<U>(k), sh);
102 }
103
104 template <typename T>
105 force_inline
FindFrom(int i,dword sh,const T & k,int end) const106 int Index<T>::FindFrom(int i, dword sh, const T& k, int end) const
107 {
108 if(i >= 0)
109 do {
110 if(key[i] == k)
111 return i;
112 i = hash[i].next;
113 }
114 while(i != end);
115 return -1;
116 }
117
118 template <class T>
Find(const T & k) const119 int Index<T>::Find(const T& k) const
120 {
121 dword sh = Smear(k);
122 int& m = map[sh & mask];
123 return FindFrom(m, sh, k, m);
124 }
125
126 template <class T>
FindNext(int i) const127 int Index<T>::FindNext(int i) const
128 {
129 const Hash& hh = hash[i];
130 int end = map[hash[i].hash & mask];
131 return hh.next == end ? -1 : FindFrom(hh.next, hh.hash, key[i], end);
132 }
133
134 template <typename T>
135 force_inline
FindBack(int i,dword sh,const T & k,int end) const136 int Index<T>::FindBack(int i, dword sh, const T& k, int end) const
137 {
138 do {
139 const Hash& ih = hash[i];
140 if(key[i] == k)
141 return i;
142 i = ih.prev;
143 }
144 while(i != end);
145 return -1;
146 }
147
148 template <class T>
FindLast(const T & k) const149 int Index<T>::FindLast(const T& k) const
150 {
151 dword sh = Smear(k);
152 int& m = map[sh & mask];
153 return m < 0 ? -1 : FindBack(hash[m].prev, sh, k, hash[m].prev);
154 }
155
156 template <class T>
FindPrev(int i) const157 int Index<T>::FindPrev(int i) const
158 {
159 const Hash& hh = hash[i];
160 int end = map[hash[i].hash & mask];
161 return hh.prev == hash[end].prev ? -1 : FindBack(hh.prev, hh.hash, key[i], hash[end].prev);
162 }
163
164 template <class T>
165 template <class OP, class U>
166 force_inline
FindAdd(U && k,OP op)167 int Index<T>::FindAdd(U&& k, OP op) {
168 dword sh = Smear(k);
169 int& m = map[sh & mask];
170 int i = m;
171 if(i >= 0)
172 do {
173 if(key[i] == k)
174 return i;
175 i = hash[i].next;
176 }
177 while(i != m);
178 i = key.GetCount();
179 AddS(m, std::forward<U>(k), sh);
180 op();
181 return i;
182 }
183
184 template <typename T>
Unlink(int ii)185 void Index<T>::Unlink(int ii)
186 {
187 Hash& hh = hash[ii];
188 Del(map[hh.hash & mask], hh, ii);
189 Link(unlinked, hh, ii);
190 hh.hash = 0;
191 }
192
193 template <typename T>
UnlinkKey(const T & k)194 int Index<T>::UnlinkKey(const T& k)
195 {
196 dword sh = Smear(k);
197 int& m = map[sh & mask];
198 int i = m;
199 int n = 0;
200 if(i >= 0)
201 for(;;) {
202 Hash& hh = hash[i];
203 int ni = hh.next;
204 if(key[i] == k) {
205 Del(m, hh, i);
206 Link(unlinked, hh, i);
207 n++;
208 hh.hash = 0;
209 if(ni == i) // last item removed
210 break;
211 i = ni;
212 }
213 else {
214 i = ni;
215 if(i == m)
216 break;
217 }
218 }
219 return n;
220 }
221
222 template <typename T>
223 template <typename U>
Put0(U && k,dword sh)224 int Index<T>::Put0(U&& k, dword sh)
225 {
226 int i;
227 if(HasUnlinked()) {
228 i = hash[unlinked].prev;
229 Hash& hh = hash[i];
230 Del(unlinked, hh, i);
231 Link(map[sh & mask], hh, i);
232 hh.hash = sh;
233 key[i] = std::forward<U>(k);
234 }
235 else {
236 i = GetCount();
237 AddS(std::forward<U>(k), sh);
238 }
239 return i;
240 }
241
242 template <class T>
243 template <class U>
244 force_inline
FindPut0(U && k)245 int Index<T>::FindPut0(U&& k) {
246 dword sh = Smear(k);
247 int& m = map[sh & mask];
248 int i = m;
249 if(i >= 0)
250 do {
251 if(key[i] == k)
252 return i;
253 i = hash[i].next;
254 }
255 while(i != m);
256 return Put0(std::forward<U>(k), sh);
257 }
258
259 template <typename T>
260 template <typename U>
Set0(int ii,U && k)261 void Index<T>::Set0(int ii, U&& k)
262 {
263 Hash& hh = hash[ii];
264 if(IsUnlinked(ii))
265 Del(unlinked, hh, ii);
266 else
267 Del(map[hh.hash & mask], hh, ii);
268
269 dword sh = Smear(k);
270 hh.hash = sh;
271 Link(map[sh & mask], hh, ii);
272 key[ii] = std::forward<U>(k);
273 }
274
275 template <typename T>
276 never_inline
Sweep()277 void Index<T>::Sweep()
278 {
279 if(unlinked >= 0) {
280 int n = key.GetCount();
281 key.RemoveIf([&](int i) { return hash[i].hash == 0; });
282 IndexCommon::Sweep(n);
283 }
284 }
285
286 template <typename T>
287 never_inline
Reserve(int n)288 void Index<T>::Reserve(int n)
289 {
290 int a = key.GetAlloc();
291 key.Reserve(n);
292 if(a != key.GetAlloc()) {
293 ReallocHash(key.GetCount());
294 AdjustMap(key.GetCount(), n);
295 }
296 }
297
298 template <typename T>
299 never_inline
Shrink()300 void Index<T>::Shrink()
301 {
302 int a = key.GetAlloc();
303 key.Shrink();
304 if(a != key.GetAlloc()) {
305 ReallocHash(key.GetCount());
306 AdjustMap(key.GetCount(), key.GetCount());
307 }
308 }
309
310 template <typename T>
Remove(const int * sorted_list,int count)311 void Index<T>::Remove(const int *sorted_list, int count)
312 {
313 if(HasUnlinked()) {
314 Vector<bool> u;
315 u.SetCount(GetCount());
316 for(int i = 0; i < GetCount(); i++)
317 u[i] = IsUnlinked(i);
318 key.Remove(sorted_list, count);
319 u.Remove(sorted_list, count);
320 FixHash(false);
321 for(int i = 0; i < GetCount(); i++)
322 if(u[i])
323 Unlink(i);
324 }
325 else {
326 key.Remove(sorted_list, count);
327 FixHash(false);
328 }
329 }
330
331 template <typename T>
332 never_inline
Serialize(Stream & s)333 void Index<T>::Serialize(Stream& s)
334 {
335 key.Serialize(s);
336 if(s.IsLoading())
337 FixHash();
338
339 int version = 1;
340 s / version;
341 if(version == 0) { // support previous version
342 Vector<unsigned> h;
343 h.Serialize(s);
344 if(s.IsLoading())
345 for(int i = 0; i < h.GetCount(); i++)
346 if(h[i] & 0x80000000)
347 Unlink(i);
348 }
349 else {
350 Vector<int> u = GetUnlinked();
351 u.Serialize(s);
352 if(s.IsLoading())
353 for(int i : ReverseRange(u)) // Reverse range to ensure the correct order of Put
354 Unlink(i);
355 }
356 }
357
358 template <class T>
Xmlize(XmlIO & xio,const char * itemtag)359 void Index<T>::Xmlize(XmlIO& xio, const char *itemtag)
360 {
361 XmlizeIndex<T, Index<T> >(xio, itemtag, *this);
362 }
363
364 template <class T>
Jsonize(JsonIO & jio)365 void Index<T>::Jsonize(JsonIO& jio)
366 {
367 JsonizeIndex<Index<T>, T>(jio, *this);
368 }
369
370 template <class T>
ToString() const371 String Index<T>::ToString() const
372 {
373 return AsStringArray(*this);
374 }
375
376 #ifdef _DEBUG
377 template <typename T>
Dump() const378 String Index<T>::Dump() const
379 {
380 String h;
381 for(int i = 0; i < key.GetCount(); i++) {
382 if(i)
383 h << "; ";
384 if(IsUnlinked(i))
385 h << "#";
386 h << i << ": " << key[i] << '/' << (hash[i].hash & mask) << " -> " << hash[i].prev << ":" << hash[i].next;
387 }
388 return h;
389 }
390 #endif