| 1 |
|
| #ifndef CHD_H |
| 2 |
|
| #define CHD_H |
| 3 |
|
| #include "phash.h" |
| 4 |
|
| #include <string.h> |
| 5 |
|
| #include <stdint.h> |
| 6 |
|
| #include <stdlib.h> |
| 7 |
|
| #include <stdio.h> |
| 8 |
|
| #include <errno.h> |
| 9 |
|
| #include <fcntl.h> |
| 10 |
|
| #include <unistd.h> |
| 11 |
|
| |
| 12 |
|
| /* Average keys per bucket: bucket_count r = ceil(n / PH_LAMBDA). lambda=6 is |
| 13 |
|
| * chosen empirically as the largest value that still reliably converges on the |
| 14 |
|
| * first placement attempt (swept up to n=500k), giving the smallest index at |
| 15 |
|
| * ~4.0 bits/key; lower lambda trades index size for a faster build. */ |
| 16 |
|
| #define PH_LAMBDA 6u |
| 17 |
|
| |
| 18 |
|
| /* TLS qualifier for the qsort() context pointers below: ph_build() may run |
| 19 |
|
| * concurrently in multiple ithreads, and a plain file-static context would let |
| 20 |
|
| * one thread's qsort() read another's pointer (OOB / silent corruption). */ |
| 21 |
|
| #if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112L |
| 22 |
|
| # define PH_TLS _Thread_local |
| 23 |
|
| #elif defined(__GNUC__) |
| 24 |
|
| # define PH_TLS __thread |
| 25 |
|
| #else |
| 26 |
|
| # define PH_TLS |
| 27 |
|
| #endif |
| 28 |
|
| |
| 29 |
|
| typedef struct { |
| 30 |
|
| uint32_t type_tag; /* PH_BUILDER_TAG; must stay the first member -- see phash.h */ |
| 31 |
|
| uint32_t key_type; |
| 32 |
|
| int64_t *ints; size_t nint, capint; /* int keys */ |
| 33 |
|
| uint8_t *arena; size_t arena_len, arena_cap; /* str bytes */ |
| 34 |
|
| PhStrSlot *sslots; size_t nstr, capstr; /* (off,len) into arena */ |
| 35 |
|
| } PhBuilder; |
| 36 |
|
| |
| 37 |
|
| /* ph_builder_new/add_int/add_str run only from Shared.xs (chd.h compiled into |
| 38 |
|
| * the XS unit after perl.h), so croak() is the right way to fail here: unlike |
| 39 |
|
| * ph_build below there's no caller-supplied err buffer at this layer, and croak unwinds cleanly without leaving a half-built PhBuilder. */ |
| 40 |
47 |
| static PhBuilder *ph_builder_new(uint32_t type) { |
| 41 |
47 |
| PhBuilder *b = (PhBuilder *)calloc(1, sizeof *b); |
| 42 |
47 |
▶ | if (!b) croak("out of memory"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!b) croak("out of memory"); |
0 |
47 |
47 |
|
| 43 |
47 |
| b->type_tag = PH_BUILDER_TAG; b->key_type = type; return b; |
| 44 |
|
| } |
| 45 |
8656 |
| static void ph_builder_add_int(PhBuilder *b, int64_t k) { |
| 46 |
8656 |
▶ | if (b->nint == b->capint) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (b->nint == b->capint) { |
60 |
8596 |
8656 |
|
| 47 |
60 |
▶ | size_t newcap = b->capint ? b->capint*2 : 16; |
Branch: 1 branch
| Branch | True | False | Total |
| size_t newcap = b->capint ? b->capint*2 : 16; |
35 |
25 |
60 |
|
| 48 |
60 |
| int64_t *p = (int64_t*)realloc(b->ints, newcap*sizeof(int64_t)); |
| 49 |
60 |
▶ | if (!p) croak("out of memory"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!p) croak("out of memory"); |
0 |
60 |
60 |
|
| 50 |
60 |
| b->ints = p; b->capint = newcap; |
| 51 |
|
| } |
| 52 |
8656 |
| b->ints[b->nint++] = k; |
| 53 |
8656 |
| } |
| 54 |
4233 |
| static void ph_builder_add_str(PhBuilder *b, const void *k, size_t len) { |
| 55 |
4233 |
▶ | if (!b->arena || b->arena_len + len > b->arena_cap) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (!b->arena || b->arena_len + len > b->arena_cap) { |
4215 |
18 |
4233 |
| if (!b->arena || b->arena_len + len > b->arena_cap) { |
13 |
4202 |
4215 |
|
| 56 |
31 |
▶ | size_t newcap = b->arena_cap ? b->arena_cap : 4096; |
Branch: 1 branch
| Branch | True | False | Total |
| size_t newcap = b->arena_cap ? b->arena_cap : 4096; |
13 |
18 |
31 |
|
| 57 |
44 |
▶ | while (newcap < b->arena_len + len) newcap *= 2; |
Branch: 1 branch
| Branch | True | False | Total |
| while (newcap < b->arena_len + len) newcap *= 2; |
13 |
31 |
44 |
|
| 58 |
31 |
| uint8_t *p = (uint8_t*)realloc(b->arena, newcap); |
| 59 |
31 |
▶ | if (!p) croak("out of memory"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!p) croak("out of memory"); |
0 |
31 |
31 |
|
| 60 |
31 |
| b->arena = p; b->arena_cap = newcap; |
| 61 |
|
| } |
| 62 |
4233 |
▶ | if (b->nstr == b->capstr) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (b->nstr == b->capstr) { |
39 |
4194 |
4233 |
|
| 63 |
39 |
▶ | size_t newcap = b->capstr ? b->capstr*2 : 16; |
Branch: 1 branch
| Branch | True | False | Total |
| size_t newcap = b->capstr ? b->capstr*2 : 16; |
21 |
18 |
39 |
|
| 64 |
39 |
| PhStrSlot *p = (PhStrSlot*)realloc(b->sslots, newcap*sizeof(PhStrSlot)); |
| 65 |
39 |
▶ | if (!p) croak("out of memory"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!p) croak("out of memory"); |
0 |
39 |
39 |
|
| 66 |
39 |
| b->sslots = p; b->capstr = newcap; |
| 67 |
|
| } |
| 68 |
4233 |
| PhStrSlot s = { b->arena_len, len }; |
| 69 |
4233 |
| memcpy(b->arena + b->arena_len, k, len); b->arena_len += len; |
| 70 |
4233 |
| b->sslots[b->nstr++] = s; |
| 71 |
4233 |
| } |
| 72 |
51 |
▶ | static size_t ph_builder_count(const PhBuilder *b) { return b->key_type==PH_TYPE_INT ? b->nint : b->nstr; } |
Branch: 1 branch
| Branch | True | False | Total |
| static size_t ph_builder_count(const PhBuilder *b) { return b->key_type==PH_TYPE_INT ? b->nint : b->nstr; } |
26 |
25 |
51 |
|
| 73 |
47 |
▶ | static void ph_builder_free(PhBuilder *b) { if(!b) return; free(b->ints); free(b->arena); free(b->sslots); free(b); } |
Branch: 1 branch
| Branch | True | False | Total |
| static void ph_builder_free(PhBuilder *b) { if(!b) return; free(b->ints); free(b->arena); free(b->sslots); free(b); } |
0 |
47 |
47 |
|
| 74 |
|
| |
| 75 |
|
| /* --- CHD build: comparator helpers ------------------------------------- |
| 76 |
|
| * The two qsort() comparators below need extra context (the builder, for byte |
| 77 |
|
| * comparison; the bucket-size array, for the descending sort) that plain |
| 78 |
|
| * qsort() has no way to pass through. qsort_r() would do it, but its argument |
| 79 |
|
| * order differs between glibc and BSD/macOS -- so instead, a pair of PH_TLS |
| 80 |
|
| * "current call" pointers, set immediately before each qsort() and read only from inside it. */ |
| 81 |
|
| static PH_TLS const PhBuilder *ph_cmp_ctx_builder; |
| 82 |
|
| static PH_TLS const uint64_t *ph_cmp_ctx_bsize; |
| 83 |
|
| |
| 84 |
106879 |
| static int cmp_i64(const void*a,const void*b){int64_t x=*(const int64_t*)a,y=*(const int64_t*)b;return (x>y)-(x<y);} |
| 85 |
|
| |
| 86 |
|
| /* Hash of the survivor key at builder-index idx (int: value; str: arena bytes). */ |
| 87 |
15743632 |
| static inline uint64_t ph_hash_of(const PhBuilder *b, size_t idx, uint64_t seed) { |
| 88 |
15743632 |
▶ | if (b->key_type == PH_TYPE_INT) return ph_h_int(b->ints[idx], seed); |
Branch: 1 branch
| Branch | True | False | Total |
| if (b->key_type == PH_TYPE_INT) return ph_h_int(b->ints[idx], seed); |
11517049 |
4226583 |
15743632 |
|
| 89 |
4226583 |
| { const PhStrSlot *ss = &b->sslots[idx]; return ph_h_str(b->arena + ss->off, ss->len, seed); } |
| 90 |
|
| } |
| 91 |
|
| |
| 92 |
|
| /* Lexicographic order over string keys, referenced by index into b->sslots. */ |
| 93 |
72903 |
| static int ph_cmp_stridx(const void *pa, const void *pb) { |
| 94 |
72903 |
| size_t ia = *(const size_t*)pa, ib = *(const size_t*)pb; |
| 95 |
72903 |
| const PhBuilder *b = ph_cmp_ctx_builder; |
| 96 |
72903 |
| const PhStrSlot *sa = &b->sslots[ia], *sb = &b->sslots[ib]; |
| 97 |
72903 |
| size_t n = sa->len < sb->len ? sa->len : sb->len; |
| 98 |
72903 |
▶ | int c = n ? memcmp(b->arena + sa->off, b->arena + sb->off, n) : 0; |
Branch: 1 branch
| Branch | True | False | Total |
| int c = n ? memcmp(b->arena + sa->off, b->arena + sb->off, n) : 0; |
67043 |
5860 |
72903 |
|
| 99 |
72903 |
▶ | if (c) return c; |
Branch: 1 branch
| Branch | True | False | Total |
| if (c) return c; |
62778 |
10125 |
72903 |
|
| 100 |
10125 |
▶ | if (sa->len != sb->len) return (sa->len > sb->len) - (sa->len < sb->len); |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa->len != sb->len) return (sa->len > sb->len) - (sa->len < sb->len); |
5146 |
4979 |
10125 |
|
| 101 |
4979 |
| return 0; |
| 102 |
|
| } |
| 103 |
8531 |
| static int ph_stridx_ne(const PhBuilder *b, size_t ia, size_t ib) { |
| 104 |
8531 |
| const PhStrSlot *sa = &b->sslots[ia], *sb = &b->sslots[ib]; |
| 105 |
8531 |
▶ | return sa->len != sb->len || memcmp(b->arena + sa->off, b->arena + sb->off, sa->len) != 0; |
Branch: 2 branches
| Branch | True | False | Total |
| return sa->len != sb->len || memcmp(b->arena + sa->off, b->arena + sb->off, sa->len) != 0; |
3854 |
4677 |
8531 |
| return sa->len != sb->len || memcmp(b->arena + sa->off, b->arena + sb->off, sa->len) != 0; |
295 |
3559 |
3854 |
|
| 106 |
|
| } |
| 107 |
|
| /* Descending sort of bucket ids by size -- standard CHD heuristic: hardest (largest) buckets get first pick of displacement values. */ |
| 108 |
17163 |
| static int ph_cmp_bkt_desc(const void *pa, const void *pb) { |
| 109 |
17163 |
| uint64_t ba = *(const uint64_t*)pa, bb = *(const uint64_t*)pb; |
| 110 |
17163 |
| uint64_t sa = ph_cmp_ctx_bsize[ba], sb = ph_cmp_ctx_bsize[bb]; |
| 111 |
17163 |
| return (sa < sb) - (sa > sb); |
| 112 |
|
| } |
| 113 |
|
| /* Sum of survivor key lengths -- the str arena size needed in the image. */ |
| 114 |
29 |
| static uint64_t ph_arena_len_final(const PhBuilder *b, const size_t *idx, size_t N) { |
| 115 |
29 |
| uint64_t total = 0; size_t i; |
| 116 |
5027 |
▶ | for (i = 0; i < N; i++) total += b->sslots[idx[i]].len; |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < N; i++) total += b->sslots[idx[i]].len; |
4998 |
29 |
5027 |
|
| 117 |
29 |
| return total; |
| 118 |
|
| } |
| 119 |
|
| |
| 120 |
|
| /* Build over the collected keys; write image to path. err on failure. */ |
| 121 |
65 |
| static int ph_build(PhBuilder *b, const char *path, mode_t mode, char *err, size_t el) { |
| 122 |
|
| /* --- gather N distinct keys as (hashable) entries --- */ |
| 123 |
|
| size_t N; |
| 124 |
|
| /* Index array 0..N-1 into the builder's key store, after dedup. Every |
| 125 |
|
| * pointer below is hoisted here (NULL until allocated) so PHB_OOM() can |
| 126 |
|
| * free(NULL)-safely unwind from any allocation site, including img itself |
| 127 |
|
| * -- which is fully assembled in memory before the output file is ever opened, so OOM never leaves a partial file behind. */ |
| 128 |
65 |
| size_t *idx = NULL; /* surviving key indices */ |
| 129 |
65 |
| uint32_t *disp = NULL; |
| 130 |
65 |
| char *occ = NULL; |
| 131 |
65 |
| uint64_t *bkt_of = NULL, *order = NULL, *bsize = NULL, *tmp_slots = NULL, *boff = NULL, *mem = NULL; |
| 132 |
65 |
| uint8_t *img = NULL; |
| 133 |
|
| #define PHB_FREEALL() do { \ |
| 134 |
|
| free(idx);free(disp);free(occ);free(bkt_of);free(order);free(bsize); \ |
| 135 |
|
| free(tmp_slots);free(boff);free(mem);free(img); \ |
| 136 |
|
| } while (0) |
| 137 |
|
| #define PHB_OOM() do { PHB_FREEALL(); snprintf(err,el,"out of memory"); return -1; } while (0) |
| 138 |
65 |
▶ | if (b->key_type == PH_TYPE_INT) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (b->key_type == PH_TYPE_INT) { |
36 |
29 |
65 |
|
| 139 |
|
| /* b->ints is NULL when empty; qsort() declares its base nonnull, so |
| 140 |
|
| * qsort(NULL,0,...) is UB even though it would sort nothing -- guard it. */ |
| 141 |
36 |
▶ | if (b->nint) qsort(b->ints, b->nint, sizeof(int64_t), cmp_i64); |
Branch: 1 branch
| Branch | True | False | Total |
| if (b->nint) qsort(b->ints, b->nint, sizeof(int64_t), cmp_i64); |
33 |
3 |
36 |
|
| 142 |
12997 |
▶ | N = 0; for (size_t i=0;i<b->nint;i++){ if(i==0||b->ints[i]!=b->ints[i-1]) b->ints[N++]=b->ints[i]; } |
Branch: 3 branches
| Branch | True | False | Total |
| N = 0; for (size_t i=0;i<b->nint;i++){ if(i==0||b->ints[i]!=b->ints[i-1]) b->ints[N++]=b->ints[i]; } |
12928 |
33 |
12961 |
| N = 0; for (size_t i=0;i<b->nint;i++){ if(i==0||b->ints[i]!=b->ints[i-1]) b->ints[N++]=b->ints[i]; } |
9694 |
3234 |
12928 |
| N = 0; for (size_t i=0;i<b->nint;i++){ if(i==0||b->ints[i]!=b->ints[i-1]) b->ints[N++]=b->ints[i]; } |
12961 |
36 |
12997 |
|
| 143 |
36 |
▶ | idx = (size_t*)malloc((N?N:1)*sizeof(size_t)); if (!idx) PHB_OOM(); |
Branch: 2 branches
| Branch | True | False | Total |
| idx = (size_t*)malloc((N?N:1)*sizeof(size_t)); if (!idx) PHB_OOM(); |
33 |
3 |
36 |
| idx = (size_t*)malloc((N?N:1)*sizeof(size_t)); if (!idx) PHB_OOM(); |
0 |
36 |
36 |
|
| 144 |
9763 |
▶ | for(size_t i=0;i<N;i++) idx[i]=i; |
Branch: 1 branch
| Branch | True | False | Total |
| for(size_t i=0;i<N;i++) idx[i]=i; |
9727 |
36 |
9763 |
|
| 145 |
|
| } else { |
| 146 |
|
| /* dedup str keys: sort an index array over the arena bytes, then unique it */ |
| 147 |
29 |
| N = b->nstr; |
| 148 |
29 |
▶ | idx = (size_t*)malloc((N?N:1)*sizeof(size_t)); if (!idx) PHB_OOM(); |
Branch: 2 branches
| Branch | True | False | Total |
| idx = (size_t*)malloc((N?N:1)*sizeof(size_t)); if (!idx) PHB_OOM(); |
26 |
3 |
29 |
| idx = (size_t*)malloc((N?N:1)*sizeof(size_t)); if (!idx) PHB_OOM(); |
0 |
29 |
29 |
|
| 149 |
8586 |
▶ | for(size_t i=0;i<N;i++) idx[i]=i; |
Branch: 1 branch
| Branch | True | False | Total |
| for(size_t i=0;i<N;i++) idx[i]=i; |
8557 |
29 |
8586 |
|
| 150 |
29 |
| ph_cmp_ctx_builder = b; |
| 151 |
29 |
| qsort(idx, N, sizeof(size_t), ph_cmp_stridx); |
| 152 |
8586 |
▶ | size_t w=0; for(size_t i=0;i<N;i++){ if(i==0 || ph_stridx_ne(b, idx[i], idx[i-1])) idx[w++]=idx[i]; } |
Branch: 3 branches
| Branch | True | False | Total |
| size_t w=0; for(size_t i=0;i<N;i++){ if(i==0 || ph_stridx_ne(b, idx[i], idx[i-1])) idx[w++]=idx[i]; } |
8531 |
26 |
8557 |
| size_t w=0; for(size_t i=0;i<N;i++){ if(i==0 || ph_stridx_ne(b, idx[i], idx[i-1])) idx[w++]=idx[i]; } |
4972 |
3559 |
8531 |
| size_t w=0; for(size_t i=0;i<N;i++){ if(i==0 || ph_stridx_ne(b, idx[i], idx[i-1])) idx[w++]=idx[i]; } |
8557 |
29 |
8586 |
|
| 153 |
29 |
| N = w; |
| 154 |
|
| } |
| 155 |
|
| /* n==N: exactly minimal, no slack. sort-desc (below) places multi-key |
| 156 |
|
| * buckets first while slots are still free; the working disp[] stays a |
| 157 |
|
| * full uint32 here (only the emitted image, further down, is byte-packed to |
| 158 |
|
| * the minimal width), so even the last free slot is found within the 2^32 |
| 159 |
|
| * search range. r==1 for N==0 keeps the '% r' bucketing well-defined (no key ever reaches it). */ |
| 160 |
65 |
▶ | uint64_t n = N, r = N ? (N/PH_LAMBDA + (N%PH_LAMBDA ? 1 : 0)) : 1; |
Branch: 2 branches
| Branch | True | False | Total |
| uint64_t n = N, r = N ? (N/PH_LAMBDA + (N%PH_LAMBDA ? 1 : 0)) : 1; |
59 |
6 |
65 |
| uint64_t n = N, r = N ? (N/PH_LAMBDA + (N%PH_LAMBDA ? 1 : 0)) : 1; |
56 |
3 |
59 |
|
| 161 |
65 |
▶ | disp = (uint32_t*)calloc(r, sizeof(uint32_t)); if (!disp) PHB_OOM(); |
Branch: 1 branch
| Branch | True | False | Total |
| disp = (uint32_t*)calloc(r, sizeof(uint32_t)); if (!disp) PHB_OOM(); |
0 |
65 |
65 |
|
| 162 |
65 |
▶ | occ = (char*)calloc(n?n:1,1); if (!occ) PHB_OOM(); |
Branch: 2 branches
| Branch | True | False | Total |
| occ = (char*)calloc(n?n:1,1); if (!occ) PHB_OOM(); |
59 |
6 |
65 |
| occ = (char*)calloc(n?n:1,1); if (!occ) PHB_OOM(); |
0 |
65 |
65 |
|
| 163 |
|
| /* bucket assignment buffers */ |
| 164 |
65 |
▶ | bkt_of = (uint64_t*)malloc((N?N:1)*sizeof(uint64_t)); if (!bkt_of) PHB_OOM(); |
Branch: 2 branches
| Branch | True | False | Total |
| bkt_of = (uint64_t*)malloc((N?N:1)*sizeof(uint64_t)); if (!bkt_of) PHB_OOM(); |
59 |
6 |
65 |
| bkt_of = (uint64_t*)malloc((N?N:1)*sizeof(uint64_t)); if (!bkt_of) PHB_OOM(); |
0 |
65 |
65 |
|
| 165 |
65 |
▶ | order = (uint64_t*)malloc(r*sizeof(uint64_t)); if (!order) PHB_OOM(); /* bucket ids sorted by size desc */ |
Branch: 1 branch
| Branch | True | False | Total |
| order = (uint64_t*)malloc(r*sizeof(uint64_t)); if (!order) PHB_OOM(); /* bucket ids sorted by size desc */ |
0 |
65 |
65 |
|
| 166 |
65 |
▶ | bsize = (uint64_t*)malloc(r*sizeof(uint64_t)); if (!bsize) PHB_OOM(); |
Branch: 1 branch
| Branch | True | False | Total |
| bsize = (uint64_t*)malloc(r*sizeof(uint64_t)); if (!bsize) PHB_OOM(); |
0 |
65 |
65 |
|
| 167 |
65 |
| uint64_t seed0 = 0x243F6A8885A308D3ull; |
| 168 |
65 |
| uint64_t tmp_slots_cap = n; |
| 169 |
65 |
▶ | tmp_slots = (uint64_t*)malloc((tmp_slots_cap?tmp_slots_cap:1)*sizeof(uint64_t)); if (!tmp_slots) PHB_OOM(); |
Branch: 2 branches
| Branch | True | False | Total |
| tmp_slots = (uint64_t*)malloc((tmp_slots_cap?tmp_slots_cap:1)*sizeof(uint64_t)); if (!tmp_slots) PHB_OOM(); |
59 |
6 |
65 |
| tmp_slots = (uint64_t*)malloc((tmp_slots_cap?tmp_slots_cap:1)*sizeof(uint64_t)); if (!tmp_slots) PHB_OOM(); |
0 |
65 |
65 |
|
| 170 |
|
| /* keys grouped per bucket: build a CSR (offsets + members) each attempt */ |
| 171 |
65 |
▶ | boff = (uint64_t*)malloc((r+1)*sizeof(uint64_t)); if (!boff) PHB_OOM(); |
Branch: 1 branch
| Branch | True | False | Total |
| boff = (uint64_t*)malloc((r+1)*sizeof(uint64_t)); if (!boff) PHB_OOM(); |
0 |
65 |
65 |
|
| 172 |
65 |
▶ | mem = (uint64_t*)malloc((N?N:1)*sizeof(uint64_t)); if (!mem) PHB_OOM(); |
Branch: 2 branches
| Branch | True | False | Total |
| mem = (uint64_t*)malloc((N?N:1)*sizeof(uint64_t)); if (!mem) PHB_OOM(); |
59 |
6 |
65 |
| mem = (uint64_t*)malloc((N?N:1)*sizeof(uint64_t)); if (!mem) PHB_OOM(); |
0 |
65 |
65 |
|
| 173 |
|
| |
| 174 |
|
| /* Cap the per-bucket displacement scan far above any real max_d (real sets |
| 175 |
|
| * need ~4*n; dcap is 256*n, floored at 65536), so genuine convergence is |
| 176 |
|
| * untouched but a pathological/adversarial bucket bails out quickly and |
| 177 |
|
| * reseeds instead of scanning the full 2^32 range for hours. */ |
| 178 |
65 |
▶ | uint64_t dcap = (n > 0xFFFFFFFFull/256 ? 0xFFFFFFFFull : 256*n); |
Branch: 1 branch
| Branch | True | False | Total |
| uint64_t dcap = (n > 0xFFFFFFFFull/256 ? 0xFFFFFFFFull : 256*n); |
65 |
0 |
65 |
|
| 179 |
65 |
▶ | if (dcap < 65536) dcap = 65536; |
Branch: 1 branch
| Branch | True | False | Total |
| if (dcap < 65536) dcap = 65536; |
56 |
9 |
65 |
|
| 180 |
|
| |
| 181 |
65 |
| int placed = 0; |
| 182 |
72 |
▶ | for (int attempt = 0; attempt < 200 && !placed; attempt++, seed0 = seed0*6364136223846793005ull + 1) { |
Branch: 2 branches
| Branch | True | False | Total |
| for (int attempt = 0; attempt < 200 && !placed; attempt++, seed0 = seed0*6364136223846793005ull + 1) { |
72 |
0 |
72 |
| for (int attempt = 0; attempt < 200 && !placed; attempt++, seed0 = seed0*6364136223846793005ull + 1) { |
72 |
0 |
72 |
|
| 183 |
72 |
| memset(occ,0,n); memset(disp,0,r*sizeof(uint32_t)); memset(bsize,0,r*sizeof(uint64_t)); |
| 184 |
15779 |
▶ | for (size_t i=0;i<N;i++){ uint64_t hb = ph_hash_of(b, idx[i], seed0); uint64_t bk = hb % r; bkt_of[i]=bk; bsize[bk]++; } |
Branch: 1 branch
| Branch | True | False | Total |
| for (size_t i=0;i<N;i++){ uint64_t hb = ph_hash_of(b, idx[i], seed0); uint64_t bk = hb % r; bkt_of[i]=bk; bsize[bk]++; } |
15707 |
72 |
15779 |
|
| 185 |
2732 |
▶ | boff[0]=0; for (uint64_t k2=0;k2<r;k2++) boff[k2+1]=boff[k2]+bsize[k2]; |
Branch: 1 branch
| Branch | True | False | Total |
| boff[0]=0; for (uint64_t k2=0;k2<r;k2++) boff[k2+1]=boff[k2]+bsize[k2]; |
2660 |
72 |
2732 |
|
| 186 |
72 |
▶ | { uint64_t *cur=(uint64_t*)malloc(r*sizeof(uint64_t)); if (!cur) PHB_OOM(); |
Branch: 1 branch
| Branch | True | False | Total |
| { uint64_t *cur=(uint64_t*)malloc(r*sizeof(uint64_t)); if (!cur) PHB_OOM(); |
0 |
72 |
72 |
|
| 187 |
72 |
| memcpy(cur,boff,r*sizeof(uint64_t)); |
| 188 |
15779 |
▶ | for(size_t i=0;i<N;i++){ mem[cur[bkt_of[i]]++]=idx[i]; } free(cur); } |
Branch: 1 branch
| Branch | True | False | Total |
| for(size_t i=0;i<N;i++){ mem[cur[bkt_of[i]]++]=idx[i]; } free(cur); } |
15707 |
72 |
15779 |
|
| 189 |
2732 |
▶ | for (uint64_t k2=0;k2<r;k2++) order[k2]=k2; |
Branch: 1 branch
| Branch | True | False | Total |
| for (uint64_t k2=0;k2<r;k2++) order[k2]=k2; |
2660 |
72 |
2732 |
|
| 190 |
72 |
| ph_cmp_ctx_bsize = bsize; |
| 191 |
72 |
| qsort(order,r,sizeof(uint64_t),ph_cmp_bkt_desc); |
| 192 |
72 |
| int ok = 1; |
| 193 |
2720 |
▶ | for (uint64_t oi=0; oi<r && ok; oi++) { |
Branch: 2 branches
| Branch | True | False | Total |
| for (uint64_t oi=0; oi<r && ok; oi++) { |
2652 |
68 |
2720 |
| for (uint64_t oi=0; oi<r && ok; oi++) { |
2648 |
4 |
2652 |
|
| 194 |
2648 |
▶ | uint64_t bk=order[oi]; uint64_t cnt=bsize[bk]; if(!cnt) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| uint64_t bk=order[oi]; uint64_t cnt=bsize[bk]; if(!cnt) continue; |
10 |
2638 |
2648 |
|
| 195 |
2638 |
| int found=0; |
| 196 |
|
| /* Search up to dcap (<= UINT32_MAX); d is uint64_t purely so |
| 197 |
|
| * "d <= dcap; d++" terminates cleanly instead of wrapping a uint32_t back to 0 when dcap == UINT32_MAX. */ |
| 198 |
14594159 |
▶ | for (uint64_t d=0; d<=dcap; d++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (uint64_t d=0; d<=dcap; d++) { |
14594152 |
7 |
14594159 |
|
| 199 |
14594152 |
| int good=1; uint64_t m=ph_mix(seed0,d); |
| 200 |
15701106 |
▶ | for (uint64_t j=0;j<cnt;j++){ uint64_t s=ph_hash_of(b, mem[boff[bk]+j], m)%n; tmp_slots[j]=s; |
Branch: 1 branch
| Branch | True | False | Total |
| for (uint64_t j=0;j<cnt;j++){ uint64_t s=ph_hash_of(b, mem[boff[bk]+j], m)%n; tmp_slots[j]=s; |
15698475 |
2631 |
15701106 |
|
| 201 |
15698475 |
▶ | if (occ[s]) { good=0; break; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (occ[s]) { good=0; break; } |
14588307 |
1110168 |
15698475 |
|
| 202 |
1392267 |
▶ | for (uint64_t p=0;p<j;p++) if (tmp_slots[p]==s){ good=0; break; } |
Branch: 2 branches
| Branch | True | False | Total |
| for (uint64_t p=0;p<j;p++) if (tmp_slots[p]==s){ good=0; break; } |
3214 |
282099 |
285313 |
| for (uint64_t p=0;p<j;p++) if (tmp_slots[p]==s){ good=0; break; } |
285313 |
1106954 |
1392267 |
|
| 203 |
1110168 |
▶ | if(!good) break; } |
Branch: 1 branch
| Branch | True | False | Total |
| if(!good) break; } |
3214 |
1106954 |
1110168 |
|
| 204 |
14609803 |
▶ | if (good){ for(uint64_t j=0;j<cnt;j++) occ[tmp_slots[j]]=1; disp[bk]=(uint32_t)d; found=1; break; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (good){ for(uint64_t j=0;j<cnt;j++) occ[tmp_slots[j]]=1; disp[bk]=(uint32_t)d; found=1; break; } |
2631 |
14591521 |
14594152 |
| if (good){ for(uint64_t j=0;j<cnt;j++) occ[tmp_slots[j]]=1; disp[bk]=(uint32_t)d; found=1; break; } |
15651 |
2631 |
18282 |
|
| 205 |
|
| } |
| 206 |
2638 |
▶ | if(!found) ok=0; |
Branch: 1 branch
| Branch | True | False | Total |
| if(!found) ok=0; |
7 |
2631 |
2638 |
|
| 207 |
|
| } |
| 208 |
|
| /* WARNING: must break here, not just set placed=1 and fall through. |
| 209 |
|
| * The for-loop's increment (seed0 = seed0*...+1) still runs once more |
| 210 |
|
| * even on the successful iteration -- only the *next* condition check |
| 211 |
|
| * is skipped. Falling through would silently advance seed0 past the |
| 212 |
|
| * value actually used to compute disp[]/bkt_of[] above, so the header |
| 213 |
|
| * would record a seed inconsistent with the written displacement array -- has() would then fail for essentially every key. */ |
| 214 |
72 |
▶ | if (ok) { placed = 1; break; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (ok) { placed = 1; break; } |
65 |
7 |
72 |
|
| 215 |
|
| } |
| 216 |
65 |
▶ | if (!placed) { snprintf(err,el,"CHD build failed to converge (pathological key set)"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!placed) { snprintf(err,el,"CHD build failed to converge (pathological key set)"); |
0 |
65 |
65 |
|
| 217 |
0 |
| PHB_FREEALL(); return -1; } |
| 218 |
|
| |
| 219 |
|
| /* --- pick the minimal byte width holding every displacement (r*disp_width |
| 220 |
|
| * bytes instead of r*4). In practice max_d ~ n, so disp_width is 1..3 for |
| 221 |
|
| * any realistic set (4 is the safety ceiling); always >=1, even for the empty set (r==1,d==0). */ |
| 222 |
65 |
| uint32_t max_d = 0; |
| 223 |
2559 |
▶ | for (uint64_t k2=0;k2<r;k2++) if (disp[k2] > max_d) max_d = disp[k2]; |
Branch: 2 branches
| Branch | True | False | Total |
| for (uint64_t k2=0;k2<r;k2++) if (disp[k2] > max_d) max_d = disp[k2]; |
161 |
2333 |
2494 |
| for (uint64_t k2=0;k2<r;k2++) if (disp[k2] > max_d) max_d = disp[k2]; |
2494 |
65 |
2559 |
|
| 224 |
65 |
▶ | uint32_t disp_width = max_d <= 0xFFu ? 1u : max_d <= 0xFFFFu ? 2u : max_d <= 0xFFFFFFu ? 3u : 4u; |
Branch: 3 branches
| Branch | True | False | Total |
| uint32_t disp_width = max_d <= 0xFFu ? 1u : max_d <= 0xFFFFu ? 2u : max_d <= 0xFFFFFFu ? 3u : 4u; |
23 |
42 |
65 |
| uint32_t disp_width = max_d <= 0xFFu ? 1u : max_d <= 0xFFFFu ? 2u : max_d <= 0xFFFFFFu ? 3u : 4u; |
9 |
14 |
23 |
| uint32_t disp_width = max_d <= 0xFFu ? 1u : max_d <= 0xFFFFu ? 2u : max_d <= 0xFFFFFFu ? 3u : 4u; |
9 |
0 |
9 |
|
| 225 |
|
| |
| 226 |
|
| /* --- compute the FINAL slot for each key, lay out the image, write it --- */ |
| 227 |
65 |
| uint64_t disp_off = sizeof(PhHeader); |
| 228 |
65 |
| uint64_t disp_bytes = r * (uint64_t)disp_width; |
| 229 |
65 |
| uint64_t slots_off = (disp_off + disp_bytes + 7) & ~(uint64_t)7; /* 8-byte align slots[] (int64_t/PhStrSlot); disp[] is byte-packed, needs none */ |
| 230 |
65 |
▶ | uint64_t slot_sz = (b->key_type==PH_TYPE_INT) ? sizeof(int64_t) : sizeof(PhStrSlot); |
Branch: 1 branch
| Branch | True | False | Total |
| uint64_t slot_sz = (b->key_type==PH_TYPE_INT) ? sizeof(int64_t) : sizeof(PhStrSlot); |
36 |
29 |
65 |
|
| 231 |
65 |
| uint64_t arena_off = slots_off + n*slot_sz; |
| 232 |
65 |
▶ | uint64_t arena_len = (b->key_type==PH_TYPE_STR) ? ph_arena_len_final(b, idx, N) : 0; /* sum of surviving key lens */ |
Branch: 1 branch
| Branch | True | False | Total |
| uint64_t arena_len = (b->key_type==PH_TYPE_STR) ? ph_arena_len_final(b, idx, N) : 0; /* sum of surviving key lens */ |
29 |
36 |
65 |
|
| 233 |
65 |
| uint64_t file_size = arena_off + arena_len; |
| 234 |
65 |
▶ | img = (uint8_t*)calloc(file_size?file_size:1,1); if (!img) PHB_OOM(); |
Branch: 2 branches
| Branch | True | False | Total |
| img = (uint8_t*)calloc(file_size?file_size:1,1); if (!img) PHB_OOM(); |
65 |
0 |
65 |
| img = (uint8_t*)calloc(file_size?file_size:1,1); if (!img) PHB_OOM(); |
0 |
65 |
65 |
|
| 235 |
65 |
| PhHeader *H = (PhHeader*)img; |
| 236 |
65 |
| H->magic=PH_MAGIC; H->version=PH_VERSION; H->key_type=b->key_type; H->disp_width=disp_width; |
| 237 |
65 |
| H->endian=PH_ENDIAN_MARK; H->n=n; H->bucket_count=r; H->seed0=seed0; |
| 238 |
65 |
| H->disp_off=disp_off; H->disp_len=disp_bytes; H->slots_off=slots_off; H->slots_len=n*slot_sz; |
| 239 |
65 |
| H->arena_off=arena_off; H->arena_len=arena_len; H->file_size=file_size; |
| 240 |
|
| /* Emit disp[] byte-packed: disp_width little-endian bytes per entry, exactly |
| 241 |
|
| * what ph_load_uint_le reads back. img is calloc'd, so all padding stays zero (deterministic image, no heap disclosure). */ |
| 242 |
2559 |
▶ | for (uint64_t bkt=0; bkt<r; bkt++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (uint64_t bkt=0; bkt<r; bkt++) { |
2494 |
65 |
2559 |
|
| 243 |
2494 |
| uint32_t d = disp[bkt]; |
| 244 |
9718 |
▶ | for (uint32_t wi=0; wi<disp_width; wi++) img[disp_off + bkt*disp_width + wi] = (uint8_t)(d >> (8u*wi)); |
Branch: 1 branch
| Branch | True | False | Total |
| for (uint32_t wi=0; wi<disp_width; wi++) img[disp_off + bkt*disp_width + wi] = (uint8_t)(d >> (8u*wi)); |
7224 |
2494 |
9718 |
|
| 245 |
|
| } |
| 246 |
|
| /* place each key at slot = hash(key, mix(seed0, disp[bucket])) % n */ |
| 247 |
65 |
| uint64_t awrite = 0; |
| 248 |
14790 |
▶ | for (size_t i=0;i<N;i++){ |
Branch: 1 branch
| Branch | True | False | Total |
| for (size_t i=0;i<N;i++){ |
14725 |
65 |
14790 |
|
| 249 |
14725 |
| uint64_t bk = ph_hash_of(b, idx[i], seed0) % r; |
| 250 |
14725 |
| uint64_t slot = ph_hash_of(b, idx[i], ph_mix(seed0, disp[bk])) % n; |
| 251 |
14725 |
▶ | if (b->key_type==PH_TYPE_INT) ((int64_t*)(img+slots_off))[slot] = b->ints[idx[i]]; |
Branch: 1 branch
| Branch | True | False | Total |
| if (b->key_type==PH_TYPE_INT) ((int64_t*)(img+slots_off))[slot] = b->ints[idx[i]]; |
9727 |
4998 |
14725 |
|
| 252 |
4998 |
| else { PhStrSlot *ss=&((PhStrSlot*)(img+slots_off))[slot]; size_t len=b->sslots[idx[i]].len; |
| 253 |
4998 |
| memcpy(img+arena_off+awrite, b->arena+b->sslots[idx[i]].off, len); |
| 254 |
4998 |
| ss->off=awrite; ss->len=len; awrite+=len; } |
| 255 |
|
| } |
| 256 |
|
| /* Atomic write: build a temp file in the SAME directory, then rename(2) it |
| 257 |
|
| * over `path`. Readers mmap `path`, and O_TRUNC on a mapped file would |
| 258 |
|
| * SIGBUS them; rename instead leaves the old inode alive until they unmap. |
| 259 |
|
| * mkstemp creates it O_CREAT|O_EXCL 0600 (no symlink to follow, so unlike |
| 260 |
|
| * ph_open's read side this needs no O_NOFOLLOW); fchmod applies the requested mode after. */ |
| 261 |
65 |
| size_t plen = strlen(path); |
| 262 |
65 |
| char *tmp = (char*)malloc(plen + 12); |
| 263 |
65 |
▶ | if (!tmp) { snprintf(err,el,"out of memory"); PHB_FREEALL(); return -1; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (!tmp) { snprintf(err,el,"out of memory"); PHB_FREEALL(); return -1; } |
0 |
65 |
65 |
|
| 264 |
65 |
| memcpy(tmp, path, plen); memcpy(tmp+plen, ".tmpXXXXXX", 11); /* 10 chars + NUL */ |
| 265 |
65 |
| int fd = mkstemp(tmp); /* creates 0600, O_EXCL; fills XXXXXX */ |
| 266 |
65 |
▶ | if (fd < 0) { snprintf(err,el,"mkstemp %s: %s", tmp, strerror(errno)); free(tmp); PHB_FREEALL(); return -1; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (fd < 0) { snprintf(err,el,"mkstemp %s: %s", tmp, strerror(errno)); free(tmp); PHB_FREEALL(); return -1; } |
0 |
65 |
65 |
|
| 267 |
65 |
| int rc = 0; |
| 268 |
65 |
▶ | if (fchmod(fd, mode) != 0) { snprintf(err,el,"fchmod: %s", strerror(errno)); rc=-1; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (fchmod(fd, mode) != 0) { snprintf(err,el,"fchmod: %s", strerror(errno)); rc=-1; } |
0 |
65 |
65 |
|
| 269 |
|
| else { |
| 270 |
65 |
| size_t off = 0; |
| 271 |
130 |
▶ | while (off < file_size) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (off < file_size) { |
65 |
65 |
130 |
|
| 272 |
65 |
| ssize_t w = write(fd, img + off, file_size - off); |
| 273 |
65 |
▶ | if (w < 0 && errno == EINTR) continue; |
Branch: 2 branches
| Branch | True | False | Total |
| if (w < 0 && errno == EINTR) continue; |
0 |
65 |
65 |
| if (w < 0 && errno == EINTR) continue; |
0 |
0 |
0 |
|
| 274 |
65 |
▶ | if (w <= 0) { snprintf(err,el,"write: %s",strerror(w == 0 ? EIO : errno)); rc=-1; break; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (w <= 0) { snprintf(err,el,"write: %s",strerror(w == 0 ? EIO : errno)); rc=-1; break; } |
0 |
65 |
65 |
| if (w <= 0) { snprintf(err,el,"write: %s",strerror(w == 0 ? EIO : errno)); rc=-1; break; } |
0 |
0 |
0 |
|
| 275 |
65 |
| off += w; |
| 276 |
|
| } |
| 277 |
|
| } |
| 278 |
65 |
▶ | if (close(fd) != 0 && rc == 0) { snprintf(err,el,"close: %s",strerror(errno)); rc=-1; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (close(fd) != 0 && rc == 0) { snprintf(err,el,"close: %s",strerror(errno)); rc=-1; } |
0 |
65 |
65 |
| if (close(fd) != 0 && rc == 0) { snprintf(err,el,"close: %s",strerror(errno)); rc=-1; } |
0 |
0 |
0 |
|
| 279 |
65 |
▶ | if (rc==0 && rename(tmp, path) != 0) { snprintf(err,el,"rename %s: %s", path, strerror(errno)); rc=-1; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (rc==0 && rename(tmp, path) != 0) { snprintf(err,el,"rename %s: %s", path, strerror(errno)); rc=-1; } |
65 |
0 |
65 |
| if (rc==0 && rename(tmp, path) != 0) { snprintf(err,el,"rename %s: %s", path, strerror(errno)); rc=-1; } |
0 |
65 |
65 |
|
| 280 |
65 |
▶ | if (rc!=0) unlink(tmp); /* leave no partial temp on failure */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (rc!=0) unlink(tmp); /* leave no partial temp on failure */ |
0 |
65 |
65 |
|
| 281 |
65 |
| free(tmp); |
| 282 |
65 |
| PHB_FREEALL(); |
| 283 |
65 |
| return rc; |
| 284 |
|
| } |
| 285 |
|
| #undef PHB_OOM |
| 286 |
|
| #undef PHB_FREEALL |
| 287 |
|
| |
| 288 |
|
| #endif |