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 : ulong mytable_col_cnt( void );
111 :
112 : myrow_t * mytable_idx_insert( mytable_t * table, ulong n, myrow_t * pool );
113 : void mytable_idx_remove( mytable_t * table, ulong d, myrow_t * pool );
114 :
115 : myrow_t * mytable_ele_insert( mytable_t * table, myrow_t * n, myrow_t * pool );
116 : void mytable_ele_remove( mytable_t * table, myrow_t * d, myrow_t * pool );
117 :
118 : void mytable_seed( myrow_t * pool, ulong ele_max, ulong seed );
119 :
120 : int mytable_verify( mytable_t const * table, myrow_t const * pool );
121 :
122 : // mytable_verify_sort_key checks that a sort key doesn't contain
123 : // duplicate columns and that all sort directions are valid
124 : int mytable_verify_sort_key( mytable_sort_key_t const * sort_key );
125 :
126 : // A sort key is a structure used to define multi-column sorting
127 : // behavior. It consists of:
128 : // - An array of LIVE_TABLE_COLUMN_CNT column indices,
129 : // specifying which columns are sorted.
130 : // - An array of corresponding sort directions (null, asc, or
131 : // desc), defining the sorting order.
132 : //
133 : // Rows are sorted by prioritizing earlier columns in the sort key,
134 : // with each column sorted according to its specified direction.
135 : // These directions are:
136 : // - null ( 0): No sorting applied to the column.
137 : // - asc ( 1): Sort the column in ascending order.
138 : // - desc (-1): Sort the column in descending order.
139 : //
140 : // e.g.
141 : //
142 : // mytable_sort_key_t my_sort_key = { .col = { 0, 1, 2 }, .dir = { 0, 1, 0 } };
143 : //
144 : // The position of a column in col determined the precedence of the
145 : // column. Earlier columns are considered first when sorting, which
146 : // increases the visual impact of their sort.
147 : //
148 : // Also note that two sort keys may have different column orderings
149 : // but still be isomorphic (i.e. always result in the same sort).
150 : // For example, the following sort key is isomorphic with the key
151 : // above.
152 : //
153 : // mytable_sort_key_t my_sort_key = { .col = { 1, 0, 2 }, .dir = { 1, 0, 0 } };
154 : //
155 : // mytable_lt compares two myrow_t according to the specified sort key.
156 :
157 : int mytable_lt( mytable_sort_key_t const * sort_key, myrow_t const * e0, myrow_t const * e1 );
158 :
159 : // mytable_sort_key_remove removes sort_key from the collection of
160 : // sort_keys maintained by mytable.
161 :
162 : void mytable_sort_key_remove( mytable_t * join, mytable_sort_key_t const * sort_key );
163 :
164 : // mytable_fwd_iter_{init,done,next,idx,ele,ele_const} provide an
165 : // in-order iterator from smallest to largest value. Typical
166 : // usage:
167 : //
168 : // for( mytable_fwd_iter_t iter = mytable_fwd_iter_init( table, pool );
169 : // !mytable_fwd_iter_done( iter );
170 : // iter = mytable_fwd_iter_next( iter, pool ) ) {
171 : // ulong i = mytable_fwd_iter_idx( iter );
172 : // ... or myrow_t * e = mytable_fwd_iter_ele ( iter, pool );
173 : // ... or myrow_t const * e = mytable_fwd_iter_ele_const( iter, pool );
174 : //
175 : // ... process i (or e) here
176 : //
177 : // ... Do not remove the element the iterator is currently
178 : // ... pointing to, and do not change the element's parent,
179 : // ... left, right, or prio here. It is fine to run other
180 : // ... iterations concurrently. Other fields are free to
181 : // ... modify (from the table's POV, the application manages
182 : // ... concurrency for other fields).
183 : // }
184 : //
185 : // pool is a pointer in the caller's address space to the ele_max
186 : // linearly addressable storage region backing the table.
187 :
188 : int mytable_fwd_iter_done ( mytable_fwd_iter_t iter );
189 : ulong mytable_fwd_iter_idx ( mytable_fwd_iter_t iter );
190 : mytable_fwd_iter_t mytable_fwd_iter_init ( mytable_t * join, mytable_sort_key_t const * sort_key, myrow_t * pool );
191 : mytable_fwd_iter_t mytable_fwd_iter_next ( mytable_t * join, mytable_sort_key_t const * sort_key, mytable_fwd_iter_t iter, myrow_t * pool );
192 : myrow_t * mytable_fwd_iter_ele ( mytable_t * join, mytable_sort_key_t const * sort_key, mytable_fwd_iter_t iter, myrow_t * pool );
193 : myrow_t const * mytable_fwd_iter_ele_const( mytable_t * join, mytable_sort_key_t const * sort_key, mytable_fwd_iter_t iter, myrow_t * pool );
194 : */
195 :
196 : #ifndef LIVE_TABLE_NAME
197 : #error "need to define LIVE_TABLE_NAME"
198 : #endif
199 :
200 : #ifndef LIVE_TABLE_COLUMN_CNT
201 : #error "need to define LIVE_TABLE_COLUMN_CNT"
202 : #endif
203 : FD_STATIC_ASSERT( LIVE_TABLE_COLUMN_CNT >= 1UL, "Expected 1+ live table columns" );
204 :
205 : #ifndef LIVE_TABLE_MAX_SORT_KEY_CNT
206 : #define LIVE_TABLE_MAX_SORT_KEY_CNT (1024UL)
207 : #endif
208 : FD_STATIC_ASSERT( LIVE_TABLE_MAX_SORT_KEY_CNT >= 2UL, "Requires at least 2 sort keys" );
209 :
210 : #ifndef LIVE_TABLE_ROW_T
211 : #error "need to define LIVE_TABLE_ROW_T"
212 : #endif
213 :
214 : #ifndef LIVE_TABLE_COLUMNS
215 : #error "need to define LIVE_TABLE_COLUMNS"
216 : #endif
217 :
218 : #ifndef LIVE_TABLE_SORT_KEYS
219 : #define LIVE_TABLE_SORT_KEYS sort_keys
220 : #endif
221 :
222 : #ifndef LIVE_TABLE_TREAP
223 0 : #define LIVE_TABLE_TREAP treaps
224 : #endif
225 :
226 : #ifndef LIVE_TABLE_DLIST
227 : #define LIVE_TABLE_DLIST dlist
228 : #endif
229 :
230 0 : #define LIVE_TABLE_(n) FD_EXPAND_THEN_CONCAT3(LIVE_TABLE_NAME,_,n)
231 :
232 : #include <stddef.h> // offsetof
233 :
234 : #define LIVE_TABLE_COL_ENTRY(col_id, field, lt_func) \
235 : (LIVE_TABLE_(private_column_t)){ .col_name = col_id, .off = offsetof( LIVE_TABLE_ROW_T , field ), .lt = lt_func }
236 :
237 0 : #define LIVE_TABLE_COL_ARRAY(...) { __VA_ARGS__ }
238 :
239 : #ifndef LIVE_TABLE_IMPL_STYLE
240 : #define LIVE_TABLE_IMPL_STYLE 0
241 : #endif
242 :
243 : #if LIVE_TABLE_IMPL_STYLE==0
244 : #define LIVE_TABLE_STATIC static FD_FN_UNUSED
245 : #else
246 : #define LIVE_TABLE_STATIC
247 : #endif
248 :
249 : #include "../../util/log/fd_log.h" /* failure logs */
250 : #include "../../util/bits/fd_bits.h"
251 : #include "../../util/math/fd_stat.h"
252 :
253 : #if LIVE_TABLE_IMPL_STYLE!=2 /* need structures, prototypes and inlines */
254 : struct LIVE_TABLE_(private_column) {
255 : char * col_name; /* cstr */
256 : ulong off;
257 : int (* const lt)(void const * a, void const * b);
258 : };
259 : typedef struct LIVE_TABLE_(private_column) LIVE_TABLE_(private_column_t);
260 :
261 : struct LIVE_TABLE_(sort_key) {
262 : ulong col[ LIVE_TABLE_COLUMN_CNT ];
263 : int dir[ LIVE_TABLE_COLUMN_CNT ];
264 : };
265 : typedef struct LIVE_TABLE_(sort_key) LIVE_TABLE_(sort_key_t);
266 :
267 : /* Global state is ugly. We only have one type of treap and they all
268 : share the same static comparison function, but we need that function
269 : to change dynamically. The simplest way to do this is to have the
270 : function reference changing global state. Not ideal but the
271 : alternative is to change the implementation of the treap template.
272 :
273 : This variable never needs to be shared across compile units. All of
274 : the functions in this template do not retain interest in this
275 : variable after each call. */
276 : static ulong LIVE_TABLE_(private_active_sort_key_idx) = ULONG_MAX;
277 :
278 : static int
279 0 : LIVE_TABLE_(private_row_lt)(LIVE_TABLE_ROW_T const * a, LIVE_TABLE_ROW_T const * b) {
280 0 : FD_TEST( LIVE_TABLE_(private_active_sort_key_idx) < LIVE_TABLE_MAX_SORT_KEY_CNT );
281 :
282 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) ];
283 :
284 0 : for( ulong i=0UL; i<LIVE_TABLE_COLUMN_CNT; i++ ) {
285 0 : if( FD_LIKELY( active_sort_key->dir[ i ]==0 ) ) continue;
286 :
287 0 : LIVE_TABLE_(private_column_t) cols[ LIVE_TABLE_COLUMN_CNT ] = LIVE_TABLE_COLUMNS;
288 :
289 0 : void * col_a = ((uchar *)a) + cols[ active_sort_key->col[ i ] ].off;
290 0 : void * col_b = ((uchar *)b) + cols[ active_sort_key->col[ i ] ].off;
291 0 : int a_lt_b = cols[ active_sort_key->col[ i ] ].lt(col_a, col_b);
292 0 : int b_lt_a = cols[ active_sort_key->col[ i ] ].lt(col_b, col_a);
293 :
294 0 : if( FD_UNLIKELY( !(a_lt_b || b_lt_a) ) ) continue; /* equal */
295 0 : return fd_int_if( active_sort_key->dir[ i ]==1, a_lt_b, !a_lt_b );
296 0 : }
297 :
298 0 : return 0; /* all columns equal */
299 0 : }
300 :
301 : #define TREAP_NAME LIVE_TABLE_(private_treap)
302 : #define TREAP_T LIVE_TABLE_ROW_T
303 : #define TREAP_QUERY_T void * /* query isn't used */
304 : #define TREAP_CMP(q,e) (__extension__({ (void)(q); (void)(e); -1; })) /* which means we don't need to give a real
305 : implementation to cmp either */
306 0 : #define TREAP_LT(e0,e1) (LIVE_TABLE_(private_row_lt)( (e0), (e1) ))
307 : #define TREAP_OPTIMIZE_ITERATION 1
308 0 : #define TREAP_PARENT LIVE_TABLE_TREAP[ LIVE_TABLE_(private_active_sort_key_idx) ].parent
309 0 : #define TREAP_LEFT LIVE_TABLE_TREAP[ LIVE_TABLE_(private_active_sort_key_idx) ].left
310 0 : #define TREAP_RIGHT LIVE_TABLE_TREAP[ LIVE_TABLE_(private_active_sort_key_idx) ].right
311 0 : #define TREAP_NEXT LIVE_TABLE_TREAP[ LIVE_TABLE_(private_active_sort_key_idx) ].next
312 0 : #define TREAP_PREV LIVE_TABLE_TREAP[ LIVE_TABLE_(private_active_sort_key_idx) ].prev
313 0 : #define TREAP_PRIO LIVE_TABLE_TREAP[ LIVE_TABLE_(private_active_sort_key_idx) ].prio
314 : #define TREAP_IMPL_STYLE LIVE_TABLE_IMPL_STYLE
315 : #include "../../util/tmpl/fd_treap.c"
316 :
317 : #define DLIST_NAME LIVE_TABLE_(private_dlist)
318 : #define DLIST_ELE_T LIVE_TABLE_ROW_T
319 0 : #define DLIST_PREV LIVE_TABLE_DLIST.prev
320 0 : #define DLIST_NEXT LIVE_TABLE_DLIST.next
321 : #include "../../util/tmpl/fd_dlist.c"
322 :
323 : struct LIVE_TABLE_() {
324 : LIVE_TABLE_(private_dlist_t) * dlist;
325 :
326 : LIVE_TABLE_(private_treap_t) * treaps [ LIVE_TABLE_MAX_SORT_KEY_CNT ];
327 : void * treaps_shmem [ LIVE_TABLE_MAX_SORT_KEY_CNT ];
328 : int treaps_is_active[ LIVE_TABLE_MAX_SORT_KEY_CNT ];
329 :
330 : ulong count;
331 : ulong max_rows;
332 : LIVE_TABLE_(sort_key_t) sort_keys[ LIVE_TABLE_MAX_SORT_KEY_CNT ];
333 : };
334 : typedef struct LIVE_TABLE_() LIVE_TABLE_(t);
335 :
336 : typedef LIVE_TABLE_(private_treap_fwd_iter_t) LIVE_TABLE_(fwd_iter_t);
337 :
338 : FD_PROTOTYPES_BEGIN
339 :
340 : LIVE_TABLE_STATIC void LIVE_TABLE_(seed)( LIVE_TABLE_ROW_T * pool, ulong rows_max, ulong seed );
341 :
342 : LIVE_TABLE_STATIC FD_FN_CONST ulong LIVE_TABLE_(align) ( void );
343 : LIVE_TABLE_STATIC FD_FN_CONST ulong LIVE_TABLE_(footprint)( ulong rows_max );
344 : LIVE_TABLE_STATIC void * LIVE_TABLE_(new) ( void * shmem, ulong rows_max );
345 : LIVE_TABLE_STATIC LIVE_TABLE_(t) * LIVE_TABLE_(join) ( void * shtable );
346 : LIVE_TABLE_STATIC void * LIVE_TABLE_(leave) ( LIVE_TABLE_(t) * join );
347 : LIVE_TABLE_STATIC void * LIVE_TABLE_(delete) ( void * shtable );
348 :
349 : LIVE_TABLE_STATIC LIVE_TABLE_ROW_T * LIVE_TABLE_(idx_insert)( LIVE_TABLE_(t) * join, ulong pool_idx, LIVE_TABLE_ROW_T * pool );
350 : LIVE_TABLE_STATIC void LIVE_TABLE_(idx_remove)( LIVE_TABLE_(t) * join, ulong pool_idx, LIVE_TABLE_ROW_T * pool );
351 :
352 : 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 );
353 : LIVE_TABLE_STATIC 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 );
354 :
355 : LIVE_TABLE_STATIC int LIVE_TABLE_(verify)( LIVE_TABLE_(t) const * table, LIVE_TABLE_ROW_T const * pool );
356 : LIVE_TABLE_STATIC int LIVE_TABLE_(verify_sort_key)( LIVE_TABLE_(sort_key_t) const * sort_key );
357 :
358 : LIVE_TABLE_STATIC void
359 : LIVE_TABLE_(sort_key_remove)( LIVE_TABLE_(t) * join, LIVE_TABLE_(sort_key_t) const * sort_key );
360 :
361 : /* inlines */
362 :
363 0 : FD_FN_CONST static inline ulong LIVE_TABLE_(idx_null) ( void ) { return LIVE_TABLE_(private_treap_idx_null)(); }
364 0 : FD_FN_CONST static inline LIVE_TABLE_ROW_T * LIVE_TABLE_(ele_null) ( void ) { return LIVE_TABLE_(private_treap_ele_null)(); }
365 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)(); }
366 :
367 0 : FD_FN_CONST static inline int LIVE_TABLE_(idx_is_null)( ulong i ) { return LIVE_TABLE_(private_treap_idx_is_null)( i ); }
368 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 ); }
369 :
370 : FD_FN_CONST static inline ulong
371 0 : LIVE_TABLE_(idx)( LIVE_TABLE_ROW_T const * e, LIVE_TABLE_ROW_T const * pool ) { return LIVE_TABLE_(private_treap_idx)( e, pool ); }
372 :
373 : FD_FN_CONST static inline LIVE_TABLE_ROW_T *
374 0 : LIVE_TABLE_(ele)( ulong i, LIVE_TABLE_ROW_T * pool ) { return LIVE_TABLE_(private_treap_ele)( i, pool ); }
375 :
376 : FD_FN_CONST static inline LIVE_TABLE_ROW_T const *
377 0 : LIVE_TABLE_(ele_const)( ulong i, LIVE_TABLE_ROW_T const * pool ) { return LIVE_TABLE_(private_treap_ele_const)( i, pool ); }
378 :
379 : FD_FN_CONST static inline ulong
380 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 ); }
381 :
382 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 ); }
383 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 ); }
384 :
385 : FD_FN_CONST static inline LIVE_TABLE_(fwd_iter_t)
386 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 ); }
387 :
388 : FD_FN_CONST static inline LIVE_TABLE_ROW_T *
389 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 ); }
390 :
391 : FD_FN_CONST static inline LIVE_TABLE_ROW_T const *
392 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 ); }
393 :
394 : FD_FN_CONST static inline int
395 0 : LIVE_TABLE_(fwd_iter_done)( LIVE_TABLE_(fwd_iter_t) iter ) { return LIVE_TABLE_(private_treap_fwd_iter_done)( iter ); }
396 :
397 : FD_FN_CONST static inline ulong
398 0 : LIVE_TABLE_(fwd_iter_idx)( LIVE_TABLE_(fwd_iter_t) iter ) { return LIVE_TABLE_(private_treap_fwd_iter_idx)( iter ); }
399 :
400 : static inline LIVE_TABLE_ROW_T *
401 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 ); }
402 :
403 : static inline void
404 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 ); }
405 :
406 0 : FD_FN_PURE static inline ulong LIVE_TABLE_(ele_cnt)( LIVE_TABLE_(t) * join ) { return join->count; }
407 0 : FD_FN_PURE static inline ulong LIVE_TABLE_(ele_max)( LIVE_TABLE_(t) * join ) { return join->max_rows; }
408 0 : FD_FN_PURE static inline ulong LIVE_TABLE_(col_cnt)( void ) { return LIVE_TABLE_COLUMN_CNT; }
409 :
410 : FD_FN_PURE static inline ulong
411 0 : LIVE_TABLE_(active_sort_key_cnt)( LIVE_TABLE_(t) * join ) {
412 0 : ulong count = 0UL;
413 0 : for( ulong i=0; i<LIVE_TABLE_MAX_SORT_KEY_CNT; i++ ) {
414 0 : if( FD_LIKELY( join->treaps_is_active[ i ] ) ) count++;
415 0 : }
416 0 : return count;
417 0 : }
418 :
419 : FD_FN_CONST static inline ulong
420 0 : LIVE_TABLE_(col_name_to_idx)( LIVE_TABLE_(t) * join, char const * col_name ) {
421 0 : (void)join;
422 0 : LIVE_TABLE_(private_column_t) cols[ LIVE_TABLE_COLUMN_CNT ] = LIVE_TABLE_COLUMNS;
423 0 : for( ulong i=0; i < LIVE_TABLE_COLUMN_CNT; i++ ) {
424 0 : if( FD_UNLIKELY( strcmp( cols[ i ].col_name, col_name ) ) ) continue;
425 0 : return i;
426 0 : }
427 0 : return ULONG_MAX;
428 0 : }
429 :
430 : FD_FN_CONST static inline char const *
431 0 : LIVE_TABLE_(col_idx_to_name)( LIVE_TABLE_(t) * join, ulong col_idx ) {
432 0 : (void)join;
433 0 : if( FD_UNLIKELY( col_idx>=LIVE_TABLE_COLUMN_CNT ) ) return NULL;
434 0 : LIVE_TABLE_(private_column_t) cols[ LIVE_TABLE_COLUMN_CNT ] = LIVE_TABLE_COLUMNS;
435 0 : return cols[ col_idx ].col_name;
436 0 : }
437 :
438 : static inline void
439 0 : LIVE_TABLE_(private_sort_key_print)( LIVE_TABLE_(sort_key_t) const * sort_key ) {
440 0 : char out[ 4096 ];
441 0 : char * p = fd_cstr_init( out );
442 :
443 0 : p = fd_cstr_append_printf( p, "cols: %lu", sort_key->col[ 0 ] );
444 0 : for( ulong i=1UL; i<LIVE_TABLE_COLUMN_CNT; i++ ) {
445 0 : p = fd_cstr_append_printf( p, ",%lu", sort_key->col[ i ] );
446 0 : }
447 0 : p = fd_cstr_append_printf( p, "\ndir: %d", sort_key->dir[ 0 ] );
448 0 : for( ulong i=1UL; i<LIVE_TABLE_COLUMN_CNT; i++ ) {
449 0 : p = fd_cstr_append_printf( p, ",%d", sort_key->dir[ i ] );
450 0 : }
451 0 : fd_cstr_fini( p );
452 0 : FD_LOG_WARNING(( "%s", out ));
453 0 : }
454 :
455 : static inline void
456 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 ) {
457 0 : fd_memcpy( &join->sort_keys[ sort_key_idx ], sort_key, sizeof(LIVE_TABLE_(sort_key_t)) );
458 :
459 0 : LIVE_TABLE_(private_active_sort_key_idx) = sort_key_idx;
460 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 ) );
461 0 : join->treaps_is_active[ sort_key_idx ] = 1;
462 : #if FD_TMPL_USE_HANDHOLDING
463 : FD_TEST( sort_key_idx<LIVE_TABLE_MAX_SORT_KEY_CNT );
464 : FD_TEST( join->treaps[ sort_key_idx ] );
465 : FD_TEST( !LIVE_TABLE_(private_treap_verify)( join->treaps[ sort_key_idx ], pool ) );
466 : #endif
467 :
468 0 : for( LIVE_TABLE_(private_dlist_iter_t) iter = LIVE_TABLE_(private_dlist_iter_fwd_init)( join->dlist, pool );
469 0 : !LIVE_TABLE_(private_dlist_iter_done)( iter, join->dlist, pool );
470 0 : iter = LIVE_TABLE_(private_dlist_iter_fwd_next)( iter, join->dlist, pool ) ) {
471 0 : ulong pool_idx = LIVE_TABLE_(private_dlist_iter_idx)( iter, join->dlist, pool );
472 0 : LIVE_TABLE_(private_treap_idx_insert)( join->treaps[ sort_key_idx ], pool_idx, pool );
473 0 : }
474 :
475 : #if FD_TMPL_USE_HANDHOLDING
476 : FD_TEST( !LIVE_TABLE_(private_treap_verify)( join->treaps[ sort_key_idx ], pool ) );
477 : #endif
478 0 : }
479 :
480 : static inline ulong
481 0 : LIVE_TABLE_(private_query_sort_key)( LIVE_TABLE_(t) * join, LIVE_TABLE_(sort_key_t) const * sort_key ) {
482 0 : for( ulong i=0; i<LIVE_TABLE_MAX_SORT_KEY_CNT; i++ ) {
483 0 : if( FD_UNLIKELY( !join->treaps_is_active[ i ] ) ) continue;
484 0 : int equal = 1;
485 0 : ulong j = 0;
486 0 : ulong k = 0;
487 0 : do {
488 : /* columns with dir=0 don't actually count, they're ignored */
489 0 : if( FD_UNLIKELY( j<LIVE_TABLE_COLUMN_CNT-1UL && join->sort_keys[ i ].dir[ j ]==0 ) ) {
490 0 : j++;
491 0 : continue;
492 0 : }
493 0 : if( FD_UNLIKELY( k<LIVE_TABLE_COLUMN_CNT-1UL && sort_key->dir[ k ]==0 ) ) {
494 0 : k++;
495 0 : continue;
496 0 : }
497 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 ]) ) ) {
498 0 : equal = 0;
499 0 : break;
500 0 : }
501 0 : if( FD_LIKELY( j<LIVE_TABLE_COLUMN_CNT-1UL ) ) j++;
502 0 : if( FD_LIKELY( k<LIVE_TABLE_COLUMN_CNT-1UL ) ) k++; /* todo ... test edge case */
503 0 : } while( !(j==LIVE_TABLE_COLUMN_CNT-1UL && k==LIVE_TABLE_COLUMN_CNT-1UL) );
504 0 : if( FD_LIKELY( !equal ) ) continue;
505 0 : return i;
506 0 : }
507 :
508 0 : return ULONG_MAX;
509 0 : }
510 :
511 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 ) {
512 0 : LIVE_TABLE_(private_column_t) cols[ LIVE_TABLE_COLUMN_CNT ] = LIVE_TABLE_COLUMNS;
513 0 : for( ulong i=0UL; i<LIVE_TABLE_COLUMN_CNT; i++ ) {
514 0 : if( FD_LIKELY( sort_key->dir[ i ]==0 ) ) continue;
515 :
516 0 : void * col_a = ((uchar *)e0) + cols[ sort_key->col[ i ] ].off;
517 0 : void * col_b = ((uchar *)e1) + cols[ sort_key->col[ i ] ].off;
518 0 : int a_lt_b = cols[ sort_key->col[ i ] ].lt( col_a, col_b );
519 0 : int b_lt_a = cols[ sort_key->col[ i ] ].lt( col_b, col_a );
520 :
521 0 : if( FD_UNLIKELY( !(a_lt_b || b_lt_a) ) ) continue;
522 0 : return fd_int_if( sort_key->dir[ i ]==1, a_lt_b, !a_lt_b );
523 0 : }
524 :
525 0 : return 0;
526 0 : }
527 :
528 : #endif /* LIVE_TABLE_IMPL_STYLE!=2 */
529 :
530 : #if LIVE_TABLE_IMPL_STYLE!=1 /* need implementations */
531 :
532 : LIVE_TABLE_STATIC ulong
533 0 : LIVE_TABLE_(align)(void) {
534 0 : ulong a = 1UL;
535 0 : a = fd_ulong_max( a, alignof(LIVE_TABLE_(t)) );
536 0 : a = fd_ulong_max( a, LIVE_TABLE_(private_treap_align)() );
537 0 : a = fd_ulong_max( a, LIVE_TABLE_(private_dlist_align)() );
538 0 : a = fd_ulong_max( a, 128UL );
539 0 : FD_TEST( fd_ulong_pow2_up( a )==a );
540 0 : return a;
541 0 : }
542 :
543 : LIVE_TABLE_STATIC ulong
544 0 : LIVE_TABLE_(footprint)( ulong max_rows ) {
545 0 : ulong l = FD_LAYOUT_INIT;
546 0 : l = FD_LAYOUT_APPEND( l, alignof(LIVE_TABLE_(t)), sizeof(LIVE_TABLE_(t)) );
547 0 : l = FD_LAYOUT_APPEND( l, LIVE_TABLE_(private_dlist_align)(), LIVE_TABLE_(private_dlist_footprint)() );
548 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 ) );
549 0 : return FD_LAYOUT_FINI( l, LIVE_TABLE_(align)() );
550 0 : }
551 :
552 : LIVE_TABLE_STATIC void *
553 0 : LIVE_TABLE_(new)( void * shmem, ulong max_rows ) {
554 0 : if( !shmem ) {
555 0 : FD_LOG_WARNING(( "NULL shmem" ));
556 0 : return NULL;
557 0 : }
558 :
559 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, LIVE_TABLE_(align)() ) ) ) {
560 0 : FD_LOG_WARNING(( "misaligned shmem" ));
561 0 : return NULL;
562 0 : }
563 :
564 0 : FD_SCRATCH_ALLOC_INIT( l, shmem );
565 0 : LIVE_TABLE_(t) * _table = FD_SCRATCH_ALLOC_APPEND( l, alignof(LIVE_TABLE_(t)), sizeof(LIVE_TABLE_(t)) );
566 0 : void * _dlist = FD_SCRATCH_ALLOC_APPEND( l, LIVE_TABLE_(private_dlist_align)(), LIVE_TABLE_(private_dlist_footprint)() );
567 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 ) );
568 0 : FD_SCRATCH_ALLOC_FINI( l, LIVE_TABLE_(align)() );
569 :
570 0 : _table->dlist = LIVE_TABLE_(private_dlist_join)( LIVE_TABLE_(private_dlist_new)( _dlist ) );
571 0 : _table->max_rows = max_rows;
572 0 : _table->count = 0UL;
573 0 : for( ulong i=0; i<LIVE_TABLE_MAX_SORT_KEY_CNT; i++ ) _table->treaps_is_active[ i ] = 0;
574 :
575 0 : LIVE_TABLE_(private_column_t) cols[ LIVE_TABLE_COLUMN_CNT ] = LIVE_TABLE_COLUMNS;
576 0 : FD_TEST( LIVE_TABLE_COLUMN_CNT == sizeof(cols)/sizeof(LIVE_TABLE_(private_column_t)) );
577 :
578 : /* live_table_treap_new( ... ) not called since all treaps start as inactive */
579 :
580 0 : return _table;
581 0 : }
582 :
583 : FD_PROTOTYPES_END
584 :
585 : LIVE_TABLE_STATIC void
586 0 : LIVE_TABLE_(seed)( LIVE_TABLE_ROW_T * pool, ulong rows_max, ulong seed ) {
587 0 : for( ulong i=0; i<LIVE_TABLE_MAX_SORT_KEY_CNT; i++ ) {
588 0 : LIVE_TABLE_(private_active_sort_key_idx) = i;
589 0 : LIVE_TABLE_(private_treap_seed)( pool, rows_max, seed ); /* set random priorities */
590 0 : }
591 0 : }
592 :
593 : LIVE_TABLE_STATIC LIVE_TABLE_(t) *
594 0 : LIVE_TABLE_(join)( void * shtable ) {
595 0 : if( !shtable ) {
596 0 : FD_LOG_WARNING(( "NULL shtable" ));
597 0 : return NULL;
598 0 : }
599 :
600 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shtable, LIVE_TABLE_(align)() ) ) ) {
601 0 : FD_LOG_WARNING(( "misaligned shtable" ));
602 0 : return NULL;
603 0 : }
604 :
605 0 : return (LIVE_TABLE_(t) *)shtable;
606 0 : }
607 :
608 : LIVE_TABLE_STATIC void *
609 0 : LIVE_TABLE_(leave)( LIVE_TABLE_(t) * join ) {
610 0 : if( FD_UNLIKELY( !join ) ) {
611 0 : FD_LOG_WARNING(( "NULL join" ));
612 0 : return NULL;
613 0 : }
614 :
615 0 : LIVE_TABLE_(private_dlist_delete)( LIVE_TABLE_(private_dlist_leave)( join->dlist ) );
616 0 : for( ulong i=0; i<LIVE_TABLE_MAX_SORT_KEY_CNT; i++ ) {
617 0 : if( FD_LIKELY( !join->treaps_is_active[ i ] ) ) continue;
618 0 : LIVE_TABLE_(private_active_sort_key_idx) = i;
619 0 : FD_TEST( LIVE_TABLE_(private_treap_delete)( LIVE_TABLE_(private_treap_leave)( join->treaps[ i ] ) ) );
620 0 : }
621 :
622 0 : return (void *)join;
623 0 : }
624 :
625 : LIVE_TABLE_STATIC void *
626 0 : LIVE_TABLE_(delete)( void * shtable ) {
627 0 : LIVE_TABLE_(t) * table = (LIVE_TABLE_(t) *)shtable;
628 :
629 0 : if( FD_UNLIKELY( !table ) ) {
630 0 : FD_LOG_WARNING(( "NULL shtable" ));
631 0 : return NULL;
632 0 : }
633 :
634 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)table, alignof(LIVE_TABLE_(t)) ) ) ) {
635 0 : FD_LOG_WARNING(( "misaligned shtable" ));
636 0 : return NULL;
637 0 : }
638 :
639 0 : return (void *)table;
640 0 : }
641 :
642 : LIVE_TABLE_STATIC void
643 0 : LIVE_TABLE_(idx_remove)( LIVE_TABLE_(t) * join, ulong pool_idx, LIVE_TABLE_ROW_T * pool ) {
644 : #if FD_TMPL_USE_HANDHOLDING
645 : FD_TEST( !LIVE_TABLE_(private_treap_idx_is_null)( pool_idx ) );
646 : FD_TEST( join->count >= 1UL );
647 : #endif
648 : /* remove from all active treaps */
649 0 : for( ulong i=0; i<LIVE_TABLE_MAX_SORT_KEY_CNT; i++ ) {
650 0 : if( FD_LIKELY( !join->treaps_is_active[ i ] ) ) continue;
651 0 : LIVE_TABLE_(private_active_sort_key_idx) = i;
652 0 : LIVE_TABLE_(private_treap_idx_remove)( join->treaps[ i ], pool_idx, pool );
653 0 : }
654 0 : LIVE_TABLE_(private_dlist_idx_remove)( join->dlist, pool_idx, pool );
655 0 : join->count--;
656 0 : }
657 :
658 : LIVE_TABLE_STATIC LIVE_TABLE_ROW_T *
659 0 : LIVE_TABLE_(idx_insert)( LIVE_TABLE_(t) * join, ulong pool_idx, LIVE_TABLE_ROW_T * pool ) {
660 0 : pool[ pool_idx ].LIVE_TABLE_SORT_KEYS = (ulong)(&join->sort_keys);
661 : #if FD_TMPL_USE_HANDHOLDING
662 : FD_TEST( !LIVE_TABLE_(private_treap_idx_is_null)( pool_idx ) );
663 : #endif
664 : /* insert into all active treaps */
665 0 : for( ulong i=0; i<LIVE_TABLE_MAX_SORT_KEY_CNT; i++ ) {
666 0 : if( FD_LIKELY( !join->treaps_is_active[ i ] ) ) continue;
667 0 : LIVE_TABLE_(private_active_sort_key_idx) = i;
668 0 : LIVE_TABLE_(private_treap_idx_insert)( join->treaps[ i ], pool_idx, pool );
669 0 : }
670 0 : LIVE_TABLE_(private_dlist_idx_push_tail)( join->dlist, pool_idx, pool );
671 0 : join->count++;
672 :
673 0 : return pool + pool_idx;
674 0 : }
675 :
676 : LIVE_TABLE_STATIC void
677 0 : LIVE_TABLE_(sort_key_remove)( LIVE_TABLE_(t) * join, LIVE_TABLE_(sort_key_t) const * sort_key ) {
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 ) ) return;
680 :
681 0 : LIVE_TABLE_(private_active_sort_key_idx) = sort_key_idx;
682 : #if FD_TMPL_USE_HANDHOLDING
683 : FD_TEST( sort_key_idx<LIVE_TABLE_MAX_SORT_KEY_CNT );
684 : FD_TEST( join->treaps[ sort_key_idx ] );
685 : #endif
686 0 : join->treaps_is_active[ sort_key_idx ] = 0;
687 0 : LIVE_TABLE_(private_treap_delete)( LIVE_TABLE_(private_treap_leave)( join->treaps[ sort_key_idx ] ) );
688 0 : join->treaps[ sort_key_idx ] = NULL;
689 0 : }
690 :
691 : LIVE_TABLE_STATIC LIVE_TABLE_(fwd_iter_t)
692 0 : LIVE_TABLE_(fwd_iter_init)( LIVE_TABLE_(t) * join, LIVE_TABLE_(sort_key_t) const * sort_key, LIVE_TABLE_ROW_T * pool ) {
693 0 : ulong sort_key_idx = LIVE_TABLE_(private_query_sort_key)( join, sort_key );
694 0 : if( FD_UNLIKELY( sort_key_idx==ULONG_MAX ) ) {
695 0 : for( ulong i=0UL; i<LIVE_TABLE_MAX_SORT_KEY_CNT; i++ ) {
696 0 : if( FD_UNLIKELY( join->treaps_is_active[ i ] ) ) continue;
697 0 : sort_key_idx = i;
698 0 : LIVE_TABLE_(private_sort_key_create)( join, i, sort_key, pool );
699 0 : break;
700 0 : }
701 0 : }
702 0 : LIVE_TABLE_(private_active_sort_key_idx) = sort_key_idx;
703 : #if FD_TMPL_USE_HANDHOLDING
704 : FD_TEST( sort_key_idx!=ULONG_MAX );
705 : FD_TEST( join->treaps_is_active[ sort_key_idx ] );
706 : #endif
707 0 : return LIVE_TABLE_(private_treap_fwd_iter_init)( join->treaps[ sort_key_idx ], pool );
708 0 : }
709 :
710 : LIVE_TABLE_STATIC int
711 0 : LIVE_TABLE_(verify_sort_key)( LIVE_TABLE_(sort_key_t) const * key ) {
712 0 : LIVE_TABLE_(sort_key_t) tmp_key[ 1 ];
713 0 : fd_memcpy( tmp_key, key, sizeof(LIVE_TABLE_(sort_key_t)) );
714 0 : fd_sort_up_ulong_insert( tmp_key->col, LIVE_TABLE_COLUMN_CNT );
715 :
716 0 : for( ulong j=0UL; j<LIVE_TABLE_COLUMN_CNT; j++ ) {
717 0 : if( FD_UNLIKELY( tmp_key->col[ j ]!=j || tmp_key->dir[ j ] > 1 || tmp_key->dir[ j ] < -1 ) ) {
718 0 : return 0;
719 0 : }
720 0 : }
721 :
722 0 : return 1;
723 0 : }
724 :
725 : LIVE_TABLE_STATIC int
726 0 : LIVE_TABLE_(verify)( LIVE_TABLE_(t) const * join, LIVE_TABLE_ROW_T const * pool ) {
727 0 : ulong prev_sk_idx = LIVE_TABLE_(private_active_sort_key_idx);
728 0 : for( ulong i=0UL; i<LIVE_TABLE_MAX_SORT_KEY_CNT; i++ ) {
729 0 : if( FD_LIKELY( !join->treaps_is_active[ i ] ) ) continue;
730 :
731 0 : LIVE_TABLE_(private_active_sort_key_idx) = i;
732 0 : if( FD_UNLIKELY( LIVE_TABLE_(private_treap_verify)( join->treaps[ i ], pool ) ) ) {
733 0 : FD_LOG_CRIT(("failed verify"));
734 0 : }
735 :
736 0 : if( FD_UNLIKELY( !LIVE_TABLE_(verify_sort_key)( &join->sort_keys[ i ] ) ) ) {
737 0 : LIVE_TABLE_(private_sort_key_print)( &join->sort_keys[ i ] );
738 0 : FD_LOG_CRIT(( "bad sort key %lu", i ));
739 0 : }
740 0 : }
741 0 : LIVE_TABLE_(private_active_sort_key_idx) = prev_sk_idx;
742 0 : return 0;
743 0 : }
744 :
745 : #endif /* LIVE_TABLE_IMPL_STYLE!=1 */
746 :
747 : #undef LIVE_TABLE_NAME
748 : #undef LIVE_TABLE_COLUMN_CNT
749 : #undef LIVE_TABLE_MAX_SORT_KEY_CNT
750 : #undef LIVE_TABLE_ROW_T
751 : #undef LIVE_TABLE_COLUMNS
752 : #undef LIVE_TABLE_SORT_KEYS
753 : #undef LIVE_TABLE_TREAP
754 : #undef LIVE_TABLE_DLIST
755 : #undef LIVE_TABLE_
756 : #undef LIVE_TABLE_COL_ENTRY
757 : #undef LIVE_TABLE_COL_ARRAY
758 : #undef LIVE_TABLE_IMPL_STYLE
759 : #undef LIVE_TABLE_STATIC
|
