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