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