/src/htslib/htslib/khash.h
Line | Count | Source (jump to first uncovered line) |
1 | | /* The MIT License |
2 | | |
3 | | Copyright (c) 2008, 2009, 2011 by Attractive Chaos <attractor@live.co.uk> |
4 | | Copyright (C) 2014-2015, 2018 Genome Research Ltd. |
5 | | |
6 | | Permission is hereby granted, free of charge, to any person obtaining |
7 | | a copy of this software and associated documentation files (the |
8 | | "Software"), to deal in the Software without restriction, including |
9 | | without limitation the rights to use, copy, modify, merge, publish, |
10 | | distribute, sublicense, and/or sell copies of the Software, and to |
11 | | permit persons to whom the Software is furnished to do so, subject to |
12 | | the following conditions: |
13 | | |
14 | | The above copyright notice and this permission notice shall be |
15 | | included in all copies or substantial portions of the Software. |
16 | | |
17 | | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
18 | | EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
19 | | MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
20 | | NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS |
21 | | BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN |
22 | | ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
23 | | CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE |
24 | | SOFTWARE. |
25 | | */ |
26 | | |
27 | | /* |
28 | | An example: |
29 | | |
30 | | #include "khash.h" |
31 | | KHASH_MAP_INIT_INT(32, char) |
32 | | int main() { |
33 | | int ret, is_missing; |
34 | | khiter_t k; |
35 | | khash_t(32) *h = kh_init(32); |
36 | | k = kh_put(32, h, 5, &ret); |
37 | | kh_value(h, k) = 10; |
38 | | k = kh_get(32, h, 10); |
39 | | is_missing = (k == kh_end(h)); |
40 | | k = kh_get(32, h, 5); |
41 | | kh_del(32, h, k); |
42 | | for (k = kh_begin(h); k != kh_end(h); ++k) |
43 | | if (kh_exist(h, k)) kh_value(h, k) = 1; |
44 | | kh_destroy(32, h); |
45 | | return 0; |
46 | | } |
47 | | */ |
48 | | |
49 | | /* |
50 | | 2013-05-02 (0.2.8): |
51 | | |
52 | | * Use quadratic probing. When the capacity is power of 2, stepping function |
53 | | i*(i+1)/2 guarantees to traverse each bucket. It is better than double |
54 | | hashing on cache performance and is more robust than linear probing. |
55 | | |
56 | | In theory, double hashing should be more robust than quadratic probing. |
57 | | However, my implementation is probably not for large hash tables, because |
58 | | the second hash function is closely tied to the first hash function, |
59 | | which reduce the effectiveness of double hashing. |
60 | | |
61 | | Reference: http://research.cs.vt.edu/AVresearch/hashing/quadratic.php |
62 | | |
63 | | 2011-12-29 (0.2.7): |
64 | | |
65 | | * Minor code clean up; no actual effect. |
66 | | |
67 | | 2011-09-16 (0.2.6): |
68 | | |
69 | | * The capacity is a power of 2. This seems to dramatically improve the |
70 | | speed for simple keys. Thank Zilong Tan for the suggestion. Reference: |
71 | | |
72 | | - http://code.google.com/p/ulib/ |
73 | | - http://nothings.org/computer/judy/ |
74 | | |
75 | | * Allow to optionally use linear probing which usually has better |
76 | | performance for random input. Double hashing is still the default as it |
77 | | is more robust to certain non-random input. |
78 | | |
79 | | * Added Wang's integer hash function (not used by default). This hash |
80 | | function is more robust to certain non-random input. |
81 | | |
82 | | 2011-02-14 (0.2.5): |
83 | | |
84 | | * Allow to declare global functions. |
85 | | |
86 | | 2009-09-26 (0.2.4): |
87 | | |
88 | | * Improve portability |
89 | | |
90 | | 2008-09-19 (0.2.3): |
91 | | |
92 | | * Corrected the example |
93 | | * Improved interfaces |
94 | | |
95 | | 2008-09-11 (0.2.2): |
96 | | |
97 | | * Improved speed a little in kh_put() |
98 | | |
99 | | 2008-09-10 (0.2.1): |
100 | | |
101 | | * Added kh_clear() |
102 | | * Fixed a compiling error |
103 | | |
104 | | 2008-09-02 (0.2.0): |
105 | | |
106 | | * Changed to token concatenation which increases flexibility. |
107 | | |
108 | | 2008-08-31 (0.1.2): |
109 | | |
110 | | * Fixed a bug in kh_get(), which has not been tested previously. |
111 | | |
112 | | 2008-08-31 (0.1.1): |
113 | | |
114 | | * Added destructor |
115 | | */ |
116 | | |
117 | | |
118 | | #ifndef __AC_KHASH_H |
119 | | #define __AC_KHASH_H |
120 | | |
121 | | /*! |
122 | | @header |
123 | | |
124 | | Generic hash table library. |
125 | | */ |
126 | | |
127 | | #define AC_VERSION_KHASH_H "0.2.8" |
128 | | |
129 | | #include <stdlib.h> |
130 | | #include <string.h> |
131 | | #include <limits.h> |
132 | | |
133 | | #include "kstring.h" |
134 | | #include "kroundup.h" |
135 | | |
136 | | /* compiler specific configuration */ |
137 | | |
138 | | #if UINT_MAX == 0xffffffffu |
139 | | typedef unsigned int khint32_t; |
140 | | #elif ULONG_MAX == 0xffffffffu |
141 | | typedef unsigned long khint32_t; |
142 | | #endif |
143 | | |
144 | | #if ULONG_MAX == ULLONG_MAX |
145 | | typedef unsigned long khint64_t; |
146 | | #else |
147 | | typedef unsigned long long khint64_t; |
148 | | #endif |
149 | | |
150 | | #ifndef kh_inline |
151 | | #ifdef _MSC_VER |
152 | | #define kh_inline __inline |
153 | | #else |
154 | | #define kh_inline inline |
155 | | #endif |
156 | | #endif /* kh_inline */ |
157 | | |
158 | | #ifndef klib_unused |
159 | | #if (defined __clang__ && __clang_major__ >= 3) || (defined __GNUC__ && __GNUC__ >= 3) |
160 | | #define klib_unused __attribute__ ((__unused__)) |
161 | | #else |
162 | | #define klib_unused |
163 | | #endif |
164 | | #endif /* klib_unused */ |
165 | | |
166 | | typedef khint32_t khint_t; |
167 | | typedef khint_t khiter_t; |
168 | | |
169 | 40.5M | #define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2) |
170 | 24.0M | #define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1) |
171 | 5.26M | #define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3) |
172 | | #define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1))) |
173 | 25.6k | #define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1))) |
174 | 23.5k | #define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1))) |
175 | 27.0k | #define __ac_set_isdel_true(flag, i) (flag[i>>4]|=1ul<<((i&0xfU)<<1)) |
176 | | |
177 | 6.01k | #define __ac_fsize(m) ((m) < 16? 1 : (m)>>4) |
178 | | |
179 | | #ifndef kroundup32 |
180 | | #define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x)) |
181 | | #endif |
182 | | |
183 | | #ifndef kcalloc |
184 | 9.14k | #define kcalloc(N,Z) calloc(N,Z) |
185 | | #endif |
186 | | #ifndef kmalloc |
187 | 12.0k | #define kmalloc(Z) malloc(Z) |
188 | | #endif |
189 | | #ifndef krealloc |
190 | 11.4k | #define krealloc(P,Z) realloc(P,Z) |
191 | | #endif |
192 | | #ifndef kfree |
193 | 42.5k | #define kfree(P) free(P) |
194 | | #endif |
195 | | |
196 | | static const double __ac_HASH_UPPER = 0.77; |
197 | | |
198 | | #define __KHASH_TYPE(name, khkey_t, khval_t) \ |
199 | | typedef struct kh_##name##_s { \ |
200 | | khint_t n_buckets, size, n_occupied, upper_bound; \ |
201 | | khint32_t *flags; \ |
202 | | khkey_t *keys; \ |
203 | | khval_t *vals; \ |
204 | | } kh_##name##_t; |
205 | | |
206 | | #define __KHASH_PROTOTYPES(name, khkey_t, khval_t) \ |
207 | | extern kh_##name##_t *kh_init_##name(void); \ |
208 | | extern void kh_destroy_##name(kh_##name##_t *h); \ |
209 | | extern void kh_clear_##name(kh_##name##_t *h); \ |
210 | | extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key); \ |
211 | | extern int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \ |
212 | | extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret); \ |
213 | | extern void kh_del_##name(kh_##name##_t *h, khint_t x); |
214 | | |
215 | | #define __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ |
216 | 9.14k | SCOPE kh_##name##_t *kh_init_##name(void) { \ |
217 | 9.14k | return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \ |
218 | 9.14k | } \ header.c:kh_init_sam_hrecs_t Line | Count | Source | 216 | 1.16k | SCOPE kh_##name##_t *kh_init_##name(void) { \ | 217 | 1.16k | return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \ | 218 | 1.16k | } \ |
Line | Count | Source | 216 | 3.49k | SCOPE kh_##name##_t *kh_init_##name(void) { \ | 217 | 3.49k | return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \ | 218 | 3.49k | } \ |
Unexecuted instantiation: header.c:kh_init_rm hfile.c:kh_init_scheme_string Line | Count | Source | 216 | 1 | SCOPE kh_##name##_t *kh_init_##name(void) { \ | 217 | 1 | return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \ | 218 | 1 | } \ |
Line | Count | Source | 216 | 566 | SCOPE kh_##name##_t *kh_init_##name(void) { \ | 217 | 566 | return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \ | 218 | 566 | } \ |
Unexecuted instantiation: hts.c:kh_init_bin Unexecuted instantiation: hts.c:kh_init_sam_hrecs_t Unexecuted instantiation: hts.c:kh_init_m_s2i Unexecuted instantiation: hts.c:kh_init_m_i2i Unexecuted instantiation: hts.c:kh_init_s_i2i Unexecuted instantiation: hts.c:kh_init_map Unexecuted instantiation: hts.c:kh_init_m_metrics Unexecuted instantiation: hts.c:kh_init_m_tagmap Unexecuted instantiation: hts.c:kh_init_refs Unexecuted instantiation: region.c:kh_init_reg Unexecuted instantiation: sam.c:kh_init_tag Unexecuted instantiation: sam.c:kh_init_olap_hash Unexecuted instantiation: sam.c:kh_init_sam_hrecs_t Unexecuted instantiation: sam.c:kh_init_m_s2i Unexecuted instantiation: sam.c:kh_init_m_i2i Unexecuted instantiation: sam.c:kh_init_s_i2i Unexecuted instantiation: sam.c:kh_init_map Unexecuted instantiation: sam.c:kh_init_m_metrics Unexecuted instantiation: sam.c:kh_init_m_tagmap Unexecuted instantiation: sam.c:kh_init_refs Line | Count | Source | 216 | 2.54k | SCOPE kh_##name##_t *kh_init_##name(void) { \ | 217 | 2.54k | return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \ | 218 | 2.54k | } \ |
Unexecuted instantiation: vcf.c:kh_init_str2int cram_decode.c:kh_init_map Line | Count | Source | 216 | 498 | SCOPE kh_##name##_t *kh_init_##name(void) { \ | 217 | 498 | return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \ | 218 | 498 | } \ |
Unexecuted instantiation: cram_decode.c:kh_init_sam_hrecs_t Unexecuted instantiation: cram_decode.c:kh_init_m_s2i Unexecuted instantiation: cram_decode.c:kh_init_m_i2i Unexecuted instantiation: cram_decode.c:kh_init_s_i2i Unexecuted instantiation: cram_decode.c:kh_init_m_metrics Unexecuted instantiation: cram_decode.c:kh_init_m_tagmap Unexecuted instantiation: cram_decode.c:kh_init_refs Unexecuted instantiation: cram_encode.c:kh_init_map Unexecuted instantiation: cram_encode.c:kh_init_m_s2u64 Unexecuted instantiation: cram_encode.c:kh_init_sam_hrecs_t Unexecuted instantiation: cram_encode.c:kh_init_m_s2i Unexecuted instantiation: cram_encode.c:kh_init_m_i2i Unexecuted instantiation: cram_encode.c:kh_init_s_i2i Unexecuted instantiation: cram_encode.c:kh_init_m_metrics Unexecuted instantiation: cram_encode.c:kh_init_m_tagmap Unexecuted instantiation: cram_encode.c:kh_init_refs Unexecuted instantiation: cram_index.c:kh_init_sam_hrecs_t Unexecuted instantiation: cram_index.c:kh_init_m_s2i Unexecuted instantiation: cram_index.c:kh_init_m_i2i Unexecuted instantiation: cram_index.c:kh_init_s_i2i Unexecuted instantiation: cram_index.c:kh_init_map Unexecuted instantiation: cram_index.c:kh_init_m_metrics Unexecuted instantiation: cram_index.c:kh_init_m_tagmap Unexecuted instantiation: cram_index.c:kh_init_refs Line | Count | Source | 216 | 245 | SCOPE kh_##name##_t *kh_init_##name(void) { \ | 217 | 245 | return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \ | 218 | 245 | } \ |
Unexecuted instantiation: cram_io.c:kh_init_m_tagmap Unexecuted instantiation: cram_io.c:kh_init_m_s2i cram_io.c:kh_init_m_metrics Line | Count | Source | 216 | 245 | SCOPE kh_##name##_t *kh_init_##name(void) { \ | 217 | 245 | return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \ | 218 | 245 | } \ |
Unexecuted instantiation: cram_io.c:kh_init_sam_hrecs_t Unexecuted instantiation: cram_io.c:kh_init_m_i2i Unexecuted instantiation: cram_io.c:kh_init_s_i2i Unexecuted instantiation: cram_io.c:kh_init_map Unexecuted instantiation: cram_stats.c:kh_init_m_i2i Unexecuted instantiation: cram_stats.c:kh_init_sam_hrecs_t Unexecuted instantiation: cram_stats.c:kh_init_m_s2i Unexecuted instantiation: cram_stats.c:kh_init_s_i2i Unexecuted instantiation: cram_stats.c:kh_init_map Unexecuted instantiation: cram_stats.c:kh_init_m_metrics Unexecuted instantiation: cram_stats.c:kh_init_m_tagmap Unexecuted instantiation: cram_stats.c:kh_init_refs Unexecuted instantiation: hfile_libcurl.c:kh_init_auth_map Line | Count | Source | 216 | 384 | SCOPE kh_##name##_t *kh_init_##name(void) { \ | 217 | 384 | return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \ | 218 | 384 | } \ |
Unexecuted instantiation: faidx.c:kh_init_s Unexecuted instantiation: cram_codecs.c:kh_init_sam_hrecs_t Unexecuted instantiation: cram_codecs.c:kh_init_m_s2i Unexecuted instantiation: cram_codecs.c:kh_init_m_i2i Unexecuted instantiation: cram_codecs.c:kh_init_s_i2i Unexecuted instantiation: cram_codecs.c:kh_init_map Unexecuted instantiation: cram_codecs.c:kh_init_m_metrics Unexecuted instantiation: cram_codecs.c:kh_init_m_tagmap Unexecuted instantiation: cram_codecs.c:kh_init_refs |
219 | | SCOPE void kh_destroy_##name(kh_##name##_t *h) \ |
220 | 9.15k | { \ |
221 | 9.15k | if (h) { \ |
222 | 9.14k | kfree((void *)h->keys); kfree(h->flags); \ |
223 | 9.14k | kfree((void *)h->vals); \ |
224 | 9.14k | kfree(h); \ |
225 | 9.14k | } \ |
226 | 9.15k | } \ header.c:kh_destroy_sam_hrecs_t Line | Count | Source | 220 | 1.16k | { \ | 221 | 1.16k | if (h) { \ | 222 | 1.16k | kfree((void *)h->keys); kfree(h->flags); \ | 223 | 1.16k | kfree((void *)h->vals); \ | 224 | 1.16k | kfree(h); \ | 225 | 1.16k | } \ | 226 | 1.16k | } \ |
header.c:kh_destroy_m_s2i Line | Count | Source | 220 | 3.49k | { \ | 221 | 3.49k | if (h) { \ | 222 | 3.49k | kfree((void *)h->keys); kfree(h->flags); \ | 223 | 3.49k | kfree((void *)h->vals); \ | 224 | 3.49k | kfree(h); \ | 225 | 3.49k | } \ | 226 | 3.49k | } \ |
Unexecuted instantiation: header.c:kh_destroy_rm hfile.c:kh_destroy_scheme_string Line | Count | Source | 220 | 1 | { \ | 221 | 1 | if (h) { \ | 222 | 1 | kfree((void *)h->keys); kfree(h->flags); \ | 223 | 1 | kfree((void *)h->vals); \ | 224 | 1 | kfree(h); \ | 225 | 1 | } \ | 226 | 1 | } \ |
Line | Count | Source | 220 | 576 | { \ | 221 | 576 | if (h) { \ | 222 | 566 | kfree((void *)h->keys); kfree(h->flags); \ | 223 | 566 | kfree((void *)h->vals); \ | 224 | 566 | kfree(h); \ | 225 | 566 | } \ | 226 | 576 | } \ |
Unexecuted instantiation: hts.c:kh_destroy_bin Unexecuted instantiation: hts.c:kh_destroy_sam_hrecs_t Unexecuted instantiation: hts.c:kh_destroy_m_s2i Unexecuted instantiation: hts.c:kh_destroy_m_i2i Unexecuted instantiation: hts.c:kh_destroy_s_i2i Unexecuted instantiation: hts.c:kh_destroy_map Unexecuted instantiation: hts.c:kh_destroy_m_metrics Unexecuted instantiation: hts.c:kh_destroy_m_tagmap Unexecuted instantiation: hts.c:kh_destroy_refs Unexecuted instantiation: region.c:kh_destroy_reg Unexecuted instantiation: sam.c:kh_destroy_tag Unexecuted instantiation: sam.c:kh_destroy_olap_hash Unexecuted instantiation: sam.c:kh_destroy_sam_hrecs_t Unexecuted instantiation: sam.c:kh_destroy_m_s2i Unexecuted instantiation: sam.c:kh_destroy_m_i2i Unexecuted instantiation: sam.c:kh_destroy_s_i2i Unexecuted instantiation: sam.c:kh_destroy_map Unexecuted instantiation: sam.c:kh_destroy_m_metrics Unexecuted instantiation: sam.c:kh_destroy_m_tagmap Unexecuted instantiation: sam.c:kh_destroy_refs Line | Count | Source | 220 | 2.54k | { \ | 221 | 2.54k | if (h) { \ | 222 | 2.54k | kfree((void *)h->keys); kfree(h->flags); \ | 223 | 2.54k | kfree((void *)h->vals); \ | 224 | 2.54k | kfree(h); \ | 225 | 2.54k | } \ | 226 | 2.54k | } \ |
Unexecuted instantiation: vcf.c:kh_destroy_str2int Unexecuted instantiation: cram_decode.c:kh_destroy_sam_hrecs_t Unexecuted instantiation: cram_decode.c:kh_destroy_m_s2i Unexecuted instantiation: cram_decode.c:kh_destroy_m_i2i Unexecuted instantiation: cram_decode.c:kh_destroy_s_i2i Unexecuted instantiation: cram_decode.c:kh_destroy_map Unexecuted instantiation: cram_decode.c:kh_destroy_m_metrics Unexecuted instantiation: cram_decode.c:kh_destroy_m_tagmap Unexecuted instantiation: cram_decode.c:kh_destroy_refs Unexecuted instantiation: cram_encode.c:kh_destroy_map Unexecuted instantiation: cram_encode.c:kh_destroy_m_s2u64 Unexecuted instantiation: cram_encode.c:kh_destroy_sam_hrecs_t Unexecuted instantiation: cram_encode.c:kh_destroy_m_s2i Unexecuted instantiation: cram_encode.c:kh_destroy_m_i2i Unexecuted instantiation: cram_encode.c:kh_destroy_s_i2i Unexecuted instantiation: cram_encode.c:kh_destroy_m_metrics Unexecuted instantiation: cram_encode.c:kh_destroy_m_tagmap Unexecuted instantiation: cram_encode.c:kh_destroy_refs Unexecuted instantiation: cram_index.c:kh_destroy_sam_hrecs_t Unexecuted instantiation: cram_index.c:kh_destroy_m_s2i Unexecuted instantiation: cram_index.c:kh_destroy_m_i2i Unexecuted instantiation: cram_index.c:kh_destroy_s_i2i Unexecuted instantiation: cram_index.c:kh_destroy_map Unexecuted instantiation: cram_index.c:kh_destroy_m_metrics Unexecuted instantiation: cram_index.c:kh_destroy_m_tagmap Unexecuted instantiation: cram_index.c:kh_destroy_refs cram_io.c:kh_destroy_refs Line | Count | Source | 220 | 245 | { \ | 221 | 245 | if (h) { \ | 222 | 245 | kfree((void *)h->keys); kfree(h->flags); \ | 223 | 245 | kfree((void *)h->vals); \ | 224 | 245 | kfree(h); \ | 225 | 245 | } \ | 226 | 245 | } \ |
Unexecuted instantiation: cram_io.c:kh_destroy_m_tagmap Unexecuted instantiation: cram_io.c:kh_destroy_m_s2i Line | Count | Source | 220 | 498 | { \ | 221 | 498 | if (h) { \ | 222 | 498 | kfree((void *)h->keys); kfree(h->flags); \ | 223 | 498 | kfree((void *)h->vals); \ | 224 | 498 | kfree(h); \ | 225 | 498 | } \ | 226 | 498 | } \ |
cram_io.c:kh_destroy_m_metrics Line | Count | Source | 220 | 245 | { \ | 221 | 245 | if (h) { \ | 222 | 245 | kfree((void *)h->keys); kfree(h->flags); \ | 223 | 245 | kfree((void *)h->vals); \ | 224 | 245 | kfree(h); \ | 225 | 245 | } \ | 226 | 245 | } \ |
Unexecuted instantiation: cram_io.c:kh_destroy_sam_hrecs_t Unexecuted instantiation: cram_io.c:kh_destroy_m_i2i Unexecuted instantiation: cram_io.c:kh_destroy_s_i2i Unexecuted instantiation: cram_stats.c:kh_destroy_m_i2i Unexecuted instantiation: cram_stats.c:kh_destroy_sam_hrecs_t Unexecuted instantiation: cram_stats.c:kh_destroy_m_s2i Unexecuted instantiation: cram_stats.c:kh_destroy_s_i2i Unexecuted instantiation: cram_stats.c:kh_destroy_map Unexecuted instantiation: cram_stats.c:kh_destroy_m_metrics Unexecuted instantiation: cram_stats.c:kh_destroy_m_tagmap Unexecuted instantiation: cram_stats.c:kh_destroy_refs Unexecuted instantiation: hfile_libcurl.c:kh_destroy_auth_map Line | Count | Source | 220 | 384 | { \ | 221 | 384 | if (h) { \ | 222 | 384 | kfree((void *)h->keys); kfree(h->flags); \ | 223 | 384 | kfree((void *)h->vals); \ | 224 | 384 | kfree(h); \ | 225 | 384 | } \ | 226 | 384 | } \ |
Unexecuted instantiation: faidx.c:kh_destroy_s Unexecuted instantiation: cram_codecs.c:kh_destroy_sam_hrecs_t Unexecuted instantiation: cram_codecs.c:kh_destroy_m_s2i Unexecuted instantiation: cram_codecs.c:kh_destroy_m_i2i Unexecuted instantiation: cram_codecs.c:kh_destroy_s_i2i Unexecuted instantiation: cram_codecs.c:kh_destroy_map Unexecuted instantiation: cram_codecs.c:kh_destroy_m_metrics Unexecuted instantiation: cram_codecs.c:kh_destroy_m_tagmap Unexecuted instantiation: cram_codecs.c:kh_destroy_refs |
227 | | SCOPE void kh_clear_##name(kh_##name##_t *h) \ |
228 | 0 | { \ |
229 | 0 | if (h && h->flags) { \ |
230 | 0 | memset(h->flags, 0xaa, __ac_fsize(h->n_buckets) * sizeof(khint32_t)); \ |
231 | 0 | h->size = h->n_occupied = 0; \ |
232 | 0 | } \ |
233 | 0 | } \ Unexecuted instantiation: header.c:kh_clear_sam_hrecs_t Unexecuted instantiation: header.c:kh_clear_m_s2i Unexecuted instantiation: header.c:kh_clear_rm Unexecuted instantiation: hfile.c:kh_clear_scheme_string Unexecuted instantiation: kh_clear_s2i Unexecuted instantiation: hts.c:kh_clear_sam_hrecs_t Unexecuted instantiation: hts.c:kh_clear_m_s2i Unexecuted instantiation: hts.c:kh_clear_m_i2i Unexecuted instantiation: hts.c:kh_clear_s_i2i Unexecuted instantiation: hts.c:kh_clear_map Unexecuted instantiation: hts.c:kh_clear_m_metrics Unexecuted instantiation: hts.c:kh_clear_m_tagmap Unexecuted instantiation: hts.c:kh_clear_refs Unexecuted instantiation: hts.c:kh_clear_bin Unexecuted instantiation: region.c:kh_clear_reg Unexecuted instantiation: sam.c:kh_clear_sam_hrecs_t Unexecuted instantiation: sam.c:kh_clear_m_s2i Unexecuted instantiation: sam.c:kh_clear_m_i2i Unexecuted instantiation: sam.c:kh_clear_s_i2i Unexecuted instantiation: sam.c:kh_clear_map Unexecuted instantiation: sam.c:kh_clear_m_metrics Unexecuted instantiation: sam.c:kh_clear_m_tagmap Unexecuted instantiation: sam.c:kh_clear_refs Unexecuted instantiation: sam.c:kh_clear_tag Unexecuted instantiation: sam.c:kh_clear_olap_hash Unexecuted instantiation: vcf.c:kh_clear_str2int Unexecuted instantiation: vcf.c:kh_clear_vdict Unexecuted instantiation: cram_decode.c:kh_clear_sam_hrecs_t Unexecuted instantiation: cram_decode.c:kh_clear_m_s2i Unexecuted instantiation: cram_decode.c:kh_clear_m_i2i Unexecuted instantiation: cram_decode.c:kh_clear_s_i2i Unexecuted instantiation: cram_decode.c:kh_clear_map Unexecuted instantiation: cram_decode.c:kh_clear_m_metrics Unexecuted instantiation: cram_decode.c:kh_clear_m_tagmap Unexecuted instantiation: cram_decode.c:kh_clear_refs Unexecuted instantiation: cram_encode.c:kh_clear_sam_hrecs_t Unexecuted instantiation: cram_encode.c:kh_clear_m_s2i Unexecuted instantiation: cram_encode.c:kh_clear_m_i2i Unexecuted instantiation: cram_encode.c:kh_clear_s_i2i Unexecuted instantiation: cram_encode.c:kh_clear_map Unexecuted instantiation: cram_encode.c:kh_clear_m_metrics Unexecuted instantiation: cram_encode.c:kh_clear_m_tagmap Unexecuted instantiation: cram_encode.c:kh_clear_refs Unexecuted instantiation: cram_encode.c:kh_clear_m_s2u64 Unexecuted instantiation: cram_index.c:kh_clear_sam_hrecs_t Unexecuted instantiation: cram_index.c:kh_clear_m_s2i Unexecuted instantiation: cram_index.c:kh_clear_m_i2i Unexecuted instantiation: cram_index.c:kh_clear_s_i2i Unexecuted instantiation: cram_index.c:kh_clear_map Unexecuted instantiation: cram_index.c:kh_clear_m_metrics Unexecuted instantiation: cram_index.c:kh_clear_m_tagmap Unexecuted instantiation: cram_index.c:kh_clear_refs Unexecuted instantiation: cram_io.c:kh_clear_sam_hrecs_t Unexecuted instantiation: cram_io.c:kh_clear_m_s2i Unexecuted instantiation: cram_io.c:kh_clear_m_i2i Unexecuted instantiation: cram_io.c:kh_clear_s_i2i Unexecuted instantiation: cram_io.c:kh_clear_map Unexecuted instantiation: cram_io.c:kh_clear_m_metrics Unexecuted instantiation: cram_io.c:kh_clear_m_tagmap Unexecuted instantiation: cram_io.c:kh_clear_refs Unexecuted instantiation: cram_stats.c:kh_clear_sam_hrecs_t Unexecuted instantiation: cram_stats.c:kh_clear_m_s2i Unexecuted instantiation: cram_stats.c:kh_clear_m_i2i Unexecuted instantiation: cram_stats.c:kh_clear_s_i2i Unexecuted instantiation: cram_stats.c:kh_clear_map Unexecuted instantiation: cram_stats.c:kh_clear_m_metrics Unexecuted instantiation: cram_stats.c:kh_clear_m_tagmap Unexecuted instantiation: cram_stats.c:kh_clear_refs Unexecuted instantiation: hfile_libcurl.c:kh_clear_auth_map Unexecuted instantiation: bgzf.c:kh_clear_cache Unexecuted instantiation: faidx.c:kh_clear_s Unexecuted instantiation: cram_codecs.c:kh_clear_sam_hrecs_t Unexecuted instantiation: cram_codecs.c:kh_clear_m_s2i Unexecuted instantiation: cram_codecs.c:kh_clear_m_i2i Unexecuted instantiation: cram_codecs.c:kh_clear_s_i2i Unexecuted instantiation: cram_codecs.c:kh_clear_map Unexecuted instantiation: cram_codecs.c:kh_clear_m_metrics Unexecuted instantiation: cram_codecs.c:kh_clear_m_tagmap Unexecuted instantiation: cram_codecs.c:kh_clear_refs |
234 | | SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \ |
235 | 3.46M | { \ |
236 | 3.46M | if (h->n_buckets) { \ |
237 | 3.45M | khint_t k, i, last, mask, step = 0; \ |
238 | 3.45M | mask = h->n_buckets - 1; \ |
239 | 3.45M | k = __hash_func(key); i = k & mask; \ |
240 | 3.45M | last = i; \ |
241 | 3.81M | while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ |
242 | 352k | i = (i + (++step)) & mask; \ |
243 | 352k | if (i == last) return h->n_buckets; \ |
244 | 352k | } \ |
245 | 3.45M | return __ac_iseither(h->flags, i)? h->n_buckets : i; \ |
246 | 3.45M | } else return 0; \ |
247 | 3.46M | } \ Line | Count | Source | 235 | 62.3k | { \ | 236 | 62.3k | if (h->n_buckets) { \ | 237 | 57.9k | khint_t k, i, last, mask, step = 0; \ | 238 | 57.9k | mask = h->n_buckets - 1; \ | 239 | 57.9k | k = __hash_func(key); i = k & mask; \ | 240 | 57.9k | last = i; \ | 241 | 127k | while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ | 242 | 69.1k | i = (i + (++step)) & mask; \ | 243 | 69.1k | if (i == last) return h->n_buckets; \ | 244 | 69.1k | } \ | 245 | 57.9k | return __ac_iseither(h->flags, i)? h->n_buckets : i; \ | 246 | 57.9k | } else return 0; \ | 247 | 62.3k | } \ |
Unexecuted instantiation: header.c:kh_get_sam_hrecs_t Unexecuted instantiation: header.c:kh_get_rm hfile.c:kh_get_scheme_string Line | Count | Source | 235 | 1.79k | { \ | 236 | 1.79k | if (h->n_buckets) { \ | 237 | 1.79k | khint_t k, i, last, mask, step = 0; \ | 238 | 1.79k | mask = h->n_buckets - 1; \ | 239 | 1.79k | k = __hash_func(key); i = k & mask; \ | 240 | 1.79k | last = i; \ | 241 | 1.79k | while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ | 242 | 0 | i = (i + (++step)) & mask; \ | 243 | 0 | if (i == last) return h->n_buckets; \ | 244 | 0 | } \ | 245 | 1.79k | return __ac_iseither(h->flags, i)? h->n_buckets : i; \ | 246 | 1.79k | } else return 0; \ | 247 | 1.79k | } \ |
Line | Count | Source | 235 | 1.11k | { \ | 236 | 1.11k | if (h->n_buckets) { \ | 237 | 1.11k | khint_t k, i, last, mask, step = 0; \ | 238 | 1.11k | mask = h->n_buckets - 1; \ | 239 | 1.11k | k = __hash_func(key); i = k & mask; \ | 240 | 1.11k | last = i; \ | 241 | 2.16k | while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ | 242 | 1.05k | i = (i + (++step)) & mask; \ | 243 | 1.05k | if (i == last) return h->n_buckets; \ | 244 | 1.05k | } \ | 245 | 1.11k | return __ac_iseither(h->flags, i)? h->n_buckets : i; \ | 246 | 1.11k | } else return 0; \ | 247 | 1.11k | } \ |
Unexecuted instantiation: hts.c:kh_get_bin Unexecuted instantiation: hts.c:kh_get_sam_hrecs_t Unexecuted instantiation: hts.c:kh_get_m_s2i Unexecuted instantiation: hts.c:kh_get_m_i2i Unexecuted instantiation: hts.c:kh_get_s_i2i Unexecuted instantiation: hts.c:kh_get_map Unexecuted instantiation: hts.c:kh_get_m_metrics Unexecuted instantiation: hts.c:kh_get_m_tagmap Unexecuted instantiation: hts.c:kh_get_refs Unexecuted instantiation: region.c:kh_get_reg Unexecuted instantiation: sam.c:kh_get_tag Unexecuted instantiation: sam.c:kh_get_olap_hash Unexecuted instantiation: sam.c:kh_get_sam_hrecs_t Unexecuted instantiation: sam.c:kh_get_m_s2i Unexecuted instantiation: sam.c:kh_get_m_i2i Unexecuted instantiation: sam.c:kh_get_s_i2i Unexecuted instantiation: sam.c:kh_get_map Unexecuted instantiation: sam.c:kh_get_m_metrics Unexecuted instantiation: sam.c:kh_get_m_tagmap Unexecuted instantiation: sam.c:kh_get_refs Line | Count | Source | 235 | 3.40M | { \ | 236 | 3.40M | if (h->n_buckets) { \ | 237 | 3.39M | khint_t k, i, last, mask, step = 0; \ | 238 | 3.39M | mask = h->n_buckets - 1; \ | 239 | 3.39M | k = __hash_func(key); i = k & mask; \ | 240 | 3.39M | last = i; \ | 241 | 3.67M | while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ | 242 | 281k | i = (i + (++step)) & mask; \ | 243 | 281k | if (i == last) return h->n_buckets; \ | 244 | 281k | } \ | 245 | 3.39M | return __ac_iseither(h->flags, i)? h->n_buckets : i; \ | 246 | 3.39M | } else return 0; \ | 247 | 3.40M | } \ |
Unexecuted instantiation: vcf.c:kh_get_str2int Unexecuted instantiation: cram_decode.c:kh_get_sam_hrecs_t Unexecuted instantiation: cram_decode.c:kh_get_m_s2i Unexecuted instantiation: cram_decode.c:kh_get_m_i2i Unexecuted instantiation: cram_decode.c:kh_get_s_i2i Unexecuted instantiation: cram_decode.c:kh_get_map Unexecuted instantiation: cram_decode.c:kh_get_m_metrics Unexecuted instantiation: cram_decode.c:kh_get_m_tagmap Unexecuted instantiation: cram_decode.c:kh_get_refs Unexecuted instantiation: cram_encode.c:kh_get_m_s2u64 Unexecuted instantiation: cram_encode.c:kh_get_sam_hrecs_t Unexecuted instantiation: cram_encode.c:kh_get_m_s2i Unexecuted instantiation: cram_encode.c:kh_get_m_i2i Unexecuted instantiation: cram_encode.c:kh_get_s_i2i Unexecuted instantiation: cram_encode.c:kh_get_map Unexecuted instantiation: cram_encode.c:kh_get_m_metrics Unexecuted instantiation: cram_encode.c:kh_get_m_tagmap Unexecuted instantiation: cram_encode.c:kh_get_refs Unexecuted instantiation: cram_index.c:kh_get_sam_hrecs_t Unexecuted instantiation: cram_index.c:kh_get_m_s2i Unexecuted instantiation: cram_index.c:kh_get_m_i2i Unexecuted instantiation: cram_index.c:kh_get_s_i2i Unexecuted instantiation: cram_index.c:kh_get_map Unexecuted instantiation: cram_index.c:kh_get_m_metrics Unexecuted instantiation: cram_index.c:kh_get_m_tagmap Unexecuted instantiation: cram_index.c:kh_get_refs Line | Count | Source | 235 | 216 | { \ | 236 | 216 | if (h->n_buckets) { \ | 237 | 198 | khint_t k, i, last, mask, step = 0; \ | 238 | 198 | mask = h->n_buckets - 1; \ | 239 | 198 | k = __hash_func(key); i = k & mask; \ | 240 | 198 | last = i; \ | 241 | 580 | while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ | 242 | 382 | i = (i + (++step)) & mask; \ | 243 | 382 | if (i == last) return h->n_buckets; \ | 244 | 382 | } \ | 245 | 198 | return __ac_iseither(h->flags, i)? h->n_buckets : i; \ | 246 | 198 | } else return 0; \ | 247 | 216 | } \ |
Unexecuted instantiation: cram_io.c:kh_get_sam_hrecs_t Unexecuted instantiation: cram_io.c:kh_get_m_s2i Unexecuted instantiation: cram_io.c:kh_get_m_i2i Unexecuted instantiation: cram_io.c:kh_get_s_i2i Unexecuted instantiation: cram_io.c:kh_get_map Unexecuted instantiation: cram_io.c:kh_get_m_metrics Unexecuted instantiation: cram_io.c:kh_get_m_tagmap Unexecuted instantiation: cram_stats.c:kh_get_m_i2i Unexecuted instantiation: cram_stats.c:kh_get_sam_hrecs_t Unexecuted instantiation: cram_stats.c:kh_get_m_s2i Unexecuted instantiation: cram_stats.c:kh_get_s_i2i Unexecuted instantiation: cram_stats.c:kh_get_map Unexecuted instantiation: cram_stats.c:kh_get_m_metrics Unexecuted instantiation: cram_stats.c:kh_get_m_tagmap Unexecuted instantiation: cram_stats.c:kh_get_refs Unexecuted instantiation: hfile_libcurl.c:kh_get_auth_map Unexecuted instantiation: bgzf.c:kh_get_cache Unexecuted instantiation: faidx.c:kh_get_s Unexecuted instantiation: cram_codecs.c:kh_get_sam_hrecs_t Unexecuted instantiation: cram_codecs.c:kh_get_m_s2i Unexecuted instantiation: cram_codecs.c:kh_get_m_i2i Unexecuted instantiation: cram_codecs.c:kh_get_s_i2i Unexecuted instantiation: cram_codecs.c:kh_get_map Unexecuted instantiation: cram_codecs.c:kh_get_m_metrics Unexecuted instantiation: cram_codecs.c:kh_get_m_tagmap Unexecuted instantiation: cram_codecs.c:kh_get_refs |
248 | | SCOPE int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \ |
249 | 6.01k | { /* This function uses 0.25*n_buckets bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \ |
250 | 6.01k | khint32_t *new_flags = 0; \ |
251 | 6.01k | khint_t j = 1; \ |
252 | 6.01k | { \ |
253 | 6.01k | kroundup32(new_n_buckets); \ |
254 | 6.01k | if (new_n_buckets < 4) new_n_buckets = 4; \ |
255 | 6.01k | if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; /* requested size is too small */ \ |
256 | 6.01k | else { /* hash table size to be changed (shrink or expand); rehash */ \ |
257 | 6.01k | new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ |
258 | 6.01k | if (!new_flags) return -1; \ |
259 | 6.01k | memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ |
260 | 6.01k | if (h->n_buckets < new_n_buckets) { /* expand */ \ |
261 | 5.70k | khkey_t *new_keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ |
262 | 5.70k | if (!new_keys) { kfree(new_flags); return -1; } \ |
263 | 5.70k | h->keys = new_keys; \ |
264 | 5.70k | if (kh_is_map) { \ |
265 | 5.70k | khval_t *new_vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ |
266 | 5.70k | if (!new_vals) { kfree(new_flags); return -1; } \ |
267 | 5.70k | h->vals = new_vals; \ |
268 | 5.70k | } \ |
269 | 5.70k | } /* otherwise shrink */ \ |
270 | 6.01k | } \ |
271 | 6.01k | } \ |
272 | 6.01k | if (j) { /* rehashing is needed */ \ |
273 | 40.7k | for (j = 0; j != h->n_buckets; ++j) { \ |
274 | 34.7k | if (__ac_iseither(h->flags, j) == 0) { \ |
275 | 24.4k | khkey_t key = h->keys[j]; \ |
276 | 24.4k | khval_t val; \ |
277 | 24.4k | khint_t new_mask; \ |
278 | 24.4k | new_mask = new_n_buckets - 1; \ |
279 | 24.4k | if (kh_is_map) val = h->vals[j]; \ |
280 | 24.4k | __ac_set_isdel_true(h->flags, j); \ |
281 | 25.6k | while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \ |
282 | 25.6k | khint_t k, i, step = 0; \ |
283 | 25.6k | k = __hash_func(key); \ |
284 | 25.6k | i = k & new_mask; \ |
285 | 34.0k | while (!__ac_isempty(new_flags, i)) i = (i + (++step)) & new_mask; \ |
286 | 25.6k | __ac_set_isempty_false(new_flags, i); \ |
287 | 25.6k | if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \ |
288 | 1.15k | { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \ |
289 | 1.15k | if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \ |
290 | 1.15k | __ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \ |
291 | 24.4k | } else { /* write the element and jump out of the loop */ \ |
292 | 24.4k | h->keys[i] = key; \ |
293 | 24.4k | if (kh_is_map) h->vals[i] = val; \ |
294 | 24.4k | break; \ |
295 | 24.4k | } \ |
296 | 25.6k | } \ |
297 | 24.4k | } \ |
298 | 34.7k | } \ |
299 | 6.01k | if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \ |
300 | 0 | h->keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ |
301 | 0 | if (kh_is_map) h->vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ |
302 | 0 | } \ |
303 | 6.01k | kfree(h->flags); /* free the working space */ \ |
304 | 6.01k | h->flags = new_flags; \ |
305 | 6.01k | h->n_buckets = new_n_buckets; \ |
306 | 6.01k | h->n_occupied = h->size; \ |
307 | 6.01k | h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \ |
308 | 6.01k | } \ |
309 | 6.01k | return 0; \ |
310 | 6.01k | } \ header.c:kh_resize_sam_hrecs_t Line | Count | Source | 249 | 628 | { /* This function uses 0.25*n_buckets bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \ | 250 | 628 | khint32_t *new_flags = 0; \ | 251 | 628 | khint_t j = 1; \ | 252 | 628 | { \ | 253 | 628 | kroundup32(new_n_buckets); \ | 254 | 628 | if (new_n_buckets < 4) new_n_buckets = 4; \ | 255 | 628 | if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; /* requested size is too small */ \ | 256 | 628 | else { /* hash table size to be changed (shrink or expand); rehash */ \ | 257 | 628 | new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ | 258 | 628 | if (!new_flags) return -1; \ | 259 | 628 | memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ | 260 | 628 | if (h->n_buckets < new_n_buckets) { /* expand */ \ | 261 | 628 | khkey_t *new_keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ | 262 | 628 | if (!new_keys) { kfree(new_flags); return -1; } \ | 263 | 628 | h->keys = new_keys; \ | 264 | 628 | if (kh_is_map) { \ | 265 | 628 | khval_t *new_vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ | 266 | 628 | if (!new_vals) { kfree(new_flags); return -1; } \ | 267 | 628 | h->vals = new_vals; \ | 268 | 628 | } \ | 269 | 628 | } /* otherwise shrink */ \ | 270 | 628 | } \ | 271 | 628 | } \ | 272 | 628 | if (j) { /* rehashing is needed */ \ | 273 | 872 | for (j = 0; j != h->n_buckets; ++j) { \ | 274 | 244 | if (__ac_iseither(h->flags, j) == 0) { \ | 275 | 183 | khkey_t key = h->keys[j]; \ | 276 | 183 | khval_t val; \ | 277 | 183 | khint_t new_mask; \ | 278 | 183 | new_mask = new_n_buckets - 1; \ | 279 | 183 | if (kh_is_map) val = h->vals[j]; \ | 280 | 183 | __ac_set_isdel_true(h->flags, j); \ | 281 | 183 | while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \ | 282 | 183 | khint_t k, i, step = 0; \ | 283 | 183 | k = __hash_func(key); \ | 284 | 183 | i = k & new_mask; \ | 285 | 248 | while (!__ac_isempty(new_flags, i)) i = (i + (++step)) & new_mask; \ | 286 | 183 | __ac_set_isempty_false(new_flags, i); \ | 287 | 183 | if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \ | 288 | 0 | { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \ | 289 | 0 | if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \ | 290 | 0 | __ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \ | 291 | 183 | } else { /* write the element and jump out of the loop */ \ | 292 | 183 | h->keys[i] = key; \ | 293 | 183 | if (kh_is_map) h->vals[i] = val; \ | 294 | 183 | break; \ | 295 | 183 | } \ | 296 | 183 | } \ | 297 | 183 | } \ | 298 | 244 | } \ | 299 | 628 | if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \ | 300 | 0 | h->keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ | 301 | 0 | if (kh_is_map) h->vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ | 302 | 0 | } \ | 303 | 628 | kfree(h->flags); /* free the working space */ \ | 304 | 628 | h->flags = new_flags; \ | 305 | 628 | h->n_buckets = new_n_buckets; \ | 306 | 628 | h->n_occupied = h->size; \ | 307 | 628 | h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \ | 308 | 628 | } \ | 309 | 628 | return 0; \ | 310 | 628 | } \ |
Line | Count | Source | 249 | 999 | { /* This function uses 0.25*n_buckets bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \ | 250 | 999 | khint32_t *new_flags = 0; \ | 251 | 999 | khint_t j = 1; \ | 252 | 999 | { \ | 253 | 999 | kroundup32(new_n_buckets); \ | 254 | 999 | if (new_n_buckets < 4) new_n_buckets = 4; \ | 255 | 999 | if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; /* requested size is too small */ \ | 256 | 999 | else { /* hash table size to be changed (shrink or expand); rehash */ \ | 257 | 999 | new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ | 258 | 999 | if (!new_flags) return -1; \ | 259 | 999 | memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ | 260 | 999 | if (h->n_buckets < new_n_buckets) { /* expand */ \ | 261 | 999 | khkey_t *new_keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ | 262 | 999 | if (!new_keys) { kfree(new_flags); return -1; } \ | 263 | 999 | h->keys = new_keys; \ | 264 | 999 | if (kh_is_map) { \ | 265 | 999 | khval_t *new_vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ | 266 | 999 | if (!new_vals) { kfree(new_flags); return -1; } \ | 267 | 999 | h->vals = new_vals; \ | 268 | 999 | } \ | 269 | 999 | } /* otherwise shrink */ \ | 270 | 999 | } \ | 271 | 999 | } \ | 272 | 999 | if (j) { /* rehashing is needed */ \ | 273 | 8.07k | for (j = 0; j != h->n_buckets; ++j) { \ | 274 | 7.07k | if (__ac_iseither(h->flags, j) == 0) { \ | 275 | 5.09k | khkey_t key = h->keys[j]; \ | 276 | 5.09k | khval_t val; \ | 277 | 5.09k | khint_t new_mask; \ | 278 | 5.09k | new_mask = new_n_buckets - 1; \ | 279 | 5.09k | if (kh_is_map) val = h->vals[j]; \ | 280 | 5.09k | __ac_set_isdel_true(h->flags, j); \ | 281 | 5.39k | while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \ | 282 | 5.39k | khint_t k, i, step = 0; \ | 283 | 5.39k | k = __hash_func(key); \ | 284 | 5.39k | i = k & new_mask; \ | 285 | 7.28k | while (!__ac_isempty(new_flags, i)) i = (i + (++step)) & new_mask; \ | 286 | 5.39k | __ac_set_isempty_false(new_flags, i); \ | 287 | 5.39k | if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \ | 288 | 297 | { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \ | 289 | 297 | if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \ | 290 | 297 | __ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \ | 291 | 5.09k | } else { /* write the element and jump out of the loop */ \ | 292 | 5.09k | h->keys[i] = key; \ | 293 | 5.09k | if (kh_is_map) h->vals[i] = val; \ | 294 | 5.09k | break; \ | 295 | 5.09k | } \ | 296 | 5.39k | } \ | 297 | 5.09k | } \ | 298 | 7.07k | } \ | 299 | 999 | if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \ | 300 | 0 | h->keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ | 301 | 0 | if (kh_is_map) h->vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ | 302 | 0 | } \ | 303 | 999 | kfree(h->flags); /* free the working space */ \ | 304 | 999 | h->flags = new_flags; \ | 305 | 999 | h->n_buckets = new_n_buckets; \ | 306 | 999 | h->n_occupied = h->size; \ | 307 | 999 | h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \ | 308 | 999 | } \ | 309 | 999 | return 0; \ | 310 | 999 | } \ |
Unexecuted instantiation: header.c:kh_resize_rm hfile.c:kh_resize_scheme_string Line | Count | Source | 249 | 5 | { /* This function uses 0.25*n_buckets bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \ | 250 | 5 | khint32_t *new_flags = 0; \ | 251 | 5 | khint_t j = 1; \ | 252 | 5 | { \ | 253 | 5 | kroundup32(new_n_buckets); \ | 254 | 5 | if (new_n_buckets < 4) new_n_buckets = 4; \ | 255 | 5 | if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; /* requested size is too small */ \ | 256 | 5 | else { /* hash table size to be changed (shrink or expand); rehash */ \ | 257 | 5 | new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ | 258 | 5 | if (!new_flags) return -1; \ | 259 | 5 | memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ | 260 | 5 | if (h->n_buckets < new_n_buckets) { /* expand */ \ | 261 | 5 | khkey_t *new_keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ | 262 | 5 | if (!new_keys) { kfree(new_flags); return -1; } \ | 263 | 5 | h->keys = new_keys; \ | 264 | 5 | if (kh_is_map) { \ | 265 | 5 | khval_t *new_vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ | 266 | 5 | if (!new_vals) { kfree(new_flags); return -1; } \ | 267 | 5 | h->vals = new_vals; \ | 268 | 5 | } \ | 269 | 5 | } /* otherwise shrink */ \ | 270 | 5 | } \ | 271 | 5 | } \ | 272 | 5 | if (j) { /* rehashing is needed */ \ | 273 | 65 | for (j = 0; j != h->n_buckets; ++j) { \ | 274 | 60 | if (__ac_iseither(h->flags, j) == 0) { \ | 275 | 46 | khkey_t key = h->keys[j]; \ | 276 | 46 | khval_t val; \ | 277 | 46 | khint_t new_mask; \ | 278 | 46 | new_mask = new_n_buckets - 1; \ | 279 | 46 | if (kh_is_map) val = h->vals[j]; \ | 280 | 46 | __ac_set_isdel_true(h->flags, j); \ | 281 | 46 | while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \ | 282 | 46 | khint_t k, i, step = 0; \ | 283 | 46 | k = __hash_func(key); \ | 284 | 46 | i = k & new_mask; \ | 285 | 51 | while (!__ac_isempty(new_flags, i)) i = (i + (++step)) & new_mask; \ | 286 | 46 | __ac_set_isempty_false(new_flags, i); \ | 287 | 46 | if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \ | 288 | 0 | { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \ | 289 | 0 | if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \ | 290 | 0 | __ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \ | 291 | 46 | } else { /* write the element and jump out of the loop */ \ | 292 | 46 | h->keys[i] = key; \ | 293 | 46 | if (kh_is_map) h->vals[i] = val; \ | 294 | 46 | break; \ | 295 | 46 | } \ | 296 | 46 | } \ | 297 | 46 | } \ | 298 | 60 | } \ | 299 | 5 | if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \ | 300 | 0 | h->keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ | 301 | 0 | if (kh_is_map) h->vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ | 302 | 0 | } \ | 303 | 5 | kfree(h->flags); /* free the working space */ \ | 304 | 5 | h->flags = new_flags; \ | 305 | 5 | h->n_buckets = new_n_buckets; \ | 306 | 5 | h->n_occupied = h->size; \ | 307 | 5 | h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \ | 308 | 5 | } \ | 309 | 5 | return 0; \ | 310 | 5 | } \ |
Line | Count | Source | 249 | 644 | { /* This function uses 0.25*n_buckets bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \ | 250 | 644 | khint32_t *new_flags = 0; \ | 251 | 644 | khint_t j = 1; \ | 252 | 644 | { \ | 253 | 644 | kroundup32(new_n_buckets); \ | 254 | 644 | if (new_n_buckets < 4) new_n_buckets = 4; \ | 255 | 644 | if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; /* requested size is too small */ \ | 256 | 644 | else { /* hash table size to be changed (shrink or expand); rehash */ \ | 257 | 644 | new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ | 258 | 644 | if (!new_flags) return -1; \ | 259 | 644 | memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ | 260 | 644 | if (h->n_buckets < new_n_buckets) { /* expand */ \ | 261 | 644 | khkey_t *new_keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ | 262 | 644 | if (!new_keys) { kfree(new_flags); return -1; } \ | 263 | 644 | h->keys = new_keys; \ | 264 | 644 | if (kh_is_map) { \ | 265 | 644 | khval_t *new_vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ | 266 | 644 | if (!new_vals) { kfree(new_flags); return -1; } \ | 267 | 644 | h->vals = new_vals; \ | 268 | 644 | } \ | 269 | 644 | } /* otherwise shrink */ \ | 270 | 644 | } \ | 271 | 644 | } \ | 272 | 644 | if (j) { /* rehashing is needed */ \ | 273 | 6.57k | for (j = 0; j != h->n_buckets; ++j) { \ | 274 | 5.93k | if (__ac_iseither(h->flags, j) == 0) { \ | 275 | 4.29k | khkey_t key = h->keys[j]; \ | 276 | 4.29k | khval_t val; \ | 277 | 4.29k | khint_t new_mask; \ | 278 | 4.29k | new_mask = new_n_buckets - 1; \ | 279 | 4.29k | if (kh_is_map) val = h->vals[j]; \ | 280 | 4.29k | __ac_set_isdel_true(h->flags, j); \ | 281 | 4.54k | while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \ | 282 | 4.54k | khint_t k, i, step = 0; \ | 283 | 4.54k | k = __hash_func(key); \ | 284 | 4.54k | i = k & new_mask; \ | 285 | 6.00k | while (!__ac_isempty(new_flags, i)) i = (i + (++step)) & new_mask; \ | 286 | 4.54k | __ac_set_isempty_false(new_flags, i); \ | 287 | 4.54k | if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \ | 288 | 246 | { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \ | 289 | 246 | if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \ | 290 | 246 | __ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \ | 291 | 4.29k | } else { /* write the element and jump out of the loop */ \ | 292 | 4.29k | h->keys[i] = key; \ | 293 | 4.29k | if (kh_is_map) h->vals[i] = val; \ | 294 | 4.29k | break; \ | 295 | 4.29k | } \ | 296 | 4.54k | } \ | 297 | 4.29k | } \ | 298 | 5.93k | } \ | 299 | 644 | if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \ | 300 | 0 | h->keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ | 301 | 0 | if (kh_is_map) h->vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ | 302 | 0 | } \ | 303 | 644 | kfree(h->flags); /* free the working space */ \ | 304 | 644 | h->flags = new_flags; \ | 305 | 644 | h->n_buckets = new_n_buckets; \ | 306 | 644 | h->n_occupied = h->size; \ | 307 | 644 | h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \ | 308 | 644 | } \ | 309 | 644 | return 0; \ | 310 | 644 | } \ |
Unexecuted instantiation: hts.c:kh_resize_bin Unexecuted instantiation: hts.c:kh_resize_sam_hrecs_t Unexecuted instantiation: hts.c:kh_resize_m_s2i Unexecuted instantiation: hts.c:kh_resize_m_i2i Unexecuted instantiation: hts.c:kh_resize_s_i2i Unexecuted instantiation: hts.c:kh_resize_map Unexecuted instantiation: hts.c:kh_resize_m_metrics Unexecuted instantiation: hts.c:kh_resize_m_tagmap Unexecuted instantiation: hts.c:kh_resize_refs Unexecuted instantiation: region.c:kh_resize_reg Unexecuted instantiation: sam.c:kh_resize_tag Unexecuted instantiation: sam.c:kh_resize_olap_hash Unexecuted instantiation: sam.c:kh_resize_sam_hrecs_t Unexecuted instantiation: sam.c:kh_resize_m_s2i Unexecuted instantiation: sam.c:kh_resize_m_i2i Unexecuted instantiation: sam.c:kh_resize_s_i2i Unexecuted instantiation: sam.c:kh_resize_map Unexecuted instantiation: sam.c:kh_resize_m_metrics Unexecuted instantiation: sam.c:kh_resize_m_tagmap Unexecuted instantiation: sam.c:kh_resize_refs Unexecuted instantiation: vcf.c:kh_resize_str2int Line | Count | Source | 249 | 3.68k | { /* This function uses 0.25*n_buckets bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \ | 250 | 3.68k | khint32_t *new_flags = 0; \ | 251 | 3.68k | khint_t j = 1; \ | 252 | 3.68k | { \ | 253 | 3.68k | kroundup32(new_n_buckets); \ | 254 | 3.68k | if (new_n_buckets < 4) new_n_buckets = 4; \ | 255 | 3.68k | if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; /* requested size is too small */ \ | 256 | 3.68k | else { /* hash table size to be changed (shrink or expand); rehash */ \ | 257 | 3.68k | new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ | 258 | 3.68k | if (!new_flags) return -1; \ | 259 | 3.68k | memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ | 260 | 3.68k | if (h->n_buckets < new_n_buckets) { /* expand */ \ | 261 | 3.37k | khkey_t *new_keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ | 262 | 3.37k | if (!new_keys) { kfree(new_flags); return -1; } \ | 263 | 3.37k | h->keys = new_keys; \ | 264 | 3.37k | if (kh_is_map) { \ | 265 | 3.37k | khval_t *new_vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ | 266 | 3.37k | if (!new_vals) { kfree(new_flags); return -1; } \ | 267 | 3.37k | h->vals = new_vals; \ | 268 | 3.37k | } \ | 269 | 3.37k | } /* otherwise shrink */ \ | 270 | 3.68k | } \ | 271 | 3.68k | } \ | 272 | 3.68k | if (j) { /* rehashing is needed */ \ | 273 | 24.7k | for (j = 0; j != h->n_buckets; ++j) { \ | 274 | 21.0k | if (__ac_iseither(h->flags, j) == 0) { \ | 275 | 14.6k | khkey_t key = h->keys[j]; \ | 276 | 14.6k | khval_t val; \ | 277 | 14.6k | khint_t new_mask; \ | 278 | 14.6k | new_mask = new_n_buckets - 1; \ | 279 | 14.6k | if (kh_is_map) val = h->vals[j]; \ | 280 | 14.6k | __ac_set_isdel_true(h->flags, j); \ | 281 | 15.2k | while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \ | 282 | 15.2k | khint_t k, i, step = 0; \ | 283 | 15.2k | k = __hash_func(key); \ | 284 | 15.2k | i = k & new_mask; \ | 285 | 19.9k | while (!__ac_isempty(new_flags, i)) i = (i + (++step)) & new_mask; \ | 286 | 15.2k | __ac_set_isempty_false(new_flags, i); \ | 287 | 15.2k | if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \ | 288 | 586 | { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \ | 289 | 586 | if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \ | 290 | 586 | __ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \ | 291 | 14.6k | } else { /* write the element and jump out of the loop */ \ | 292 | 14.6k | h->keys[i] = key; \ | 293 | 14.6k | if (kh_is_map) h->vals[i] = val; \ | 294 | 14.6k | break; \ | 295 | 14.6k | } \ | 296 | 15.2k | } \ | 297 | 14.6k | } \ | 298 | 21.0k | } \ | 299 | 3.68k | if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \ | 300 | 0 | h->keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ | 301 | 0 | if (kh_is_map) h->vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ | 302 | 0 | } \ | 303 | 3.68k | kfree(h->flags); /* free the working space */ \ | 304 | 3.68k | h->flags = new_flags; \ | 305 | 3.68k | h->n_buckets = new_n_buckets; \ | 306 | 3.68k | h->n_occupied = h->size; \ | 307 | 3.68k | h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \ | 308 | 3.68k | } \ | 309 | 3.68k | return 0; \ | 310 | 3.68k | } \ |
cram_decode.c:kh_resize_map Line | Count | Source | 249 | 7 | { /* This function uses 0.25*n_buckets bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \ | 250 | 7 | khint32_t *new_flags = 0; \ | 251 | 7 | khint_t j = 1; \ | 252 | 7 | { \ | 253 | 7 | kroundup32(new_n_buckets); \ | 254 | 7 | if (new_n_buckets < 4) new_n_buckets = 4; \ | 255 | 7 | if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; /* requested size is too small */ \ | 256 | 7 | else { /* hash table size to be changed (shrink or expand); rehash */ \ | 257 | 7 | new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ | 258 | 7 | if (!new_flags) return -1; \ | 259 | 7 | memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ | 260 | 7 | if (h->n_buckets < new_n_buckets) { /* expand */ \ | 261 | 7 | khkey_t *new_keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ | 262 | 7 | if (!new_keys) { kfree(new_flags); return -1; } \ | 263 | 7 | h->keys = new_keys; \ | 264 | 7 | if (kh_is_map) { \ | 265 | 7 | khval_t *new_vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ | 266 | 7 | if (!new_vals) { kfree(new_flags); return -1; } \ | 267 | 7 | h->vals = new_vals; \ | 268 | 7 | } \ | 269 | 7 | } /* otherwise shrink */ \ | 270 | 7 | } \ | 271 | 7 | } \ | 272 | 7 | if (j) { /* rehashing is needed */ \ | 273 | 31 | for (j = 0; j != h->n_buckets; ++j) { \ | 274 | 24 | if (__ac_iseither(h->flags, j) == 0) { \ | 275 | 18 | khkey_t key = h->keys[j]; \ | 276 | 18 | khval_t val; \ | 277 | 18 | khint_t new_mask; \ | 278 | 18 | new_mask = new_n_buckets - 1; \ | 279 | 18 | if (kh_is_map) val = h->vals[j]; \ | 280 | 18 | __ac_set_isdel_true(h->flags, j); \ | 281 | 18 | while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \ | 282 | 18 | khint_t k, i, step = 0; \ | 283 | 18 | k = __hash_func(key); \ | 284 | 18 | i = k & new_mask; \ | 285 | 21 | while (!__ac_isempty(new_flags, i)) i = (i + (++step)) & new_mask; \ | 286 | 18 | __ac_set_isempty_false(new_flags, i); \ | 287 | 18 | if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \ | 288 | 0 | { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \ | 289 | 0 | if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \ | 290 | 0 | __ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \ | 291 | 18 | } else { /* write the element and jump out of the loop */ \ | 292 | 18 | h->keys[i] = key; \ | 293 | 18 | if (kh_is_map) h->vals[i] = val; \ | 294 | 18 | break; \ | 295 | 18 | } \ | 296 | 18 | } \ | 297 | 18 | } \ | 298 | 24 | } \ | 299 | 7 | if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \ | 300 | 0 | h->keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ | 301 | 0 | if (kh_is_map) h->vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ | 302 | 0 | } \ | 303 | 7 | kfree(h->flags); /* free the working space */ \ | 304 | 7 | h->flags = new_flags; \ | 305 | 7 | h->n_buckets = new_n_buckets; \ | 306 | 7 | h->n_occupied = h->size; \ | 307 | 7 | h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \ | 308 | 7 | } \ | 309 | 7 | return 0; \ | 310 | 7 | } \ |
Unexecuted instantiation: cram_decode.c:kh_resize_sam_hrecs_t Unexecuted instantiation: cram_decode.c:kh_resize_m_s2i Unexecuted instantiation: cram_decode.c:kh_resize_m_i2i Unexecuted instantiation: cram_decode.c:kh_resize_s_i2i Unexecuted instantiation: cram_decode.c:kh_resize_m_metrics Unexecuted instantiation: cram_decode.c:kh_resize_m_tagmap Unexecuted instantiation: cram_decode.c:kh_resize_refs Unexecuted instantiation: cram_encode.c:kh_resize_map Unexecuted instantiation: cram_encode.c:kh_resize_m_s2u64 Unexecuted instantiation: cram_encode.c:kh_resize_m_tagmap Unexecuted instantiation: cram_encode.c:kh_resize_m_metrics Unexecuted instantiation: cram_encode.c:kh_resize_m_s2i Unexecuted instantiation: cram_encode.c:kh_resize_sam_hrecs_t Unexecuted instantiation: cram_encode.c:kh_resize_m_i2i Unexecuted instantiation: cram_encode.c:kh_resize_s_i2i Unexecuted instantiation: cram_encode.c:kh_resize_refs Unexecuted instantiation: cram_index.c:kh_resize_sam_hrecs_t Unexecuted instantiation: cram_index.c:kh_resize_m_s2i Unexecuted instantiation: cram_index.c:kh_resize_m_i2i Unexecuted instantiation: cram_index.c:kh_resize_s_i2i Unexecuted instantiation: cram_index.c:kh_resize_map Unexecuted instantiation: cram_index.c:kh_resize_m_metrics Unexecuted instantiation: cram_index.c:kh_resize_m_tagmap Unexecuted instantiation: cram_index.c:kh_resize_refs Line | Count | Source | 249 | 46 | { /* This function uses 0.25*n_buckets bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \ | 250 | 46 | khint32_t *new_flags = 0; \ | 251 | 46 | khint_t j = 1; \ | 252 | 46 | { \ | 253 | 46 | kroundup32(new_n_buckets); \ | 254 | 46 | if (new_n_buckets < 4) new_n_buckets = 4; \ | 255 | 46 | if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; /* requested size is too small */ \ | 256 | 46 | else { /* hash table size to be changed (shrink or expand); rehash */ \ | 257 | 46 | new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ | 258 | 46 | if (!new_flags) return -1; \ | 259 | 46 | memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ | 260 | 46 | if (h->n_buckets < new_n_buckets) { /* expand */ \ | 261 | 46 | khkey_t *new_keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ | 262 | 46 | if (!new_keys) { kfree(new_flags); return -1; } \ | 263 | 46 | h->keys = new_keys; \ | 264 | 46 | if (kh_is_map) { \ | 265 | 46 | khval_t *new_vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ | 266 | 46 | if (!new_vals) { kfree(new_flags); return -1; } \ | 267 | 46 | h->vals = new_vals; \ | 268 | 46 | } \ | 269 | 46 | } /* otherwise shrink */ \ | 270 | 46 | } \ | 271 | 46 | } \ | 272 | 46 | if (j) { /* rehashing is needed */ \ | 273 | 382 | for (j = 0; j != h->n_buckets; ++j) { \ | 274 | 336 | if (__ac_iseither(h->flags, j) == 0) { \ | 275 | 233 | khkey_t key = h->keys[j]; \ | 276 | 233 | khval_t val; \ | 277 | 233 | khint_t new_mask; \ | 278 | 233 | new_mask = new_n_buckets - 1; \ | 279 | 233 | if (kh_is_map) val = h->vals[j]; \ | 280 | 233 | __ac_set_isdel_true(h->flags, j); \ | 281 | 256 | while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \ | 282 | 256 | khint_t k, i, step = 0; \ | 283 | 256 | k = __hash_func(key); \ | 284 | 256 | i = k & new_mask; \ | 285 | 418 | while (!__ac_isempty(new_flags, i)) i = (i + (++step)) & new_mask; \ | 286 | 256 | __ac_set_isempty_false(new_flags, i); \ | 287 | 256 | if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \ | 288 | 23 | { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \ | 289 | 23 | if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \ | 290 | 23 | __ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \ | 291 | 233 | } else { /* write the element and jump out of the loop */ \ | 292 | 233 | h->keys[i] = key; \ | 293 | 233 | if (kh_is_map) h->vals[i] = val; \ | 294 | 233 | break; \ | 295 | 233 | } \ | 296 | 256 | } \ | 297 | 233 | } \ | 298 | 336 | } \ | 299 | 46 | if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \ | 300 | 0 | h->keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ | 301 | 0 | if (kh_is_map) h->vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ | 302 | 0 | } \ | 303 | 46 | kfree(h->flags); /* free the working space */ \ | 304 | 46 | h->flags = new_flags; \ | 305 | 46 | h->n_buckets = new_n_buckets; \ | 306 | 46 | h->n_occupied = h->size; \ | 307 | 46 | h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \ | 308 | 46 | } \ | 309 | 46 | return 0; \ | 310 | 46 | } \ |
Unexecuted instantiation: cram_io.c:kh_resize_sam_hrecs_t Unexecuted instantiation: cram_io.c:kh_resize_m_s2i Unexecuted instantiation: cram_io.c:kh_resize_m_i2i Unexecuted instantiation: cram_io.c:kh_resize_s_i2i Unexecuted instantiation: cram_io.c:kh_resize_map Unexecuted instantiation: cram_io.c:kh_resize_m_metrics Unexecuted instantiation: cram_io.c:kh_resize_m_tagmap Unexecuted instantiation: cram_stats.c:kh_resize_m_i2i Unexecuted instantiation: cram_stats.c:kh_resize_sam_hrecs_t Unexecuted instantiation: cram_stats.c:kh_resize_m_s2i Unexecuted instantiation: cram_stats.c:kh_resize_s_i2i Unexecuted instantiation: cram_stats.c:kh_resize_map Unexecuted instantiation: cram_stats.c:kh_resize_m_metrics Unexecuted instantiation: cram_stats.c:kh_resize_m_tagmap Unexecuted instantiation: cram_stats.c:kh_resize_refs Unexecuted instantiation: hfile_libcurl.c:kh_resize_auth_map Unexecuted instantiation: bgzf.c:kh_resize_cache Unexecuted instantiation: faidx.c:kh_resize_s Unexecuted instantiation: cram_codecs.c:kh_resize_sam_hrecs_t Unexecuted instantiation: cram_codecs.c:kh_resize_m_s2i Unexecuted instantiation: cram_codecs.c:kh_resize_m_i2i Unexecuted instantiation: cram_codecs.c:kh_resize_s_i2i Unexecuted instantiation: cram_codecs.c:kh_resize_map Unexecuted instantiation: cram_codecs.c:kh_resize_m_metrics Unexecuted instantiation: cram_codecs.c:kh_resize_m_tagmap Unexecuted instantiation: cram_codecs.c:kh_resize_refs |
311 | | SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \ |
312 | 5.47M | { \ |
313 | 5.47M | khint_t x; \ |
314 | 5.47M | if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \ |
315 | 6.01k | if (h->n_buckets > (h->size<<1)) { \ |
316 | 311 | if (kh_resize_##name(h, h->n_buckets - 1) < 0) { /* clear "deleted" elements */ \ |
317 | 0 | *ret = -1; return h->n_buckets; \ |
318 | 0 | } \ |
319 | 5.70k | } else if (kh_resize_##name(h, h->n_buckets + 1) < 0) { /* expand the hash table */ \ |
320 | 0 | *ret = -1; return h->n_buckets; \ |
321 | 0 | } \ |
322 | 6.01k | } /* TODO: to implement automatically shrinking; resize() already support shrinking */ \ |
323 | 5.47M | { \ |
324 | 5.47M | khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \ |
325 | 5.47M | x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \ |
326 | 5.47M | if (__ac_isempty(h->flags, i)) x = i; /* for speed up */ \ |
327 | 5.47M | else { \ |
328 | 5.46M | last = i; \ |
329 | 5.52M | while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ |
330 | 61.3k | if (__ac_isdel(h->flags, i)) site = i; \ |
331 | 61.3k | i = (i + (++step)) & mask; \ |
332 | 61.3k | if (i == last) { x = site; break; } \ |
333 | 61.3k | } \ |
334 | 5.46M | if (x == h->n_buckets) { \ |
335 | 5.46M | if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \ |
336 | 5.46M | else x = i; \ |
337 | 5.46M | } \ |
338 | 5.46M | } \ |
339 | 5.47M | } \ |
340 | 5.47M | if (__ac_isempty(h->flags, x)) { /* not present at all */ \ |
341 | 22.9k | h->keys[x] = key; \ |
342 | 22.9k | __ac_set_isboth_false(h->flags, x); \ |
343 | 22.9k | ++h->size; ++h->n_occupied; \ |
344 | 22.9k | *ret = 1; \ |
345 | 5.45M | } else if (__ac_isdel(h->flags, x)) { /* deleted */ \ |
346 | 600 | h->keys[x] = key; \ |
347 | 600 | __ac_set_isboth_false(h->flags, x); \ |
348 | 600 | ++h->size; \ |
349 | 600 | *ret = 2; \ |
350 | 5.45M | } else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \ |
351 | 5.47M | return x; \ |
352 | 5.47M | } \ header.c:kh_put_sam_hrecs_t Line | Count | Source | 312 | 2.73M | { \ | 313 | 2.73M | khint_t x; \ | 314 | 2.73M | if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \ | 315 | 628 | if (h->n_buckets > (h->size<<1)) { \ | 316 | 0 | if (kh_resize_##name(h, h->n_buckets - 1) < 0) { /* clear "deleted" elements */ \ | 317 | 0 | *ret = -1; return h->n_buckets; \ | 318 | 0 | } \ | 319 | 628 | } else if (kh_resize_##name(h, h->n_buckets + 1) < 0) { /* expand the hash table */ \ | 320 | 0 | *ret = -1; return h->n_buckets; \ | 321 | 0 | } \ | 322 | 628 | } /* TODO: to implement automatically shrinking; resize() already support shrinking */ \ | 323 | 2.73M | { \ | 324 | 2.73M | khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \ | 325 | 2.73M | x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \ | 326 | 2.73M | if (__ac_isempty(h->flags, i)) x = i; /* for speed up */ \ | 327 | 2.73M | else { \ | 328 | 2.73M | last = i; \ | 329 | 2.76M | while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ | 330 | 26.8k | if (__ac_isdel(h->flags, i)) site = i; \ | 331 | 26.8k | i = (i + (++step)) & mask; \ | 332 | 26.8k | if (i == last) { x = site; break; } \ | 333 | 26.8k | } \ | 334 | 2.73M | if (x == h->n_buckets) { \ | 335 | 2.73M | if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \ | 336 | 2.73M | else x = i; \ | 337 | 2.73M | } \ | 338 | 2.73M | } \ | 339 | 2.73M | } \ | 340 | 2.73M | if (__ac_isempty(h->flags, x)) { /* not present at all */ \ | 341 | 861 | h->keys[x] = key; \ | 342 | 861 | __ac_set_isboth_false(h->flags, x); \ | 343 | 861 | ++h->size; ++h->n_occupied; \ | 344 | 861 | *ret = 1; \ | 345 | 2.73M | } else if (__ac_isdel(h->flags, x)) { /* deleted */ \ | 346 | 0 | h->keys[x] = key; \ | 347 | 0 | __ac_set_isboth_false(h->flags, x); \ | 348 | 0 | ++h->size; \ | 349 | 0 | *ret = 2; \ | 350 | 2.73M | } else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \ | 351 | 2.73M | return x; \ | 352 | 2.73M | } \ |
Line | Count | Source | 312 | 2.71M | { \ | 313 | 2.71M | khint_t x; \ | 314 | 2.71M | if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \ | 315 | 999 | if (h->n_buckets > (h->size<<1)) { \ | 316 | 0 | if (kh_resize_##name(h, h->n_buckets - 1) < 0) { /* clear "deleted" elements */ \ | 317 | 0 | *ret = -1; return h->n_buckets; \ | 318 | 0 | } \ | 319 | 999 | } else if (kh_resize_##name(h, h->n_buckets + 1) < 0) { /* expand the hash table */ \ | 320 | 0 | *ret = -1; return h->n_buckets; \ | 321 | 0 | } \ | 322 | 999 | } /* TODO: to implement automatically shrinking; resize() already support shrinking */ \ | 323 | 2.71M | { \ | 324 | 2.71M | khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \ | 325 | 2.71M | x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \ | 326 | 2.71M | if (__ac_isempty(h->flags, i)) x = i; /* for speed up */ \ | 327 | 2.71M | else { \ | 328 | 2.71M | last = i; \ | 329 | 2.72M | while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ | 330 | 12.2k | if (__ac_isdel(h->flags, i)) site = i; \ | 331 | 12.2k | i = (i + (++step)) & mask; \ | 332 | 12.2k | if (i == last) { x = site; break; } \ | 333 | 12.2k | } \ | 334 | 2.71M | if (x == h->n_buckets) { \ | 335 | 2.71M | if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \ | 336 | 2.71M | else x = i; \ | 337 | 2.71M | } \ | 338 | 2.71M | } \ | 339 | 2.71M | } \ | 340 | 2.71M | if (__ac_isempty(h->flags, x)) { /* not present at all */ \ | 341 | 4.31k | h->keys[x] = key; \ | 342 | 4.31k | __ac_set_isboth_false(h->flags, x); \ | 343 | 4.31k | ++h->size; ++h->n_occupied; \ | 344 | 4.31k | *ret = 1; \ | 345 | 2.71M | } else if (__ac_isdel(h->flags, x)) { /* deleted */ \ | 346 | 0 | h->keys[x] = key; \ | 347 | 0 | __ac_set_isboth_false(h->flags, x); \ | 348 | 0 | ++h->size; \ | 349 | 0 | *ret = 2; \ | 350 | 2.71M | } else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \ | 351 | 2.71M | return x; \ | 352 | 2.71M | } \ |
Unexecuted instantiation: header.c:kh_put_rm hfile.c:kh_put_scheme_string Line | Count | Source | 312 | 37 | { \ | 313 | 37 | khint_t x; \ | 314 | 37 | if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \ | 315 | 5 | if (h->n_buckets > (h->size<<1)) { \ | 316 | 0 | if (kh_resize_##name(h, h->n_buckets - 1) < 0) { /* clear "deleted" elements */ \ | 317 | 0 | *ret = -1; return h->n_buckets; \ | 318 | 0 | } \ | 319 | 5 | } else if (kh_resize_##name(h, h->n_buckets + 1) < 0) { /* expand the hash table */ \ | 320 | 0 | *ret = -1; return h->n_buckets; \ | 321 | 0 | } \ | 322 | 5 | } /* TODO: to implement automatically shrinking; resize() already support shrinking */ \ | 323 | 37 | { \ | 324 | 37 | khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \ | 325 | 37 | x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \ | 326 | 37 | if (__ac_isempty(h->flags, i)) x = i; /* for speed up */ \ | 327 | 37 | else { \ | 328 | 16 | last = i; \ | 329 | 44 | while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ | 330 | 28 | if (__ac_isdel(h->flags, i)) site = i; \ | 331 | 28 | i = (i + (++step)) & mask; \ | 332 | 28 | if (i == last) { x = site; break; } \ | 333 | 28 | } \ | 334 | 16 | if (x == h->n_buckets) { \ | 335 | 16 | if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \ | 336 | 16 | else x = i; \ | 337 | 16 | } \ | 338 | 16 | } \ | 339 | 37 | } \ | 340 | 37 | if (__ac_isempty(h->flags, x)) { /* not present at all */ \ | 341 | 36 | h->keys[x] = key; \ | 342 | 36 | __ac_set_isboth_false(h->flags, x); \ | 343 | 36 | ++h->size; ++h->n_occupied; \ | 344 | 36 | *ret = 1; \ | 345 | 36 | } else if (__ac_isdel(h->flags, x)) { /* deleted */ \ | 346 | 0 | h->keys[x] = key; \ | 347 | 0 | __ac_set_isboth_false(h->flags, x); \ | 348 | 0 | ++h->size; \ | 349 | 0 | *ret = 2; \ | 350 | 1 | } else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \ | 351 | 37 | return x; \ | 352 | 37 | } \ |
Line | Count | Source | 312 | 4.81k | { \ | 313 | 4.81k | khint_t x; \ | 314 | 4.81k | if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \ | 315 | 644 | if (h->n_buckets > (h->size<<1)) { \ | 316 | 0 | if (kh_resize_##name(h, h->n_buckets - 1) < 0) { /* clear "deleted" elements */ \ | 317 | 0 | *ret = -1; return h->n_buckets; \ | 318 | 0 | } \ | 319 | 644 | } else if (kh_resize_##name(h, h->n_buckets + 1) < 0) { /* expand the hash table */ \ | 320 | 0 | *ret = -1; return h->n_buckets; \ | 321 | 0 | } \ | 322 | 644 | } /* TODO: to implement automatically shrinking; resize() already support shrinking */ \ | 323 | 4.81k | { \ | 324 | 4.81k | khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \ | 325 | 4.81k | x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \ | 326 | 4.81k | if (__ac_isempty(h->flags, i)) x = i; /* for speed up */ \ | 327 | 4.81k | else { \ | 328 | 3.07k | last = i; \ | 329 | 8.80k | while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ | 330 | 5.72k | if (__ac_isdel(h->flags, i)) site = i; \ | 331 | 5.72k | i = (i + (++step)) & mask; \ | 332 | 5.72k | if (i == last) { x = site; break; } \ | 333 | 5.72k | } \ | 334 | 3.07k | if (x == h->n_buckets) { \ | 335 | 3.07k | if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \ | 336 | 3.07k | else x = i; \ | 337 | 3.07k | } \ | 338 | 3.07k | } \ | 339 | 4.81k | } \ | 340 | 4.81k | if (__ac_isempty(h->flags, x)) { /* not present at all */ \ | 341 | 3.49k | h->keys[x] = key; \ | 342 | 3.49k | __ac_set_isboth_false(h->flags, x); \ | 343 | 3.49k | ++h->size; ++h->n_occupied; \ | 344 | 3.49k | *ret = 1; \ | 345 | 3.49k | } else if (__ac_isdel(h->flags, x)) { /* deleted */ \ | 346 | 0 | h->keys[x] = key; \ | 347 | 0 | __ac_set_isboth_false(h->flags, x); \ | 348 | 0 | ++h->size; \ | 349 | 0 | *ret = 2; \ | 350 | 1.32k | } else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \ | 351 | 4.81k | return x; \ | 352 | 4.81k | } \ |
Unexecuted instantiation: hts.c:kh_put_bin Unexecuted instantiation: hts.c:kh_put_sam_hrecs_t Unexecuted instantiation: hts.c:kh_put_m_s2i Unexecuted instantiation: hts.c:kh_put_m_i2i Unexecuted instantiation: hts.c:kh_put_s_i2i Unexecuted instantiation: hts.c:kh_put_map Unexecuted instantiation: hts.c:kh_put_m_metrics Unexecuted instantiation: hts.c:kh_put_m_tagmap Unexecuted instantiation: hts.c:kh_put_refs Unexecuted instantiation: region.c:kh_put_reg Unexecuted instantiation: sam.c:kh_put_tag Unexecuted instantiation: sam.c:kh_put_olap_hash Unexecuted instantiation: sam.c:kh_put_sam_hrecs_t Unexecuted instantiation: sam.c:kh_put_m_s2i Unexecuted instantiation: sam.c:kh_put_m_i2i Unexecuted instantiation: sam.c:kh_put_s_i2i Unexecuted instantiation: sam.c:kh_put_map Unexecuted instantiation: sam.c:kh_put_m_metrics Unexecuted instantiation: sam.c:kh_put_m_tagmap Unexecuted instantiation: sam.c:kh_put_refs Unexecuted instantiation: vcf.c:kh_put_str2int Line | Count | Source | 312 | 14.5k | { \ | 313 | 14.5k | khint_t x; \ | 314 | 14.5k | if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \ | 315 | 3.68k | if (h->n_buckets > (h->size<<1)) { \ | 316 | 311 | if (kh_resize_##name(h, h->n_buckets - 1) < 0) { /* clear "deleted" elements */ \ | 317 | 0 | *ret = -1; return h->n_buckets; \ | 318 | 0 | } \ | 319 | 3.37k | } else if (kh_resize_##name(h, h->n_buckets + 1) < 0) { /* expand the hash table */ \ | 320 | 0 | *ret = -1; return h->n_buckets; \ | 321 | 0 | } \ | 322 | 3.68k | } /* TODO: to implement automatically shrinking; resize() already support shrinking */ \ | 323 | 14.5k | { \ | 324 | 14.5k | khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \ | 325 | 14.5k | x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \ | 326 | 14.5k | if (__ac_isempty(h->flags, i)) x = i; /* for speed up */ \ | 327 | 14.5k | else { \ | 328 | 6.76k | last = i; \ | 329 | 22.8k | while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ | 330 | 16.1k | if (__ac_isdel(h->flags, i)) site = i; \ | 331 | 16.1k | i = (i + (++step)) & mask; \ | 332 | 16.1k | if (i == last) { x = site; break; } \ | 333 | 16.1k | } \ | 334 | 6.76k | if (x == h->n_buckets) { \ | 335 | 6.76k | if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \ | 336 | 6.76k | else x = i; \ | 337 | 6.76k | } \ | 338 | 6.76k | } \ | 339 | 14.5k | } \ | 340 | 14.5k | if (__ac_isempty(h->flags, x)) { /* not present at all */ \ | 341 | 13.9k | h->keys[x] = key; \ | 342 | 13.9k | __ac_set_isboth_false(h->flags, x); \ | 343 | 13.9k | ++h->size; ++h->n_occupied; \ | 344 | 13.9k | *ret = 1; \ | 345 | 13.9k | } else if (__ac_isdel(h->flags, x)) { /* deleted */ \ | 346 | 600 | h->keys[x] = key; \ | 347 | 600 | __ac_set_isboth_false(h->flags, x); \ | 348 | 600 | ++h->size; \ | 349 | 600 | *ret = 2; \ | 350 | 600 | } else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \ | 351 | 14.5k | return x; \ | 352 | 14.5k | } \ |
Line | Count | Source | 312 | 23 | { \ | 313 | 23 | khint_t x; \ | 314 | 23 | if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \ | 315 | 7 | if (h->n_buckets > (h->size<<1)) { \ | 316 | 0 | if (kh_resize_##name(h, h->n_buckets - 1) < 0) { /* clear "deleted" elements */ \ | 317 | 0 | *ret = -1; return h->n_buckets; \ | 318 | 0 | } \ | 319 | 7 | } else if (kh_resize_##name(h, h->n_buckets + 1) < 0) { /* expand the hash table */ \ | 320 | 0 | *ret = -1; return h->n_buckets; \ | 321 | 0 | } \ | 322 | 7 | } /* TODO: to implement automatically shrinking; resize() already support shrinking */ \ | 323 | 23 | { \ | 324 | 23 | khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \ | 325 | 23 | x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \ | 326 | 23 | if (__ac_isempty(h->flags, i)) x = i; /* for speed up */ \ | 327 | 23 | else { \ | 328 | 13 | last = i; \ | 329 | 19 | while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ | 330 | 6 | if (__ac_isdel(h->flags, i)) site = i; \ | 331 | 6 | i = (i + (++step)) & mask; \ | 332 | 6 | if (i == last) { x = site; break; } \ | 333 | 6 | } \ | 334 | 13 | if (x == h->n_buckets) { \ | 335 | 13 | if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \ | 336 | 13 | else x = i; \ | 337 | 13 | } \ | 338 | 13 | } \ | 339 | 23 | } \ | 340 | 23 | if (__ac_isempty(h->flags, x)) { /* not present at all */ \ | 341 | 15 | h->keys[x] = key; \ | 342 | 15 | __ac_set_isboth_false(h->flags, x); \ | 343 | 15 | ++h->size; ++h->n_occupied; \ | 344 | 15 | *ret = 1; \ | 345 | 15 | } else if (__ac_isdel(h->flags, x)) { /* deleted */ \ | 346 | 0 | h->keys[x] = key; \ | 347 | 0 | __ac_set_isboth_false(h->flags, x); \ | 348 | 0 | ++h->size; \ | 349 | 0 | *ret = 2; \ | 350 | 8 | } else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \ | 351 | 23 | return x; \ | 352 | 23 | } \ |
Unexecuted instantiation: cram_decode.c:kh_put_sam_hrecs_t Unexecuted instantiation: cram_decode.c:kh_put_m_s2i Unexecuted instantiation: cram_decode.c:kh_put_m_i2i Unexecuted instantiation: cram_decode.c:kh_put_s_i2i Unexecuted instantiation: cram_decode.c:kh_put_m_metrics Unexecuted instantiation: cram_decode.c:kh_put_m_tagmap Unexecuted instantiation: cram_decode.c:kh_put_refs Unexecuted instantiation: cram_encode.c:kh_put_map Unexecuted instantiation: cram_encode.c:kh_put_m_s2u64 Unexecuted instantiation: cram_encode.c:kh_put_m_tagmap Unexecuted instantiation: cram_encode.c:kh_put_m_metrics Unexecuted instantiation: cram_encode.c:kh_put_m_s2i Unexecuted instantiation: cram_encode.c:kh_put_sam_hrecs_t Unexecuted instantiation: cram_encode.c:kh_put_m_i2i Unexecuted instantiation: cram_encode.c:kh_put_s_i2i Unexecuted instantiation: cram_encode.c:kh_put_refs Unexecuted instantiation: cram_index.c:kh_put_sam_hrecs_t Unexecuted instantiation: cram_index.c:kh_put_m_s2i Unexecuted instantiation: cram_index.c:kh_put_m_i2i Unexecuted instantiation: cram_index.c:kh_put_s_i2i Unexecuted instantiation: cram_index.c:kh_put_map Unexecuted instantiation: cram_index.c:kh_put_m_metrics Unexecuted instantiation: cram_index.c:kh_put_m_tagmap Unexecuted instantiation: cram_index.c:kh_put_refs Line | Count | Source | 312 | 216 | { \ | 313 | 216 | khint_t x; \ | 314 | 216 | if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \ | 315 | 46 | if (h->n_buckets > (h->size<<1)) { \ | 316 | 0 | if (kh_resize_##name(h, h->n_buckets - 1) < 0) { /* clear "deleted" elements */ \ | 317 | 0 | *ret = -1; return h->n_buckets; \ | 318 | 0 | } \ | 319 | 46 | } else if (kh_resize_##name(h, h->n_buckets + 1) < 0) { /* expand the hash table */ \ | 320 | 0 | *ret = -1; return h->n_buckets; \ | 321 | 0 | } \ | 322 | 46 | } /* TODO: to implement automatically shrinking; resize() already support shrinking */ \ | 323 | 216 | { \ | 324 | 216 | khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \ | 325 | 216 | x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \ | 326 | 216 | if (__ac_isempty(h->flags, i)) x = i; /* for speed up */ \ | 327 | 216 | else { \ | 328 | 137 | last = i; \ | 329 | 474 | while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ | 330 | 337 | if (__ac_isdel(h->flags, i)) site = i; \ | 331 | 337 | i = (i + (++step)) & mask; \ | 332 | 337 | if (i == last) { x = site; break; } \ | 333 | 337 | } \ | 334 | 137 | if (x == h->n_buckets) { \ | 335 | 137 | if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \ | 336 | 137 | else x = i; \ | 337 | 137 | } \ | 338 | 137 | } \ | 339 | 216 | } \ | 340 | 216 | if (__ac_isempty(h->flags, x)) { /* not present at all */ \ | 341 | 216 | h->keys[x] = key; \ | 342 | 216 | __ac_set_isboth_false(h->flags, x); \ | 343 | 216 | ++h->size; ++h->n_occupied; \ | 344 | 216 | *ret = 1; \ | 345 | 216 | } else if (__ac_isdel(h->flags, x)) { /* deleted */ \ | 346 | 0 | h->keys[x] = key; \ | 347 | 0 | __ac_set_isboth_false(h->flags, x); \ | 348 | 0 | ++h->size; \ | 349 | 0 | *ret = 2; \ | 350 | 0 | } else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \ | 351 | 216 | return x; \ | 352 | 216 | } \ |
Unexecuted instantiation: cram_io.c:kh_put_sam_hrecs_t Unexecuted instantiation: cram_io.c:kh_put_m_s2i Unexecuted instantiation: cram_io.c:kh_put_m_i2i Unexecuted instantiation: cram_io.c:kh_put_s_i2i Unexecuted instantiation: cram_io.c:kh_put_map Unexecuted instantiation: cram_io.c:kh_put_m_metrics Unexecuted instantiation: cram_io.c:kh_put_m_tagmap Unexecuted instantiation: cram_stats.c:kh_put_m_i2i Unexecuted instantiation: cram_stats.c:kh_put_sam_hrecs_t Unexecuted instantiation: cram_stats.c:kh_put_m_s2i Unexecuted instantiation: cram_stats.c:kh_put_s_i2i Unexecuted instantiation: cram_stats.c:kh_put_map Unexecuted instantiation: cram_stats.c:kh_put_m_metrics Unexecuted instantiation: cram_stats.c:kh_put_m_tagmap Unexecuted instantiation: cram_stats.c:kh_put_refs Unexecuted instantiation: hfile_libcurl.c:kh_put_auth_map Unexecuted instantiation: bgzf.c:kh_put_cache Unexecuted instantiation: faidx.c:kh_put_s Unexecuted instantiation: cram_codecs.c:kh_put_sam_hrecs_t Unexecuted instantiation: cram_codecs.c:kh_put_m_s2i Unexecuted instantiation: cram_codecs.c:kh_put_m_i2i Unexecuted instantiation: cram_codecs.c:kh_put_s_i2i Unexecuted instantiation: cram_codecs.c:kh_put_map Unexecuted instantiation: cram_codecs.c:kh_put_m_metrics Unexecuted instantiation: cram_codecs.c:kh_put_m_tagmap Unexecuted instantiation: cram_codecs.c:kh_put_refs |
353 | | SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x) \ |
354 | 1.43k | { \ |
355 | 1.43k | if (x != h->n_buckets && !__ac_iseither(h->flags, x)) { \ |
356 | 1.43k | __ac_set_isdel_true(h->flags, x); \ |
357 | 1.43k | --h->size; \ |
358 | 1.43k | } \ |
359 | 1.43k | } Unexecuted instantiation: header.c:kh_del_sam_hrecs_t Unexecuted instantiation: header.c:kh_del_m_s2i Unexecuted instantiation: header.c:kh_del_rm Unexecuted instantiation: hfile.c:kh_del_scheme_string Unexecuted instantiation: kh_del_s2i Unexecuted instantiation: hts.c:kh_del_bin Unexecuted instantiation: hts.c:kh_del_sam_hrecs_t Unexecuted instantiation: hts.c:kh_del_m_s2i Unexecuted instantiation: hts.c:kh_del_m_i2i Unexecuted instantiation: hts.c:kh_del_s_i2i Unexecuted instantiation: hts.c:kh_del_map Unexecuted instantiation: hts.c:kh_del_m_metrics Unexecuted instantiation: hts.c:kh_del_m_tagmap Unexecuted instantiation: hts.c:kh_del_refs Unexecuted instantiation: region.c:kh_del_reg Unexecuted instantiation: sam.c:kh_del_olap_hash Unexecuted instantiation: sam.c:kh_del_sam_hrecs_t Unexecuted instantiation: sam.c:kh_del_m_s2i Unexecuted instantiation: sam.c:kh_del_m_i2i Unexecuted instantiation: sam.c:kh_del_s_i2i Unexecuted instantiation: sam.c:kh_del_map Unexecuted instantiation: sam.c:kh_del_m_metrics Unexecuted instantiation: sam.c:kh_del_m_tagmap Unexecuted instantiation: sam.c:kh_del_refs Unexecuted instantiation: sam.c:kh_del_tag Line | Count | Source | 354 | 1.43k | { \ | 355 | 1.43k | if (x != h->n_buckets && !__ac_iseither(h->flags, x)) { \ | 356 | 1.43k | __ac_set_isdel_true(h->flags, x); \ | 357 | 1.43k | --h->size; \ | 358 | 1.43k | } \ | 359 | 1.43k | } |
Unexecuted instantiation: vcf.c:kh_del_str2int Unexecuted instantiation: cram_decode.c:kh_del_sam_hrecs_t Unexecuted instantiation: cram_decode.c:kh_del_m_s2i Unexecuted instantiation: cram_decode.c:kh_del_m_i2i Unexecuted instantiation: cram_decode.c:kh_del_s_i2i Unexecuted instantiation: cram_decode.c:kh_del_map Unexecuted instantiation: cram_decode.c:kh_del_m_metrics Unexecuted instantiation: cram_decode.c:kh_del_m_tagmap Unexecuted instantiation: cram_decode.c:kh_del_refs Unexecuted instantiation: cram_encode.c:kh_del_m_metrics Unexecuted instantiation: cram_encode.c:kh_del_sam_hrecs_t Unexecuted instantiation: cram_encode.c:kh_del_m_s2i Unexecuted instantiation: cram_encode.c:kh_del_m_i2i Unexecuted instantiation: cram_encode.c:kh_del_s_i2i Unexecuted instantiation: cram_encode.c:kh_del_map Unexecuted instantiation: cram_encode.c:kh_del_m_tagmap Unexecuted instantiation: cram_encode.c:kh_del_refs Unexecuted instantiation: cram_encode.c:kh_del_m_s2u64 Unexecuted instantiation: cram_index.c:kh_del_sam_hrecs_t Unexecuted instantiation: cram_index.c:kh_del_m_s2i Unexecuted instantiation: cram_index.c:kh_del_m_i2i Unexecuted instantiation: cram_index.c:kh_del_s_i2i Unexecuted instantiation: cram_index.c:kh_del_map Unexecuted instantiation: cram_index.c:kh_del_m_metrics Unexecuted instantiation: cram_index.c:kh_del_m_tagmap Unexecuted instantiation: cram_index.c:kh_del_refs Unexecuted instantiation: cram_io.c:kh_del_sam_hrecs_t Unexecuted instantiation: cram_io.c:kh_del_m_s2i Unexecuted instantiation: cram_io.c:kh_del_m_i2i Unexecuted instantiation: cram_io.c:kh_del_s_i2i Unexecuted instantiation: cram_io.c:kh_del_map Unexecuted instantiation: cram_io.c:kh_del_m_metrics Unexecuted instantiation: cram_io.c:kh_del_m_tagmap Unexecuted instantiation: cram_io.c:kh_del_refs Unexecuted instantiation: cram_stats.c:kh_del_m_i2i Unexecuted instantiation: cram_stats.c:kh_del_sam_hrecs_t Unexecuted instantiation: cram_stats.c:kh_del_m_s2i Unexecuted instantiation: cram_stats.c:kh_del_s_i2i Unexecuted instantiation: cram_stats.c:kh_del_map Unexecuted instantiation: cram_stats.c:kh_del_m_metrics Unexecuted instantiation: cram_stats.c:kh_del_m_tagmap Unexecuted instantiation: cram_stats.c:kh_del_refs Unexecuted instantiation: hfile_libcurl.c:kh_del_auth_map Unexecuted instantiation: bgzf.c:kh_del_cache Unexecuted instantiation: faidx.c:kh_del_s Unexecuted instantiation: cram_codecs.c:kh_del_sam_hrecs_t Unexecuted instantiation: cram_codecs.c:kh_del_m_s2i Unexecuted instantiation: cram_codecs.c:kh_del_m_i2i Unexecuted instantiation: cram_codecs.c:kh_del_s_i2i Unexecuted instantiation: cram_codecs.c:kh_del_map Unexecuted instantiation: cram_codecs.c:kh_del_m_metrics Unexecuted instantiation: cram_codecs.c:kh_del_m_tagmap Unexecuted instantiation: cram_codecs.c:kh_del_refs |
360 | | |
361 | | #define KHASH_DECLARE(name, khkey_t, khval_t) \ |
362 | | __KHASH_TYPE(name, khkey_t, khval_t) \ |
363 | | __KHASH_PROTOTYPES(name, khkey_t, khval_t) |
364 | | |
365 | | #define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ |
366 | | __KHASH_TYPE(name, khkey_t, khval_t) \ |
367 | | __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) |
368 | | |
369 | | #define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ |
370 | | KHASH_INIT2(name, static kh_inline klib_unused, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) |
371 | | |
372 | | /* --- BEGIN OF HASH FUNCTIONS --- */ |
373 | | |
374 | | /*! @function |
375 | | @abstract Integer hash function |
376 | | @param key The integer [khint32_t] |
377 | | @return The hash value [khint_t] |
378 | | */ |
379 | 2.73M | #define kh_int_hash_func(key) (khint32_t)(key) |
380 | | /*! @function |
381 | | @abstract Integer comparison function |
382 | | */ |
383 | 2.76M | #define kh_int_hash_equal(a, b) ((a) == (b)) |
384 | | /*! @function |
385 | | @abstract 64-bit integer hash function |
386 | | @param key The integer [khint64_t] |
387 | | @return The hash value [khint_t] |
388 | | */ |
389 | 0 | #define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11) |
390 | | /*! @function |
391 | | @abstract 64-bit integer comparison function |
392 | | */ |
393 | 0 | #define kh_int64_hash_equal(a, b) ((a) == (b)) |
394 | | /*! @function |
395 | | @abstract const char* hash function |
396 | | @param s Pointer to a null terminated string |
397 | | @return The hash value |
398 | | */ |
399 | | static kh_inline khint_t __ac_X31_hash_string(const char *s) |
400 | 6.22M | { |
401 | 6.22M | khint_t h = (khint_t)*s; |
402 | 1.22G | if (h) for (++s ; *s; ++s) h = (h << 5) - h + (khint_t)*s; |
403 | 6.22M | return h; |
404 | 6.22M | } header.c:__ac_X31_hash_string Line | Count | Source | 400 | 2.78M | { | 401 | 2.78M | khint_t h = (khint_t)*s; | 402 | 276M | if (h) for (++s ; *s; ++s) h = (h << 5) - h + (khint_t)*s; | 403 | 2.78M | return h; | 404 | 2.78M | } |
hfile.c:__ac_X31_hash_string Line | Count | Source | 400 | 1.88k | { | 401 | 1.88k | khint_t h = (khint_t)*s; | 402 | 5.78k | if (h) for (++s ; *s; ++s) h = (h << 5) - h + (khint_t)*s; | 403 | 1.88k | return h; | 404 | 1.88k | } |
hts.c:__ac_X31_hash_string Line | Count | Source | 400 | 10.4k | { | 401 | 10.4k | khint_t h = (khint_t)*s; | 402 | 318M | if (h) for (++s ; *s; ++s) h = (h << 5) - h + (khint_t)*s; | 403 | 10.4k | return h; | 404 | 10.4k | } |
Unexecuted instantiation: region.c:__ac_X31_hash_string Unexecuted instantiation: sam.c:__ac_X31_hash_string vcf.c:__ac_X31_hash_string Line | Count | Source | 400 | 3.42M | { | 401 | 3.42M | khint_t h = (khint_t)*s; | 402 | 626M | if (h) for (++s ; *s; ++s) h = (h << 5) - h + (khint_t)*s; | 403 | 3.42M | return h; | 404 | 3.42M | } |
cram_decode.c:__ac_X31_hash_string Line | Count | Source | 400 | 41 | { | 401 | 41 | khint_t h = (khint_t)*s; | 402 | 82 | if (h) for (++s ; *s; ++s) h = (h << 5) - h + (khint_t)*s; | 403 | 41 | return h; | 404 | 41 | } |
Unexecuted instantiation: cram_encode.c:__ac_X31_hash_string Unexecuted instantiation: cram_index.c:__ac_X31_hash_string cram_io.c:__ac_X31_hash_string Line | Count | Source | 400 | 670 | { | 401 | 670 | khint_t h = (khint_t)*s; | 402 | 204k | if (h) for (++s ; *s; ++s) h = (h << 5) - h + (khint_t)*s; | 403 | 670 | return h; | 404 | 670 | } |
Unexecuted instantiation: cram_stats.c:__ac_X31_hash_string Unexecuted instantiation: hfile_libcurl.c:__ac_X31_hash_string Unexecuted instantiation: hfile_s3_write.c:__ac_X31_hash_string Unexecuted instantiation: bgzf.c:__ac_X31_hash_string Unexecuted instantiation: faidx.c:__ac_X31_hash_string Unexecuted instantiation: tbx.c:__ac_X31_hash_string Unexecuted instantiation: cram_codecs.c:__ac_X31_hash_string |
405 | | /*! @function |
406 | | @abstract Another interface to const char* hash function |
407 | | @param key Pointer to a nul terminated string [const char*] |
408 | | @return The hash value [khint_t] |
409 | | */ |
410 | 6.22M | #define kh_str_hash_func(key) __ac_X31_hash_string(key) |
411 | | /*! @function |
412 | | @abstract Const char* comparison function |
413 | | */ |
414 | 6.51M | #define kh_str_hash_equal(a, b) (strcmp(a, b) == 0) |
415 | | |
416 | | /*! @function |
417 | | @abstract Kstring hash function |
418 | | @param s Pointer to a kstring |
419 | | @return The hash value |
420 | | */ |
421 | | static kh_inline khint_t __ac_X31_hash_kstring(const kstring_t ks) |
422 | 0 | { |
423 | 0 | khint_t h = 0; |
424 | 0 | size_t i; |
425 | 0 | for (i = 0; i < ks.l; i++) |
426 | 0 | h = (h << 5) - h + (khint_t)ks.s[i]; |
427 | 0 | return h; |
428 | 0 | } Unexecuted instantiation: header.c:__ac_X31_hash_kstring Unexecuted instantiation: hfile.c:__ac_X31_hash_kstring Unexecuted instantiation: hts.c:__ac_X31_hash_kstring Unexecuted instantiation: region.c:__ac_X31_hash_kstring Unexecuted instantiation: sam.c:__ac_X31_hash_kstring Unexecuted instantiation: vcf.c:__ac_X31_hash_kstring Unexecuted instantiation: cram_decode.c:__ac_X31_hash_kstring Unexecuted instantiation: cram_encode.c:__ac_X31_hash_kstring Unexecuted instantiation: cram_index.c:__ac_X31_hash_kstring Unexecuted instantiation: cram_io.c:__ac_X31_hash_kstring Unexecuted instantiation: cram_stats.c:__ac_X31_hash_kstring Unexecuted instantiation: hfile_libcurl.c:__ac_X31_hash_kstring Unexecuted instantiation: hfile_s3_write.c:__ac_X31_hash_kstring Unexecuted instantiation: bgzf.c:__ac_X31_hash_kstring Unexecuted instantiation: faidx.c:__ac_X31_hash_kstring Unexecuted instantiation: tbx.c:__ac_X31_hash_kstring Unexecuted instantiation: cram_codecs.c:__ac_X31_hash_kstring |
429 | | /*! @function |
430 | | @abstract Interface to kstring hash function. |
431 | | @param key Pointer to a khash; permits hashing on non-nul terminated strings. |
432 | | @return The hash value [khint_t] |
433 | | */ |
434 | | #define kh_kstr_hash_func(key) __ac_X31_hash_kstring(key) |
435 | | /*! @function |
436 | | @abstract kstring comparison function |
437 | | */ |
438 | | #define kh_kstr_hash_equal(a, b) ((a).l == (b).l && strncmp((a).s, (b).s, (a).l) == 0) |
439 | | |
440 | | static kh_inline khint_t __ac_Wang_hash(khint_t key) |
441 | 0 | { |
442 | 0 | key += ~(key << 15); |
443 | 0 | key ^= (key >> 10); |
444 | 0 | key += (key << 3); |
445 | 0 | key ^= (key >> 6); |
446 | 0 | key += ~(key << 11); |
447 | 0 | key ^= (key >> 16); |
448 | 0 | return key; |
449 | 0 | } Unexecuted instantiation: header.c:__ac_Wang_hash Unexecuted instantiation: hfile.c:__ac_Wang_hash Unexecuted instantiation: hts.c:__ac_Wang_hash Unexecuted instantiation: region.c:__ac_Wang_hash Unexecuted instantiation: sam.c:__ac_Wang_hash Unexecuted instantiation: vcf.c:__ac_Wang_hash Unexecuted instantiation: cram_decode.c:__ac_Wang_hash Unexecuted instantiation: cram_encode.c:__ac_Wang_hash Unexecuted instantiation: cram_index.c:__ac_Wang_hash Unexecuted instantiation: cram_io.c:__ac_Wang_hash Unexecuted instantiation: cram_stats.c:__ac_Wang_hash Unexecuted instantiation: hfile_libcurl.c:__ac_Wang_hash Unexecuted instantiation: hfile_s3_write.c:__ac_Wang_hash Unexecuted instantiation: bgzf.c:__ac_Wang_hash Unexecuted instantiation: faidx.c:__ac_Wang_hash Unexecuted instantiation: tbx.c:__ac_Wang_hash Unexecuted instantiation: cram_codecs.c:__ac_Wang_hash |
450 | | #define kh_int_hash_func2(k) __ac_Wang_hash((khint_t)key) |
451 | | |
452 | | /* --- END OF HASH FUNCTIONS --- */ |
453 | | |
454 | | /* Other convenient macros... */ |
455 | | |
456 | | /*! |
457 | | @abstract Type of the hash table. |
458 | | @param name Name of the hash table [symbol] |
459 | | */ |
460 | 2.73k | #define khash_t(name) kh_##name##_t |
461 | | |
462 | | /*! @function |
463 | | @abstract Initiate a hash table. |
464 | | @param name Name of the hash table [symbol] |
465 | | @return Pointer to the hash table [khash_t(name)*] |
466 | | */ |
467 | 9.14k | #define kh_init(name) kh_init_##name() |
468 | | |
469 | | /*! @function |
470 | | @abstract Destroy a hash table. |
471 | | @param name Name of the hash table [symbol] |
472 | | @param h Pointer to the hash table [khash_t(name)*] |
473 | | */ |
474 | 11.1k | #define kh_destroy(name, h) kh_destroy_##name(h) |
475 | | |
476 | | /*! @function |
477 | | @abstract Reset a hash table without deallocating memory. |
478 | | @param name Name of the hash table [symbol] |
479 | | @param h Pointer to the hash table [khash_t(name)*] |
480 | | */ |
481 | | #define kh_clear(name, h) kh_clear_##name(h) |
482 | | |
483 | | /*! @function |
484 | | @abstract Resize a hash table. |
485 | | @param name Name of the hash table [symbol] |
486 | | @param h Pointer to the hash table [khash_t(name)*] |
487 | | @param s New size [khint_t] |
488 | | */ |
489 | | #define kh_resize(name, h, s) kh_resize_##name(h, s) |
490 | | |
491 | | /*! @function |
492 | | @abstract Insert a key to the hash table. |
493 | | @param name Name of the hash table [symbol] |
494 | | @param h Pointer to the hash table [khash_t(name)*] |
495 | | @param k Key [type of keys] |
496 | | @param r Extra return code: -1 if the operation failed; |
497 | | 0 if the key is present in the hash table; |
498 | | 1 if the bucket is empty (never used); 2 if the element in |
499 | | the bucket has been deleted [int*] |
500 | | @return Iterator to the inserted element [khint_t] |
501 | | */ |
502 | 5.47M | #define kh_put(name, h, k, r) kh_put_##name(h, k, r) |
503 | | |
504 | | /*! @function |
505 | | @abstract Retrieve a key from the hash table. |
506 | | @param name Name of the hash table [symbol] |
507 | | @param h Pointer to the hash table [khash_t(name)*] |
508 | | @param k Key [type of keys] |
509 | | @return Iterator to the found element, or kh_end(h) if the element is absent [khint_t] |
510 | | */ |
511 | 3.46M | #define kh_get(name, h, k) kh_get_##name(h, k) |
512 | | |
513 | | /*! @function |
514 | | @abstract Remove a key from the hash table. |
515 | | @param name Name of the hash table [symbol] |
516 | | @param h Pointer to the hash table [khash_t(name)*] |
517 | | @param k Iterator to the element to be deleted [khint_t] |
518 | | */ |
519 | 1.85k | #define kh_del(name, h, k) kh_del_##name(h, k) |
520 | | |
521 | | /*! @function |
522 | | @abstract Test whether a bucket contains data. |
523 | | @param h Pointer to the hash table [khash_t(name)*] |
524 | | @param x Iterator to the bucket [khint_t] |
525 | | @return 1 if containing data; 0 otherwise [int] |
526 | | */ |
527 | 1.75M | #define kh_exist(h, x) (!__ac_iseither((h)->flags, (x))) |
528 | | |
529 | | /*! @function |
530 | | @abstract Get key given an iterator |
531 | | @param h Pointer to the hash table [khash_t(name)*] |
532 | | @param x Iterator to the bucket [khint_t] |
533 | | @return Key [type of keys] |
534 | | */ |
535 | 932k | #define kh_key(h, x) ((h)->keys[x]) |
536 | | |
537 | | /*! @function |
538 | | @abstract Get value given an iterator |
539 | | @param h Pointer to the hash table [khash_t(name)*] |
540 | | @param x Iterator to the bucket [khint_t] |
541 | | @return Value [type of values] |
542 | | @discussion For hash sets, calling this results in segfault. |
543 | | */ |
544 | 14.4M | #define kh_val(h, x) ((h)->vals[x]) |
545 | | |
546 | | /*! @function |
547 | | @abstract Alias of kh_val() |
548 | | */ |
549 | 1.83k | #define kh_value(h, x) ((h)->vals[x]) |
550 | | |
551 | | /*! @function |
552 | | @abstract Get the start iterator |
553 | | @param h Pointer to the hash table [khash_t(name)*] |
554 | | @return The start iterator [khint_t] |
555 | | */ |
556 | 37.3k | #define kh_begin(h) (khint_t)(0) |
557 | | |
558 | | /*! @function |
559 | | @abstract Get the end iterator |
560 | | @param h Pointer to the hash table [khash_t(name)*] |
561 | | @return The end iterator [khint_t] |
562 | | */ |
563 | 6.68M | #define kh_end(h) ((h)->n_buckets) |
564 | | |
565 | | /*! @function |
566 | | @abstract Get the number of elements in the hash table |
567 | | @param h Pointer to the hash table [khash_t(name)*] |
568 | | @return Number of elements in the hash table [khint_t] |
569 | | */ |
570 | 38.0k | #define kh_size(h) ((h)->size) |
571 | | |
572 | | /*! @function |
573 | | @abstract Get the number of buckets in the hash table |
574 | | @param h Pointer to the hash table [khash_t(name)*] |
575 | | @return Number of buckets in the hash table [khint_t] |
576 | | */ |
577 | | #define kh_n_buckets(h) ((h)->n_buckets) |
578 | | |
579 | | /*! @function |
580 | | @abstract Iterate over the entries in the hash table |
581 | | @param h Pointer to the hash table [khash_t(name)*] |
582 | | @param kvar Variable to which key will be assigned |
583 | | @param vvar Variable to which value will be assigned |
584 | | @param code Block of code to execute |
585 | | */ |
586 | | #define kh_foreach(h, kvar, vvar, code) { khint_t __i; \ |
587 | | for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \ |
588 | | if (!kh_exist(h,__i)) continue; \ |
589 | | (kvar) = kh_key(h,__i); \ |
590 | | (vvar) = kh_val(h,__i); \ |
591 | | code; \ |
592 | | } } |
593 | | |
594 | | /*! @function |
595 | | @abstract Iterate over the values in the hash table |
596 | | @param h Pointer to the hash table [khash_t(name)*] |
597 | | @param vvar Variable to which value will be assigned |
598 | | @param code Block of code to execute |
599 | | */ |
600 | | #define kh_foreach_value(h, vvar, code) { khint_t __i; \ |
601 | | for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \ |
602 | | if (!kh_exist(h,__i)) continue; \ |
603 | | (vvar) = kh_val(h,__i); \ |
604 | | code; \ |
605 | | } } |
606 | | |
607 | | /* More convenient interfaces */ |
608 | | |
609 | | /*! @function |
610 | | @abstract Instantiate a hash set containing integer keys |
611 | | @param name Name of the hash table [symbol] |
612 | | */ |
613 | | #define KHASH_SET_INIT_INT(name) \ |
614 | 0 | KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal) |
615 | | |
616 | | /*! @function |
617 | | @abstract Instantiate a hash map containing integer keys |
618 | | @param name Name of the hash table [symbol] |
619 | | @param khval_t Type of values [type] |
620 | | */ |
621 | | #define KHASH_MAP_INIT_INT(name, khval_t) \ |
622 | 2.76M | KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal) |
623 | | |
624 | | /*! @function |
625 | | @abstract Instantiate a hash set containing 64-bit integer keys |
626 | | @param name Name of the hash table [symbol] |
627 | | */ |
628 | | #define KHASH_SET_INIT_INT64(name) \ |
629 | | KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal) |
630 | | |
631 | | /*! @function |
632 | | @abstract Instantiate a hash map containing 64-bit integer keys |
633 | | @param name Name of the hash table [symbol] |
634 | | @param khval_t Type of values [type] |
635 | | */ |
636 | | #define KHASH_MAP_INIT_INT64(name, khval_t) \ |
637 | 0 | KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal) |
638 | | |
639 | | typedef const char *kh_cstr_t; |
640 | | /*! @function |
641 | | @abstract Instantiate a hash set containing const char* keys |
642 | | @param name Name of the hash table [symbol] |
643 | | */ |
644 | | #define KHASH_SET_INIT_STR(name) \ |
645 | 0 | KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal) |
646 | | |
647 | | /*! @function |
648 | | @abstract Instantiate a hash map containing const char* keys |
649 | | @param name Name of the hash table [symbol] |
650 | | @param khval_t Type of values [type] |
651 | | */ |
652 | | #define KHASH_MAP_INIT_STR(name, khval_t) \ |
653 | 6.50M | KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal) |
654 | | |
655 | | /*! @function |
656 | | @abstract Instantiate a hash set containing kstring_t keys |
657 | | @param name Name of the hash table [symbol] |
658 | | */ |
659 | | #define KHASH_SET_INIT_KSTR(name) \ |
660 | | KHASH_INIT(name, kstring_t, char, 0, kh_kstr_hash_func, kh_kstr_hash_equal) |
661 | | |
662 | | /*! @function |
663 | | @abstract Instantiate a hash map containing kstring_t keys |
664 | | @param name Name of the hash table [symbol] |
665 | | @param khval_t Type of values [type] |
666 | | */ |
667 | | #define KHASH_MAP_INIT_KSTR(name, khval_t) \ |
668 | | KHASH_INIT(name, kstring_t, khval_t, 1, kh_kstr_hash_func, kh_kstr_hash_equal) |
669 | | |
670 | | #endif /* __AC_KHASH_H */ |