chd.h

filter: Statementstmt 99.3% 157 / 158 Branchbran 80.6% 158 / 196 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 88.9% 315 / 354 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« Shared.xs ↑ Summary phash.h »
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (b->nint == b->capint) { 60 8596 8656
47 60 ▶ size_t newcap = b->capint ? b->capint*2 : 16;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (b->nstr == b->capstr) { 39 4194 4233
63 39 ▶ size_t newcap = b->capstr ? b->capstr*2 : 16;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
uint64_t dcap = (n > 0xFFFFFFFFull/256 ? 0xFFFFFFFFull : 256*n); 65 0 65
179 65 ▶ if (dcap < 65536) dcap = 65536;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
{ 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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
« Shared.xs ↑ Summary phash.h »