Line data Source code
1 : /*
2 : Generate prototypes, inlines and implementations for multi-sorted views
3 : with a bounded compile-time number of columns and a bounded run-time
4 : fixed row capacity.
5 :
6 : A multi-sorted view is an iterator into an underlying table that
7 : traverses the table in a particular multi-sorted ordering. A multi-sort
8 : is characterized by sorting multiple columns simultaneously, creating a
9 : hierarchical order of data.
10 :
11 : This API is an extension of the fd_treap API. As such methods included
12 : in fd_treap.c also included in the template will have the same
13 : specification, unless noted otherwise.
14 :
15 : This API is designed for ultra tight coupling with pools, treaps,
16 : heaps, maps, other tables, etc. Likewise, a live table can be persisted
17 : beyond the lifetime of the creating process, used concurrently in
18 : many common operations, used inter-process, relocated in memory,
19 : naively serialized/deserialized, moved between hosts, supports index
20 : compression for cache and memory bandwidth efficiency, etc.
21 :
22 : Typical usage:
23 :
24 : struct myrow {
25 : ulong col1;
26 : uint col2;
27 :
28 : struct {
29 : ulong parent;
30 : ulong left;
31 : ulong right;
32 : ulong prio;
33 : ulong next;
34 : ulong prev;
35 :
36 : ... these fields back one of up to MY_TABLE_MAX_SORT_KEY_CNT
37 : ... active treaps. See fd_treap.c for restrictions, lifetimes, etc.
38 :
39 : } treaps[ MY_TABLE_MAX_SORT_KEY_CNT ]; // technically LIVE_TABLE_TREAP[ MY_TABLE_MAX_SORT_KEY_CNT ]
40 :
41 : struct {
42 : ulong prev;
43 : ulong next;
44 : } dlist; // technically LIVE_TABLE_DLIST
45 :
46 : ulong sort_keys; // technically LIVE_TABLE_SORT_KEYS
47 : };
48 : typedef struct myrow myrow_t;
49 :
50 : static int col1_lt( void const * a, void const * b ) { return *(ulong *)a < *(ulong *)b; }
51 : static int col2_lt( void const * a, void const * b ) { return *(uint *)a < *(uint *)b; }
52 :
53 : #define LIVE_TABLE_NAME my_table
54 : #define LIVE_TABLE_COLUMN_CNT (MY_TABLE_MAX_COLUMN_CNT)
55 : #define LIVE_TABLE_MAX_SORT_KEY_CNT (MY_TABLE_MAX_SORT_KEY_CNT)
56 : #define LIVE_TABLE_COLUMNS LIVE_TABLE_COL_ARRAY( \
57 : LIVE_TABLE_COL_ENTRY("Column One", col1, col1_lt), \
58 : LIVE_TABLE_COL_ENTRY("Column Two", col2, col2_lt) )
59 : #define LIVE_TABLE_ROW_T myrow_t
60 : #include "fd_gui_live_table_tmpl.c"
61 :
62 : ... LIVE_TABLE_COL_ENTRY accepts 3 arguments. The name of the table
63 : ... column as a const cstr, the member of myrow_t which corresponds
64 : ... to the column being added, and a pure function that accepts two
65 : ... columns (as void* to members of myrow_t) and returns true if the
66 : ... first compares less than the second. The provided member may be
67 : ... a nested member but may not use a field that is accessed through
68 : ... a pointer dereference (due to an incompatibility with clang's
69 : ... __builtin_offsetof)
70 :
71 : ... OK: LIVE_TABLE_COL_ENTRY("Column One", col1.a.b.c, col1_lt)
72 : ... NOT OK: LIVE_TABLE_COL_ENTRY("Column One", col1->a.c, col1_lt)
73 :
74 : ... LIVE_TABLE_MAX_SORT_KEY_CNT must be greater than or equal to 2.
75 :
76 : will declare the following APIs as a header-only style library in the
77 : compilation unit:
78 :
79 : // These methods have the same behavior as their counterparts in
80 : // fd_treap.c. The main difference is that there are up to
81 : // LIVE_TABLE_MAX_SORT_KEY_CNT treaps actively maintained by
82 : // mytable, and callers should not make any assumptions about a
83 : // given treap being used or unused.
84 :
85 : ulong mytable_align ( void );
86 : ulong mytable_footprint( ulong rows_max );
87 : void * mytable_new ( void * shmem, ulong rows_max, ulong seed );
88 : mytable_t * mytable_join ( void * shtable );
89 : void * mytable_leave ( mytable_t * join );
90 : void * mytable_delete ( void * shtable );
91 :
92 : ulong mytable_idx_null ( void );
93 : myrow_t * mytable_ele_null ( void );
94 : myrow_t const * mytable_ele_null_const( void );
95 :
96 : int mytable_idx_is_null( ulong i );
97 : int mytable_ele_is_null( myrow_t const * e );
98 :
99 : ulong mytable_idx ( myrow_t const * e, myrow_t const * pool );
100 : ulong mytable_idx_fast( myrow_t const * e, myrow_t const * pool );
101 :
102 : myrow_t * mytable_ele ( ulong i, myrow_t * pool );
103 : myrow_t * mytable_ele_fast( ulong i, myrow_t * pool );
104 :
105 : myrow_t const * mytable_ele_const ( ulong i, myrow_t const * pool );
106 : myrow_t const * mytable_ele_fast_const( ulong i, myrow_t const * pool );
107 :
108 : ulong mytable_ele_max( mytable_t const * table );
109 : ulong mytable_ele_cnt( mytable_t const * table );
110 :
111 : mytable_t * mytable_idx_insert( mytable_t * table, ulong n, myrow_t * pool );
112 : mytable_t * mytable_idx_remove( mytable_t * table, ulong d, myrow_t * pool );
113 :
114 : mytable_t * mytable_ele_insert( mytable_t * table, myrow_t * n, myrow_t * pool );
115 : mytable_t * mytable_ele_remove( mytable_t * table, myrow_t * d, myrow_t * pool );
116 :
117 : void mytable_seed( myrow_t * pool, ulong ele_max, ulong seed );
118 :
119 : int mytable_verify( mytable_t const * table, myrow_t const * pool );
120 :
121 : // A sort key is a structure used to define multi-column sorting
122 : // behavior. It consists of:
123 : // - An array of LIVE_TABLE_COLUMN_CNT column indices,
124 : // specifying which columns are sorted.
125 : // - An array of corresponding sort directions (null, asc, or
126 : // desc), defining the sorting order.
127 : //
128 : // Rows are sorted by prioritizing earlier columns in the sort key,
129 : // with each column sorted according to its specified direction.
130 : // These directions are:
131 : // - null ( 0): No sorting applied to the column.
132 : // - asc ( 1): Sort the column in ascending order.
133 : // - desc (-1): Sort the column in descending order.
134 : //
135 : // e.g.
136 : //
137 : // mytable_sort_key_t my_sort_key = { .col = { 0, 1, 2 }, .dir = { 0, 1, 0 } };
138 : //
139 : // The position of a column in col determined the precedence of the
140 : // column. Earlier columns are considered first when sorting, which
141 : // increases the visual impact of their sort.
142 : //
143 : // Also note that two sort keys may have different column orderings
144 : // but still be isomorphic (i.e. always result in the same sort).
145 : // For example, the following sort key is isomorphic with the key
146 : // above.
147 : //
148 : // mytable_sort_key_t my_sort_key = { .col = { 1, 0, 2 }, .dir = { 1, 0, 0 } };
149 : //
150 : // mytable_lt compares two myrow_t according to the specified sort key.
151 :
152 : int mytable_lt( mytable_sort_key_t const * sort_key, myrow_t const * e0, myrow_t const * e1 );
153 :
154 : // mytable_sort_key_remove removes sort_key from the collection of
155 : // sort_keys maintained by mytable.
156 :
157 : void mytable_sort_key_remove( mytable_t * join, mytable_sort_key_t const * sort_key );
158 :
159 : // mytable_fwd_iter_{init,done,next,idx,ele,ele_const} provide an
160 : // in-order iterator from smallest to largest value. Typical
161 : // usage:
162 : //
163 : // for( mytable_fwd_iter_t iter = mytable_fwd_iter_init( table, pool );
164 : // !mytable_fwd_iter_done( iter );
165 : // iter = mytable_fwd_iter_next( iter, pool ) ) {
166 : // ulong i = mytable_fwd_iter_idx( iter );
167 : // ... or myrow_t * e = mytable_fwd_iter_ele ( iter, pool );
168 : // ... or myrow_t const * e = mytable_fwd_iter_ele_const( iter, pool );
169 : //
170 : // ... process i (or e) here
171 : //
172 : // ... Do not remove the element the iterator is currently
173 : // ... pointing to, and do not change the element's parent,
174 : // ... left, right, or prio here. It is fine to run other
175 : // ... iterations concurrently. Other fields are free to
176 : // ... modify (from the table's POV, the application manages
177 : // ... concurrency for other fields).
178 : // }
179 : //
180 : // pool is a pointer in the caller's address space to the ele_max
181 : // linearly addressable storage region backing the table.
182 :
183 : int mytable_fwd_iter_done ( mytable_fwd_iter_t iter );
184 : ulong mytable_fwd_iter_idx ( mytable_fwd_iter_t iter );
185 : mytable_fwd_iter_t mytable_fwd_iter_init ( mytable_t * join, mytable_sort_key_t const * sort_key );
186 : mytable_fwd_iter_t mytable_fwd_iter_next ( mytable_t * join, mytable_sort_key_t const * sort_key, mytable_fwd_iter_t iter );
187 : myrow_t * mytable_fwd_iter_ele ( mytable_t * join, mytable_sort_key_t const * sort_key, mytable_fwd_iter_t iter );
188 : myrow_t const * mytable_fwd_iter_ele_const( mytable_t * join, mytable_sort_key_t const * sort_key, mytable_fwd_iter_t iter );
189 : */
190 :
191 : #ifndef LIVE_TABLE_NAME
192 : #error "need to define LIVE_TABLE_NAME"
193 : #endif
194 :
195 : #ifndef LIVE_TABLE_COLUMN_CNT
196 : #error "need to define LIVE_TABLE_COLUMN_CNT"
197 : #endif
198 : FD_STATIC_ASSERT( LIVE_TABLE_COLUMN_CNT >= 1UL, "Expected 1+ live table columns" );
199 :
200 : #ifndef LIVE_TABLE_MAX_SORT_KEY_CNT
201 : #define LIVE_TABLE_MAX_SORT_KEY_CNT (1024UL)
202 : #endif
203 : FD_STATIC_ASSERT( LIVE_TABLE_MAX_SORT_KEY_CNT >= 2UL, "Requires at least 2 sort keys" );
204 :
205 : #ifndef LIVE_TABLE_ROW_T
206 : #error "need to define LIVE_TABLE_ROW_T"
207 : #endif
208 :
209 : #ifndef LIVE_TABLE_COLUMNS
210 : #error "need to define LIVE_TABLE_COLUMNS"
211 : #endif
212 :
213 : #ifndef LIVE_TABLE_SORT_KEYS
214 : #define LIVE_TABLE_SORT_KEYS sort_keys
215 : #endif
216 :
217 : #ifndef LIVE_TABLE_TREAP
218 0 : #define LIVE_TABLE_TREAP treaps
219 : #endif
220 :
221 : #ifndef LIVE_TABLE_DLIST
222 : #define LIVE_TABLE_DLIST dlist
223 : #endif
224 :
225 0 : #define LIVE_TABLE_(n) FD_EXPAND_THEN_CONCAT3(LIVE_TABLE_NAME,_,n)
226 :
227 : #include <stddef.h> // offsetof
228 :
229 : #define LIVE_TABLE_COL_ENTRY(col_id, field, lt_func) \
230 : (LIVE_TABLE_(private_column_t)){ .col_name = col_id, .off = offsetof( LIVE_TABLE_ROW_T , field ), .lt = lt_func }
231 :
232 0 : #define LIVE_TABLE_COL_ARRAY(...) { __VA_ARGS__ }
233 :
234 : #ifndef LIVE_TABLE_IMPL_STYLE
235 : #define LIVE_TABLE_IMPL_STYLE 0
236 : #endif
237 :
238 : #if LIVE_TABLE_IMPL_STYLE==0
239 : #define LIVE_TABLE_STATIC static FD_FN_UNUSED
240 : #else
241 : #define LIVE_TABLE_STATIC
242 : #endif
243 :
244 : #include "../../util/log/fd_log.h" /* failure logs */
245 : #include "../../util/bits/fd_bits.h"
246 : #include "../../util/math/fd_stat.h"
247 :
248 : #if LIVE_TABLE_IMPL_STYLE!=2 /* need structures, prototypes and inlines */
249 : struct LIVE_TABLE_(private_column) {
250 : char * col_name; /* cstr */
251 : ulong off;
252 : int (* const lt)(void const * a, void const * b);
253 : };
254 : typedef struct LIVE_TABLE_(private_column) LIVE_TABLE_(private_column_t);
255 :
256 : struct LIVE_TABLE_(sort_key) {
257 : ulong col[ LIVE_TABLE_COLUMN_CNT ];
258 : int dir[ LIVE_TABLE_COLUMN_CNT ];
259 : };
260 : typedef struct LIVE_TABLE_(sort_key) LIVE_TABLE_(sort_key_t);
261 :
262 : /* Global state is ugly. We only have one type of treap and they all
263 : share the same static comparison function, but we need that function
264 : to change dynamically. The simplest way to do this is to have the
265 : function reference changing global state. Not ideal but the
266 : alternative is to change the implementation of the treap template.
267 :
268 : This variable never needs to be shared across compile units. All of
269 : the functions in this template do not retain interest in this
270 : variable after each call. */
271 : static ulong LIVE_TABLE_(private_active_sort_key_idx) = ULONG_MAX;
272 :
273 : static int
274 0 : LIVE_TABLE_(private_row_lt)(LIVE_TABLE_ROW_T const * a, LIVE_TABLE_ROW_T const * b) {
275 0 : FD_TEST( LIVE_TABLE_(private_active_sort_key_idx) < LIVE_TABLE_MAX_SORT_KEY_CNT+1UL );
276 :
277 0 : LIVE_TABLE_(sort_key_t) const * active_sort_key = &((LIVE_TABLE_(sort_key_t) *)(a->LIVE_TABLE_SORT_KEYS))[ LIVE_TABLE_(private_active_sort_key_idx) ];
278 :
279 0 : for( ulong i=0UL; i<LIVE_TABLE_COLUMN_CNT; i++ ) {
280 0 : if( FD_LIKELY( active_sort_key->dir[ i ]==0 ) ) continue;
281 :
282 0 : LIVE_TABLE_(private_column_t) cols[ LIVE_TABLE_COLUMN_CNT ] = LIVE_TABLE_COLUMNS;
283 :
284 0 : void * col_a = ((uchar *)a) + cols[ active_sort_key->col[ i ] ].off;
285 0 : void * col_b = ((uchar *)b) + cols[ active_sort_key->col[ i ] ].off;
286 0 : int a_lt_b = cols[ active_sort_key->col[ i ] ].lt(col_a, col_b);
287 0 : int b_lt_a = cols[ active_sort_key->col[ i ] ].lt(col_b, col_a);
288 :
289 0 : if( FD_UNLIKELY( !(a_lt_b || b_lt_a) ) ) continue; /* equal */
290 0 : return fd_int_if( active_sort_key->dir[ i ]==1, a_lt_b, !a_lt_b );
291 0 : }
292 :
293 0 : return 0; /* all columns equal */
294 0 : }
295 :
296 : #define TREAP_NAME LIVE_TABLE_(private_treap)
297 : #define TREAP_T LIVE_TABLE_ROW_T
298 : #define TREAP_QUERY_T void * /* query isn't used */
299 : #define TREAP_CMP(q,e) (__extension__({ (void)(q); (void)(e); -1; })) /* which means we don't need to give a real
300 : implementation to cmp either */
301 0 : #define TREAP_LT(e0,e1) (LIVE_TABLE_(private_row_lt)( (e0), (e1) ))
302 : #define TREAP_OPTIMIZE_ITERATION 1
303 0 : #define TREAP_PARENT LIVE_TABLE_TREAP[ LIVE_TABLE_(private_active_sort_key_idx) ].parent
304 0 : #define TREAP_LEFT LIVE_TABLE_TREAP[ LIVE_TABLE_(private_active_sort_key_idx) ].left
305 0 : #define TREAP_RIGHT LIVE_TABLE_TREAP[ LIVE_TABLE_(private_active_sort_key_idx) ].right
306 0 : #define TREAP_NEXT LIVE_TABLE_TREAP[ LIVE_TABLE_(private_active_sort_key_idx) ].next
307 0 : #define TREAP_PREV LIVE_TABLE_TREAP[ LIVE_TABLE_(private_active_sort_key_idx) ].prev
308 0 : #define TREAP_PRIO LIVE_TABLE_TREAP[ LIVE_TABLE_(private_active_sort_key_idx) ].prio
309 : #define TREAP_IMPL_STYLE LIVE_TABLE_IMPL_STYLE
310 : #include "../../util/tmpl/fd_treap.c"
311 :
312 : #define DLIST_NAME LIVE_TABLE_(private_dlist)
313 : #define DLIST_ELE_T LIVE_TABLE_ROW_T
314 0 : #define DLIST_PREV LIVE_TABLE_DLIST.prev
315 0 : #define DLIST_NEXT LIVE_TABLE_DLIST.next
316 : #include "../../util/tmpl/fd_dlist.c"
317 :
318 : struct LIVE_TABLE_() {
319 : LIVE_TABLE_(private_dlist_t) * dlist;
320 :
321 : LIVE_TABLE_(private_treap_t) * treaps [ LIVE_TABLE_MAX_SORT_KEY_CNT ];
322 : void * treaps_shmem [ LIVE_TABLE_MAX_SORT_KEY_CNT ];
323 : int treaps_is_active[ LIVE_TABLE_MAX_SORT_KEY_CNT ];
324 :
325 : ulong count;
326 : ulong max_rows;
327 : LIVE_TABLE_(sort_key_t) sort_keys[ LIVE_TABLE_MAX_SORT_KEY_CNT ];
328 : };
329 : typedef struct LIVE_TABLE_() LIVE_TABLE_(t);
330 :
331 : typedef LIVE_TABLE_(private_treap_fwd_iter_t) LIVE_TABLE_(fwd_iter_t);
332 :
333 : FD_PROTOTYPES_BEGIN
334 :
335 : LIVE_TABLE_STATIC void LIVE_TABLE_(seed)( LIVE_TABLE_ROW_T * pool, ulong rows_max, ulong seed );
336 :
337 : LIVE_TABLE_STATIC FD_FN_CONST ulong LIVE_TABLE_(align) ( void );
338 : LIVE_TABLE_STATIC FD_FN_CONST ulong LIVE_TABLE_(footprint)( ulong rows_max );
339 : LIVE_TABLE_STATIC void * LIVE_TABLE_(new) ( void * shmem, ulong rows_max );
340 : LIVE_TABLE_STATIC LIVE_TABLE_(t) * LIVE_TABLE_(join) ( void * shtable );
341 : LIVE_TABLE_STATIC void * LIVE_TABLE_(leave) ( LIVE_TABLE_(t) * join );
342 : LIVE_TABLE_STATIC void * LIVE_TABLE_(delete) ( void * shtable );
343 :
344 : LIVE_TABLE_STATIC LIVE_TABLE_ROW_T * LIVE_TABLE_(idx_insert)( LIVE_TABLE_(t) * join, ulong pool_idx, LIVE_TABLE_ROW_T * pool );
345 : LIVE_TABLE_STATIC void LIVE_TABLE_(idx_remove)( LIVE_TABLE_(t) * join, ulong pool_idx, LIVE_TABLE_ROW_T * pool );
346 :
347 : LIVE_TABLE_STATIC FD_FN_PURE LIVE_TABLE_(fwd_iter_t) LIVE_TABLE_(fwd_iter_next)( LIVE_TABLE_(fwd_iter_t) iter, LIVE_TABLE_ROW_T const * pool );
348 : LIVE_TABLE_STATIC FD_FN_PURE LIVE_TABLE_(fwd_iter_t) LIVE_TABLE_(fwd_iter_init)( LIVE_TABLE_(t) * join, LIVE_TABLE_(sort_key_t) const * sort_key, LIVE_TABLE_ROW_T * pool );
349 :
350 : LIVE_TABLE_STATIC int LIVE_TABLE_(verify)( LIVE_TABLE_(t) const * table, LIVE_TABLE_ROW_T const * pool );
351 :
352 : LIVE_TABLE_STATIC void
353 : LIVE_TABLE_(sort_key_remove)( LIVE_TABLE_(t) * join, LIVE_TABLE_(sort_key_t) const * sort_key );
354 :
355 : /* inlines */
356 :
357 0 : FD_FN_CONST static inline ulong LIVE_TABLE_(idx_null) ( void ) { return LIVE_TABLE_(private_treap_idx_null)(); }
358 0 : FD_FN_CONST static inline LIVE_TABLE_ROW_T * LIVE_TABLE_(ele_null) ( void ) { return LIVE_TABLE_(private_treap_ele_null)(); }
359 0 : FD_FN_CONST static inline LIVE_TABLE_ROW_T const * LIVE_TABLE_(ele_null_const)( void ) { return LIVE_TABLE_(private_treap_ele_null_const)(); }
360 :
361 0 : FD_FN_CONST static inline int LIVE_TABLE_(idx_is_null)( ulong i ) { return LIVE_TABLE_(private_treap_idx_is_null)( i ); }
362 0 : FD_FN_CONST static inline int LIVE_TABLE_(ele_is_null)( LIVE_TABLE_ROW_T const * e ) { return LIVE_TABLE_(private_treap_ele_is_null)( e ); }
363 :
364 : FD_FN_CONST static inline ulong
365 0 : LIVE_TABLE_(idx)( LIVE_TABLE_ROW_T const * e, LIVE_TABLE_ROW_T const * pool ) { return LIVE_TABLE_(private_treap_idx)( e, pool ); }
366 :
367 : FD_FN_CONST static inline LIVE_TABLE_ROW_T *
368 0 : LIVE_TABLE_(ele)( ulong i, LIVE_TABLE_ROW_T * pool ) { return LIVE_TABLE_(private_treap_ele)( i, pool ); }
369 :
370 : FD_FN_CONST static inline LIVE_TABLE_ROW_T const *
371 0 : LIVE_TABLE_(ele_const)( ulong i, LIVE_TABLE_ROW_T const * pool ) { return LIVE_TABLE_(private_treap_ele_const)( i, pool ); }
372 :
373 : FD_FN_CONST static inline ulong
374 0 : LIVE_TABLE_(idx_fast)( LIVE_TABLE_ROW_T const * e, LIVE_TABLE_ROW_T const * pool ) { return LIVE_TABLE_(private_treap_idx_fast)( e, pool ); }
375 :
376 0 : FD_FN_CONST static inline LIVE_TABLE_ROW_T * LIVE_TABLE_(ele_fast) ( ulong i, LIVE_TABLE_ROW_T * pool ) { return LIVE_TABLE_(private_treap_ele_fast)( i, pool ); }
377 0 : FD_FN_CONST static inline LIVE_TABLE_ROW_T const * LIVE_TABLE_(ele_fast_const)( ulong i, LIVE_TABLE_ROW_T const * pool ) { return LIVE_TABLE_(private_treap_ele_fast_const)( i, pool ); }
378 :
379 : FD_FN_CONST static inline LIVE_TABLE_(fwd_iter_t)
380 0 : LIVE_TABLE_(fwd_iter_next)( LIVE_TABLE_(fwd_iter_t) iter, LIVE_TABLE_ROW_T const * pool ) { return LIVE_TABLE_(private_treap_fwd_iter_next)( iter, pool ); }
381 :
382 : FD_FN_CONST static inline LIVE_TABLE_ROW_T *
383 0 : LIVE_TABLE_(fwd_iter_ele)( LIVE_TABLE_(fwd_iter_t) iter, LIVE_TABLE_ROW_T * pool ) { return LIVE_TABLE_(private_treap_fwd_iter_ele)( iter, pool ); }
384 :
385 : FD_FN_CONST static inline LIVE_TABLE_ROW_T const *
386 0 : LIVE_TABLE_(fwd_iter_ele_const)( LIVE_TABLE_(fwd_iter_t) iter, LIVE_TABLE_ROW_T const * pool ) { return LIVE_TABLE_(private_treap_fwd_iter_ele_const)( iter, pool ); }
387 :
388 : FD_FN_CONST static inline int
389 0 : LIVE_TABLE_(fwd_iter_done)( LIVE_TABLE_(fwd_iter_t) iter ) { return LIVE_TABLE_(private_treap_fwd_iter_done)( iter ); }
390 :
391 : FD_FN_CONST static inline ulong
392 0 : LIVE_TABLE_(fwd_iter_idx)( LIVE_TABLE_(fwd_iter_t) iter ) { return LIVE_TABLE_(private_treap_fwd_iter_idx)( iter ); }
393 :
394 : static inline LIVE_TABLE_ROW_T *
395 0 : LIVE_TABLE_(ele_insert)( LIVE_TABLE_(t) * join, LIVE_TABLE_ROW_T * row, LIVE_TABLE_ROW_T * pool ) { return LIVE_TABLE_(idx_insert)( join, (ulong)(row - pool), pool ); }
396 :
397 : static inline void
398 0 : LIVE_TABLE_(ele_remove)( LIVE_TABLE_(t) * join, LIVE_TABLE_ROW_T * row, LIVE_TABLE_ROW_T * pool ) { LIVE_TABLE_(idx_remove)( join, (ulong)(row - pool), pool ); }
399 :
400 0 : FD_FN_PURE static inline ulong LIVE_TABLE_(ele_cnt)( LIVE_TABLE_(t) * join ) { return join->count; }
401 0 : FD_FN_PURE static inline ulong LIVE_TABLE_(ele_max)( LIVE_TABLE_(t) * join ) { return join->max_rows; }
402 :
403 : FD_FN_PURE static inline ulong
404 0 : LIVE_TABLE_(active_sort_key_cnt)( LIVE_TABLE_(t) * join ) {
405 0 : ulong count = 0UL;
406 0 : for( ulong i=0; i<LIVE_TABLE_MAX_SORT_KEY_CNT; i++ ) {
407 0 : if( FD_LIKELY( join->treaps_is_active[ i ] ) ) count++;
408 0 : }
409 0 : return count;
410 0 : }
411 :
412 : FD_FN_CONST static inline ulong
413 0 : LIVE_TABLE_(col_name_to_idx)( LIVE_TABLE_(t) * join, char const * col_name ) {
414 0 : (void)join;
415 0 : LIVE_TABLE_(private_column_t) cols[ LIVE_TABLE_COLUMN_CNT ] = LIVE_TABLE_COLUMNS;
416 0 : for( ulong i=0; i < LIVE_TABLE_COLUMN_CNT; i++ ) {
417 0 : if( FD_UNLIKELY( strcmp( cols[ i ].col_name, col_name ) ) ) continue;
418 0 : return i;
419 0 : }
420 0 : return ULONG_MAX;
421 0 : }
422 :
423 : FD_FN_CONST static inline char const *
424 0 : LIVE_TABLE_(col_idx_to_name)( LIVE_TABLE_(t) * join, ulong col_idx ) {
425 0 : (void)join;
426 0 : if( FD_UNLIKELY( col_idx>=LIVE_TABLE_COLUMN_CNT ) ) return NULL;
427 0 : LIVE_TABLE_(private_column_t) cols[ LIVE_TABLE_COLUMN_CNT ] = LIVE_TABLE_COLUMNS;
428 0 : return cols[ col_idx ].col_name;
429 0 : }
430 :
431 : static inline void
432 0 : LIVE_TABLE_(private_sort_key_print)( LIVE_TABLE_(sort_key_t) const * sort_key ) {
433 0 : char out[ 4096 ];
434 0 : char * p = fd_cstr_init( out );
435 :
436 0 : p = fd_cstr_append_printf( p, "cols: %lu", sort_key->col[ 0 ] );
437 0 : for( ulong i=1UL; i<LIVE_TABLE_COLUMN_CNT; i++ ) {
438 0 : p = fd_cstr_append_printf( p, ",%lu", sort_key->col[ i ] );
439 0 : }
440 0 : p = fd_cstr_append_printf( p, "\ndir: %d", sort_key->dir[ 0 ] );
441 0 : for( ulong i=1UL; i<LIVE_TABLE_COLUMN_CNT; i++ ) {
442 0 : p = fd_cstr_append_printf( p, ",%d", sort_key->dir[ i ] );
443 0 : }
444 0 : fd_cstr_fini( p );
445 0 : FD_LOG_WARNING(( "%s", out ));
446 0 : }
447 :
448 : static inline void
449 0 : LIVE_TABLE_(private_sort_key_create)( LIVE_TABLE_(t) * join, ulong sort_key_idx, LIVE_TABLE_(sort_key_t) const * sort_key, LIVE_TABLE_ROW_T * pool ) {
450 0 : fd_memcpy( &join->sort_keys[ sort_key_idx ], sort_key, sizeof(LIVE_TABLE_(sort_key_t)) );
451 :
452 0 : LIVE_TABLE_(private_active_sort_key_idx) = sort_key_idx;
453 0 : join->treaps[ sort_key_idx ] = LIVE_TABLE_(private_treap_join)( LIVE_TABLE_(private_treap_new)( join->treaps_shmem[ sort_key_idx ], join->max_rows ) );
454 0 : join->treaps_is_active[ sort_key_idx ] = 1;
455 : #if FD_TMPL_USE_HANDHOLDING
456 : FD_TEST( sort_key_idx<LIVE_TABLE_MAX_SORT_KEY_CNT );
457 : FD_TEST( join->treaps[ sort_key_idx ] );
458 : FD_TEST( !LIVE_TABLE_(private_treap_verify)( join->treaps[ sort_key_idx ], pool ) );
459 : #endif
460 :
461 0 : for( LIVE_TABLE_(private_dlist_iter_t) iter = LIVE_TABLE_(private_dlist_iter_fwd_init)( join->dlist, pool );
462 0 : !LIVE_TABLE_(private_dlist_iter_done)( iter, join->dlist, pool );
463 0 : iter = LIVE_TABLE_(private_dlist_iter_fwd_next)( iter, join->dlist, pool ) ) {
464 0 : ulong pool_idx = LIVE_TABLE_(private_dlist_iter_idx)( iter, join->dlist, pool );
465 0 : LIVE_TABLE_(private_treap_idx_insert)( join->treaps[ sort_key_idx ], pool_idx, pool );
466 0 : }
467 :
468 : #if FD_TMPL_USE_HANDHOLDING
469 : FD_TEST( !LIVE_TABLE_(private_treap_verify)( join->treaps[ sort_key_idx ], pool ) );
470 : #endif
471 0 : }
472 :
473 : static inline ulong
474 0 : LIVE_TABLE_(private_query_sort_key)( LIVE_TABLE_(t) * join, LIVE_TABLE_(sort_key_t) const * sort_key ) {
475 0 : for( ulong i=0; i<LIVE_TABLE_MAX_SORT_KEY_CNT; i++ ) {
476 0 : if( FD_UNLIKELY( !join->treaps_is_active[ i ] ) ) continue;
477 0 : int equal = 1;
478 0 : ulong j = 0;
479 0 : ulong k = 0;
480 0 : do {
481 : /* columns with dir=0 don't actually count, they're ignored */
482 0 : if( FD_UNLIKELY( j<LIVE_TABLE_COLUMN_CNT-1UL && join->sort_keys[ i ].dir[ j ]==0 ) ) {
483 0 : j++;
484 0 : continue;
485 0 : }
486 0 : if( FD_UNLIKELY( k<LIVE_TABLE_COLUMN_CNT-1UL && sort_key->dir[ k ]==0 ) ) {
487 0 : k++;
488 0 : continue;
489 0 : }
490 0 : if( FD_LIKELY( !(join->sort_keys[ i ].dir[ j ]==0 && sort_key->dir[ k ]==0) && (join->sort_keys[ i ].col[ j ] != sort_key->col[ k ] || join->sort_keys[ i ].dir[ j ] != sort_key->dir[ k ]) ) ) {
491 0 : equal = 0;
492 0 : break;
493 0 : }
494 0 : if( FD_LIKELY( j<LIVE_TABLE_COLUMN_CNT-1UL ) ) j++;
495 0 : if( FD_LIKELY( k<LIVE_TABLE_COLUMN_CNT-1UL ) ) k++; /* todo ... test edge case */
496 0 : } while( !(j==LIVE_TABLE_COLUMN_CNT-1UL && k==LIVE_TABLE_COLUMN_CNT-1UL) );
497 0 : if( FD_LIKELY( !equal ) ) continue;
498 0 : return i;
499 0 : }
500 :
501 0 : return ULONG_MAX;
502 0 : }
503 :
504 0 : static inline int LIVE_TABLE_(lt) ( LIVE_TABLE_(sort_key_t) const * sort_key, LIVE_TABLE_ROW_T const * e0, LIVE_TABLE_ROW_T const * e1 ) {
505 0 : ulong old_val = e0->LIVE_TABLE_SORT_KEYS;
506 0 : ((LIVE_TABLE_ROW_T *)e0)->LIVE_TABLE_SORT_KEYS = (ulong)sort_key;
507 0 : LIVE_TABLE_(private_active_sort_key_idx) = 0;
508 0 : int lt = LIVE_TABLE_(private_row_lt)(e0, e1);
509 0 : ((LIVE_TABLE_ROW_T *)e0)->LIVE_TABLE_SORT_KEYS = old_val;
510 0 : return lt;
511 0 : }
512 :
513 : #endif /* LIVE_TABLE_IMPL_STYLE!=2 */
514 :
515 : #if LIVE_TABLE_IMPL_STYLE!=1 /* need implementations */
516 :
517 : LIVE_TABLE_STATIC ulong
518 0 : LIVE_TABLE_(align)(void) {
519 0 : ulong a = 1UL;
520 0 : a = fd_ulong_max( a, alignof(LIVE_TABLE_(t)) );
521 0 : a = fd_ulong_max( a, LIVE_TABLE_(private_treap_align)() );
522 0 : a = fd_ulong_max( a, LIVE_TABLE_(private_dlist_align)() );
523 0 : a = fd_ulong_max( a, 128UL );
524 0 : FD_TEST( fd_ulong_pow2_up( a )==a );
525 0 : return a;
526 0 : }
527 :
528 : LIVE_TABLE_STATIC ulong
529 0 : LIVE_TABLE_(footprint)( ulong max_rows ) {
530 0 : ulong l = FD_LAYOUT_INIT;
531 0 : l = FD_LAYOUT_APPEND( l, alignof(LIVE_TABLE_(t)), sizeof(LIVE_TABLE_(t)) );
532 0 : l = FD_LAYOUT_APPEND( l, LIVE_TABLE_(private_dlist_align)(), LIVE_TABLE_(private_dlist_footprint)() );
533 0 : for( ulong i=0UL; i<LIVE_TABLE_MAX_SORT_KEY_CNT; i++ ) l = FD_LAYOUT_APPEND( l, LIVE_TABLE_(private_treap_align)(), LIVE_TABLE_(private_treap_footprint)( max_rows ) );
534 0 : return FD_LAYOUT_FINI( l, LIVE_TABLE_(align)() );
535 0 : }
536 :
537 : LIVE_TABLE_STATIC void *
538 0 : LIVE_TABLE_(new)( void * shmem, ulong max_rows ) {
539 0 : if( !shmem ) {
540 0 : FD_LOG_WARNING(( "NULL shmem" ));
541 0 : return NULL;
542 0 : }
543 :
544 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, LIVE_TABLE_(align)() ) ) ) {
545 0 : FD_LOG_WARNING(( "misaligned shmem" ));
546 0 : return NULL;
547 0 : }
548 :
549 0 : FD_SCRATCH_ALLOC_INIT( l, shmem );
550 0 : LIVE_TABLE_(t) * _table = FD_SCRATCH_ALLOC_APPEND( l, alignof(LIVE_TABLE_(t)), sizeof(LIVE_TABLE_(t)) );
551 0 : void * _dlist = FD_SCRATCH_ALLOC_APPEND( l, LIVE_TABLE_(private_dlist_align)(), LIVE_TABLE_(private_dlist_footprint)() );
552 0 : for( ulong i=0; i<LIVE_TABLE_MAX_SORT_KEY_CNT; i++ ) _table->treaps_shmem[ i ] = FD_SCRATCH_ALLOC_APPEND( l, LIVE_TABLE_(private_treap_align)(), LIVE_TABLE_(private_treap_footprint)( max_rows ) );
553 0 : FD_SCRATCH_ALLOC_FINI( l, LIVE_TABLE_(align)() );
554 :
555 0 : _table->dlist = LIVE_TABLE_(private_dlist_join)( LIVE_TABLE_(private_dlist_new)( _dlist ) );
556 0 : _table->max_rows = max_rows;
557 0 : _table->count = 0UL;
558 0 : for( ulong i=0; i<LIVE_TABLE_MAX_SORT_KEY_CNT; i++ ) _table->treaps_is_active[ i ] = 0;
559 :
560 0 : LIVE_TABLE_(private_column_t) cols[ LIVE_TABLE_COLUMN_CNT ] = LIVE_TABLE_COLUMNS;
561 0 : FD_TEST( LIVE_TABLE_COLUMN_CNT == sizeof(cols)/sizeof(LIVE_TABLE_(private_column_t)) );
562 :
563 : /* live_table_treap_new( ... ) not called since all treaps start as inactive */
564 :
565 0 : return _table;
566 0 : }
567 :
568 : FD_PROTOTYPES_END
569 :
570 : LIVE_TABLE_STATIC void
571 0 : LIVE_TABLE_(seed)( LIVE_TABLE_ROW_T * pool, ulong rows_max, ulong seed ) {
572 0 : for( ulong i=0; i<LIVE_TABLE_MAX_SORT_KEY_CNT; i++ ) {
573 0 : LIVE_TABLE_(private_active_sort_key_idx) = i;
574 0 : LIVE_TABLE_(private_treap_seed)( pool, rows_max, seed ); /* set random priorities */
575 0 : }
576 0 : }
577 :
578 : LIVE_TABLE_STATIC LIVE_TABLE_(t) *
579 0 : LIVE_TABLE_(join)( void * shtable ) {
580 0 : if( !shtable ) {
581 0 : FD_LOG_WARNING(( "NULL shtable" ));
582 0 : return NULL;
583 0 : }
584 :
585 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shtable, LIVE_TABLE_(align)() ) ) ) {
586 0 : FD_LOG_WARNING(( "misaligned shtable" ));
587 0 : return NULL;
588 0 : }
589 :
590 0 : return (LIVE_TABLE_(t) *)shtable;
591 0 : }
592 :
593 : LIVE_TABLE_STATIC void *
594 0 : LIVE_TABLE_(leave)( LIVE_TABLE_(t) * join ) {
595 0 : if( FD_UNLIKELY( !join ) ) {
596 0 : FD_LOG_WARNING(( "NULL join" ));
597 0 : return NULL;
598 0 : }
599 0 :
600 0 : LIVE_TABLE_(private_dlist_delete)( LIVE_TABLE_(private_dlist_leave)( join->dlist ) );
601 0 : for( ulong i=0; i<LIVE_TABLE_MAX_SORT_KEY_CNT; i++ ) {
602 0 : if( FD_LIKELY( join->treaps_is_active[ i ] ) ) continue;
603 0 : LIVE_TABLE_(private_active_sort_key_idx) = i;
604 0 : FD_TEST( LIVE_TABLE_(private_treap_delete)( LIVE_TABLE_(private_treap_leave)( join->treaps[ i ] ) ) );
605 0 : }
606 0 :
607 0 : return (void *)join;
608 0 : }
609 :
610 : LIVE_TABLE_STATIC void *
611 0 : LIVE_TABLE_(delete)( void * shtable ) {
612 0 : LIVE_TABLE_(t) * table = (LIVE_TABLE_(t) *)shtable;
613 0 :
614 0 : if( FD_UNLIKELY( !table ) ) {
615 0 : FD_LOG_WARNING(( "NULL shtable" ));
616 0 : return NULL;
617 0 : }
618 0 :
619 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)table, alignof(LIVE_TABLE_(t)) ) ) ) {
620 0 : FD_LOG_WARNING(( "misaligned shtable" ));
621 0 : return NULL;
622 0 : }
623 0 :
624 0 : return (void *)table;
625 0 : }
626 :
627 : LIVE_TABLE_STATIC void
628 0 : LIVE_TABLE_(idx_remove)( LIVE_TABLE_(t) * join, ulong pool_idx, LIVE_TABLE_ROW_T * pool ) {
629 : #if FD_TMPL_USE_HANDHOLDING
630 : FD_TEST( !LIVE_TABLE_(private_treap_idx_is_null)( pool_idx ) );
631 : FD_TEST( join->count >= 1UL );
632 : #endif
633 : /* remove from all active treaps */
634 0 : for( ulong i=0; i<LIVE_TABLE_MAX_SORT_KEY_CNT; i++ ) {
635 0 : if( FD_LIKELY( !join->treaps_is_active[ i ] ) ) continue;
636 0 : LIVE_TABLE_(private_active_sort_key_idx) = i;
637 0 : LIVE_TABLE_(private_treap_idx_remove)( join->treaps[ i ], pool_idx, pool );
638 0 : }
639 0 : LIVE_TABLE_(private_dlist_idx_remove)( join->dlist, pool_idx, pool );
640 0 : join->count--;
641 0 : }
642 :
643 : LIVE_TABLE_STATIC LIVE_TABLE_ROW_T *
644 0 : LIVE_TABLE_(idx_insert)( LIVE_TABLE_(t) * join, ulong pool_idx, LIVE_TABLE_ROW_T * pool ) {
645 0 : pool[ pool_idx ].LIVE_TABLE_SORT_KEYS = (ulong)(&join->sort_keys);
646 : #if FD_TMPL_USE_HANDHOLDING
647 : FD_TEST( !LIVE_TABLE_(private_treap_idx_is_null)( pool_idx ) );
648 : #endif
649 : /* insert into all active treaps */
650 0 : for( ulong i=0; i<LIVE_TABLE_MAX_SORT_KEY_CNT; i++ ) {
651 0 : if( FD_LIKELY( !join->treaps_is_active[ i ] ) ) continue;
652 0 : LIVE_TABLE_(private_active_sort_key_idx) = i;
653 0 : LIVE_TABLE_(private_treap_idx_insert)( join->treaps[ i ], pool_idx, pool );
654 0 : }
655 0 : LIVE_TABLE_(private_dlist_idx_push_tail)( join->dlist, pool_idx, pool );
656 0 : join->count++;
657 :
658 0 : return pool + pool_idx;
659 0 : }
660 :
661 : LIVE_TABLE_STATIC void
662 0 : LIVE_TABLE_(sort_key_remove)( LIVE_TABLE_(t) * join, LIVE_TABLE_(sort_key_t) const * sort_key ) {
663 0 : ulong sort_key_idx = LIVE_TABLE_(private_query_sort_key)( join, sort_key );
664 0 : if( FD_UNLIKELY( sort_key_idx==ULONG_MAX ) ) return;
665 :
666 0 : LIVE_TABLE_(private_active_sort_key_idx) = sort_key_idx;
667 : #if FD_TMPL_USE_HANDHOLDING
668 : FD_TEST( sort_key_idx<LIVE_TABLE_MAX_SORT_KEY_CNT );
669 : FD_TEST( join->treaps[ sort_key_idx ] );
670 : #endif
671 0 : join->treaps_is_active[ sort_key_idx ] = 0;
672 0 : LIVE_TABLE_(private_treap_delete)( LIVE_TABLE_(private_treap_leave)( join->treaps[ sort_key_idx ] ) );
673 0 : join->treaps[ sort_key_idx ] = NULL;
674 0 : }
675 :
676 : LIVE_TABLE_STATIC FD_FN_PURE LIVE_TABLE_(fwd_iter_t)
677 0 : LIVE_TABLE_(fwd_iter_init)( LIVE_TABLE_(t) * join, LIVE_TABLE_(sort_key_t) const * sort_key, LIVE_TABLE_ROW_T * pool ) {
678 0 : ulong sort_key_idx = LIVE_TABLE_(private_query_sort_key)( join, sort_key );
679 0 : if( FD_UNLIKELY( sort_key_idx==ULONG_MAX ) ) {
680 0 : for( ulong i=0UL; i<LIVE_TABLE_COLUMN_CNT; i++ ) {
681 0 : if( FD_UNLIKELY( join->treaps_is_active[ i ] ) ) continue;
682 0 : sort_key_idx = i;
683 0 : LIVE_TABLE_(private_sort_key_create)( join, i, sort_key, pool );
684 0 : break;
685 0 : }
686 0 : }
687 0 : LIVE_TABLE_(private_active_sort_key_idx) = sort_key_idx;
688 : #if FD_TMPL_USE_HANDHOLDING
689 : FD_TEST( sort_key_idx!=ULONG_MAX );
690 : FD_TEST( join->treaps_is_active[ sort_key_idx ] );
691 : #endif
692 0 : return LIVE_TABLE_(private_treap_fwd_iter_init)( join->treaps[ sort_key_idx ], pool );
693 0 : }
694 :
695 : LIVE_TABLE_STATIC int
696 0 : LIVE_TABLE_(verify)( LIVE_TABLE_(t) const * join, LIVE_TABLE_ROW_T const * pool ) {
697 0 : ulong prev_sk_idx = LIVE_TABLE_(private_active_sort_key_idx);
698 0 : for( ulong i=0UL; i<LIVE_TABLE_MAX_SORT_KEY_CNT; i++ ) {
699 0 : if( FD_LIKELY( !join->treaps_is_active[ i ] ) ) continue;
700 :
701 0 : LIVE_TABLE_(private_active_sort_key_idx) = i;
702 0 : if( FD_UNLIKELY( LIVE_TABLE_(private_treap_verify)( join->treaps[ i ], pool ) ) ) {
703 0 : FD_LOG_CRIT(("failed verify"));
704 0 : }
705 :
706 0 : LIVE_TABLE_(sort_key_t) tmp_key[ 1 ];
707 0 : fd_memcpy( tmp_key, &join->sort_keys[ i ], sizeof(LIVE_TABLE_(sort_key_t)) );
708 0 : fd_sort_up_ulong_insert( tmp_key->col, LIVE_TABLE_COLUMN_CNT );
709 :
710 0 : for( ulong j=0UL; j<LIVE_TABLE_COLUMN_CNT; j++ ) {
711 0 : if( FD_UNLIKELY( tmp_key->col[ j ]!=j || tmp_key->dir[ j ] > 1 || tmp_key->dir[ j ] < -1 ) ) {
712 0 : LIVE_TABLE_(private_sort_key_print)( &join->sort_keys[ i ] );
713 0 : FD_LOG_CRIT(( "bad sort key %lu", i ));
714 0 : }
715 0 : }
716 0 : }
717 0 : LIVE_TABLE_(private_active_sort_key_idx) = prev_sk_idx;
718 0 : return 0;
719 0 : }
720 :
721 : #endif /* LIVE_TABLE_IMPL_STYLE!=1 */
722 :
723 : #undef LIVE_TABLE_NAME
724 : #undef LIVE_TABLE_COLUMN_CNT
725 : #undef LIVE_TABLE_MAX_SORT_KEY_CNT
726 : #undef LIVE_TABLE_ROW_T
727 : #undef LIVE_TABLE_COLUMNS
728 : #undef LIVE_TABLE_SORT_KEYS
729 : #undef LIVE_TABLE_TREAP
730 : #undef LIVE_TABLE_DLIST
731 : #undef LIVE_TABLE_
732 : #undef LIVE_TABLE_COL_ENTRY
733 : #undef LIVE_TABLE_COL_ARRAY
734 : #undef LIVE_TABLE_IMPL_STYLE
735 : #undef LIVE_TABLE_STATIC
|
