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 1354108 : HASHwidth(BUN hashsize)
45 : {
46 1354108 : (void) hashsize;
47 : #ifdef BUN2
48 1354108 : if (hashsize <= (BUN) BUN2_NONE)
49 : return BUN2;
50 : #endif
51 : #ifdef BUN8
52 762 : if (hashsize > (BUN) BUN4_NONE)
53 0 : return BUN8;
54 : #endif
55 : return BUN4;
56 : }
57 :
58 : __attribute__((__const__))
59 : static inline BUN
60 8381 : hashmask(BUN m)
61 : {
62 8381 : m |= m >> 1;
63 8381 : m |= m >> 2;
64 8381 : m |= m >> 4;
65 8381 : m |= m >> 8;
66 8381 : m |= m >> 16;
67 : #if SIZEOF_BUN == 8
68 8381 : m |= m >> 32;
69 : #endif
70 8381 : return m;
71 : }
72 :
73 : static inline void
74 859580 : 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 859580 : memset(h->Bckt, 0xFF, h->nbucket * h->width);
83 859580 : }
84 :
85 : #define HASH_VERSION 6
86 : #define HASH_HEADER_SIZE 7 /* nr of size_t fields in header */
87 :
88 : void
89 23799378 : doHASHdestroy(BAT *b, Hash *hs)
90 : {
91 23799378 : if (hs == (Hash *) 1) {
92 52 : GDKunlink(BBPselectfarm(b->batRole, b->ttype, hashheap),
93 : BATDIR,
94 52 : BBP_physical(b->batCacheid),
95 : "thashl");
96 52 : GDKunlink(BBPselectfarm(b->batRole, b->ttype, hashheap),
97 : BATDIR,
98 52 : BBP_physical(b->batCacheid),
99 : "thashb");
100 23799326 : } else if (hs) {
101 11702 : TRC_DEBUG(ACCELERATOR, ALGOBATFMT ": removing%s hash\n", ALGOBATPAR(b), *(size_t *) hs->heapbckt.base & (1 << 24) ? " persisted" : "");
102 11702 : HEAPfree(&hs->heapbckt, true);
103 11692 : HEAPfree(&hs->heaplink, true);
104 11715 : GDKfree(hs);
105 : }
106 23799395 : }
107 :
108 : gdk_return
109 859513 : HASHnew(Hash *h, int tpe, BUN size, BUN mask, BUN count, bool bcktonly)
110 : {
111 859513 : if (h->width == 0)
112 846765 : h->width = HASHwidth(size);
113 :
114 859513 : if (!bcktonly) {
115 846052 : if (HEAPalloc(&h->heaplink, size, h->width) != GDK_SUCCEED)
116 : return GDK_FAIL;
117 846120 : h->heaplink.free = size * h->width;
118 846120 : h->heaplink.dirty = true;
119 846120 : h->Link = h->heaplink.base;
120 : }
121 859581 : 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 859615 : h->heapbckt.free = mask * h->width + HASH_HEADER_SIZE * SIZEOF_SIZE_T;
130 859615 : h->heapbckt.dirty = true;
131 859615 : h->nbucket = mask;
132 859615 : if (mask & (mask - 1)) {
133 8191 : h->mask2 = hashmask(mask);
134 8191 : h->mask1 = h->mask2 >> 1;
135 : } else {
136 : /* mask is a power of two */
137 851424 : h->mask1 = mask - 1;
138 851424 : h->mask2 = h->mask1 << 1 | 1;
139 : }
140 859615 : h->Bckt = h->heapbckt.base + HASH_HEADER_SIZE * SIZEOF_SIZE_T;
141 859615 : h->type = tpe;
142 859615 : HASHclear(h); /* zero the mask */
143 859572 : ((size_t *) h->heapbckt.base)[0] = (size_t) HASH_VERSION;
144 859572 : ((size_t *) h->heapbckt.base)[1] = (size_t) size;
145 859572 : ((size_t *) h->heapbckt.base)[2] = (size_t) h->nbucket;
146 859572 : ((size_t *) h->heapbckt.base)[3] = (size_t) h->width;
147 859572 : ((size_t *) h->heapbckt.base)[4] = (size_t) count;
148 859572 : ((size_t *) h->heapbckt.base)[5] = (size_t) h->nunique;
149 859572 : ((size_t *) h->heapbckt.base)[6] = (size_t) h->nheads;
150 859572 : 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 558871 : HASHfix(Hash *h, bool save, bool dosync)
285 : {
286 558871 : if (!h->heapbckt.dirty && !h->heaplink.dirty) {
287 24378 : const size_t mask = (size_t) 1 << 24;
288 24378 : if (((size_t *) h->heapbckt.base)[0] & mask) {
289 10725 : if (save)
290 : return GDK_SUCCEED;
291 10725 : ((size_t *) h->heapbckt.base)[0] &= ~mask;
292 : } else {
293 13653 : if (!save)
294 : return GDK_SUCCEED;
295 13653 : ((size_t *) h->heapbckt.base)[0] |= mask;
296 : }
297 24378 : if (h->heapbckt.storage == STORE_MEM) {
298 24351 : gdk_return rc = GDK_FAIL;
299 24351 : int fd = GDKfdlocate(h->heapbckt.farmid, h->heapbckt.filename, "rb+", NULL);
300 24352 : if (fd >= 0) {
301 24352 : if (write(fd, h->heapbckt.base, SIZEOF_SIZE_T) == SIZEOF_SIZE_T) {
302 24351 : if (dosync &&
303 24351 : !(ATOMIC_GET(&GDKdebug) & NOSYNCMASK)) {
304 : #if defined(NATIVE_WIN32)
305 : _commit(fd);
306 : #elif defined(HAVE_FDATASYNC)
307 13 : fdatasync(fd);
308 : #elif defined(HAVE_FSYNC)
309 : fsync(fd);
310 : #endif
311 : }
312 : rc = GDK_SUCCEED;
313 : }
314 24352 : close(fd);
315 : }
316 24352 : if (rc != GDK_SUCCEED)
317 0 : ((size_t *) h->heapbckt.base)[0] &= ~mask;
318 24352 : return rc;
319 : } else {
320 27 : if (dosync &&
321 27 : !(ATOMIC_GET(&GDKdebug) & NOSYNCMASK) &&
322 0 : 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 494523 : HASHgrowbucket(BAT *b)
333 : {
334 494523 : Hash *h = b->thash;
335 494523 : BUN nbucket;
336 494523 : BUN onbucket = h->nbucket;
337 494523 : lng t0 = 0;
338 :
339 494523 : TRC_DEBUG_IF(ACCELERATOR) t0 = GDKusec();
340 :
341 : /* only needed to fix hash tables built before this fix was
342 : * introduced */
343 494523 : if (h->width < SIZEOF_BUN &&
344 494523 : ((BUN) 1 << (h->width * 8)) - 1 <= h->mask2 &&
345 0 : HASHupgradehashheap(b) != GDK_SUCCEED)
346 : return GDK_FAIL;
347 :
348 494523 : h->heapbckt.dirty = true;
349 494523 : h->heaplink.dirty = true;
350 750757 : while (h->nunique >= (nbucket = h->nbucket) * 7 / 8) {
351 256234 : BUN new = h->nbucket;
352 256234 : BUN old = new & h->mask1;
353 256234 : BUN mask = h->mask1 + 1; /* == h->mask2 - h->mask1 */
354 :
355 256234 : assert(h->heapbckt.free == nbucket * h->width + HASH_HEADER_SIZE * SIZEOF_SIZE_T);
356 256234 : if (h->heapbckt.free + h->width > h->heapbckt.size) {
357 3914 : if (HEAPextend(&h->heapbckt,
358 : h->heapbckt.size + GDK_mmap_pagesize,
359 : true) != GDK_SUCCEED) {
360 0 : return GDK_FAIL;
361 : }
362 3914 : h->Bckt = h->heapbckt.base + HASH_HEADER_SIZE * SIZEOF_SIZE_T;
363 : }
364 256234 : assert(h->heapbckt.free + h->width <= h->heapbckt.size);
365 256234 : if (h->nbucket == h->mask2) {
366 249 : h->mask1 = h->mask2;
367 249 : h->mask2 |= h->mask2 << 1;
368 249 : if (h->width < SIZEOF_BUN &&
369 249 : 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 256234 : h->nbucket++;
376 256234 : h->heapbckt.free += h->width;
377 256234 : BUN lold, lnew, hb;
378 256234 : lold = lnew = BUN_NONE;
379 256234 : BATiter bi = bat_iterator(b);
380 256234 : if ((hb = HASHget(h, old)) != BUN_NONE) {
381 205755 : h->nheads--;
382 326861 : do {
383 326861 : const void *v = BUNtail(bi, hb);
384 326861 : BUN hsh = ATOMhash(h->type, v);
385 326861 : assert((hsh & (mask - 1)) == old);
386 326861 : if (hsh & mask) {
387 : /* move to new list */
388 125139 : if (lnew == BUN_NONE) {
389 109647 : HASHput(h, new, hb);
390 109647 : h->nheads++;
391 : } else
392 15492 : HASHputlink(h, lnew, hb);
393 : lnew = hb;
394 : } else {
395 : /* move to old list */
396 201722 : if (lold == BUN_NONE) {
397 154987 : h->nheads++;
398 154987 : HASHput(h, old, hb);
399 : } else
400 46735 : HASHputlink(h, lold, hb);
401 : lold = hb;
402 : }
403 326861 : hb = HASHgetlink(h, hb);
404 326861 : } while (hb != BUN_NONE);
405 : }
406 256234 : bat_iterator_end(&bi);
407 256234 : if (lnew == BUN_NONE)
408 146587 : HASHput(h, new, BUN_NONE);
409 : else
410 109647 : HASHputlink(h, lnew, BUN_NONE);
411 256234 : if (lold == BUN_NONE)
412 101247 : HASHput(h, old, BUN_NONE);
413 : else
414 154987 : HASHputlink(h, lold, BUN_NONE);
415 : }
416 494523 : 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 62819095 : BATcheckhash(BAT *b)
436 : {
437 62819095 : lng t = 0;
438 62819095 : Hash *h;
439 :
440 62819095 : MT_rwlock_rdlock(&b->thashlock);
441 62893823 : h = b->thash;
442 62893823 : MT_rwlock_rdunlock(&b->thashlock);
443 62879027 : if (h == (Hash *) 1) {
444 : /* but when we want to change it, we need the lock */
445 429 : TRC_DEBUG_IF(ACCELERATOR) t = GDKusec();
446 429 : MT_rwlock_wrlock(&b->thashlock);
447 429 : TRC_DEBUG_IF(ACCELERATOR) t = GDKusec() - t;
448 : /* if still 1 now that we have the lock, we can update */
449 429 : if (b->thash == (Hash *) 1) {
450 428 : int fd;
451 :
452 428 : assert(!GDKinmemory(b->theap->farmid));
453 428 : b->thash = NULL;
454 428 : if ((h = GDKzalloc(sizeof(*h))) != NULL &&
455 428 : (h->heaplink.farmid = BBPselectfarm(b->batRole, b->ttype, hashheap)) >= 0 &&
456 428 : (h->heapbckt.farmid = BBPselectfarm(b->batRole, b->ttype, hashheap)) >= 0) {
457 428 : const char *nme = BBP_physical(b->batCacheid);
458 428 : strconcat_len(h->heaplink.filename,
459 : sizeof(h->heaplink.filename),
460 : nme, ".thashl", NULL);
461 428 : strconcat_len(h->heapbckt.filename,
462 : sizeof(h->heapbckt.filename),
463 : nme, ".thashb", NULL);
464 428 : h->heaplink.storage = STORE_INVALID;
465 428 : h->heaplink.newstorage = STORE_INVALID;
466 428 : h->heapbckt.storage = STORE_INVALID;
467 428 : h->heapbckt.newstorage = STORE_INVALID;
468 :
469 : /* check whether a persisted hash can be found */
470 428 : if ((fd = GDKfdlocate(h->heapbckt.farmid, nme, "rb+", "thashb")) >= 0) {
471 428 : size_t hdata[HASH_HEADER_SIZE];
472 428 : struct stat st;
473 :
474 428 : if (read(fd, hdata, sizeof(hdata)) == sizeof(hdata) &&
475 428 : (hdata[0] == (((size_t) 1 << 24) | HASH_VERSION)) &&
476 369 : hdata[1] > 0 &&
477 : (
478 : #ifdef BUN2
479 369 : hdata[3] == BUN2 ||
480 : #endif
481 : hdata[3] == BUN4
482 : #ifdef BUN8
483 : || hdata[3] == BUN8
484 : #endif
485 369 : ) &&
486 738 : hdata[4] == (size_t) BATcount(b) &&
487 369 : fstat(fd, &st) == 0 &&
488 738 : 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 369 : close(fd) == 0 &&
490 738 : (fd = GDKfdlocate(h->heaplink.farmid, nme, "rb+", "thashl")) >= 0 &&
491 369 : fstat(fd, &st) == 0 &&
492 369 : st.st_size > 0 &&
493 738 : st.st_size >= (off_t) (h->heaplink.size = h->heaplink.free = hdata[1] * h->width) &&
494 369 : HEAPload(&h->heaplink, nme, "thashl", false) == GDK_SUCCEED) {
495 369 : if (HEAPload(&h->heapbckt, nme, "thashb", false) == GDK_SUCCEED) {
496 369 : if (h->nbucket & (h->nbucket - 1)) {
497 190 : h->mask2 = hashmask(h->nbucket);
498 190 : h->mask1 = h->mask2 >> 1;
499 : } else {
500 179 : h->mask1 = h->nbucket - 1;
501 179 : h->mask2 = h->mask1 << 1 | 1;
502 : }
503 369 : h->nunique = hdata[5];
504 369 : h->nheads = hdata[6];
505 369 : h->type = ATOMtype(b->ttype);
506 369 : if (h->width < SIZEOF_BUN &&
507 369 : ((BUN) 1 << (8 * h->width)) - 1 > h->nbucket) {
508 369 : close(fd);
509 369 : h->Link = h->heaplink.base;
510 369 : h->Bckt = h->heapbckt.base + HASH_HEADER_SIZE * SIZEOF_SIZE_T;
511 369 : h->heaplink.parentid = b->batCacheid;
512 369 : h->heapbckt.parentid = b->batCacheid;
513 369 : h->heaplink.dirty = false;
514 369 : h->heapbckt.dirty = false;
515 369 : b->thash = h;
516 369 : h->heapbckt.hasfile = true;
517 369 : h->heaplink.hasfile = true;
518 369 : TRC_DEBUG(ACCELERATOR,
519 : ALGOBATFMT ": reusing persisted hash\n", ALGOBATPAR(b));
520 369 : MT_rwlock_wrunlock(&b->thashlock);
521 369 : 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 59 : close(fd);
548 : /* unlink unusable file */
549 59 : GDKunlink(h->heaplink.farmid, BATDIR, nme, "thashl");
550 59 : GDKunlink(h->heapbckt.farmid, BATDIR, nme, "thashb");
551 59 : h->heapbckt.hasfile = false;
552 59 : h->heaplink.hasfile = false;
553 : }
554 : }
555 59 : GDKfree(h);
556 59 : GDKclrerr(); /* we're not currently interested in errors */
557 : }
558 60 : h = b->thash;
559 60 : MT_rwlock_wrunlock(&b->thashlock);
560 : }
561 62878658 : if (h != NULL) {
562 3791462 : TRC_DEBUG(ACCELERATOR, ALGOBATFMT ": already has hash, waited " LLFMT " usec\n", ALGOBATPAR(b), t);
563 : }
564 62878658 : 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 91013 : HASHsize(BAT *b)
571 : {
572 91013 : size_t sz = 0;
573 91013 : MT_rwlock_rdlock(&b->thashlock);
574 91013 : if (b->thash == NULL) {
575 : sz = 0;
576 5172 : } else if (b->thash != (Hash *) 1) {
577 4354 : sz = b->thash->heaplink.size + b->thash->heapbckt.size;
578 : } else {
579 818 : int farmid = BBPselectfarm(b->batRole, b->ttype, hashheap);
580 818 : if (farmid >= 0) {
581 818 : const char *nme = BBP_physical(b->batCacheid);
582 818 : char fname[MAXPATH];
583 :
584 818 : if (GDKfilepath(fname, sizeof(fname), farmid, BATDIR, nme, "thashb") == GDK_SUCCEED) {
585 818 : struct stat st;
586 818 : if (stat(fname, &st) == 0) {
587 818 : sz = (size_t) st.st_size;
588 818 : fname[strlen(fname) - 1] = 'l';
589 818 : if (stat(fname, &st) == 0)
590 818 : sz += (size_t) st.st_size;
591 : else
592 : sz = 0;
593 : }
594 : }
595 : }
596 : }
597 91013 : MT_rwlock_rdunlock(&b->thashlock);
598 91013 : return sz;
599 : }
600 :
601 : static void
602 14310 : BAThashsave_intern(BAT *b, bool dosync)
603 : {
604 14310 : Hash *h;
605 14310 : lng t0 = 0;
606 :
607 14310 : TRC_DEBUG_IF(ACCELERATOR) t0 = GDKusec();
608 :
609 14310 : if ((h = b->thash) != NULL) {
610 : /* only persist if parent BAT hasn't changed in the
611 : * mean time */
612 14310 : if (!b->theap->dirty &&
613 13654 : ((size_t *) h->heapbckt.base)[1] == BATcount(b) &&
614 27308 : ((size_t *) h->heapbckt.base)[4] == BATcount(b) &&
615 27307 : HEAPsave(&h->heaplink, h->heaplink.filename, NULL, dosync, h->heaplink.free, NULL) == GDK_SUCCEED &&
616 13654 : HEAPsave(&h->heapbckt, h->heapbckt.filename, NULL, dosync, h->heapbckt.free, NULL) == GDK_SUCCEED) {
617 13654 : h->heaplink.dirty = false;
618 13654 : h->heapbckt.dirty = false;
619 13654 : h->heaplink.hasfile = true;
620 13654 : h->heapbckt.hasfile = true;
621 13654 : gdk_return rc = HASHfix(h, true, dosync);
622 13654 : 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 14309 : GDKclrerr();
626 : }
627 14310 : }
628 :
629 : void
630 14310 : BAThashsave(BAT *b, bool dosync)
631 : {
632 14310 : Hash *h = b->thash;
633 14310 : if (h == NULL)
634 : return;
635 14310 : ((size_t *) h->heapbckt.base)[0] = (size_t) HASH_VERSION;
636 14310 : ((size_t *) h->heapbckt.base)[1] = (size_t) (h->heaplink.free / h->width);
637 14310 : ((size_t *) h->heapbckt.base)[2] = (size_t) h->nbucket;
638 14310 : ((size_t *) h->heapbckt.base)[3] = (size_t) h->width;
639 14310 : ((size_t *) h->heapbckt.base)[4] = (size_t) BATcount(b);
640 14310 : ((size_t *) h->heapbckt.base)[5] = (size_t) h->nunique;
641 14310 : ((size_t *) h->heapbckt.base)[6] = (size_t) h->nheads;
642 14310 : 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 13508 : BAThash_impl(BAT *restrict b, struct canditer *restrict ci, const char *restrict ext)
720 : {
721 13508 : lng t0 = 0;
722 13508 : BUN cnt1;
723 13508 : BUN mask, maxmask = 0;
724 13508 : BUN p, c;
725 13508 : oid o;
726 13508 : BUN hget, hb;
727 13508 : Hash *h = NULL;
728 13508 : const char *nme = GDKinmemory(b->theap->farmid) ? ":memory:" : BBP_physical(b->batCacheid);
729 13505 : BATiter bi = bat_iterator(b);
730 13515 : unsigned int tpe = ATOMbasetype(bi.type);
731 13515 : bool hascand = ci->tpe != cand_dense || ci->ncand != bi.count;
732 :
733 13515 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
734 :
735 13521 : assert(strcmp(ext, "thash") != 0 || !hascand);
736 13521 : assert(bi.type != TYPE_msk);
737 :
738 26863 : MT_thread_setalgorithm(hascand ? "create hash with candidates" : "create hash");
739 13529 : TRC_DEBUG_IF(ACCELERATOR) t0 = GDKusec();
740 13529 : TRC_DEBUG(ACCELERATOR,
741 : ALGOBATFMT ": create hash;\n", ALGOBATPAR(b));
742 13509 : 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 13509 : if ((h = GDKzalloc(sizeof(*h))) == NULL ||
757 13523 : (h->heaplink.farmid = BBPselectfarm(hascand ? TRANSIENT : b->batRole, bi.type, hashheap)) < 0 ||
758 13519 : (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 13523 : h->width = HASHwidth(BATcapacity(b));
764 13523 : h->heaplink.dirty = true;
765 13523 : h->heapbckt.dirty = true;
766 13523 : strconcat_len(h->heaplink.filename, sizeof(h->heaplink.filename),
767 : nme, ".", ext, "l", NULL);
768 13519 : strconcat_len(h->heapbckt.filename, sizeof(h->heapbckt.filename),
769 : nme, ".", ext, "b", NULL);
770 13511 : h->heapbckt.parentid = b->batCacheid;
771 13511 : h->heaplink.parentid = b->batCacheid;
772 13511 : if (HEAPalloc(&h->heaplink, hascand ? ci->ncand : BATcapacity(b),
773 13511 : h->width) != GDK_SUCCEED) {
774 0 : GDKfree(h);
775 0 : bat_iterator_end(&bi);
776 0 : return NULL;
777 : }
778 13520 : h->heaplink.free = ci->ncand * h->width;
779 13520 : h->Link = h->heaplink.base;
780 : #ifndef NDEBUG
781 : /* clear unused part of Link array */
782 13520 : if (h->heaplink.size > h->heaplink.free)
783 12243 : memset(h->heaplink.base + h->heaplink.free, 0,
784 : h->heaplink.size - h->heaplink.free);
785 : #endif
786 :
787 : /* determine hash mask size */
788 13520 : cnt1 = 0;
789 13520 : if (ATOMsize(tpe) == 1) {
790 : /* perfect hash for one-byte sized atoms */
791 : mask = (1 << 8);
792 13502 : } else if (ATOMsize(tpe) == 2) {
793 : /* perfect hash for two-byte sized atoms */
794 : mask = (1 << 16);
795 13448 : } else if (bi.key || ci->ncand <= 4096) {
796 : /* if key, or if small, don't bother dynamically
797 : * adjusting the hash mask */
798 13296 : mask = HASHmask(ci->ncand);
799 152 : } else if (!hascand && bi.unique_est != 0) {
800 152 : 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 13520 : o = canditer_next(ci); /* always one ahead */
817 0 : for (;;) {
818 13478 : lng t1 = 0;
819 13478 : TRC_DEBUG_IF(ACCELERATOR) t1 = GDKusec();
820 13478 : BUN maxslots = (mask >> 3) - 1; /* 1/8 full is too full */
821 :
822 13478 : h->nheads = 0;
823 13478 : h->nunique = 0;
824 13478 : p = 0;
825 13478 : HEAPfree(&h->heapbckt, true);
826 : /* create the hash structures */
827 27012 : 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 13471 : switch (tpe) {
836 18 : case TYPE_bte:
837 36 : starthash(bte);
838 : break;
839 54 : case TYPE_sht:
840 108 : starthash(sht);
841 : break;
842 15 : case TYPE_flt:
843 30 : starthash(flt);
844 : break;
845 11843 : case TYPE_int:
846 23678 : starthash(int);
847 : break;
848 4 : case TYPE_dbl:
849 8 : starthash(dbl);
850 : break;
851 759 : case TYPE_lng:
852 1519 : 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 775 : default: {
863 775 : int (*atomcmp)(const void *, const void *) = ATOMcompare(h->type);
864 1551 : 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 776 : TIMEOUT_CHECK(qry_ctx,
888 : GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
889 : break;
890 : }
891 : }
892 13477 : 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 13477 : if (p == cnt1 || mask == maxmask)
897 : break;
898 26 : mask <<= 2;
899 : /* if we fill up the slots fast (p <= maxslots * 1.2)
900 : * increase mask size a bit more quickly */
901 26 : 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 26 : canditer_reset(ci);
908 0 : o = canditer_next(ci);
909 : }
910 :
911 : /* finish the hashtable with the current mask */
912 13451 : switch (tpe) {
913 18 : case TYPE_bte:
914 391 : finishhash(bte);
915 : break;
916 54 : case TYPE_sht:
917 558 : finishhash(sht);
918 : break;
919 11823 : case TYPE_int:
920 108435848 : finishhash(int);
921 : break;
922 15 : case TYPE_flt:
923 537 : finishhash(flt);
924 : break;
925 4 : case TYPE_dbl:
926 2082 : finishhash(dbl);
927 : break;
928 758 : case TYPE_lng:
929 16841452 : 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 776 : default: {
940 776 : int (*atomcmp)(const void *, const void *) = ATOMcompare(h->type);
941 325019 : TIMEOUT_LOOP(ci->ncand - p, qry_ctx) {
942 323460 : const void *restrict v = BUNtail(bi, o - b->hseqbase);
943 323460 : c = hash_any(h, v);
944 323472 : hget = HASHget(h, c);
945 323472 : h->nheads += hget == BUN_NONE;
946 323472 : if (!hascand) {
947 : for (hb = hget;
948 418560 : hb != BUN_NONE;
949 95039 : hb = HASHgetlink(h, hb)) {
950 261344 : if (atomcmp(v, BUNtail(bi, hb)) == 0)
951 : break;
952 : }
953 323439 : h->nunique += hb == BUN_NONE;
954 : }
955 323390 : HASHputlink(h, p, hget);
956 323407 : HASHput(h, c, p);
957 323473 : o = canditer_next(ci);
958 323461 : p++;
959 : }
960 777 : TIMEOUT_CHECK(qry_ctx,
961 : GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
962 : break;
963 : }
964 : }
965 13516 : bat_iterator_end(&bi);
966 : /* if the number of unique values is equal to the bat count,
967 : * all values are necessarily distinct */
968 13517 : MT_lock_set(&b->theaplock);
969 13519 : if (h->nunique == BATcount(b) && !b->tkey) {
970 8869 : b->tkey = true;
971 : }
972 13519 : if (ci->ncand == BATcount(b))
973 13338 : b->tunique_est = (double) h->nunique;
974 13519 : MT_lock_unset(&b->theaplock);
975 13530 : 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 2727048 : BAThash(BAT *b)
992 : {
993 2727048 : if (b->ttype == TYPE_void) {
994 0 : GDKerror("No hash on void type bats\n");
995 0 : return GDK_FAIL;
996 : }
997 2727048 : if (ATOMstorage(b->ttype) == TYPE_msk) {
998 0 : GDKerror("No hash on msk type bats\n");
999 0 : return GDK_FAIL;
1000 : }
1001 2727048 : if (BATcheckhash(b)) {
1002 : return GDK_SUCCEED;
1003 : }
1004 : #ifdef __COVERITY__
1005 : MT_rwlock_wrlock(&b->thashlock);
1006 : #else
1007 13502 : 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 13502 : if (MT_rwlock_wrtry(&b->thashlock))
1019 : break;
1020 161 : MT_sleep_ms(1);
1021 161 : if (MT_rwlock_rdtry(&b->thashlock)) {
1022 5 : if (b->thash != NULL && b->thash != (Hash *) 1) {
1023 5 : MT_rwlock_rdunlock(&b->thashlock);
1024 5 : return GDK_SUCCEED;
1025 : }
1026 0 : MT_rwlock_rdunlock(&b->thashlock);
1027 : }
1028 : }
1029 : #endif
1030 : /* we have the write lock */
1031 13341 : if (b->thash == NULL) {
1032 13331 : struct canditer ci;
1033 13331 : canditer_init(&ci, b, NULL);
1034 13343 : if ((b->thash = BAThash_impl(b, &ci, "thash")) == NULL) {
1035 0 : MT_rwlock_wrunlock(&b->thashlock);
1036 0 : return GDK_FAIL;
1037 : }
1038 : }
1039 13355 : MT_rwlock_wrunlock(&b->thashlock);
1040 13355 : 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 540728389 : HASHprobe(const Hash *h, const void *v)
1049 : {
1050 950886880 : switch (ATOMbasetype(h->type)) {
1051 3849 : case TYPE_bte:
1052 3849 : return hash_bte(h, v);
1053 127677 : case TYPE_sht:
1054 127677 : return hash_sht(h, v);
1055 391809512 : case TYPE_int:
1056 391809512 : return hash_int(h, v);
1057 130846080 : case TYPE_lng:
1058 130846080 : return hash_lng(h, v);
1059 : #ifdef HAVE_HGE
1060 26926 : case TYPE_hge:
1061 26926 : return hash_hge(h, v);
1062 : #endif
1063 150981 : case TYPE_flt:
1064 150981 : return hash_flt(h, v);
1065 35907 : case TYPE_dbl:
1066 35907 : return hash_dbl(h, v);
1067 2104 : case TYPE_uuid:
1068 2104 : return hash_uuid(h, v);
1069 17725353 : default:
1070 17725353 : return hash_any(h, v);
1071 : }
1072 : }
1073 :
1074 : void
1075 494526 : HASHappend_locked(BAT *b, BUN i, const void *v)
1076 : {
1077 494526 : Hash *h = b->thash;
1078 494526 : if (h == NULL) {
1079 0 : return;
1080 : }
1081 494526 : if (h == (Hash *) 1) {
1082 0 : b->thash = NULL;
1083 0 : doHASHdestroy(b, h);
1084 0 : GDKclrerr();
1085 0 : return;
1086 : }
1087 494526 : assert(i * h->width == h->heaplink.free);
1088 494526 : 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 494526 : 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 494526 : if (HASHwidth(i + 1) > h->width &&
1101 0 : HASHupgradehashheap(b) != GDK_SUCCEED) {
1102 0 : GDKclrerr();
1103 0 : return;
1104 : }
1105 989049 : if ((ATOMsize(b->ttype) > 2 &&
1106 494523 : HASHgrowbucket(b) != GDK_SUCCEED) ||
1107 495757 : ((i + 1) * h->width > h->heaplink.size &&
1108 1231 : HEAPextend(&h->heaplink,
1109 1231 : 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 494526 : h->Link = h->heaplink.base;
1119 494526 : BUN c = HASHprobe(h, v);
1120 494526 : h->heaplink.free += h->width;
1121 494526 : BUN hb = HASHget(h, c);
1122 494526 : BUN hb2;
1123 494526 : BATiter bi = bat_iterator_nolock(b);
1124 494526 : int (*atomcmp)(const void *, const void *) = ATOMcompare(h->type);
1125 494526 : for (hb2 = hb;
1126 680096 : hb2 != BUN_NONE;
1127 185570 : hb2 = HASHgetlink(h, hb2)) {
1128 349570 : if (atomcmp(v, BUNtail(bi, hb2)) == 0)
1129 : break;
1130 : }
1131 494526 : h->nheads += hb == BUN_NONE;
1132 494526 : h->nunique += hb2 == BUN_NONE;
1133 494526 : HASHputlink(h, i, hb);
1134 494526 : HASHput(h, c, i);
1135 494526 : h->heapbckt.dirty = true;
1136 494526 : 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 173914495 : HASHinsert_locked(BATiter *bi, BUN p, const void *v)
1153 : {
1154 173914495 : BAT *b = bi->b;
1155 173914495 : Hash *h = b->thash;
1156 173914495 : if (h == NULL) {
1157 : return;
1158 : }
1159 25346 : if (h == (Hash *) 1) {
1160 0 : b->thash = NULL;
1161 0 : doHASHdestroy(b, h);
1162 0 : GDKclrerr();
1163 0 : return;
1164 : }
1165 25346 : assert(p * h->width < h->heaplink.free);
1166 25346 : 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 25346 : 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 25346 : BUN c = HASHprobe(h, v);
1179 25346 : BUN hb = HASHget(h, c);
1180 25346 : int (*atomcmp)(const void *, const void *) = ATOMcompare(h->type);
1181 25346 : if (hb == BUN_NONE || hb < p) {
1182 : /* bucket is empty, or bucket is used by lower numbered
1183 : * position */
1184 4947 : h->heaplink.dirty = true;
1185 4947 : h->heapbckt.dirty = true;
1186 4947 : HASHputlink(h, p, hb);
1187 4947 : HASHput(h, c, p);
1188 4947 : if (hb == BUN_NONE) {
1189 2307 : h->nheads++;
1190 : } else {
1191 3077 : do {
1192 3077 : 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 1278 : hb = HASHgetlink(h, hb);
1199 1278 : } while (hb != BUN_NONE);
1200 : }
1201 : /* this is a new value */
1202 3148 : h->nunique++;
1203 3148 : return;
1204 : }
1205 : bool seen = false;
1206 196034 : for (;;) {
1207 196034 : if (!seen)
1208 20910 : seen = atomcmp(v, BUNtail(*bi, hb)) == 0;
1209 196034 : BUN hb2 = HASHgetlink(h, hb);
1210 196034 : if (hb2 == BUN_NONE || hb2 < p) {
1211 20399 : h->heaplink.dirty = true;
1212 20399 : HASHputlink(h, p, hb2);
1213 20399 : HASHputlink(h, hb, p);
1214 20675 : while (!seen && hb2 != BUN_NONE) {
1215 276 : seen = atomcmp(v, BUNtail(*bi, hb2)) == 0;
1216 276 : hb2 = HASHgetlink(h, hb2);
1217 : }
1218 20399 : if (!seen)
1219 348 : h->nunique++;
1220 20399 : 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 168146881 : HASHdelete_locked(BATiter *bi, BUN p, const void *v)
1240 : {
1241 168146881 : BAT *b = bi->b;
1242 168146881 : Hash *h = b->thash;
1243 168146881 : if (h == NULL) {
1244 : return;
1245 : }
1246 25346 : if (h == (Hash *) 1) {
1247 0 : b->thash = NULL;
1248 0 : doHASHdestroy(b, h);
1249 0 : GDKclrerr();
1250 0 : return;
1251 : }
1252 25346 : assert(p * h->width < h->heaplink.free);
1253 25346 : 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 25346 : 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 25346 : BUN c = HASHprobe(h, v);
1266 25346 : BUN hb = HASHget(h, c);
1267 25346 : int (*atomcmp)(const void *, const void *) = ATOMcompare(h->type);
1268 25346 : if (hb == p) {
1269 3436 : BUN hb2 = HASHgetlink(h, p);
1270 3436 : h->heaplink.dirty = true;
1271 3436 : h->heapbckt.dirty = true;
1272 3436 : HASHput(h, c, hb2);
1273 3436 : HASHputlink(h, p, BUN_NONE);
1274 3436 : if (hb2 == BUN_NONE) {
1275 1602 : h->nheads--;
1276 : } else {
1277 2264 : do {
1278 2264 : 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 1284 : hb2 = HASHgetlink(h, hb2);
1285 1284 : } while (hb2 != BUN_NONE);
1286 : }
1287 : /* no rows found with the same value, so number of
1288 : * unique values is one lower */
1289 2456 : h->nunique--;
1290 2456 : return;
1291 : }
1292 : bool seen = false;
1293 : BUN links = 0;
1294 184552 : for (;;) {
1295 184552 : if (!seen)
1296 22157 : seen = atomcmp(v, BUNtail(*bi, hb)) == 0;
1297 184552 : BUN hb2 = HASHgetlink(h, hb);
1298 184552 : assert(hb2 != BUN_NONE );
1299 184552 : assert(hb2 < hb);
1300 184552 : if (hb2 == p) {
1301 21910 : for (hb2 = HASHgetlink(h, hb2);
1302 21975 : !seen && hb2 != BUN_NONE;
1303 65 : hb2 = HASHgetlink(h, hb2))
1304 65 : seen = atomcmp(v, BUNtail(*bi, hb2)) == 0;
1305 21910 : break;
1306 : }
1307 162642 : hb = hb2;
1308 162642 : 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 21910 : h->heaplink.dirty = true;
1316 21910 : HASHputlink(h, hb, HASHgetlink(h, p));
1317 21910 : HASHputlink(h, p, BUN_NONE);
1318 21910 : if (!seen)
1319 163 : 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 23843889 : HASHdestroy(BAT *b)
1350 : {
1351 23843889 : if (b) {
1352 23843889 : Hash *hs;
1353 23843889 : MT_rwlock_wrlock(&b->thashlock);
1354 23936606 : hs = b->thash;
1355 23936606 : b->thash = NULL;
1356 23936606 : MT_rwlock_wrunlock(&b->thashlock);
1357 23943299 : doHASHdestroy(b, hs);
1358 : }
1359 23812407 : }
1360 :
1361 : void
1362 578301 : HASHfree(BAT *b)
1363 : {
1364 578301 : if (b) {
1365 578301 : Hash *h;
1366 578301 : MT_rwlock_wrlock(&b->thashlock);
1367 578301 : if ((h = b->thash) != NULL && h != (Hash *) 1) {
1368 1991 : bool rmheap = h->heaplink.dirty || h->heapbckt.dirty;
1369 1991 : TRC_DEBUG(ACCELERATOR, ALGOBATFMT " free hash %s\n",
1370 : ALGOBATPAR(b),
1371 : rmheap ? "removing" : "keeping");
1372 :
1373 1991 : b->thash = rmheap ? NULL : (Hash *) 1;
1374 1991 : HEAPfree(&h->heapbckt, rmheap);
1375 1992 : HEAPfree(&h->heaplink, rmheap);
1376 1992 : GDKfree(h);
1377 : }
1378 578301 : MT_rwlock_wrunlock(&b->thashlock);
1379 : }
1380 578302 : }
|
