Line data Source code
1 : /* Declare vectors of bounded run-time maximum size suitable for 2 : persistent and IPC usage. Designed for POD types that have a trivial 3 : copy operator. Typical usage: 4 : 5 : #define VEC_NAME myvec 6 : #define VEC_T myvec_t 7 : #include "util/tmpl/fd_vec.c" 8 : 9 : will declare the following static inline APIs as a header only style 10 : library in the compilation unit: 11 : 12 : // align/footprint - Return the alignment/footprint required for a 13 : // memory region to be used as vector that can hold up to max 14 : // events. footprint returns 0 if max is so large that the 15 : // footprint would overflow ULONG_MAX. 16 : // 17 : // new - Format a memory region pointed to by shmem into a myvec 18 : // vector. Assumes shmem points to a region with the required 19 : // alignment and footprint not in use by anything else. Caller is 20 : // not joined on return. Returns shmem on success or NULL on 21 : // failure (e.g. shmem or max are obviously bad). 22 : // 23 : // join - Join a myvec vector. Assumes shvec points at a region 24 : // formatted as an vector. Returns a pointer in the caller's 25 : // address space to a memory region indexed [0,max) where elements 26 : // [0,cnt) are currently in use on success and NULL on failure 27 : // (e.g. shmem is obviously bad). THIS IS NOT JUST A SIMPLE CAST 28 : // OF SHVEC. 29 : // 30 : // leave - Leave a myvec vector. Assumes join points to a current 31 : // local join. Returns a pointer to the shared memory region the 32 : // join on success and NULL on failure. THIS IS NOT JUST A SIMPLE 33 : // CAST OF JOIN. 34 : // 35 : // delete - Unformat a memory region used as myvec vector. Assumes 36 : // myvec vector points to a formatted region with no current joins. 37 : // Returns a pointer to the unformatted memory region. 38 : 39 : ulong myvec_align ( void ); 40 : ulong myvec_footprint( ulong max ); 41 : void * myvec_new ( void * shmem, ulong max ); 42 : myvec_t * myvec_join ( void * shvec ); 43 : void * myvec_leave ( myvec_t * join ); 44 : void * myvec_delete ( void * shvec ); 45 : 46 : // All the below APIs assume join is a current local join. 47 : 48 : // myvec_max returns the maximum number of elements in a myvec vector. 49 : // myvec_cnt returns the current number of elements, in [0,max] 50 : // myvec_free = max - cnt 51 : // myvec_is_empty = (cnt==0) 52 : // myvec_is_full = (cnt==max) 53 : 54 : ulong myvec_max( myvec_t const * join ); 55 : ulong myvec_cnt ( myvec_t const * join ); 56 : ulong myvec_free ( myvec_t const * join ); 57 : int myvec_is_empty( myvec_t const * join ); 58 : int myvec_is_full ( myvec_t const * join ); 59 : 60 : // myvec_expand increases the number of elements in a vector by 61 : // delta. The new elements will be indexed [cnt,cnt+delta) Returns 62 : // a pointer to the delta (uninitialized) new elements. IMPORTANT! 63 : // AS THIS IS USED IN HPC CONTEXTS, ASSUMES CALLER KNOWS THERE ARE 64 : // DELTA AT LEAST DELTA ELEMENTS FREE (I.E. DELTA IS IN [0,FREE]. 65 : // 66 : // myvec_contract decreases the number of elements in a vector by 67 : // delta. The elements removed are indexed [cnt-delta,cnt). 68 : // Returns a pointer to delta removed elements. IMPORTANT! AS 69 : // THIS IS USED IN HPC CONTEXTS, ASSUMES CALLER KNOWS THERE ARE 70 : // DELTA AT LEAST DELTA ELEMENTS PRESENT (I.E. DELTA IS IN 71 : // [0,CNT]. 72 : 73 : myvec_t * myvec_expand ( myvec_t * join, ulong delta ); 74 : myvec_t * myvec_contract( myvec_t * join, ulong delta ); 75 : 76 : // myvec_remove removes the element at index by backfilling the 77 : // last element into element idx. This is an O(1) operation. 78 : // Returns join. IMPORTANT! AS THIS IS USED IN HPC CONTEXTS, 79 : // ASSUMES CALLER KNOWS IDX IS A CURRENT ELEMENT. THAT IS, IDX IS 80 : // IN [0,CNT). 81 : 82 : myvec_t * myvec_remove( myvec_t * join, ulong idx ); 83 : 84 : // myvec_remove_compact remove element at idx by compaction. While 85 : // this is preserves operating, this is an O(cnt-idx-1) operation 86 : // and it is very easily to accidentally create O(N^2) 87 : // if using compaction. IMPORTANT! AS THIS IS USED IN HPC 88 : // CONTEXTS, ASSUMES CALLER KNOWS IDX IS A CURRENT ELEMENT. THAT 89 : // IS, IDX IS IN [0,CNT). 90 : 91 : myvec_t * myvec_remove_compact( myvec_t * join, ulong idx ); 92 : 93 : // TODO: CONSIDER ADDING OTHER APIS LIKE SHUFFLE AND WHAT NOT? 94 : 95 : You can do this as often as you like in a compilation unit to get 96 : different types of vectors. Since it is all static inline, it is 97 : fine to do this in a header too. Additional options to fine tune 98 : this are detailed below. */ 99 : 100 : #ifndef VEC_NAME 101 : #define "Define VEC_NAME" 102 : #endif 103 : 104 : #ifndef VEC_T 105 : #define "Define VEC_T" 106 : #endif 107 : 108 : // TODO: CONSIDER LETTING USER SPECIFY COPY AND MOVE? 109 : 110 27000042 : #define VEC_(n) FD_EXPAND_THEN_CONCAT3(VEC_NAME,_,n) 111 : 112 : struct VEC_(private) { 113 : ulong max; /* Arbitrary */ 114 : ulong cnt; /* In [0,max) */ 115 : }; 116 : 117 : typedef struct VEC_(private) VEC_(private_t); 118 : 119 : FD_FN_CONST static inline VEC_(private_t) * 120 2999994 : VEC_(private)( VEC_T * join ) { 121 2999994 : return (VEC_(private_t) *)(((ulong)join) - sizeof(VEC_(private_t))); 122 2999994 : } 123 : 124 : FD_FN_CONST static inline VEC_(private_t) const * 125 15000000 : VEC_(private_const)( VEC_T const * join ) { 126 15000000 : return (VEC_(private_t) const *)(((ulong)join) - sizeof(VEC_(private_t))); 127 15000000 : } 128 : 129 : FD_FN_CONST static inline ulong 130 0 : VEC_(align)( void ) { 131 0 : return fd_ulong_max( alignof(VEC_T), 128UL ); 132 0 : } 133 : 134 : FD_FN_CONST static inline ulong 135 21 : VEC_(private_meta_footprint)( void ) { 136 21 : return fd_ulong_align_up( sizeof(VEC_(private_t)), VEC_(align)() ); 137 21 : } 138 : 139 : FD_FN_CONST static inline ulong 140 12 : VEC_(footprint)( ulong max ) { 141 12 : ulong align = VEC_(align)(); 142 12 : ulong meta_footprint = VEC_(private_meta_footprint)(); /* Multiple of align */ 143 12 : ulong data_footprint = fd_ulong_align_up( sizeof(VEC_T)*max, align ); 144 12 : ulong thresh = (ULONG_MAX - align - meta_footprint + 1UL) / sizeof(VEC_T); 145 12 : return fd_ulong_if( max > thresh, 0UL, meta_footprint + data_footprint ); 146 12 : } 147 : 148 : static inline void * 149 : VEC_(new)( void * shmem, 150 6 : ulong max ) { 151 : 152 6 : if( FD_UNLIKELY( !shmem ) ) return NULL; 153 : 154 3 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, VEC_(align)() ) ) ) return NULL; 155 : 156 3 : if( FD_UNLIKELY( !VEC_(footprint)( max ) ) ) return NULL; 157 : 158 3 : VEC_(private_t) * join = VEC_(private)( (VEC_T *)(((ulong)shmem) + VEC_(private_meta_footprint)()) ); 159 3 : join->max = max; 160 3 : join->cnt = 0UL; 161 3 : return shmem; 162 3 : } 163 : 164 : FD_FN_CONST static inline VEC_T * 165 6 : VEC_(join)( void * shvec ) { 166 : 167 6 : if( FD_UNLIKELY( !shvec ) ) return NULL; 168 : 169 3 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shvec, VEC_(align)() ) ) ) return NULL; 170 : 171 3 : return (VEC_T *)(((ulong)shvec) + VEC_(private_meta_footprint)()); 172 3 : } 173 : 174 : FD_FN_CONST static inline void * 175 6 : VEC_(leave)( VEC_T * join ) { 176 : 177 6 : if( FD_UNLIKELY( !join ) ) return NULL; 178 : 179 3 : return (void *)(((ulong)join) - VEC_(private_meta_footprint)()); 180 6 : } 181 : 182 : FD_FN_CONST static inline void * 183 6 : VEC_(delete)( void * shvec ) { 184 : 185 6 : if( FD_UNLIKELY( !shvec ) ) return NULL; 186 : 187 3 : return shvec; 188 6 : } 189 : 190 3000000 : FD_FN_PURE static inline ulong VEC_(max)( VEC_T const * join ) { return VEC_(private_const)( join )->max; } 191 3000000 : FD_FN_PURE static inline ulong VEC_(cnt)( VEC_T const * join ) { return VEC_(private_const)( join )->cnt; } 192 : 193 : FD_FN_PURE static inline ulong 194 3000000 : VEC_(free)( VEC_T const * join ) { 195 3000000 : VEC_(private_t) const * vec = VEC_(private_const)( join ); 196 3000000 : return vec->max - vec->cnt; 197 3000000 : } 198 : 199 3000000 : FD_FN_PURE static inline int VEC_(is_empty)( VEC_T const * join ) { return !VEC_(private_const)( join )->cnt; } 200 : 201 : FD_FN_PURE static inline int 202 3000000 : VEC_(is_full) ( VEC_T const * join ) { 203 3000000 : VEC_(private_t) const * vec = VEC_(private_const)( join ); 204 3000000 : return vec->cnt==vec->max; 205 3000000 : } 206 : 207 : static inline VEC_T * 208 : VEC_(expand)( VEC_T * join, 209 749937 : ulong delta ) { 210 749937 : VEC_(private_t) * vec = VEC_(private)( join ); 211 749937 : ulong cnt = vec->cnt; 212 749937 : vec->cnt = cnt + delta; 213 749937 : return join + cnt; 214 749937 : } 215 : 216 : static inline VEC_T * 217 : VEC_(contract)( VEC_T * join, 218 752100 : ulong delta ) { 219 752100 : VEC_(private_t) * vec = VEC_(private)( join ); 220 752100 : ulong cnt = vec->cnt - delta; 221 752100 : vec->cnt = cnt; 222 752100 : return join + cnt; 223 752100 : } 224 : 225 : static inline VEC_T * 226 : VEC_(remove)( VEC_T * join, 227 748614 : ulong idx ) { 228 748614 : VEC_(private_t) * vec = VEC_(private)( join ); 229 748614 : ulong cnt = vec->cnt - 1UL; 230 748614 : join[idx] = join[cnt]; /* TODO: Consider letting user decide if self copy is cheaper than testing */ 231 748614 : vec->cnt = cnt; 232 748614 : return join; 233 748614 : } 234 : 235 : static inline VEC_T * 236 : VEC_(remove_compact)( VEC_T * join, 237 749340 : ulong idx ) { 238 749340 : VEC_(private_t) * vec = VEC_(private)( join ); 239 749340 : ulong cnt = vec->cnt - 1UL; 240 190835202 : for( ; idx<cnt; idx++ ) join[idx] = join[idx+1UL]; 241 749340 : vec->cnt = cnt; 242 749340 : return join; 243 749340 : } 244 : 245 : #undef VEC_ 246 : 247 : #undef VEC_T 248 : #undef VEC_NAME 249 :
