Line data Source code
1 : /*
2 : * SPDX-License-Identifier: MPL-2.0
3 : *
4 : * This Source Code Form is subject to the terms of the Mozilla Public
5 : * License, v. 2.0. If a copy of the MPL was not distributed with this
6 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7 : *
8 : * Copyright 2024 MonetDB Foundation;
9 : * Copyright August 2008 - 2023 MonetDB B.V.;
10 : * Copyright 1997 - July 2008 CWI.
11 : */
12 :
13 : /*
14 : * - Hash Table Creation
15 : * The hash indexing scheme for BATs reserves a block of memory to
16 : * maintain the hash table and a collision list. A one-to-one mapping
17 : * exists between the BAT and the collision list using the BUN
18 : * index. NOTE: we alloc the link list as a parallel array to the BUN
19 : * array; hence the hash link array has the same size as
20 : * BATcapacity(b) (not BATcount(b)). This allows us in the BUN insert
21 : * and delete to assume that there is hash space if there is BUN
22 : * space.
23 : *
24 : * The hash mask size is a power of two, so we can do bitwise AND on
25 : * the hash (integer) number to quickly find the head of the bucket
26 : * chain. Clearly, the hash mask size is a crucial parameter. If we
27 : * know that the column is unique (tkey), we use direct hashing (mask
28 : * size ~= BATcount). Otherwise we dynamically determine the mask size
29 : * by starting out with mask size = BATcount/64 (just 1.5% of memory
30 : * storage overhead). Then we start building the hash table on the
31 : * first 25% of the BAT. As we aim for max-collisions list length of
32 : * 4, the list on 25% should not exceed length 1. So, if a small
33 : * number of collisssions occurs (mask/2) then we abandon the attempt
34 : * and restart with a mask that is 4 times larger. This converges
35 : * after three cycles to direct hashing.
36 : */
37 :
38 : #include "monetdb_config.h"
39 : #include "gdk.h"
40 : #include "gdk_private.h"
41 :
42 : __attribute__((__const__))
43 : static inline uint8_t
44 1325940 : HASHwidth(BUN hashsize)
45 : {
46 1325940 : (void) hashsize;
47 : #ifdef BUN2
48 1325940 : if (hashsize <= (BUN) BUN2_NONE)
49 : return BUN2;
50 : #endif
51 : #ifdef BUN8
52 680 : if (hashsize > (BUN) BUN4_NONE)
53 0 : return BUN8;
54 : #endif
55 : return BUN4;
56 : }
57 :
58 : __attribute__((__const__))
59 : static inline BUN
60 5648 : hashmask(BUN m)
61 : {
62 5648 : m |= m >> 1;
63 5648 : m |= m >> 2;
64 5648 : m |= m >> 4;
65 5648 : m |= m >> 8;
66 5648 : m |= m >> 16;
67 : #if SIZEOF_BUN == 8
68 5648 : m |= m >> 32;
69 : #endif
70 5648 : return m;
71 : }
72 :
73 : static inline void
74 837547 : HASHclear(Hash *h)
75 : {
76 : /* since BUN2_NONE, BUN4_NONE, BUN8_NONE
77 : * are all equal to ~0, i.e., have all bits set,
78 : * we can use a simple memset() to clear the Hash,
79 : * rather than iteratively assigning individual
80 : * BUNi_NONE values in a for-loop
81 : */
82 837547 : memset(h->Bckt, 0xFF, h->nbucket * h->width);
83 837547 : }
84 :
85 : #define HASH_VERSION 6
86 : #define HASH_HEADER_SIZE 7 /* nr of size_t fields in header */
87 :
88 : void
89 21398149 : doHASHdestroy(BAT *b, Hash *hs)
90 : {
91 21398149 : if (hs == (Hash *) 1) {
92 14 : GDKunlink(BBPselectfarm(b->batRole, b->ttype, hashheap),
93 : BATDIR,
94 14 : BBP_physical(b->batCacheid),
95 : "thashl");
96 14 : GDKunlink(BBPselectfarm(b->batRole, b->ttype, hashheap),
97 : BATDIR,
98 14 : BBP_physical(b->batCacheid),
99 : "thashb");
100 21398135 : } else if (hs) {
101 9255 : TRC_DEBUG(ACCELERATOR, ALGOBATFMT ": removing%s hash\n", ALGOBATPAR(b), *(size_t *) hs->heapbckt.base & (1 << 24) ? " persisted" : "");
102 9255 : HEAPfree(&hs->heapbckt, true);
103 9268 : HEAPfree(&hs->heaplink, true);
104 9268 : GDKfree(hs);
105 : }
106 21398162 : }
107 :
108 : gdk_return
109 837522 : HASHnew(Hash *h, int tpe, BUN size, BUN mask, BUN count, bool bcktonly)
110 : {
111 837522 : if (h->width == 0)
112 827276 : h->width = HASHwidth(size);
113 :
114 837522 : if (!bcktonly) {
115 826658 : if (HEAPalloc(&h->heaplink, size, h->width) != GDK_SUCCEED)
116 : return GDK_FAIL;
117 826678 : h->heaplink.free = size * h->width;
118 826678 : h->heaplink.dirty = true;
119 826678 : h->Link = h->heaplink.base;
120 : }
121 837542 : if (HEAPalloc(&h->heapbckt, mask + HASH_HEADER_SIZE * SIZEOF_SIZE_T / h->width, h->width) != GDK_SUCCEED) {
122 0 : if (!bcktonly) {
123 0 : HEAPfree(&h->heaplink, true);
124 0 : h->heaplink.free = 0;
125 0 : h->Link = NULL;
126 : }
127 0 : return GDK_FAIL;
128 : }
129 837554 : h->heapbckt.free = mask * h->width + HASH_HEADER_SIZE * SIZEOF_SIZE_T;
130 837554 : h->heapbckt.dirty = true;
131 837554 : h->nbucket = mask;
132 837554 : if (mask & (mask - 1)) {
133 5548 : h->mask2 = hashmask(mask);
134 5548 : h->mask1 = h->mask2 >> 1;
135 : } else {
136 : /* mask is a power of two */
137 832006 : h->mask1 = mask - 1;
138 832006 : h->mask2 = h->mask1 << 1 | 1;
139 : }
140 837554 : h->Bckt = h->heapbckt.base + HASH_HEADER_SIZE * SIZEOF_SIZE_T;
141 837554 : h->type = tpe;
142 837554 : HASHclear(h); /* zero the mask */
143 837565 : ((size_t *) h->heapbckt.base)[0] = (size_t) HASH_VERSION;
144 837565 : ((size_t *) h->heapbckt.base)[1] = (size_t) size;
145 837565 : ((size_t *) h->heapbckt.base)[2] = (size_t) h->nbucket;
146 837565 : ((size_t *) h->heapbckt.base)[3] = (size_t) h->width;
147 837565 : ((size_t *) h->heapbckt.base)[4] = (size_t) count;
148 837565 : ((size_t *) h->heapbckt.base)[5] = (size_t) h->nunique;
149 837565 : ((size_t *) h->heapbckt.base)[6] = (size_t) h->nheads;
150 837565 : TRC_DEBUG(ACCELERATOR,
151 : "create hash(size " BUNFMT ", mask " BUNFMT ", width %d, total " BUNFMT " bytes);\n", size, mask, h->width, (size + mask) * h->width);
152 : return GDK_SUCCEED;
153 : }
154 :
155 : /* collect HASH statistics for analysis */
156 : static void
157 0 : HASHcollisions(BAT *b, Hash *h, const char *func)
158 : {
159 0 : lng cnt, entries = 0, max = 0;
160 0 : double total = 0;
161 0 : BUN p, i, j;
162 :
163 0 : if (b == 0 || h == 0)
164 : return;
165 0 : for (i = 0, j = h->nbucket; i < j; i++)
166 0 : if ((p = HASHget(h, i)) != BUN_NONE) {
167 0 : entries++;
168 0 : cnt = 0;
169 0 : for (; p != BUN_NONE; p = HASHgetlink(h, p))
170 0 : cnt++;
171 0 : if (cnt > max)
172 : max = cnt;
173 0 : total += cnt;
174 : }
175 0 : TRC_DEBUG_ENDIF(ACCELERATOR,
176 : "%s(" ALGOBATFMT "): statistics " BUNFMT ", "
177 : "entries " LLFMT ", nunique " BUNFMT ", "
178 : "nbucket " BUNFMT ", max " LLFMT ", avg %2.6f;\n",
179 : func, ALGOBATPAR(b), BATcount(b), entries,
180 : h->nunique, h->nbucket, max,
181 : entries == 0 ? 0 : total / entries);
182 : }
183 :
184 : static gdk_return
185 0 : HASHupgradehashheap(BAT *b)
186 : {
187 : #if defined(BUN2) || defined(BUN8)
188 0 : Hash *h = b->thash;
189 0 : int nwidth = h->width << 1;
190 0 : BUN i;
191 :
192 0 : assert(nwidth <= SIZEOF_BUN);
193 0 : assert((nwidth & (nwidth - 1)) == 0);
194 :
195 0 : if (HEAPextend(&h->heaplink, h->heaplink.size * nwidth / h->width, true) != GDK_SUCCEED ||
196 0 : HEAPextend(&h->heapbckt, (h->heapbckt.size - HASH_HEADER_SIZE * SIZEOF_SIZE_T) * nwidth / h->width + HASH_HEADER_SIZE * SIZEOF_SIZE_T, true) != GDK_SUCCEED) {
197 0 : b->thash = NULL;
198 0 : doHASHdestroy(b, h);
199 0 : return GDK_FAIL;
200 : }
201 0 : h->Link = h->heaplink.base;
202 0 : h->Bckt = h->heapbckt.base + HASH_HEADER_SIZE * SIZEOF_SIZE_T;
203 0 : switch (nwidth) {
204 0 : case BUN4:
205 : #ifdef BUN2
206 0 : switch (h->width) {
207 0 : case BUN2:
208 0 : i = h->heaplink.free / h->width;
209 0 : h->heaplink.free = i * nwidth;
210 0 : while (i > 0) {
211 0 : i--;
212 0 : BUN2type v = ((BUN2type *) h->Link)[i];
213 0 : ((BUN4type *) h->Link)[i] = v == BUN2_NONE ? BUN4_NONE : v;
214 : }
215 0 : i = (h->heapbckt.free - HASH_HEADER_SIZE * SIZEOF_SIZE_T) / h->width;
216 0 : h->heapbckt.free = HASH_HEADER_SIZE * SIZEOF_SIZE_T + i * nwidth;
217 0 : while (i > 0) {
218 0 : i--;
219 0 : BUN2type v = ((BUN2type *) h->Bckt)[i];
220 0 : ((BUN4type *) h->Bckt)[i] = v == BUN2_NONE ? BUN4_NONE : v;
221 : }
222 0 : h->heapbckt.dirty = true;
223 0 : h->heaplink.dirty = true;
224 0 : break;
225 : }
226 : #endif
227 : break;
228 : #ifdef BUN8
229 0 : case BUN8:
230 0 : switch (h->width) {
231 : #ifdef BUN2
232 0 : case BUN2:
233 0 : i = h->heaplink.free / h->width;
234 0 : h->heaplink.free = i * nwidth;
235 0 : while (i > 0) {
236 0 : i--;
237 0 : BUN2type v = ((BUN2type *) h->Link)[i];
238 0 : ((BUN8type *) h->Link)[i] = v == BUN2_NONE ? BUN8_NONE : v;
239 : }
240 0 : i = (h->heapbckt.free - HASH_HEADER_SIZE * SIZEOF_SIZE_T) / h->width;
241 0 : h->heapbckt.free = HASH_HEADER_SIZE * SIZEOF_SIZE_T + i * nwidth;
242 0 : while (i > 0) {
243 0 : i--;
244 0 : BUN2type v = ((BUN2type *) h->Bckt)[i];
245 0 : ((BUN8type *) h->Bckt)[i] = v == BUN2_NONE ? BUN8_NONE : v;
246 : }
247 0 : h->heapbckt.dirty = true;
248 0 : h->heaplink.dirty = true;
249 0 : break;
250 : #endif
251 0 : case BUN4:
252 0 : i = h->heaplink.free / h->width;
253 0 : h->heaplink.free = i * nwidth;
254 0 : while (i > 0) {
255 0 : i--;
256 0 : BUN4type v = ((BUN4type *) h->Link)[i];
257 0 : ((BUN8type *) h->Link)[i] = v == BUN4_NONE ? BUN8_NONE : v;
258 : }
259 0 : i = (h->heapbckt.free - HASH_HEADER_SIZE * SIZEOF_SIZE_T) / h->width;
260 0 : h->heapbckt.free = HASH_HEADER_SIZE * SIZEOF_SIZE_T + i * nwidth;
261 0 : while (i > 0) {
262 0 : i--;
263 0 : BUN4type v = ((BUN4type *) h->Bckt)[i];
264 0 : ((BUN8type *) h->Bckt)[i] = v == BUN4_NONE ? BUN8_NONE : v;
265 : }
266 0 : h->heapbckt.dirty = true;
267 0 : h->heaplink.dirty = true;
268 0 : break;
269 : }
270 : break;
271 : #endif
272 : }
273 0 : h->width = nwidth;
274 : #else
275 : (void) b;
276 : #endif
277 0 : return GDK_SUCCEED;
278 : }
279 :
280 : /* write/remove the bit into/from the hash file that indicates the hash
281 : * is good to go; the bit is the last part to be written and the first
282 : * to be removed */
283 : static inline gdk_return
284 507521 : HASHfix(Hash *h, bool save, bool dosync)
285 : {
286 507521 : if (!h->heapbckt.dirty && !h->heaplink.dirty) {
287 24001 : const size_t mask = (size_t) 1 << 24;
288 24001 : if (((size_t *) h->heapbckt.base)[0] & mask) {
289 10579 : if (save)
290 : return GDK_SUCCEED;
291 10579 : ((size_t *) h->heapbckt.base)[0] &= ~mask;
292 : } else {
293 13422 : if (!save)
294 : return GDK_SUCCEED;
295 13422 : ((size_t *) h->heapbckt.base)[0] |= mask;
296 : }
297 24001 : if (h->heapbckt.storage == STORE_MEM) {
298 23995 : gdk_return rc = GDK_FAIL;
299 23995 : int fd = GDKfdlocate(h->heapbckt.farmid, h->heapbckt.filename, "rb+", NULL);
300 23995 : if (fd >= 0) {
301 23995 : if (write(fd, h->heapbckt.base, SIZEOF_SIZE_T) == SIZEOF_SIZE_T) {
302 23995 : if (dosync &&
303 23995 : !(ATOMIC_GET(&GDKdebug) & NOSYNCMASK)) {
304 : #if defined(NATIVE_WIN32)
305 : _commit(fd);
306 : #elif defined(HAVE_FDATASYNC)
307 37 : fdatasync(fd);
308 : #elif defined(HAVE_FSYNC)
309 : fsync(fd);
310 : #endif
311 : }
312 : rc = GDK_SUCCEED;
313 : }
314 23995 : close(fd);
315 : }
316 23995 : if (rc != GDK_SUCCEED)
317 0 : ((size_t *) h->heapbckt.base)[0] &= ~mask;
318 23995 : return rc;
319 : } else {
320 6 : if (dosync &&
321 10 : !(ATOMIC_GET(&GDKdebug) & NOSYNCMASK) &&
322 5 : MT_msync(h->heapbckt.base, SIZEOF_SIZE_T) < 0) {
323 0 : ((size_t *) h->heapbckt.base)[0] &= ~mask;
324 0 : return GDK_FAIL;
325 : }
326 : }
327 : }
328 : return GDK_SUCCEED;
329 : }
330 :
331 : static gdk_return
332 488392 : HASHgrowbucket(BAT *b)
333 : {
334 488392 : Hash *h = b->thash;
335 488392 : BUN nbucket;
336 488392 : BUN onbucket = h->nbucket;
337 488392 : lng t0 = 0;
338 :
339 488392 : TRC_DEBUG_IF(ACCELERATOR) t0 = GDKusec();
340 :
341 : /* only needed to fix hash tables built before this fix was
342 : * introduced */
343 488392 : if (h->width < SIZEOF_BUN &&
344 488392 : ((BUN) 1 << (h->width * 8)) - 1 <= h->mask2 &&
345 0 : HASHupgradehashheap(b) != GDK_SUCCEED)
346 : return GDK_FAIL;
347 :
348 488392 : h->heapbckt.dirty = true;
349 488392 : h->heaplink.dirty = true;
350 742863 : while (h->nunique >= (nbucket = h->nbucket) * 7 / 8) {
351 254471 : BUN new = h->nbucket;
352 254471 : BUN old = new & h->mask1;
353 254471 : BUN mask = h->mask1 + 1; /* == h->mask2 - h->mask1 */
354 :
355 254471 : assert(h->heapbckt.free == nbucket * h->width + HASH_HEADER_SIZE * SIZEOF_SIZE_T);
356 254471 : if (h->heapbckt.free + h->width > h->heapbckt.size) {
357 3825 : if (HEAPextend(&h->heapbckt,
358 : h->heapbckt.size + GDK_mmap_pagesize,
359 : true) != GDK_SUCCEED) {
360 0 : return GDK_FAIL;
361 : }
362 3825 : h->Bckt = h->heapbckt.base + HASH_HEADER_SIZE * SIZEOF_SIZE_T;
363 : }
364 254471 : assert(h->heapbckt.free + h->width <= h->heapbckt.size);
365 254471 : if (h->nbucket == h->mask2) {
366 239 : h->mask1 = h->mask2;
367 239 : h->mask2 |= h->mask2 << 1;
368 239 : if (h->width < SIZEOF_BUN &&
369 239 : h->mask2 == ((BUN) 1 << (h->width * 8)) - 1) {
370 : /* time to widen the hash table */
371 0 : if (HASHupgradehashheap(b) != GDK_SUCCEED)
372 : return GDK_FAIL;
373 : }
374 : }
375 254471 : h->nbucket++;
376 254471 : h->heapbckt.free += h->width;
377 254471 : BUN lold, lnew, hb;
378 254471 : lold = lnew = BUN_NONE;
379 254471 : BATiter bi = bat_iterator(b);
380 254471 : if ((hb = HASHget(h, old)) != BUN_NONE) {
381 204551 : h->nheads--;
382 326569 : do {
383 326569 : const void *v = BUNtail(bi, hb);
384 326569 : BUN hsh = ATOMhash(h->type, v);
385 326569 : assert((hsh & (mask - 1)) == old);
386 326569 : if (hsh & mask) {
387 : /* move to new list */
388 125142 : if (lnew == BUN_NONE) {
389 109238 : HASHput(h, new, hb);
390 109238 : h->nheads++;
391 : } else
392 15904 : HASHputlink(h, lnew, hb);
393 : lnew = hb;
394 : } else {
395 : /* move to old list */
396 201427 : if (lold == BUN_NONE) {
397 153774 : h->nheads++;
398 153774 : HASHput(h, old, hb);
399 : } else
400 47653 : HASHputlink(h, lold, hb);
401 : lold = hb;
402 : }
403 326569 : hb = HASHgetlink(h, hb);
404 326569 : } while (hb != BUN_NONE);
405 : }
406 254471 : bat_iterator_end(&bi);
407 254471 : if (lnew == BUN_NONE)
408 145233 : HASHput(h, new, BUN_NONE);
409 : else
410 109238 : HASHputlink(h, lnew, BUN_NONE);
411 254471 : if (lold == BUN_NONE)
412 100697 : HASHput(h, old, BUN_NONE);
413 : else
414 153774 : HASHputlink(h, lold, BUN_NONE);
415 : }
416 488392 : TRC_DEBUG_IF(ACCELERATOR) if (h->nbucket > onbucket) {
417 0 : TRC_DEBUG_ENDIF(ACCELERATOR, ALGOBATFMT " " BUNFMT
418 : " -> " BUNFMT " buckets (" LLFMT " usec)\n",
419 : ALGOBATPAR(b),
420 : onbucket, h->nbucket, GDKusec() - t0);
421 0 : HASHcollisions(b, h, __func__);
422 : }
423 : return GDK_SUCCEED;
424 : }
425 :
426 : /* Return TRUE if we have a hash on the tail, even if we need to read
427 : * one from disk.
428 : *
429 : * Note that the b->thash pointer can be NULL, meaning there is no
430 : * hash; (Hash *) 1, meaning there is no hash loaded, but it may exist
431 : * on disk; or a valid pointer to a loaded hash. These values are
432 : * maintained here, in the HASHdestroy and HASHfree functions, and in
433 : * BBPdiskscan during initialization. */
434 : bool
435 59751293 : BATcheckhash(BAT *b)
436 : {
437 59751293 : lng t = 0;
438 59751293 : Hash *h;
439 :
440 59751293 : MT_rwlock_rdlock(&b->thashlock);
441 59803218 : h = b->thash;
442 59803218 : MT_rwlock_rdunlock(&b->thashlock);
443 59789718 : if (h == (Hash *) 1) {
444 : /* but when we want to change it, we need the lock */
445 219 : TRC_DEBUG_IF(ACCELERATOR) t = GDKusec();
446 219 : MT_rwlock_wrlock(&b->thashlock);
447 219 : TRC_DEBUG_IF(ACCELERATOR) t = GDKusec() - t;
448 : /* if still 1 now that we have the lock, we can update */
449 219 : if (b->thash == (Hash *) 1) {
450 219 : int fd;
451 :
452 219 : assert(!GDKinmemory(b->theap->farmid));
453 219 : b->thash = NULL;
454 219 : if ((h = GDKzalloc(sizeof(*h))) != NULL &&
455 219 : (h->heaplink.farmid = BBPselectfarm(b->batRole, b->ttype, hashheap)) >= 0 &&
456 219 : (h->heapbckt.farmid = BBPselectfarm(b->batRole, b->ttype, hashheap)) >= 0) {
457 219 : const char *nme = BBP_physical(b->batCacheid);
458 219 : strconcat_len(h->heaplink.filename,
459 : sizeof(h->heaplink.filename),
460 : nme, ".thashl", NULL);
461 219 : strconcat_len(h->heapbckt.filename,
462 : sizeof(h->heapbckt.filename),
463 : nme, ".thashb", NULL);
464 219 : h->heaplink.storage = STORE_INVALID;
465 219 : h->heaplink.newstorage = STORE_INVALID;
466 219 : h->heapbckt.storage = STORE_INVALID;
467 219 : h->heapbckt.newstorage = STORE_INVALID;
468 :
469 : /* check whether a persisted hash can be found */
470 219 : if ((fd = GDKfdlocate(h->heapbckt.farmid, nme, "rb+", "thashb")) >= 0) {
471 219 : size_t hdata[HASH_HEADER_SIZE];
472 219 : struct stat st;
473 :
474 219 : if (read(fd, hdata, sizeof(hdata)) == sizeof(hdata) &&
475 219 : (hdata[0] == (((size_t) 1 << 24) | HASH_VERSION)) &&
476 200 : hdata[1] > 0 &&
477 : (
478 : #ifdef BUN2
479 200 : hdata[3] == BUN2 ||
480 : #endif
481 : hdata[3] == BUN4
482 : #ifdef BUN8
483 : || hdata[3] == BUN8
484 : #endif
485 200 : ) &&
486 400 : hdata[4] == (size_t) BATcount(b) &&
487 200 : fstat(fd, &st) == 0 &&
488 400 : st.st_size >= (off_t) (h->heapbckt.size = h->heapbckt.free = (h->nbucket = (BUN) hdata[2]) * (BUN) (h->width = (uint8_t) hdata[3]) + HASH_HEADER_SIZE * SIZEOF_SIZE_T) &&
489 200 : close(fd) == 0 &&
490 400 : (fd = GDKfdlocate(h->heaplink.farmid, nme, "rb+", "thashl")) >= 0 &&
491 200 : fstat(fd, &st) == 0 &&
492 200 : st.st_size > 0 &&
493 400 : st.st_size >= (off_t) (h->heaplink.size = h->heaplink.free = hdata[1] * h->width) &&
494 200 : HEAPload(&h->heaplink, nme, "thashl", false) == GDK_SUCCEED) {
495 200 : if (HEAPload(&h->heapbckt, nme, "thashb", false) == GDK_SUCCEED) {
496 200 : if (h->nbucket & (h->nbucket - 1)) {
497 100 : h->mask2 = hashmask(h->nbucket);
498 100 : h->mask1 = h->mask2 >> 1;
499 : } else {
500 100 : h->mask1 = h->nbucket - 1;
501 100 : h->mask2 = h->mask1 << 1 | 1;
502 : }
503 200 : h->nunique = hdata[5];
504 200 : h->nheads = hdata[6];
505 200 : h->type = ATOMtype(b->ttype);
506 200 : if (h->width < SIZEOF_BUN &&
507 200 : ((BUN) 1 << (8 * h->width)) - 1 > h->nbucket) {
508 200 : close(fd);
509 200 : h->Link = h->heaplink.base;
510 200 : h->Bckt = h->heapbckt.base + HASH_HEADER_SIZE * SIZEOF_SIZE_T;
511 200 : h->heaplink.parentid = b->batCacheid;
512 200 : h->heapbckt.parentid = b->batCacheid;
513 200 : h->heaplink.dirty = false;
514 200 : h->heapbckt.dirty = false;
515 200 : b->thash = h;
516 200 : h->heapbckt.hasfile = true;
517 200 : h->heaplink.hasfile = true;
518 200 : TRC_DEBUG(ACCELERATOR,
519 : ALGOBATFMT ": reusing persisted hash\n", ALGOBATPAR(b));
520 200 : MT_rwlock_wrunlock(&b->thashlock);
521 200 : return true;
522 : }
523 : /* if h->nbucket
524 : * equals the
525 : * BUN_NONE
526 : * representation
527 : * for the
528 : * current hash
529 : * width (was
530 : * possible in
531 : * previous
532 : * iterations of
533 : * the code),
534 : * then we can't
535 : * use the hash
536 : * since we
537 : * can't
538 : * distinguish
539 : * between
540 : * end-of-list
541 : * and a valid
542 : * link */
543 0 : HEAPfree(&h->heapbckt, false);
544 : }
545 0 : HEAPfree(&h->heaplink, false);
546 : }
547 19 : close(fd);
548 : /* unlink unusable file */
549 19 : GDKunlink(h->heaplink.farmid, BATDIR, nme, "thashl");
550 19 : GDKunlink(h->heapbckt.farmid, BATDIR, nme, "thashb");
551 19 : h->heapbckt.hasfile = false;
552 19 : h->heaplink.hasfile = false;
553 : }
554 : }
555 19 : GDKfree(h);
556 19 : GDKclrerr(); /* we're not currently interested in errors */
557 : }
558 19 : h = b->thash;
559 19 : MT_rwlock_wrunlock(&b->thashlock);
560 : }
561 59789518 : if (h != NULL) {
562 3671219 : TRC_DEBUG(ACCELERATOR, ALGOBATFMT ": already has hash, waited " LLFMT " usec\n", ALGOBATPAR(b), t);
563 : }
564 59789518 : return h != NULL;
565 : }
566 :
567 : /* figure out size of the hash (sum of the sizes of the two hash files)
568 : * without loading them */
569 : size_t
570 33245 : HASHsize(BAT *b)
571 : {
572 33245 : size_t sz = 0;
573 33245 : MT_rwlock_rdlock(&b->thashlock);
574 33245 : if (b->thash == NULL) {
575 : sz = 0;
576 1812 : } else if (b->thash != (Hash *) 1) {
577 1812 : sz = b->thash->heaplink.size + b->thash->heapbckt.size;
578 : } else {
579 0 : int farmid = BBPselectfarm(b->batRole, b->ttype, hashheap);
580 0 : if (farmid >= 0) {
581 0 : const char *nme = BBP_physical(b->batCacheid);
582 0 : char *fname = GDKfilepath(farmid, BATDIR, nme, "thashb");
583 0 : if (fname != NULL) {
584 0 : struct stat st;
585 0 : if (stat(fname, &st) == 0) {
586 0 : sz = (size_t) st.st_size;
587 0 : fname[strlen(fname) - 1] = 'l';
588 0 : if (stat(fname, &st) == 0)
589 0 : sz += (size_t) st.st_size;
590 : else
591 : sz = 0;
592 : }
593 0 : GDKfree(fname);
594 : }
595 : }
596 : }
597 33245 : MT_rwlock_rdunlock(&b->thashlock);
598 33245 : return sz;
599 : }
600 :
601 : static void
602 14058 : BAThashsave_intern(BAT *b, bool dosync)
603 : {
604 14058 : Hash *h;
605 14058 : lng t0 = 0;
606 :
607 14058 : TRC_DEBUG_IF(ACCELERATOR) t0 = GDKusec();
608 :
609 14058 : if ((h = b->thash) != NULL) {
610 : /* only persist if parent BAT hasn't changed in the
611 : * mean time */
612 14058 : if (!b->theap->dirty &&
613 13422 : ((size_t *) h->heapbckt.base)[1] == BATcount(b) &&
614 26844 : ((size_t *) h->heapbckt.base)[4] == BATcount(b) &&
615 26844 : HEAPsave(&h->heaplink, h->heaplink.filename, NULL, dosync, h->heaplink.free, NULL) == GDK_SUCCEED &&
616 13422 : HEAPsave(&h->heapbckt, h->heapbckt.filename, NULL, dosync, h->heapbckt.free, NULL) == GDK_SUCCEED) {
617 13422 : h->heaplink.dirty = false;
618 13422 : h->heapbckt.dirty = false;
619 13422 : h->heaplink.hasfile = true;
620 13422 : h->heapbckt.hasfile = true;
621 13422 : gdk_return rc = HASHfix(h, true, dosync);
622 13422 : TRC_DEBUG(ACCELERATOR,
623 : ALGOBATFMT ": persisting hash %s%s (" LLFMT " usec)%s\n", ALGOBATPAR(b), h->heapbckt.filename, dosync ? "" : " no sync", GDKusec() - t0, rc == GDK_SUCCEED ? "" : " failed");
624 : }
625 14058 : GDKclrerr();
626 : }
627 14058 : }
628 :
629 : void
630 14058 : BAThashsave(BAT *b, bool dosync)
631 : {
632 14058 : Hash *h = b->thash;
633 14058 : if (h == NULL)
634 : return;
635 14058 : ((size_t *) h->heapbckt.base)[0] = (size_t) HASH_VERSION;
636 14058 : ((size_t *) h->heapbckt.base)[1] = (size_t) (h->heaplink.free / h->width);
637 14058 : ((size_t *) h->heapbckt.base)[2] = (size_t) h->nbucket;
638 14058 : ((size_t *) h->heapbckt.base)[3] = (size_t) h->width;
639 14058 : ((size_t *) h->heapbckt.base)[4] = (size_t) BATcount(b);
640 14058 : ((size_t *) h->heapbckt.base)[5] = (size_t) h->nunique;
641 14058 : ((size_t *) h->heapbckt.base)[6] = (size_t) h->nheads;
642 14058 : BAThashsave_intern(b, dosync);
643 : }
644 :
645 : #define EQbte(a, b) ((a) == (b))
646 : #define EQsht(a, b) ((a) == (b))
647 : #define EQint(a, b) ((a) == (b))
648 : #define EQlng(a, b) ((a) == (b))
649 : #ifdef HAVE_HGE
650 : #define EQhge(a, b) ((a) == (b))
651 : #endif
652 : #define EQflt(a, b) (is_flt_nil(a) ? is_flt_nil(b) : (a) == (b))
653 : #define EQdbl(a, b) (is_dbl_nil(a) ? is_dbl_nil(b) : (a) == (b))
654 : #ifdef HAVE_HGE
655 : #define EQuuid(a, b) ((a).h == (b).h)
656 : #else
657 : #define EQuuid(a, b) (memcmp((a).u, (b).u, UUID_SIZE) == 0)
658 : #endif
659 :
660 : #define starthash(TYPE) \
661 : do { \
662 : const TYPE *restrict v = (const TYPE *) BUNtloc(bi, 0); \
663 : TIMEOUT_LOOP(p, qry_ctx) { \
664 : hget = HASHget(h, c); \
665 : if (hget == BUN_NONE) { \
666 : if (h->nheads == maxslots) \
667 : TIMEOUT_LOOP_BREAK; /* mask too full */ \
668 : h->nheads++; \
669 : h->nunique++; \
670 : } else { \
671 : for (hb = hget; \
672 : hb != BUN_NONE; \
673 : hb = HASHgetlink(h, hb)) { \
674 : if (EQ##TYPE(v[o - b->hseqbase], v[hb])) \
675 : break; \
676 : } \
677 : h->nunique += hb == BUN_NONE; \
678 : } \
679 : HASHputlink(h, p, hget); \
680 : HASHput(h, c, p); \
681 : o = canditer_next(ci); \
682 : } \
683 : TIMEOUT_CHECK(qry_ctx, \
684 : GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx)); \
685 : } while (0)
686 : #define finishhash(TYPE) \
687 : do { \
688 : const TYPE *restrict v = (const TYPE *) BUNtloc(bi, 0); \
689 : TIMEOUT_LOOP(ci->ncand - p, qry_ctx) { \
690 : c = hash_##TYPE(h, v + o - b->hseqbase); \
691 : hget = HASHget(h, c); \
692 : h->nheads += hget == BUN_NONE; \
693 : if (!hascand) { \
694 : for (hb = hget; \
695 : hb != BUN_NONE; \
696 : hb = HASHgetlink(h, hb)) { \
697 : if (EQ##TYPE(v[o - b->hseqbase], v[hb])) \
698 : break; \
699 : } \
700 : h->nunique += hb == BUN_NONE; \
701 : o = canditer_next_dense(ci); \
702 : } else { \
703 : o = canditer_next(ci); \
704 : } \
705 : HASHputlink(h, p, hget); \
706 : HASHput(h, c, p); \
707 : p++; \
708 : } \
709 : TIMEOUT_CHECK(qry_ctx, \
710 : GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx)); \
711 : } while (0)
712 :
713 : /* Internal function to create a hash table for the given BAT b.
714 : * If a candidate list s is also given, the hash table is specific for
715 : * the combination of the two: only values from b that are referred to
716 : * by s are included in the hash table, so if a result is found when
717 : * searching the hash table, the result is a candidate. */
718 : Hash *
719 10887 : BAThash_impl(BAT *restrict b, struct canditer *restrict ci, const char *restrict ext)
720 : {
721 10887 : lng t0 = 0;
722 10887 : BUN cnt1;
723 10887 : BUN mask, maxmask = 0;
724 10887 : BUN p, c;
725 10887 : oid o;
726 10887 : BUN hget, hb;
727 10887 : Hash *h = NULL;
728 10887 : const char *nme = GDKinmemory(b->theap->farmid) ? ":memory:" : BBP_physical(b->batCacheid);
729 10888 : BATiter bi = bat_iterator(b);
730 10888 : unsigned int tpe = ATOMbasetype(bi.type);
731 10888 : bool hascand = ci->tpe != cand_dense || ci->ncand != bi.count;
732 :
733 10888 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
734 :
735 10892 : assert(strcmp(ext, "thash") != 0 || !hascand);
736 10892 : assert(bi.type != TYPE_msk);
737 :
738 21642 : MT_thread_setalgorithm(hascand ? "create hash with candidates" : "create hash");
739 10898 : TRC_DEBUG_IF(ACCELERATOR) t0 = GDKusec();
740 10898 : TRC_DEBUG(ACCELERATOR,
741 : ALGOBATFMT ": create hash;\n", ALGOBATPAR(b));
742 10884 : if (bi.type == TYPE_void) {
743 0 : if (is_oid_nil(b->tseqbase)) {
744 0 : TRC_DEBUG(ACCELERATOR,
745 : "cannot create hash-table on void-NIL column.\n");
746 0 : GDKerror("no hash on void/nil column\n");
747 0 : bat_iterator_end(&bi);
748 0 : return NULL;
749 : }
750 0 : TRC_DEBUG(ACCELERATOR,
751 : "creating hash-table on void column..\n");
752 0 : assert(0);
753 : tpe = TYPE_void;
754 : }
755 :
756 10884 : if ((h = GDKzalloc(sizeof(*h))) == NULL ||
757 10895 : (h->heaplink.farmid = BBPselectfarm(hascand ? TRANSIENT : b->batRole, bi.type, hashheap)) < 0 ||
758 10893 : (h->heapbckt.farmid = BBPselectfarm(hascand ? TRANSIENT : b->batRole, bi.type, hashheap)) < 0) {
759 0 : GDKfree(h);
760 0 : bat_iterator_end(&bi);
761 0 : return NULL;
762 : }
763 10892 : h->width = HASHwidth(BATcapacity(b));
764 10892 : h->heaplink.dirty = true;
765 10892 : h->heapbckt.dirty = true;
766 10892 : strconcat_len(h->heaplink.filename, sizeof(h->heaplink.filename),
767 : nme, ".", ext, "l", NULL);
768 10894 : strconcat_len(h->heapbckt.filename, sizeof(h->heapbckt.filename),
769 : nme, ".", ext, "b", NULL);
770 10891 : h->heapbckt.parentid = b->batCacheid;
771 10891 : h->heaplink.parentid = b->batCacheid;
772 10891 : if (HEAPalloc(&h->heaplink, hascand ? ci->ncand : BATcapacity(b),
773 10891 : h->width) != GDK_SUCCEED) {
774 0 : GDKfree(h);
775 0 : bat_iterator_end(&bi);
776 0 : return NULL;
777 : }
778 10894 : h->heaplink.free = ci->ncand * h->width;
779 10894 : h->Link = h->heaplink.base;
780 : #ifndef NDEBUG
781 : /* clear unused part of Link array */
782 10894 : if (h->heaplink.size > h->heaplink.free)
783 9856 : memset(h->heaplink.base + h->heaplink.free, 0,
784 : h->heaplink.size - h->heaplink.free);
785 : #endif
786 :
787 : /* determine hash mask size */
788 10894 : cnt1 = 0;
789 10894 : if (ATOMsize(tpe) == 1) {
790 : /* perfect hash for one-byte sized atoms */
791 : mask = (1 << 8);
792 10884 : } else if (ATOMsize(tpe) == 2) {
793 : /* perfect hash for two-byte sized atoms */
794 : mask = (1 << 16);
795 10862 : } else if (bi.key || ci->ncand <= 4096) {
796 : /* if key, or if small, don't bother dynamically
797 : * adjusting the hash mask */
798 10748 : mask = HASHmask(ci->ncand);
799 114 : } else if (!hascand && bi.unique_est != 0) {
800 114 : mask = (BUN) (bi.unique_est * 1.15); /* about 8/7 */
801 : } else {
802 : /* dynamic hash: we start with HASHmask(ci->ncand)/64, or,
803 : * if ci->ncand large enough, HASHmask(ci->ncand)/256; if there
804 : * are too many collisions we try HASHmask(ci->ncand)/64,
805 : * HASHmask(ci->ncand)/16, HASHmask(ci->ncand)/4, and finally
806 : * HASHmask(ci->ncand), but we might skip some of these if
807 : * there are many distinct values. */
808 0 : maxmask = HASHmask(ci->ncand);
809 0 : mask = maxmask >> 6;
810 0 : while (mask > 4096)
811 0 : mask >>= 2;
812 : /* try out on first 25% of b */
813 0 : cnt1 = ci->ncand >> 2;
814 : }
815 :
816 10894 : o = canditer_next(ci); /* always one ahead */
817 0 : for (;;) {
818 10882 : lng t1 = 0;
819 10882 : TRC_DEBUG_IF(ACCELERATOR) t1 = GDKusec();
820 10882 : BUN maxslots = (mask >> 3) - 1; /* 1/8 full is too full */
821 :
822 10882 : h->nheads = 0;
823 10882 : h->nunique = 0;
824 10882 : p = 0;
825 10882 : HEAPfree(&h->heapbckt, true);
826 : /* create the hash structures */
827 21767 : if (HASHnew(h, ATOMtype(bi.type), BATcapacity(b),
828 : mask, ci->ncand, true) != GDK_SUCCEED) {
829 0 : HEAPfree(&h->heaplink, true);
830 0 : GDKfree(h);
831 0 : bat_iterator_end(&bi);
832 0 : return NULL;
833 : }
834 :
835 10865 : switch (tpe) {
836 10 : case TYPE_bte:
837 20 : starthash(bte);
838 : break;
839 22 : case TYPE_sht:
840 44 : starthash(sht);
841 : break;
842 16 : case TYPE_flt:
843 32 : starthash(flt);
844 : break;
845 9545 : case TYPE_int:
846 19088 : starthash(int);
847 : break;
848 4 : case TYPE_dbl:
849 8 : starthash(dbl);
850 : break;
851 727 : case TYPE_lng:
852 1455 : starthash(lng);
853 : break;
854 : #ifdef HAVE_HGE
855 2 : case TYPE_hge:
856 4 : starthash(hge);
857 : break;
858 : #endif
859 1 : case TYPE_uuid:
860 2 : starthash(uuid);
861 : break;
862 538 : default: {
863 538 : int (*atomcmp)(const void *, const void *) = ATOMcompare(h->type);
864 1076 : TIMEOUT_LOOP(p, qry_ctx) {
865 0 : const void *restrict v = BUNtail(bi, o - b->hseqbase);
866 0 : c = hash_any(h, v);
867 0 : hget = HASHget(h, c);
868 0 : if (hget == BUN_NONE) {
869 0 : if (h->nheads == maxslots)
870 0 : TIMEOUT_LOOP_BREAK; /* mask too full */
871 0 : h->nheads++;
872 0 : h->nunique++;
873 : } else {
874 : for (hb = hget;
875 0 : hb != BUN_NONE;
876 0 : hb = HASHgetlink(h, hb)) {
877 0 : if (atomcmp(v,
878 0 : BUNtail(bi, hb)) == 0)
879 : break;
880 : }
881 0 : h->nunique += hb == BUN_NONE;
882 : }
883 0 : HASHputlink(h, p, hget);
884 0 : HASHput(h, c, p);
885 0 : o = canditer_next(ci);
886 : }
887 538 : TIMEOUT_CHECK(qry_ctx,
888 : GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
889 : break;
890 : }
891 : }
892 10877 : TRC_DEBUG_IF(ACCELERATOR) if (p < cnt1)
893 0 : TRC_DEBUG_ENDIF(ACCELERATOR,
894 : "%s: abort starthash with "
895 : "mask " BUNFMT " at " BUNFMT " after " LLFMT " usec\n", BATgetId(b), mask, p, GDKusec() - t1);
896 10877 : if (p == cnt1 || mask == maxmask)
897 : break;
898 16 : mask <<= 2;
899 : /* if we fill up the slots fast (p <= maxslots * 1.2)
900 : * increase mask size a bit more quickly */
901 16 : if (p == h->nunique) {
902 : /* only unique values so far: grow really fast */
903 : mask = maxmask;
904 : cnt1 = 0;
905 0 : } else if (mask < maxmask && p <= maxslots * 1.2)
906 0 : mask <<= 2;
907 16 : canditer_reset(ci);
908 0 : o = canditer_next(ci);
909 : }
910 :
911 : /* finish the hashtable with the current mask */
912 10861 : switch (tpe) {
913 10 : case TYPE_bte:
914 343 : finishhash(bte);
915 : break;
916 22 : case TYPE_sht:
917 230 : finishhash(sht);
918 : break;
919 9541 : case TYPE_int:
920 67302366 : finishhash(int);
921 : break;
922 16 : case TYPE_flt:
923 532 : finishhash(flt);
924 : break;
925 4 : case TYPE_dbl:
926 2082 : finishhash(dbl);
927 : break;
928 727 : case TYPE_lng:
929 16675838 : finishhash(lng);
930 : break;
931 : #ifdef HAVE_HGE
932 2 : case TYPE_hge:
933 14 : finishhash(hge);
934 : break;
935 : #endif
936 1 : case TYPE_uuid:
937 2 : finishhash(uuid);
938 : break;
939 538 : default: {
940 538 : int (*atomcmp)(const void *, const void *) = ATOMcompare(h->type);
941 228473 : TIMEOUT_LOOP(ci->ncand - p, qry_ctx) {
942 227390 : const void *restrict v = BUNtail(bi, o - b->hseqbase);
943 227390 : c = hash_any(h, v);
944 227397 : hget = HASHget(h, c);
945 227397 : h->nheads += hget == BUN_NONE;
946 227397 : if (!hascand) {
947 : for (hb = hget;
948 303131 : hb != BUN_NONE;
949 75676 : hb = HASHgetlink(h, hb)) {
950 166162 : if (atomcmp(v, BUNtail(bi, hb)) == 0)
951 : break;
952 : }
953 227368 : h->nunique += hb == BUN_NONE;
954 : }
955 227310 : HASHputlink(h, p, hget);
956 227384 : HASHput(h, c, p);
957 227424 : o = canditer_next(ci);
958 227392 : p++;
959 : }
960 539 : TIMEOUT_CHECK(qry_ctx,
961 : GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
962 : break;
963 : }
964 : }
965 10895 : bat_iterator_end(&bi);
966 : /* if the number of unique values is equal to the bat count,
967 : * all values are necessarily distinct */
968 10891 : MT_lock_set(&b->theaplock);
969 10891 : if (h->nunique == BATcount(b) && !b->tkey) {
970 7643 : b->tkey = true;
971 : }
972 10891 : if (ci->ncand == BATcount(b))
973 10742 : b->tunique_est = (double) h->nunique;
974 10891 : MT_lock_unset(&b->theaplock);
975 10899 : TRC_DEBUG_IF(ACCELERATOR) {
976 0 : TRC_DEBUG_ENDIF(ACCELERATOR,
977 : "hash construction " LLFMT " usec\n", GDKusec() - t0);
978 0 : HASHcollisions(b, h, __func__);
979 : }
980 : return h;
981 :
982 0 : bailout:
983 0 : bat_iterator_end(&bi);
984 0 : HEAPfree(&h->heaplink, true);
985 0 : HEAPfree(&h->heapbckt, true);
986 0 : GDKfree(h);
987 0 : return NULL;
988 : }
989 :
990 : gdk_return
991 2663158 : BAThash(BAT *b)
992 : {
993 2663158 : if (b->ttype == TYPE_void) {
994 0 : GDKerror("No hash on void type bats\n");
995 0 : return GDK_FAIL;
996 : }
997 2663158 : if (ATOMstorage(b->ttype) == TYPE_msk) {
998 0 : GDKerror("No hash on msk type bats\n");
999 0 : return GDK_FAIL;
1000 : }
1001 2663158 : if (BATcheckhash(b)) {
1002 : return GDK_SUCCEED;
1003 : }
1004 : #ifdef __COVERITY__
1005 : MT_rwlock_wrlock(&b->thashlock);
1006 : #else
1007 10766 : for (;;) {
1008 : /* If multiple threads simultaneously try to build a
1009 : * hash on a bat, e.g. in order to perform a join, it
1010 : * may happen that one thread succeeds in obtaining the
1011 : * write lock, then builds the hash, releases the lock,
1012 : * acquires the read lock, and performs the join. The
1013 : * other threads may then still be attempting to acquire
1014 : * the write lock. But now they have to wait until the
1015 : * read lock is released, which can be quite a long
1016 : * time. Especially if a second thread goes through the
1017 : * same process as the first. */
1018 10766 : if (MT_rwlock_wrtry(&b->thashlock))
1019 : break;
1020 13 : MT_sleep_ms(1);
1021 13 : if (MT_rwlock_rdtry(&b->thashlock)) {
1022 10 : if (b->thash != NULL && b->thash != (Hash *) 1) {
1023 10 : MT_rwlock_rdunlock(&b->thashlock);
1024 10 : return GDK_SUCCEED;
1025 : }
1026 0 : MT_rwlock_rdunlock(&b->thashlock);
1027 : }
1028 : }
1029 : #endif
1030 : /* we have the write lock */
1031 10750 : if (b->thash == NULL) {
1032 10741 : struct canditer ci;
1033 10741 : canditer_init(&ci, b, NULL);
1034 10744 : if ((b->thash = BAThash_impl(b, &ci, "thash")) == NULL) {
1035 0 : MT_rwlock_wrunlock(&b->thashlock);
1036 0 : return GDK_FAIL;
1037 : }
1038 : }
1039 10758 : MT_rwlock_wrunlock(&b->thashlock);
1040 10758 : return GDK_SUCCEED;
1041 : }
1042 :
1043 : /*
1044 : * The entry on which a value hashes can be calculated with the
1045 : * routine HASHprobe.
1046 : */
1047 : BUN
1048 436887218 : HASHprobe(const Hash *h, const void *v)
1049 : {
1050 841206588 : switch (ATOMbasetype(h->type)) {
1051 3627 : case TYPE_bte:
1052 3627 : return hash_bte(h, v);
1053 51546 : case TYPE_sht:
1054 51546 : return hash_sht(h, v);
1055 387660812 : case TYPE_int:
1056 387660812 : return hash_int(h, v);
1057 32765826 : case TYPE_lng:
1058 32765826 : return hash_lng(h, v);
1059 : #ifdef HAVE_HGE
1060 26926 : case TYPE_hge:
1061 26926 : return hash_hge(h, v);
1062 : #endif
1063 150956 : case TYPE_flt:
1064 150956 : return hash_flt(h, v);
1065 34946 : case TYPE_dbl:
1066 34946 : return hash_dbl(h, v);
1067 2104 : case TYPE_uuid:
1068 2104 : return hash_uuid(h, v);
1069 16190475 : default:
1070 16190475 : return hash_any(h, v);
1071 : }
1072 : }
1073 :
1074 : void
1075 488395 : HASHappend_locked(BAT *b, BUN i, const void *v)
1076 : {
1077 488395 : Hash *h = b->thash;
1078 488395 : if (h == NULL) {
1079 0 : return;
1080 : }
1081 488395 : if (h == (Hash *) 1) {
1082 0 : b->thash = NULL;
1083 0 : doHASHdestroy(b, h);
1084 0 : GDKclrerr();
1085 0 : return;
1086 : }
1087 488395 : assert(i * h->width == h->heaplink.free);
1088 488395 : if (h->nunique < b->batCount / hash_destroy_uniques_fraction) {
1089 0 : b->thash = NULL;
1090 0 : doHASHdestroy(b, h);
1091 0 : GDKclrerr();
1092 0 : return;
1093 : }
1094 488395 : if (HASHfix(h, false, true) != GDK_SUCCEED) {
1095 0 : b->thash = NULL;
1096 0 : doHASHdestroy(b, h);
1097 0 : GDKclrerr();
1098 0 : return;
1099 : }
1100 488395 : if (HASHwidth(i + 1) > h->width &&
1101 0 : HASHupgradehashheap(b) != GDK_SUCCEED) {
1102 0 : GDKclrerr();
1103 0 : return;
1104 : }
1105 976787 : if ((ATOMsize(b->ttype) > 2 &&
1106 488392 : HASHgrowbucket(b) != GDK_SUCCEED) ||
1107 489559 : ((i + 1) * h->width > h->heaplink.size &&
1108 1164 : HEAPextend(&h->heaplink,
1109 1164 : i * h->width + GDK_mmap_pagesize,
1110 : true) != GDK_SUCCEED)) {
1111 0 : b->thash = NULL;
1112 0 : HEAPfree(&h->heapbckt, true);
1113 0 : HEAPfree(&h->heaplink, true);
1114 0 : GDKfree(h);
1115 0 : GDKclrerr();
1116 0 : return;
1117 : }
1118 488395 : h->Link = h->heaplink.base;
1119 488395 : BUN c = HASHprobe(h, v);
1120 488395 : h->heaplink.free += h->width;
1121 488395 : BUN hb = HASHget(h, c);
1122 488395 : BUN hb2;
1123 488395 : BATiter bi = bat_iterator_nolock(b);
1124 488395 : int (*atomcmp)(const void *, const void *) = ATOMcompare(h->type);
1125 488395 : for (hb2 = hb;
1126 672997 : hb2 != BUN_NONE;
1127 184602 : hb2 = HASHgetlink(h, hb2)) {
1128 345254 : if (atomcmp(v, BUNtail(bi, hb2)) == 0)
1129 : break;
1130 : }
1131 488395 : h->nheads += hb == BUN_NONE;
1132 488395 : h->nunique += hb2 == BUN_NONE;
1133 488395 : HASHputlink(h, i, hb);
1134 488395 : HASHput(h, c, i);
1135 488395 : h->heapbckt.dirty = true;
1136 488395 : h->heaplink.dirty = true;
1137 : }
1138 :
1139 : BUN
1140 0 : HASHappend(BAT *b, BUN i, const void *v)
1141 : {
1142 0 : BUN nunique;
1143 0 : MT_rwlock_wrlock(&b->thashlock);
1144 0 : HASHappend_locked(b, i, v);
1145 0 : nunique = b->thash ? b->thash->nunique : 0;
1146 0 : MT_rwlock_wrunlock(&b->thashlock);
1147 0 : return nunique;
1148 : }
1149 :
1150 : /* insert value v at position p into the hash table of b */
1151 : void
1152 158833921 : HASHinsert_locked(BATiter *bi, BUN p, const void *v)
1153 : {
1154 158833921 : BAT *b = bi->b;
1155 158833921 : Hash *h = b->thash;
1156 158833921 : if (h == NULL) {
1157 : return;
1158 : }
1159 2852 : if (h == (Hash *) 1) {
1160 0 : b->thash = NULL;
1161 0 : doHASHdestroy(b, h);
1162 0 : GDKclrerr();
1163 0 : return;
1164 : }
1165 2852 : assert(p * h->width < h->heaplink.free);
1166 2852 : if (h->nunique < b->batCount / hash_destroy_uniques_fraction) {
1167 0 : b->thash = NULL;
1168 0 : doHASHdestroy(b, h);
1169 0 : GDKclrerr();
1170 0 : return;
1171 : }
1172 2852 : if (HASHfix(h, false, true) != GDK_SUCCEED) {
1173 0 : b->thash = NULL;
1174 0 : doHASHdestroy(b, h);
1175 0 : GDKclrerr();
1176 0 : return;
1177 : }
1178 2852 : BUN c = HASHprobe(h, v);
1179 2852 : BUN hb = HASHget(h, c);
1180 2852 : int (*atomcmp)(const void *, const void *) = ATOMcompare(h->type);
1181 2852 : if (hb == BUN_NONE || hb < p) {
1182 : /* bucket is empty, or bucket is used by lower numbered
1183 : * position */
1184 2464 : h->heaplink.dirty = true;
1185 2464 : h->heapbckt.dirty = true;
1186 2464 : HASHputlink(h, p, hb);
1187 2464 : HASHput(h, c, p);
1188 2464 : if (hb == BUN_NONE) {
1189 1225 : h->nheads++;
1190 : } else {
1191 1547 : do {
1192 1547 : if (atomcmp(v, BUNtail(*bi, hb)) == 0) {
1193 : /* found another row with the
1194 : * same value, so don't
1195 : * increment nunique */
1196 : return;
1197 : }
1198 986 : hb = HASHgetlink(h, hb);
1199 986 : } while (hb != BUN_NONE);
1200 : }
1201 : /* this is a new value */
1202 1903 : h->nunique++;
1203 1903 : return;
1204 : }
1205 : bool seen = false;
1206 4688 : for (;;) {
1207 4688 : if (!seen)
1208 422 : seen = atomcmp(v, BUNtail(*bi, hb)) == 0;
1209 4688 : BUN hb2 = HASHgetlink(h, hb);
1210 4688 : if (hb2 == BUN_NONE || hb2 < p) {
1211 388 : h->heaplink.dirty = true;
1212 388 : HASHputlink(h, p, hb2);
1213 388 : HASHputlink(h, hb, p);
1214 441 : while (!seen && hb2 != BUN_NONE) {
1215 53 : seen = atomcmp(v, BUNtail(*bi, hb2)) == 0;
1216 53 : hb2 = HASHgetlink(h, hb2);
1217 : }
1218 388 : if (!seen)
1219 154 : h->nunique++;
1220 388 : return;
1221 : }
1222 : hb = hb2;
1223 : }
1224 : }
1225 :
1226 : BUN
1227 2 : HASHinsert(BATiter *bi, BUN p, const void *v)
1228 : {
1229 2 : BUN nunique;
1230 2 : MT_rwlock_wrlock(&bi->b->thashlock);
1231 2 : HASHinsert_locked(bi, p, v);
1232 2 : nunique = bi->b->thash ? bi->b->thash->nunique : 0;
1233 2 : MT_rwlock_wrunlock(&bi->b->thashlock);
1234 2 : return nunique;
1235 : }
1236 :
1237 : /* delete value v at position p from the hash table of b */
1238 : void
1239 152386028 : HASHdelete_locked(BATiter *bi, BUN p, const void *v)
1240 : {
1241 152386028 : BAT *b = bi->b;
1242 152386028 : Hash *h = b->thash;
1243 152386028 : if (h == NULL) {
1244 : return;
1245 : }
1246 2852 : if (h == (Hash *) 1) {
1247 0 : b->thash = NULL;
1248 0 : doHASHdestroy(b, h);
1249 0 : GDKclrerr();
1250 0 : return;
1251 : }
1252 2852 : assert(p * h->width < h->heaplink.free);
1253 2852 : if (h->nunique < b->batCount / hash_destroy_uniques_fraction) {
1254 0 : b->thash = NULL;
1255 0 : doHASHdestroy(b, h);
1256 0 : GDKclrerr();
1257 0 : return;
1258 : }
1259 2852 : if (HASHfix(h, false, true) != GDK_SUCCEED) {
1260 0 : b->thash = NULL;
1261 0 : doHASHdestroy(b, h);
1262 0 : GDKclrerr();
1263 0 : return;
1264 : }
1265 2852 : BUN c = HASHprobe(h, v);
1266 2852 : BUN hb = HASHget(h, c);
1267 2852 : int (*atomcmp)(const void *, const void *) = ATOMcompare(h->type);
1268 2852 : if (hb == p) {
1269 2035 : BUN hb2 = HASHgetlink(h, p);
1270 2035 : h->heaplink.dirty = true;
1271 2035 : h->heapbckt.dirty = true;
1272 2035 : HASHput(h, c, hb2);
1273 2035 : HASHputlink(h, p, BUN_NONE);
1274 2035 : if (hb2 == BUN_NONE) {
1275 1267 : h->nheads--;
1276 : } else {
1277 1107 : do {
1278 1107 : if (atomcmp(v, BUNtail(*bi, hb2)) == 0) {
1279 : /* found another row with the
1280 : * same value, so don't
1281 : * decrement nunique below */
1282 : return;
1283 : }
1284 1091 : hb2 = HASHgetlink(h, hb2);
1285 1091 : } while (hb2 != BUN_NONE);
1286 : }
1287 : /* no rows found with the same value, so number of
1288 : * unique values is one lower */
1289 2019 : h->nunique--;
1290 2019 : return;
1291 : }
1292 : bool seen = false;
1293 : BUN links = 0;
1294 6747 : for (;;) {
1295 6747 : if (!seen)
1296 844 : seen = atomcmp(v, BUNtail(*bi, hb)) == 0;
1297 6747 : BUN hb2 = HASHgetlink(h, hb);
1298 6747 : assert(hb2 != BUN_NONE );
1299 6747 : assert(hb2 < hb);
1300 6747 : if (hb2 == p) {
1301 817 : for (hb2 = HASHgetlink(h, hb2);
1302 831 : !seen && hb2 != BUN_NONE;
1303 14 : hb2 = HASHgetlink(h, hb2))
1304 14 : seen = atomcmp(v, BUNtail(*bi, hb2)) == 0;
1305 817 : break;
1306 : }
1307 5930 : hb = hb2;
1308 5930 : if (++links > hash_destroy_chain_length) {
1309 0 : b->thash = NULL;
1310 0 : doHASHdestroy(b, h);
1311 0 : GDKclrerr();
1312 0 : return;
1313 : }
1314 : }
1315 817 : h->heaplink.dirty = true;
1316 817 : HASHputlink(h, hb, HASHgetlink(h, p));
1317 817 : HASHputlink(h, p, BUN_NONE);
1318 817 : if (!seen)
1319 68 : h->nunique--;
1320 : }
1321 :
1322 : BUN
1323 6 : HASHdelete(BATiter *bi, BUN p, const void *v)
1324 : {
1325 6 : BUN nunique;
1326 6 : MT_rwlock_wrlock(&bi->b->thashlock);
1327 6 : HASHdelete_locked(bi, p, v);
1328 6 : nunique = bi->b->thash ? bi->b->thash->nunique : 0;
1329 6 : MT_rwlock_wrunlock(&bi->b->thashlock);
1330 6 : return nunique;
1331 : }
1332 :
1333 : BUN
1334 0 : HASHlist(Hash *h, BUN i)
1335 : {
1336 0 : BUN c = 1;
1337 0 : BUN j = HASHget(h, i);
1338 :
1339 0 : if (j == BUN_NONE)
1340 : return 1;
1341 0 : while ((j = HASHgetlink(h, i)) != BUN_NONE) {
1342 0 : c++;
1343 0 : i = j;
1344 : }
1345 : return c;
1346 : }
1347 :
1348 : void
1349 21414422 : HASHdestroy(BAT *b)
1350 : {
1351 21414422 : if (b) {
1352 21414422 : Hash *hs;
1353 21414422 : MT_rwlock_wrlock(&b->thashlock);
1354 21495429 : hs = b->thash;
1355 21495429 : b->thash = NULL;
1356 21495429 : MT_rwlock_wrunlock(&b->thashlock);
1357 21500456 : doHASHdestroy(b, hs);
1358 : }
1359 21397095 : }
1360 :
1361 : void
1362 443588 : HASHfree(BAT *b)
1363 : {
1364 443588 : if (b) {
1365 443588 : Hash *h;
1366 443588 : MT_rwlock_wrlock(&b->thashlock);
1367 443588 : if ((h = b->thash) != NULL && h != (Hash *) 1) {
1368 1562 : bool rmheap = h->heaplink.dirty || h->heapbckt.dirty;
1369 1562 : TRC_DEBUG(ACCELERATOR, ALGOBATFMT " free hash %s\n",
1370 : ALGOBATPAR(b),
1371 : rmheap ? "removing" : "keeping");
1372 :
1373 1562 : b->thash = rmheap ? NULL : (Hash *) 1;
1374 1562 : HEAPfree(&h->heapbckt, rmheap);
1375 1562 : HEAPfree(&h->heaplink, rmheap);
1376 1562 : GDKfree(h);
1377 : }
1378 443588 : MT_rwlock_wrunlock(&b->thashlock);
1379 : }
1380 443588 : }
|
