Line data Source code
1 : #include "fd_votes.h"
2 :
3 : /* fd_votes tracks blks, vtrs, and slots.
4 :
5 : blk_pool / blk_map (capacity blk_max = slot_max * vtr_max):
6 :
7 : Each blk tracks the aggregate stake voted for a particular block_id.
8 :
9 : vtr_pool / vtr_map / vtr_dlist / vtr_set (capacity vtr_max):
10 :
11 : Each vtr corresponds to a vote account address and has a bit position
12 : in the slot vtrs bitset. vtr entries are explicitly managed by
13 : fd_votes_update_voters when the epoch stake set changes.
14 : dlist of all active voters, used for mark-sweep in
15 : fd_votes_update_voters.
16 :
17 : slot_pool / slot_map / blk_dlist (capacity slot_max):
18 :
19 : Each slot corresponds to a slot and tracks which voters have voted
20 : for that slot and all the blks that are associated for that slot.
21 : Each slot also tracks all the blks associated with that slot in
22 : blk_dlist.
23 :
24 : slot_map vtr_map
25 : map[0] +--------------------+ map[0] +--------------------+
26 : | (slot_t) { | | (vtr_t) { |
27 : | .slot = 100, | | .vote_acc = X, |
28 : | .vtrs = ..., | | .bit = 0, |
29 : | .blk_dlist = ... | | } |
30 : | } | | |
31 : map[1] +--------------------+ map[1] +--------------------+
32 : | (slot_t) { | | (vtr_t) { |
33 : | .slot = 101, | | .vote_acc = Y, |
34 : | .vtrs = ..., | | .bit = 1, |
35 : | .blk_dlist = + | | } |
36 : | } | | | |
37 : +----------------|---+ +--------------------+
38 : |
39 : V
40 : blk_dlist
41 : +------------------+------------------+
42 : | (blk_t) { | (blk_t) { |
43 : | .block_id = A, | .block_id = B, |
44 : | .stake = 10, | .stake = 51, |
45 : | ... | ... |
46 : | } | } |
47 : +------------------+------------------+
48 :
49 : When a vote is counted, the voter's bit is set in the slot's vtrs
50 : bitset. If the voter already voted for this slot (bit already set),
51 : the vote is ignored. The vote's stake is added to both the slot's
52 : aggregate stake and the blk's stake. blk entries are also in the
53 : global blk_map for O(1) lookup by block_id. */
54 :
55 : typedef fd_votes_blk_t blk_t;
56 :
57 : #define POOL_NAME blk_pool
58 24 : #define POOL_T blk_t
59 : #include "../../util/tmpl/fd_pool.c"
60 :
61 : #define MAP_NAME blk_map
62 102 : #define MAP_ELE_T blk_t
63 : #define MAP_KEY_T fd_votes_blk_key_t
64 141 : #define MAP_KEY key
65 522 : #define MAP_PREV map.prev
66 5088 : #define MAP_NEXT map.next
67 5022 : #define MAP_KEY_EQ(k0,k1) ((k0)->slot==(k1)->slot && !memcmp((k0)->block_id.key,(k1)->block_id.key,32UL))
68 837 : #define MAP_KEY_HASH(key,seed) ((ulong)((key)->block_id.ul[1]^(key)->slot^(seed)))
69 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
70 : #include "../../util/tmpl/fd_map_chain.c"
71 :
72 : #define DLIST_NAME blk_dlist
73 : #define DLIST_ELE_T blk_t
74 135 : #define DLIST_PREV dlist.prev
75 237 : #define DLIST_NEXT dlist.next
76 : #include "../../util/tmpl/fd_dlist.c"
77 :
78 : struct vtr {
79 : fd_pubkey_t vote_acc; /* vtr_map key */
80 : ulong next; /* pool next */
81 : struct {
82 : ulong prev;
83 : ulong next;
84 : } map;
85 : struct {
86 : ulong prev;
87 : ulong next;
88 : } dlist;
89 : ulong bit;
90 : };
91 : typedef struct vtr vtr_t;
92 :
93 : #define POOL_NAME vtr_pool
94 24 : #define POOL_T vtr_t
95 : #include "../../util/tmpl/fd_pool.c"
96 :
97 : #define MAP_NAME vtr_map
98 9 : #define MAP_ELE_T vtr_t
99 : #define MAP_KEY_T fd_pubkey_t
100 261 : #define MAP_KEY vote_acc
101 1491 : #define MAP_PREV map.prev
102 16968 : #define MAP_NEXT map.next
103 16221 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0)->key,(k1)->key,sizeof(fd_pubkey_t)))
104 675 : #define MAP_KEY_HASH(key,seed) ((ulong)((key)->ul[1]^(seed)))
105 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
106 : #include "../../util/tmpl/fd_map_chain.c"
107 :
108 : #define DLIST_NAME vtr_dlist
109 : #define DLIST_ELE_T vtr_t
110 279 : #define DLIST_PREV dlist.prev
111 312 : #define DLIST_NEXT dlist.next
112 : #include "../../util/tmpl/fd_dlist.c"
113 :
114 : struct slot {
115 : ulong slot; /* map key, vote slot */
116 : ulong next; /* pool next */
117 : struct {
118 : ulong prev;
119 : ulong next;
120 : } map;
121 : struct {
122 : ulong prev;
123 : ulong next;
124 : } dlist;
125 : blk_dlist_t * blks;
126 : ulong blk_cnt; /* number of distinct block ids for this slot */
127 : slot_vtrs_t * vtrs; /* who has voted for this slot, curr epoch */
128 : };
129 : typedef struct slot slot_t;
130 :
131 : #define POOL_NAME slot_pool
132 36 : #define POOL_T slot_t
133 : #include "../../util/tmpl/fd_pool.c"
134 :
135 : #define MAP_NAME slot_map
136 6 : #define MAP_ELE_T slot_t
137 : #define MAP_KEY_T ulong
138 42 : #define MAP_KEY slot
139 45 : #define MAP_PREV map.prev
140 51 : #define MAP_NEXT map.next
141 336 : #define MAP_KEY_EQ(k0,k1) (*(k0)==*(k1))
142 411 : #define MAP_KEY_HASH(key,seed) ((*key)^(seed))
143 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
144 : #include "../../util/tmpl/fd_map_chain.c"
145 :
146 : #define DLIST_NAME slot_dlist
147 : #define DLIST_ELE_T slot_t
148 42 : #define DLIST_PREV dlist.prev
149 57 : #define DLIST_NEXT dlist.next
150 : #include "../../util/tmpl/fd_dlist.c"
151 :
152 : struct __attribute__((aligned(128UL))) fd_votes {
153 : ulong root;
154 : ulong slot_max;
155 : ulong vtr_max;
156 : ulong blk_max;
157 : slot_t * slot_pool;
158 : slot_map_t * slot_map;
159 : slot_dlist_t * slot_dlist;
160 : blk_t * blk_pool;
161 : blk_map_t * blk_map;
162 : vtr_t * vtr_pool;
163 : vtr_map_t * vtr_map;
164 : vtr_dlist_t * vtr_dlist;
165 : slot_vtrs_t * vtr_set;
166 : };
167 :
168 : ulong
169 108 : fd_votes_align( void ) {
170 108 : return 128UL;
171 108 : }
172 :
173 : ulong
174 : fd_votes_footprint( ulong slot_max,
175 24 : ulong vtr_max ) {
176 :
177 24 : slot_max = fd_ulong_pow2_up( slot_max );
178 24 : vtr_max = fd_ulong_pow2_up( vtr_max );
179 24 : ulong blk_max = fd_ulong_pow2_up( slot_max * vtr_max );
180 :
181 24 : ulong l = FD_LAYOUT_INIT;
182 24 : l = FD_LAYOUT_APPEND( l, 128UL, sizeof(fd_votes_t) );
183 24 : l = FD_LAYOUT_APPEND( l, slot_pool_align(), slot_pool_footprint( slot_max ) );
184 24 : l = FD_LAYOUT_APPEND( l, slot_map_align(), slot_map_footprint( slot_map_chain_cnt_est( slot_max ) ) );
185 24 : l = FD_LAYOUT_APPEND( l, slot_dlist_align(), slot_dlist_footprint() );
186 24 : l = FD_LAYOUT_APPEND( l, blk_pool_align(), blk_pool_footprint( blk_max ) );
187 24 : l = FD_LAYOUT_APPEND( l, blk_map_align(), blk_map_footprint( blk_map_chain_cnt_est( blk_max ) ) );
188 24 : l = FD_LAYOUT_APPEND( l, vtr_pool_align(), vtr_pool_footprint( vtr_max ) );
189 24 : l = FD_LAYOUT_APPEND( l, vtr_map_align(), vtr_map_footprint( vtr_map_chain_cnt_est( vtr_max ) ) );
190 24 : l = FD_LAYOUT_APPEND( l, vtr_dlist_align(), vtr_dlist_footprint() );
191 24 : l = FD_LAYOUT_APPEND( l, slot_vtrs_align(), slot_vtrs_footprint( vtr_max ) );
192 216 : for( ulong i = 0UL; i < slot_max; i++ ) {
193 192 : l = FD_LAYOUT_APPEND( l, slot_vtrs_align(), slot_vtrs_footprint( vtr_max ) );
194 192 : l = FD_LAYOUT_APPEND( l, blk_dlist_align(), blk_dlist_footprint() );
195 192 : }
196 24 : return FD_LAYOUT_FINI( l, fd_votes_align() );
197 24 : }
198 :
199 : void *
200 : fd_votes_new( void * shmem,
201 : ulong slot_max,
202 : ulong vtr_max,
203 12 : ulong seed ) {
204 :
205 12 : if( FD_UNLIKELY( !shmem ) ) {
206 0 : FD_LOG_WARNING(( "NULL mem" ));
207 0 : return NULL;
208 0 : }
209 :
210 12 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_votes_align() ) ) ) {
211 0 : FD_LOG_WARNING(( "misaligned mem" ));
212 0 : return NULL;
213 0 : }
214 :
215 12 : ulong footprint = fd_votes_footprint( slot_max, vtr_max );
216 12 : if( FD_UNLIKELY( !footprint ) ) {
217 0 : FD_LOG_WARNING(( "bad slot_max (%lu) or vtr_max (%lu)", slot_max, vtr_max ));
218 0 : return NULL;
219 0 : }
220 :
221 12 : fd_memset( shmem, 0, footprint );
222 :
223 12 : slot_max = fd_ulong_pow2_up( slot_max );
224 12 : vtr_max = fd_ulong_pow2_up( vtr_max );
225 12 : ulong blk_max = fd_ulong_pow2_up( slot_max * vtr_max );
226 :
227 12 : FD_SCRATCH_ALLOC_INIT( l, shmem );
228 12 : fd_votes_t * votes = FD_SCRATCH_ALLOC_APPEND( l, 128UL, sizeof(fd_votes_t) );
229 12 : void * slot_pool = FD_SCRATCH_ALLOC_APPEND( l, slot_pool_align(), slot_pool_footprint( slot_max ) );
230 12 : void * slot_map = FD_SCRATCH_ALLOC_APPEND( l, slot_map_align(), slot_map_footprint( slot_map_chain_cnt_est( slot_max ) ) );
231 12 : void * slot_dlist = FD_SCRATCH_ALLOC_APPEND( l, slot_dlist_align(), slot_dlist_footprint() );
232 12 : void * blk_pool = FD_SCRATCH_ALLOC_APPEND( l, blk_pool_align(), blk_pool_footprint( blk_max ) );
233 12 : void * blk_map = FD_SCRATCH_ALLOC_APPEND( l, blk_map_align(), blk_map_footprint( blk_map_chain_cnt_est( blk_max ) ) );
234 12 : void * vtr_pool = FD_SCRATCH_ALLOC_APPEND( l, vtr_pool_align(), vtr_pool_footprint( vtr_max ) );
235 12 : void * vtr_map = FD_SCRATCH_ALLOC_APPEND( l, vtr_map_align(), vtr_map_footprint( vtr_map_chain_cnt_est( vtr_max ) ) );
236 12 : void * vtr_dlist = FD_SCRATCH_ALLOC_APPEND( l, vtr_dlist_align(), vtr_dlist_footprint() );
237 12 : void * vtr_set = FD_SCRATCH_ALLOC_APPEND( l, slot_vtrs_align(), slot_vtrs_footprint( vtr_max ) );
238 :
239 12 : votes->root = ULONG_MAX;
240 12 : votes->slot_max = slot_max;
241 12 : votes->vtr_max = vtr_max;
242 12 : votes->blk_max = blk_max;
243 12 : votes->slot_pool = slot_pool_new ( slot_pool, slot_max );
244 12 : votes->slot_map = slot_map_new ( slot_map, slot_map_chain_cnt_est( slot_max ), seed );
245 12 : votes->slot_dlist = slot_dlist_new( slot_dlist );
246 12 : votes->blk_pool = blk_pool_new ( blk_pool, blk_max );
247 12 : votes->blk_map = blk_map_new ( blk_map, blk_map_chain_cnt_est( blk_max ), seed );
248 12 : votes->vtr_pool = vtr_pool_new ( vtr_pool, vtr_max );
249 12 : votes->vtr_map = vtr_map_new ( vtr_map, vtr_map_chain_cnt_est( vtr_max ), seed );
250 12 : votes->vtr_dlist = vtr_dlist_new ( vtr_dlist );
251 12 : votes->vtr_set = slot_vtrs_new ( vtr_set, vtr_max );
252 :
253 : /* Pre-allocate a vtrs set and blk_dlist per slot pool position. */
254 :
255 12 : slot_t * slot_join = slot_pool_join( votes->slot_pool );
256 108 : for( ulong i = 0UL; i < slot_max; i++ ) {
257 96 : void * vtrs = FD_SCRATCH_ALLOC_APPEND( l, slot_vtrs_align(), slot_vtrs_footprint( vtr_max ) );
258 96 : void * blk_dlist = FD_SCRATCH_ALLOC_APPEND( l, blk_dlist_align(), blk_dlist_footprint() );
259 96 : slot_join[i].vtrs = slot_vtrs_new( vtrs, vtr_max );
260 96 : slot_join[i].blks = blk_dlist_new( blk_dlist );
261 96 : slot_join[i].blk_cnt = 0;
262 96 : }
263 12 : slot_pool_leave( slot_join );
264 :
265 12 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_votes_align() ) == (ulong)shmem + footprint );
266 12 : return shmem;
267 12 : }
268 :
269 : fd_votes_t *
270 12 : fd_votes_join( void * shvotes ) {
271 12 : fd_votes_t * votes = (fd_votes_t *)shvotes;
272 :
273 12 : if( FD_UNLIKELY( !votes ) ) {
274 0 : FD_LOG_WARNING(( "NULL votes" ));
275 0 : return NULL;
276 0 : }
277 :
278 12 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)votes, fd_votes_align() ) ) ) {
279 0 : FD_LOG_WARNING(( "misaligned votes" ));
280 0 : return NULL;
281 0 : }
282 :
283 12 : votes->slot_pool = slot_pool_join ( votes->slot_pool );
284 12 : votes->slot_map = slot_map_join ( votes->slot_map );
285 12 : votes->slot_dlist = slot_dlist_join( votes->slot_dlist );
286 12 : votes->blk_pool = blk_pool_join ( votes->blk_pool );
287 12 : votes->blk_map = blk_map_join ( votes->blk_map );
288 12 : votes->vtr_pool = vtr_pool_join ( votes->vtr_pool );
289 12 : votes->vtr_map = vtr_map_join ( votes->vtr_map );
290 12 : votes->vtr_dlist = vtr_dlist_join ( votes->vtr_dlist );
291 12 : votes->vtr_set = slot_vtrs_join ( votes->vtr_set );
292 :
293 : /* Re-join vtrs sets and blk_dlists per slot pool position. */
294 :
295 108 : for( ulong i = 0UL; i < votes->slot_max; i++ ) {
296 96 : votes->slot_pool[i].vtrs = slot_vtrs_join( votes->slot_pool[i].vtrs );
297 96 : votes->slot_pool[i].blks = blk_dlist_join( votes->slot_pool[i].blks );
298 96 : }
299 :
300 12 : return votes;
301 12 : }
302 :
303 : void *
304 12 : fd_votes_leave( fd_votes_t const * votes ) {
305 :
306 12 : if( FD_UNLIKELY( !votes ) ) {
307 0 : FD_LOG_WARNING(( "NULL votes" ));
308 0 : return NULL;
309 0 : }
310 :
311 12 : return (void *)votes;
312 12 : }
313 :
314 : void *
315 12 : fd_votes_delete( void * votes ) {
316 :
317 12 : if( FD_UNLIKELY( !votes ) ) {
318 0 : FD_LOG_WARNING(( "NULL votes" ));
319 0 : return NULL;
320 0 : }
321 :
322 12 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)votes, fd_votes_align() ) ) ) {
323 0 : FD_LOG_WARNING(( "misaligned votes" ));
324 0 : return NULL;
325 0 : }
326 :
327 12 : return votes;
328 12 : }
329 :
330 : int
331 : fd_votes_count_vote( fd_votes_t * votes,
332 : fd_pubkey_t const * vote_acc,
333 : ulong stake,
334 : ulong vote_slot,
335 390 : fd_hash_t const * vote_block_id ) {
336 :
337 390 : if( FD_UNLIKELY( vote_slot >= votes->root + votes->slot_max ) ) return FD_VOTES_ERR_VOTE_TOO_NEW;
338 :
339 363 : vtr_t * vtr = vtr_map_ele_query( votes->vtr_map, vote_acc, NULL, votes->vtr_pool );
340 363 : if( FD_UNLIKELY( !vtr ) ) return FD_VOTES_ERR_UNKNOWN_VTR;
341 :
342 : /* Check we haven't already counted the voter's stake for this slot.
343 : If a voter votes for multiple block ids for the same slot, we only
344 : count their first one. Honest voters never vote more than once for
345 : the same slot so the percentage of stake doing this should be small
346 : as only malicious voters would equivocate votes this way. */
347 :
348 357 : slot_t * slot = slot_map_ele_query( votes->slot_map, &vote_slot, NULL, votes->slot_pool );
349 357 : if( FD_UNLIKELY( !slot ) ) {
350 36 : slot = slot_pool_ele_acquire( votes->slot_pool );
351 36 : slot->slot = vote_slot;
352 36 : slot->blk_cnt = 0;
353 36 : slot_vtrs_null( slot->vtrs );
354 36 : slot_map_ele_insert( votes->slot_map, slot, votes->slot_pool );
355 36 : slot_dlist_ele_push_tail( votes->slot_dlist, slot, votes->slot_pool );
356 36 : }
357 357 : if( FD_UNLIKELY( slot_vtrs_test( slot->vtrs, vtr->bit ) ) ) return FD_VOTES_ERR_ALREADY_VOTED;
358 258 : slot_vtrs_insert( slot->vtrs, vtr->bit );
359 :
360 258 : fd_votes_blk_key_t blk_key = { .slot = vote_slot, .block_id = *vote_block_id };
361 258 : blk_t * blk = blk_map_ele_query( votes->blk_map, &blk_key, NULL, votes->blk_pool );
362 258 : if( FD_UNLIKELY( !blk ) ) {
363 135 : blk = blk_pool_ele_acquire( votes->blk_pool );
364 135 : blk->key = blk_key;
365 135 : blk->stake = 0;
366 135 : blk->flags = 0;
367 135 : blk_map_ele_insert( votes->blk_map, blk, votes->blk_pool );
368 135 : blk_dlist_ele_push_tail( slot->blks, blk, votes->blk_pool );
369 135 : slot->blk_cnt++;
370 135 : }
371 258 : blk->stake += stake;
372 258 : return FD_VOTES_SUCCESS;
373 357 : }
374 :
375 : fd_votes_blk_t *
376 : fd_votes_query( fd_votes_t * votes,
377 : ulong slot,
378 0 : fd_hash_t const * block_id ) {
379 :
380 0 : if( FD_LIKELY( block_id ) ) {
381 0 : fd_votes_blk_key_t key = { .slot = slot, .block_id = *block_id };
382 0 : return blk_map_ele_query( votes->blk_map, &key, NULL, votes->blk_pool );
383 0 : }
384 :
385 : /* NULL block_id: search all block_ids for this slot, return the one
386 : with the highest forward confirmation level. */
387 :
388 0 : slot_t * votes_slot = slot_map_ele_query( votes->slot_map, &slot, NULL, votes->slot_pool );
389 0 : if( FD_UNLIKELY( !votes_slot ) ) return NULL;
390 :
391 0 : blk_t * best = NULL;
392 0 : for( blk_dlist_iter_t iter = blk_dlist_iter_fwd_init( votes_slot->blks, votes->blk_pool );
393 0 : !blk_dlist_iter_done( iter, votes_slot->blks, votes->blk_pool );
394 0 : iter = blk_dlist_iter_fwd_next( iter, votes_slot->blks, votes->blk_pool ) ) {
395 0 : blk_t * blk = blk_dlist_iter_ele( iter, votes_slot->blks, votes->blk_pool );
396 0 : if( FD_UNLIKELY( ( blk->flags >> 4 ) > ( best ? best->flags >> 4 : 0 ) ) ) best = blk;
397 0 : }
398 0 : return best;
399 0 : }
400 :
401 : void
402 : fd_votes_publish( fd_votes_t * votes,
403 18 : ulong root ) {
404 18 : if( FD_UNLIKELY( votes->root==ULONG_MAX ) ) { votes->root = root; return; }
405 18 : for( ulong slot = votes->root; slot < root; slot++ ) {
406 12 : slot_t * votes_slot = slot_map_ele_query( votes->slot_map, &slot, NULL, votes->slot_pool );
407 12 : if( FD_LIKELY( votes_slot ) ) {
408 108 : while( FD_LIKELY( !blk_dlist_is_empty( votes_slot->blks, votes->blk_pool ) ) ) {
409 102 : blk_t * blk = blk_dlist_ele_pop_head( votes_slot->blks, votes->blk_pool );
410 102 : blk_map_ele_remove_fast( votes->blk_map, blk, votes->blk_pool );
411 102 : blk_pool_ele_release( votes->blk_pool, blk );
412 102 : }
413 6 : slot_dlist_ele_remove( votes->slot_dlist, votes_slot, votes->slot_pool );
414 6 : slot_map_ele_remove_fast( votes->slot_map, votes_slot, votes->slot_pool );
415 6 : slot_pool_ele_release( votes->slot_pool, votes_slot );
416 6 : }
417 12 : }
418 6 : votes->root = root;
419 6 : }
420 :
421 : void
422 : fd_votes_update_voters( fd_votes_t * votes,
423 : fd_pubkey_t const * vote_accs,
424 12 : ulong cnt ) {
425 :
426 : /* Mark all existing voters for removal. */
427 :
428 12 : for( vtr_dlist_iter_t iter = vtr_dlist_iter_fwd_init( votes->vtr_dlist, votes->vtr_pool );
429 30 : !vtr_dlist_iter_done( iter, votes->vtr_dlist, votes->vtr_pool );
430 18 : iter = vtr_dlist_iter_fwd_next( iter, votes->vtr_dlist, votes->vtr_pool ) ) {
431 18 : votes->vtr_pool[iter].next = 1; /* mark for removal */
432 18 : }
433 :
434 : /* First pass: unmark kept voters from being released. Build a set
435 : of kept old bit positions. Existing voters keep their old bit
436 : positions (no compaction). */
437 :
438 12 : slot_vtrs_null( votes->vtr_set );
439 :
440 30 : for( ulong i=0UL; i<cnt; i++ ) {
441 18 : fd_pubkey_t const * vote_acc = &vote_accs[i];
442 18 : vtr_t * vtr = vtr_map_ele_query( votes->vtr_map, vote_acc, NULL, votes->vtr_pool );
443 18 : if( FD_LIKELY( vtr ) ) {
444 9 : vtr_dlist_ele_remove( votes->vtr_dlist, vtr, votes->vtr_pool );
445 9 : slot_vtrs_insert( votes->vtr_set, vtr->bit );
446 9 : vtr->next = 0; /* unmark for removal */
447 9 : vtr_dlist_ele_push_tail( votes->vtr_dlist, vtr, votes->vtr_pool );
448 9 : }
449 18 : }
450 :
451 : /* Pop and release marked voters until the first unmarked voter. */
452 :
453 21 : while( FD_LIKELY( !vtr_dlist_is_empty( votes->vtr_dlist, votes->vtr_pool ) ) ) {
454 15 : vtr_t * vtr = vtr_dlist_ele_pop_head( votes->vtr_dlist, votes->vtr_pool );
455 15 : if( FD_UNLIKELY( !vtr->next ) ) { /* can short-circuit since all the existing and new voters were appended */
456 6 : vtr_dlist_ele_push_tail( votes->vtr_dlist, vtr, votes->vtr_pool );
457 6 : break;
458 6 : }
459 9 : vtr_map_ele_remove_fast( votes->vtr_map, vtr, votes->vtr_pool );
460 9 : vtr_pool_ele_release( votes->vtr_pool, vtr );
461 9 : }
462 :
463 : /* Clear removed voters' bits from all existing slots' vtrs by
464 : intersecting with the kept set. */
465 :
466 12 : for( slot_dlist_iter_t iter = slot_dlist_iter_fwd_init( votes->slot_dlist, votes->slot_pool );
467 27 : !slot_dlist_iter_done( iter, votes->slot_dlist, votes->slot_pool );
468 15 : iter = slot_dlist_iter_fwd_next( iter, votes->slot_dlist, votes->slot_pool ) ) {
469 15 : slot_t * votes_slot = &votes->slot_pool[iter];
470 15 : slot_vtrs_intersect( votes_slot->vtrs, votes_slot->vtrs, votes->vtr_set );
471 15 : }
472 :
473 : /* Second pass: acquire and insert new voters, assigning bit positions
474 : from freed positions. */
475 :
476 12 : ulong free_bit = 0;
477 30 : for( ulong i=0UL; i<cnt; i++ ) {
478 18 : fd_pubkey_t const * vote_acc = &vote_accs[i];
479 18 : if( FD_LIKELY( vtr_map_ele_query( votes->vtr_map, vote_acc, NULL, votes->vtr_pool ) ) ) continue;
480 9 : vtr_t * vtr = vtr_pool_ele_acquire( votes->vtr_pool );
481 9 : vtr->vote_acc = *vote_acc;
482 9 : vtr->next = 0;
483 9 : while( slot_vtrs_test( votes->vtr_set, free_bit ) ) free_bit++;
484 9 : vtr->bit = free_bit;
485 9 : slot_vtrs_insert( votes->vtr_set, free_bit );
486 9 : free_bit++;
487 9 : vtr_map_ele_insert( votes->vtr_map, vtr, votes->vtr_pool );
488 9 : vtr_dlist_ele_push_tail( votes->vtr_dlist, vtr, votes->vtr_pool );
489 9 : }
490 12 : }
|
