1 /* Jitter: word set data structure. 2 3 Copyright (C) 2020 Luca Saiu 4 Written by Luca Saiu 5 6 This file is part of Jitter. 7 8 Jitter is free software: you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation, either version 3 of the License, or 11 (at your option) any later version. 12 13 Jitter is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with Jitter. If not, see <http://www.gnu.org/licenses/>. */ 20 21 22 #ifndef JITTER_WORD_SET_H_ 23 #define JITTER_WORD_SET_H_ 24 25 #include <config.h> // FIXME: I almost certainly do not want this, but now I want to be able to use Gnulib as well, for my tests. 26 27 #include <stdbool.h> 28 #include <stdlib.h> 29 30 #include <jitter/jitter.h> 31 #include <jitter/jitter-bitwise.h> 32 33 34 35 36 /* Introduction. 37 * ************************************************************************** */ 38 39 /* This is an efficient implementation of a set data structure using words as 40 keys, based on open-address hashing and mostly designed for one specialised 41 purpose: holding the remembered set in a generational garbage collector, 42 where keys are tagged objects. 43 In that application the critical operation is add-unique. 44 (For a more general but heavyweight alternative please see 45 jitter/jitter-hash.h ; that implementation, differently from this one, 46 includes sophisticated hash functions achieving a good "randomness".) 47 48 The keys are non-NULL non-1 unsigned words (those two values are reserved), 49 which may be tagged. 50 51 Keys have no associated data: this data structure implements a set or a 52 multiset, not a map. 53 54 This structure features very efficient access, with an intentionally simple 55 and "bad" first hash function. 56 The table is automatically resized, always to a power of two, when the fill 57 factor reaches a fixed threshold. Collisions are handled by double hashing. 58 Key removal is supported by marking removed elements as deleted, without 59 reusing space. The table access routines have been designed never to 60 require multiplication, division, remainder. 61 62 By convention both hash functions return an *offset* in bytes instead of an 63 index. (In a previous version using untagged aligned pointers as keys this 64 choice saved one shift operation or made the addressing mode simpler; 65 unfortunately the garbage collector remembered set now requires tagged 66 objects as keys rather than object fields, in order to support pointers from 67 out-of-heap objects.) 68 69 The offset which is the result of either hash function needs to be masked to 70 make it wrap around; the mask is stored in the data structure, updated when 71 the structure is resized. 72 73 74 Thanks to Bruno Haible for suggesting the use of double hashing in the first 75 place, after hearing of my initial more naïve version relying on linear 76 probing. Bruno also cited Knuth's analysis and suggested the idea of h2 as 77 defined below. About h2 I do not claim to have followed his suggestions 78 exactly, and any remaining oversights are mine. */ 79 80 81 82 83 /* Configuration parameters. 84 * ************************************************************************** */ 85 86 /* The initial allocated size of an empty table, in elements. 87 This must be an even power of two. */ 88 #define JITTER_WORD_SET_INITIAL_ELEMENT_NO 8//(1 << 10)//2//(1 << 16)//64 // 64 89 90 /* This is the reciprocal of the maximum table fill ratio a. Assuming uniformity 91 (which is not a given in practice, particularly due to the distribution of 92 object updates with respect to tags -- this should be taken as an optimistic 93 estimate) an upper bound on the expected number of probes in a successful 94 search is 95 1 / a * ln (1 / (1 - a)) 96 . The analysis can be found in Knuth and in Cormen-Leiserson-Rivest-Stein. 97 Apart from the question of the optimal choice of a value this is allowed 98 to be any number greater than one, even floating-point. This value is only 99 used for computing the used-element limit (an integer) when initialising and 100 resizing a table, so the efficiency of computations using it is not really 101 critical. 102 Since the table is built associatively but also scanned linearly it is 103 important to strike a balance between the optimisation of the number of 104 probes and the density of valid elements. 105 Here is a convenient way to sample possible values from Emacs: 106 (dolist (a (sort (list (/ 16.0) (/ 8.0) (/ 4.0) (/ 2.0) 107 (/ 10.0) (/ 5.0) (/ 3.0) 108 .4 .6 (/ 2 3.0) (/ 3 4.0) (/ 4 5.0)) 109 '<=)) 110 (let* ((a (float a)) 111 (reciprocal-a (/ a)) 112 (probe-no (* (/ a) (log (/ (- 1 a)))))) 113 (insert (format " a:%7.3f reciprocal-a:%7.3f probe-no:%7.3f\n" 114 a reciprocal-a probe-no)))) 115 a: 0.062 reciprocal-a: 16.000 probe-no: 1.033 116 a: 0.100 reciprocal-a: 10.000 probe-no: 1.054 117 a: 0.125 reciprocal-a: 8.000 probe-no: 1.068 118 a: 0.200 reciprocal-a: 5.000 probe-no: 1.116 119 a: 0.250 reciprocal-a: 4.000 probe-no: 1.151 120 a: 0.333 reciprocal-a: 3.000 probe-no: 1.216 121 a: 0.400 reciprocal-a: 2.500 probe-no: 1.277 122 a: 0.500 reciprocal-a: 2.000 probe-no: 1.386 123 a: 0.600 reciprocal-a: 1.667 probe-no: 1.527 124 a: 0.667 reciprocal-a: 1.500 probe-no: 1.648 125 a: 0.750 reciprocal-a: 1.333 probe-no: 1.848 126 a: 0.800 reciprocal-a: 1.250 probe-no: 2.012 */ 127 #define JITTER_WORD_SET_RECIPROCAL_FILL_RATIO \ 128 3 129 130 131 132 133 /* Core definitions. 134 * ************************************************************************** */ 135 136 /* The special element configuration reserved for unused elements. */ 137 #define JITTER_WORD_SET_UNUSED ((jitter_uint) NULL) 138 139 /* The special element configuration reserved for elements marked as deleted. */ 140 #define JITTER_WORD_SET_DELETED ((jitter_uint) 1) 141 142 143 144 145 /* Data structure. 146 * ************************************************************************** */ 147 148 /* The keys are values of type jitter_uint . */ 149 150 /* The table data structure. */ 151 struct jitter_word_set 152 { 153 /* How many elements fit in the currently allocated memory. */ 154 size_t allocated_element_no; 155 156 /* How many used elements there can be in this set before it is automatically 157 resized. Resizing happens *after* every insertion of a new element. */ 158 size_t used_element_limit; 159 160 /* How many elements are used. Deleted elements are considered in use, as 161 they take space in the structure; deleted elements are not explicitly 162 counted, and "deleting" an existing entry does not change the number of 163 used elements. */ 164 size_t used_element_no; 165 166 /* A bit mask to be combined by a bitwise and operation with an offset in 167 bytes (this is not a mistake: *in bytes*) from buffer to produce an offset, 168 again in bytes, respecting the valid range. Of course the size is always a 169 power of two. The mask is automatically computed at the time of 170 initialisation and resizing. */ 171 jitter_uint mask; 172 173 /* A pointer to a buffer of elements, dynamically allocated. Eech element 174 may be: JITTER_WORD_SET_UNUSED , JITTER_WORD_SET_DELETED , or a 175 valid pointer. */ 176 jitter_uint *buffer; 177 }; 178 179 180 181 182 /* Hash functions. 183 * ************************************************************************** */ 184 185 /* Hash functions here are only functions in the mathematical sense; they are 186 implemented as macros to avoid function call overhead in this 187 performance-critical code. These hash functions return an *offset* in bytes, 188 not an index; see the comment in the introduction. */ 189 190 /* The word set uses double hashing: the first hash h1, given a key k, 191 returns an offset into the buffer; in case of collision the probe distance 192 (again as an offset) from the first offset is the result of the second hash 193 h2 on the key. Each probe after the first is at distance h2 (k) modulo the 194 table size M from the previous one. 195 The i-th probe will be therefore at offset 196 (h1 (k) + i h2 (k)) mod M 197 . Only if the first probe fails there is need to compute h2 (k), and in 198 that case it can be computed just once, even if more probes are needed after 199 the second. The modulo needs to be computed at each probe, but it should be 200 efficient requring as it does only one bitwise and operation. In critical 201 code, where multiple accesses occur in a loop, the mask will be loaded once 202 from memory and then kept in a register. */ 203 204 /* The first hash function, named h1 in the comment above. */ 205 #define JITTER_WORD_SET_HASH1_CHAR_STAR_OFFSET(key) \ 206 /* Make the low bits zero so that the offset, starting \ 207 from an aligned base, gives an aligned pointer. */ \ 208 (((jitter_uint) (key)) << JITTER_LG_BYTES_PER_WORD) 209 210 /* This is a definition of h2. 211 In order to guarantee coverage of the entire buffer, and considering that the 212 buffer size is a power of two, this function must return a result which is 213 odd in terms of elements -- in terms of offsets it need to be an odd multiple 214 of the (always even) word size. 215 In general, in terms of indices, h2 must yield a result which is coprime with 216 M. M being a power of two here, any odd number will be correct. */ 217 #define JITTER_WORD_SET_HASH2_CHAR_STAR_OFFSET(key) \ 218 ((((jitter_uint) (key)) \ 219 & JITTER_POINTER_NON_MISALIGNMENT_BITS_MASK) \ 220 | (jitter_uint) 1 << JITTER_LG_BYTES_PER_WORD) 221 222 223 224 225 /* Initialisation and finalisation. 226 * ************************************************************************** */ 227 228 /* Initialise the pointed structure, which must not have been previously 229 initalised, or must have been first initalised and then finalised. */ 230 void 231 jitter_word_set_initialize (struct jitter_word_set *ps) 232 __attribute__ ((nonnull (1))); 233 234 /* Finalise the pointed structure, freeing up its memory resources. */ 235 void 236 jitter_word_set_finalize (struct jitter_word_set *ps) 237 __attribute__ ((nonnull (1))); 238 239 240 241 242 /* Emptying and rebuilding. 243 * ************************************************************************** */ 244 245 /* Remove every element from the pointed word set, making future insertions 246 faster. The memory buffer must have been correctly initialised. This does 247 not resize the buffer. */ 248 void 249 jitter_word_set_clear (struct jitter_word_set *ps) 250 __attribute__ ((nonnull (1))); 251 252 /* Remove every element from the pointed word set and reallocate it so as to 253 take the minimum space in memory. The data structure must have been 254 correctly initialised. */ 255 void 256 jitter_word_set_clear_and_minimize (struct jitter_word_set *ps) 257 __attribute__ ((nonnull (1))); 258 259 /* Behave like jitter_word_set_clear or like 260 jitter_word_set_clear_and_minimize, according to the value of minimize. */ 261 void 262 jitter_word_set_clear_and_possibly_minimize (struct jitter_word_set *ps, 263 bool minimize) 264 __attribute__ ((nonnull (1))); 265 266 /* Rebuild the pointed word set, keeping the same valid elements. This makes 267 future accesses to the structure more efficient by eliminating the 268 possibility of collisions with deleted entries, but of course is an expensive 269 operation. */ 270 void 271 jitter_word_set_rebuild (struct jitter_word_set *ps) 272 __attribute__ ((nonnull (1))); 273 274 /* Like jitter_word_set_rebuild, but also make the set become as small as 275 possible. Compared to jitter_word_set_rebuild this will save memory but 276 make future insertions slower. */ 277 void 278 jitter_word_set_rebuild_and_minimize (struct jitter_word_set *ps) 279 __attribute__ ((nonnull (1))); 280 281 /* Behave like jitter_word_set_rebuild or like 282 jitter_word_set_rebuild_and_minimize, according to the value of 283 minimize. */ 284 void 285 jitter_word_set_rebuild_and_possibly_minimize (struct jitter_word_set *ps, 286 bool minimize) 287 __attribute__ ((nonnull (1))); 288 289 290 291 292 /* Macro API. 293 * ************************************************************************** */ 294 295 /* Some of the macros here write into an l-value; unfortunately it is not 296 possible in standard C to define them as expanding to expressions, which 297 makes them slightly cumbersome to use. */ 298 299 /* Add a new copy of the element to the pointed word set. Here the "set" 300 behaves in fact as a multiset. */ 301 #define JITTER_WORD_SET_ADD_NEW(psp_expr, \ 302 p_expr) \ 303 do \ 304 { \ 305 struct jitter_word_set *_jitter_ps_an_psp = (psp_expr); \ 306 jitter_uint _jitter_ps_an_p = (p_expr); \ 307 jitter_uint *_jitter_ps_an_item; \ 308 size_t _jitter_ps_au_probeno __attribute__ ((unused)); \ 309 JITTER_WORD_SET_SEARCH (_jitter_ps_an_psp, \ 310 _jitter_ps_an_p, \ 311 true, \ 312 _jitter_ps_au_probeno, \ 313 _jitter_ps_an_item); \ 314 * _jitter_ps_an_item = _jitter_ps_an_p; \ 315 _jitter_ps_an_psp->used_element_no ++; \ 316 JITTER_WORD_SET_RESIZE_IF_NEEDED (_jitter_ps_an_psp); \ 317 } \ 318 while (false) 319 320 /* Like JITTER_WORD_SET_ADD_NEW, except that this does nothing if the key is 321 already present. */ 322 #define JITTER_WORD_SET_ADD_UNIQUE(psp_expr, \ 323 p_expr) \ 324 do \ 325 { \ 326 struct jitter_word_set *_jitter_ps_au_psp = (psp_expr); \ 327 jitter_uint _jitter_ps_au_p = (p_expr); \ 328 jitter_uint *_jitter_ps_au_item; \ 329 size_t _jitter_ps_au_probeno __attribute__ ((unused)); \ 330 JITTER_WORD_SET_SEARCH (_jitter_ps_au_psp, \ 331 _jitter_ps_au_p, \ 332 false, \ 333 _jitter_ps_au_probeno, \ 334 _jitter_ps_au_item); \ 335 if (* _jitter_ps_au_item == JITTER_WORD_SET_UNUSED) \ 336 { \ 337 * _jitter_ps_au_item = _jitter_ps_au_p; \ 338 _jitter_ps_au_psp->used_element_no ++; \ 339 JITTER_WORD_SET_RESIZE_IF_NEEDED (_jitter_ps_au_psp); \ 340 } \ 341 } \ 342 while (false) 343 344 /* Set the given result lvalue to a non-false result if the given key belongs to 345 the pointed word set. */ 346 #define JITTER_WORD_SET_SET_HAS(psp_expr, \ 347 p_expr, \ 348 res_lvalue) \ 349 do \ 350 { \ 351 struct jitter_word_set *_jitter_ps_sh_psp = (psp_expr); \ 352 jitter_uint _jitter_ps_sh_p = (p_expr); \ 353 jitter_uint *_jitter_ps_sh_item; \ 354 size_t _jitter_ps_au_probeno __attribute__ ((unused)); \ 355 JITTER_WORD_SET_SEARCH (_jitter_ps_sh_psp, \ 356 _jitter_ps_sh_p, \ 357 false, \ 358 _jitter_ps_au_probeno, \ 359 _jitter_ps_sh_item); \ 360 (res_lvalue) \ 361 = (* _jitter_ps_sh_item == _jitter_ps_sh_p); \ 362 } \ 363 while (false) 364 365 /* Remove one entry; if any more equal entries are present, all of them except 366 the first one remain. */ 367 #define JITTER_WORD_SET_REMOVE(psp_expr, \ 368 p_expr) \ 369 do \ 370 { \ 371 struct jitter_word_set *_jitter_ps_r_psp = (psp_expr); \ 372 jitter_uint _jitter_ps_r_p = (p_expr); \ 373 jitter_uint *_jitter_ps_r_item; \ 374 size_t _jitter_ps_au_probeno __attribute__ ((unused)); \ 375 JITTER_WORD_SET_SEARCH (_jitter_ps_r_psp, \ 376 _jitter_ps_r_p, \ 377 false, \ 378 _jitter_ps_au_probeno, \ 379 _jitter_ps_r_item); \ 380 if (* _jitter_ps_r_item == _jitter_ps_r_p) \ 381 * _jitter_ps_r_item = JITTER_WORD_SET_DELETED; \ 382 } \ 383 while (false) 384 385 /* Set the given l-value to the number of probes necessary to find the given 386 element, or to find that it is not present. */ 387 #define JITTER_WORD_SET_SET_PROBE_NO(ps_expr, \ 388 p_expr, \ 389 res_lvalue) \ 390 do \ 391 { \ 392 struct jitter_word_set *_jitter_ps_sh_psp = (ps_expr); \ 393 jitter_uint _jitter_ps_sh_p = (p_expr); \ 394 jitter_uint *_jitter_ps_sh_item __attribute__ ((unused)); \ 395 JITTER_WORD_SET_SEARCH (_jitter_ps_sh_psp, \ 396 _jitter_ps_sh_p, \ 397 false, \ 398 (res_lvalue), \ 399 _jitter_ps_sh_item); \ 400 } \ 401 while (false) 402 403 404 405 406 /* Debugging. 407 * ************************************************************************** */ 408 409 /* Print the pointed word set. */ 410 void 411 jitter_word_set_print (struct jitter_word_set *rsp) 412 __attribute__((nonnull (1))); 413 414 /* Print debugging statistics about the pointed word set. This is useful to 415 experiment with different tuning parameters. */ 416 void 417 jitter_word_set_print_statistics (struct jitter_word_set *rsp) 418 __attribute__((nonnull (1))); 419 420 421 422 423 /* Internal accessor macros. 424 * ************************************************************************** */ 425 426 /* Expand to an expression evaluating to non-false if the given element is a 427 "used" element: either a valid key or the "deleted" special element. */ 428 #define JITTER_WORD_SET_IS_USED(_jitter_ps_p_expr) \ 429 ((_jitter_ps_p_expr) > JITTER_WORD_SET_UNUSED) 430 431 /* Expand to an expression evaluating to non-false if the given element is an 432 "unused" element: notice that the "deleted" special element does not count 433 as unused. */ 434 #define JITTER_WORD_SET_IS_UNUSED(_jitter_ps_p_expr) \ 435 ((_jitter_ps_p_expr) == JITTER_WORD_SET_UNUSED) 436 437 /* Expand to an expression evaluating to non-false if the given element is a 438 valid non-reserved element: not unused, not deleted. */ 439 #define JITTER_WORD_SET_IS_VALID(_jitter_ps_p_expr) \ 440 ((_jitter_ps_p_expr) > JITTER_WORD_SET_DELETED) 441 442 /* Given the number of elements of a table expand to an expression evaluating to 443 its resize threshold. */ 444 #define JITTER_WORD_SET_ELEMENT_NO_TO_LIMIT(_jitter_buffer_element_no) \ 445 ((size_t) \ 446 ((_jitter_buffer_element_no) / JITTER_WORD_SET_RECIPROCAL_FILL_RATIO)) 447 448 449 450 451 /* Internal macros operating on buffers only. 452 * ************************************************************************** */ 453 454 /* Expand to an expression of type jitter_uint * evaluating to the address of 455 the given buffer at the given offset. The buffer is an array of jitter_uint 456 objects but the offset is in bytes, as computed by the hash functions 457 above. 458 This macro serves to conveniently do pointer arithmetic with an offset 459 incompatible with the pointer. */ 460 #define JITTER_WORD_SET_ACCESS_BUFFER(_jitter_ps_buffer_p_expr, \ 461 _jitter_ps_offset_expr) \ 462 ((jitter_uint *) \ 463 ((char *) (_jitter_ps_buffer_p_expr) + (_jitter_ps_offset_expr))) 464 465 /* There are two kind of match criteria: 466 If search_first_unused is: 467 - non-false: starting at h1 (key) search for the first entry which is unused 468 - false: starting at h1 (key) search for the first entry which is either 469 unused or matching p */ 470 471 /* Expand to an expression evaluating to true if the result of the evaluation 472 of the first argument "matches", as per the definition above, the result 473 of the evaluation of the second according to the criterion which is the 474 result of the evaluation of search_first_unused. 475 Use __builtin_expect to compile more efficiently in case of match. 476 This macro may evaluate some arguments zero, one or multiple times. */ 477 #define JITTER_WORD_SET_MATCHES(some_object, \ 478 key, \ 479 search_first_unused) \ 480 ((search_first_unused) \ 481 ? (__builtin_expect (JITTER_WORD_SET_IS_UNUSED (some_object), true)) \ 482 : (__builtin_expect ((some_object) == (key), true) \ 483 || __builtin_expect (JITTER_WORD_SET_IS_UNUSED (some_object), true))) 484 485 /* This is the fundamental search facility used by every access macros, working 486 on buffers. 487 The exapansion is a statement assinging to the given l-values the number of 488 required probes and the address of the found entry in the table; usually only 489 one of the two will be needed, but the compiler will easily optimise away the 490 unnecessary part of the computation. Use the given search criterion. */ 491 #define JITTER_WORD_SET_BUFFER_SEARCH(buffer_p_expr, \ 492 mask_expr, \ 493 key_expr, \ 494 search_first_unused, \ 495 probeno_lvalue, \ 496 entryp_lvalue) \ 497 do \ 498 { \ 499 /* Compute the expresisons given as arguments, once. */ \ 500 jitter_uint *_jitter_ps_bs_buffer_p = (buffer_p_expr); \ 501 jitter_uint _jitter_ps_bs_key = (key_expr); \ 502 int /* bool */ _jitter_ps_bs_search_first_unused \ 503 = (search_first_unused); \ 504 jitter_uint _jitter_ps_bs_mask = (mask_expr); \ 505 /* Compute the first hash, giving the initial offset. */ \ 506 jitter_uint _jitter_ps_bs_offset \ 507 = (JITTER_WORD_SET_HASH1_CHAR_STAR_OFFSET (_jitter_ps_bs_key) \ 508 & _jitter_ps_bs_mask); \ 509 jitter_uint * _jitter_ps_bs_some_p \ 510 = JITTER_WORD_SET_ACCESS_BUFFER (_jitter_ps_bs_buffer_p, \ 511 _jitter_ps_bs_offset); \ 512 /* This could have been written in a single loop, but I find that GCC \ 513 generates better code on some architectures if I unroll the first \ 514 iteration and give __builtin_expected hints. This is normal: most \ 515 loops iterate either zero or many times, and it is uncommon for a \ 516 loop to roll exactly once; hash table accesses follow this rare \ 517 pattern. \ 518 A do..while loop would not work well here because of the computation \ 519 of h2 on the key, which must come after the first iteration: see the \ 520 comment below. */ \ 521 jitter_int _jitter_ps_bs_probeno = 1; \ 522 if (__builtin_expect (! JITTER_WORD_SET_MATCHES \ 523 (* _jitter_ps_bs_some_p, \ 524 _jitter_ps_bs_key, \ 525 _jitter_ps_bs_search_first_unused), \ 526 false)) \ 527 { \ 528 /* The first probe failed; only now it is worth computing h2 on the \ 529 key. If I put this variable definition above GCC would not move \ 530 it down after the first probe, even on architectures whose \ 531 implementations are typically weaker at exploiting ILP. If I do \ 532 this the result appears to be good on every configuration. */ \ 533 jitter_uint _jitter_ps_bs_step \ 534 = JITTER_WORD_SET_HASH2_CHAR_STAR_OFFSET (_jitter_ps_bs_key); \ 535 while (_jitter_ps_bs_probeno ++, \ 536 (! JITTER_WORD_SET_MATCHES \ 537 (* _jitter_ps_bs_some_p, \ 538 _jitter_ps_bs_key, \ 539 _jitter_ps_bs_search_first_unused))) \ 540 { \ 541 _jitter_ps_bs_offset \ 542 = ((_jitter_ps_bs_offset + _jitter_ps_bs_step) \ 543 & _jitter_ps_bs_mask); \ 544 _jitter_ps_bs_some_p \ 545 = JITTER_WORD_SET_ACCESS_BUFFER \ 546 (_jitter_ps_bs_buffer_p, _jitter_ps_bs_offset); \ 547 } \ 548 } \ 549 /* Either the first probe succeeded and control fell here immediately, \ 550 or the loop is over. In any case _jitter_ps_bs_some_p contains the \ 551 interesting element: either what the user searched for, or an unused \ 552 slot. GCC has no problem duplicating this final basic block, which \ 553 is good. */ \ 554 (entryp_lvalue) = _jitter_ps_bs_some_p; \ 555 (probeno_lvalue) = _jitter_ps_bs_probeno; \ 556 } \ 557 while (false) 558 559 560 561 562 /* Internal macros operating on struct jitter_word_set . 563 * ************************************************************************** */ 564 565 /* Expand to a statement resizing the pointed word set if the threshold has 566 been reached. */ 567 #define JITTER_WORD_SET_RESIZE_IF_NEEDED(_jitter_ps_psp_expr) \ 568 do \ 569 { \ 570 struct jitter_word_set *_jitter_ps_rin_psp = (_jitter_ps_psp_expr); \ 571 if (__builtin_expect (_jitter_ps_rin_psp->used_element_no \ 572 >= _jitter_ps_rin_psp->used_element_limit, \ 573 false)) \ 574 jitter_word_set_double (_jitter_ps_rin_psp); \ 575 } \ 576 while (false) 577 578 /* This is an obvious extension to word sets of the fundamental macro 579 JITTER_WORD_SET_BUFFER_SEARCH which works on buffers. Values for the 580 arguments to JITTER_WORD_SET_BUFFER_SEARCH not given here are found 581 as fields within the pointed word buffer. */ 582 #define JITTER_WORD_SET_SEARCH(psp_expr, \ 583 key_expr, \ 584 search_first_unused, \ 585 probe_no_lvalue, \ 586 res_lvalue) \ 587 do \ 588 { \ 589 struct jitter_word_set *_jitter_ps_s_psp = (psp_expr); \ 590 jitter_uint _jitter_ps_s_key = (key_expr); \ 591 int /*bool*/ _jitter_ps_s_search_first_unused \ 592 = (search_first_unused); \ 593 jitter_uint _jitter_ps_s_mask = _jitter_ps_s_psp->mask; \ 594 JITTER_WORD_SET_BUFFER_SEARCH (_jitter_ps_s_psp->buffer, \ 595 _jitter_ps_s_mask, \ 596 _jitter_ps_s_key, \ 597 _jitter_ps_s_search_first_unused, \ 598 (probe_no_lvalue), \ 599 (res_lvalue)); \ 600 } \ 601 while (false) 602 603 604 605 606 /* Internal functions. 607 * ************************************************************************** */ 608 609 /* Double the allocated size of the pointed word set. Only used 610 internally. */ 611 void 612 jitter_word_set_double (struct jitter_word_set *ps) 613 __attribute__ ((cold, nonnull (1))); 614 615 616 #endif // #ifndef JITTER_WORD_SET_H_ 617