Line data    Source code

       1             : /* Declares a family of functions implementing a single-threaded
       2             :    run-time fixed-capacity stack designed for high performance contexts.
       3             :    Example usage:
       4             : 
       5             :      #define STACK_NAME my_stack
       6             :      #define STACK_T    my_ele_t
       7             :      #include "util/tmpl/fd_stack.c"
       8             : 
       9             :    This creates the following API for use in the local compilation unit:
      10             : 
      11             :      ulong      my_stack_align    ( void               ); // required byte alignment of a stack
      12             :      ulong      my_stack_footprint( ulong max          ); // required byte footprint of a stack with max capacity
      13             :      void     * my_stack_new      ( void     * shmem,     // format memory region into a my_stack, my_stack will be empty
      14             :                                     ulong      max );     // (caller not joined on return, mem has required align/footprint, etc)
      15             :      my_ele_t * my_stack_join     ( void     * shstack ); // join a my_stack (unlimited joins, etc) (NOT A CAST OF SHSTACK)
      16             :                                                           // join can be indexed like a normal array with max elements
      17             :                                                           // stack[i] for i in [0,cnt) are the elements currently in the
      18             :                                                           // stack from bottom to top
      19             :      void     * my_stack_leave    ( my_ele_t * stack   ); // leave a my_stack (matched with join, etc) (NOT A CAST OF STACK)
      20             :      void     * my_stack_delete   ( void     * shstack ); // unformat memory (no active joins, etc)
      21             : 
      22             :      // Accessors
      23             : 
      24             :      ulong my_stack_max  ( my_ele_t const * stack ); // returns the max elements that could be in the stack
      25             :      ulong my_stack_cnt  ( my_ele_t const * stack ); // returns the number of elements in the stack, in [0,max]
      26             :      ulong my_stack_avail( my_ele_t const * stack ); // return max-cnt
      27             :      int   my_stack_empty( my_ele_t const * stack ); // returns 1 if empty and 0 otherwise
      28             :      int   my_stack_full ( my_ele_t const * stack ); // returns 1 if full and 0 otherwise
      29             : 
      30             :      // Simple API
      31             : 
      32             :      my_ele_t * my_stack_push( my_ele_t * stack, my_ele_t ele ); // push ele to stack, returns stack
      33             :      my_ele_t   my_stack_pop ( my_ele_t * stack               ); // pop ele from stack, returns ele
      34             : 
      35             :      // Advanced API for zero-copy usage
      36             : 
      37             :      my_ele_t * my_stack_peek      ( my_ele_t * stack ); // peeks at stack top, returned ptr lifetime is until next op on stack
      38             :      my_ele_t * my_stack_insert    ( my_ele_t * stack ); // inserts uninitialized element at tail, returns stack
      39             :      my_ele_t * my_stack_remove    ( my_ele_t * stack ); // removes tail, returns stack
      40             :      my_ele_t * my_stack_remove_all( my_ele_t * stack ); // removes all, returns stack, fast O(1)
      41             : 
      42             :      my_ele_t const * my_stack_peek_const( my_ele_t const * stack ); // const version of peek
      43             : 
      44             :    For performance, none of the functions do any error checking.
      45             :    Specifically, the caller promises that max is such that footprint
      46             :    will not overflow 2^64 (e.g. max << (2^64)/sizeof(my_ele_t)), cnt<max
      47             :    for any push or insert operation and cnt>0 for any pop, peek or
      48             :    remove operation (remove_all is fine on an empty stack). */
      49             : 
      50             : #include "../bits/fd_bits.h"
      51             : #include <stddef.h>
      52             : 
      53             : #ifndef STACK_NAME
      54             : #error "Define STACK_NAME"
      55             : #endif
      56             : 
      57             : #ifndef STACK_T
      58             : #error "Define STACK_T"
      59             : #endif
      60             : 
      61             : /* Implementation *****************************************************/
      62             : 
      63  2766673488 : #define STACK_(x) FD_EXPAND_THEN_CONCAT3(STACK_NAME,_,x)
      64             : 
      65             : struct STACK_(private) {
      66             : 
      67             :   /* The number of elements in the stack is cnt and cnt will be in
      68             :      [0,max].  If cnt==0, the stack is empty.  If cnt==max, the stack if
      69             :      full.  For a non-empty stack, the oldest element in the stack is at
      70             :      element stack[0] and the newest element in the stack is at element
      71             :      stack[cnt-1UL]. */
      72             : 
      73             :   ulong   max;
      74             :   ulong   cnt;
      75             :   STACK_T stack[1]; /* Actually max in size */
      76             : };
      77             : 
      78             : typedef struct STACK_(private) STACK_(private_t);
      79             : 
      80             : FD_PROTOTYPES_BEGIN
      81             : 
      82             : /* private_from_stack return a pointer to the stack_private given a
      83             :    pointer to the stack. */
      84             : 
      85             : FD_FN_CONST static inline STACK_(private_t) *
      86           0 : STACK_(private_hdr_from_stack)( STACK_T * stack ) {
      87           0 :   return (STACK_(private_t) *)( (ulong)stack - offsetof(STACK_(private_t), stack) );
      88           0 : }
      89             : 
      90             : /* const-correct version of above */
      91             : 
      92             : FD_FN_CONST static inline STACK_(private_t) const *
      93           0 : STACK_(private_const_hdr_from_stack)( STACK_T const * stack ) {
      94           0 :   return (STACK_(private_t) const *)( (ulong)stack - offsetof(STACK_(private_t), stack) );
      95           0 : }
      96             : 
      97           0 : FD_FN_CONST static inline ulong STACK_(align)( void ) { return alignof(STACK_(private_t)); }
      98             : 
      99             : FD_FN_CONST static inline ulong
     100           3 : STACK_(footprint)( ulong max ) {
     101           3 :   return fd_ulong_align_up( fd_ulong_align_up( 16UL, alignof(STACK_T) ) + sizeof(STACK_T)*max, alignof(STACK_(private_t)) );
     102           3 : }
     103             : 
     104             : static inline void *
     105             : STACK_(new)( void * shmem,
     106           3 :              ulong  max ) {
     107           3 :   STACK_(private_t) * hdr = (STACK_(private_t) *)shmem;
     108           3 :   hdr->max = max;
     109           3 :   hdr->cnt = 0UL;
     110           3 :   return hdr;
     111           3 : }
     112             : 
     113             : static inline STACK_T *
     114           3 : STACK_(join)( void * shstack ) {
     115           3 :   STACK_(private_t) * hdr = (STACK_(private_t) *)shstack;
     116           3 :   return hdr->stack;
     117           3 : } 
     118             : 
     119           3 : static inline void * STACK_(leave) ( STACK_T * stack   ) { return (void *)STACK_(private_hdr_from_stack)( stack ); }
     120           3 : static inline void * STACK_(delete)( void *    shstack ) { return shstack; }
     121             : 
     122             : FD_FN_PURE static inline ulong
     123   300000003 : STACK_(max)( STACK_T const * stack ) {
     124   300000003 :   return STACK_(private_const_hdr_from_stack)( stack )->max;
     125   300000003 : }
     126             : 
     127             : FD_FN_PURE static inline ulong
     128   300000003 : STACK_(cnt)( STACK_T const * stack ) {
     129   300000003 :   return STACK_(private_const_hdr_from_stack)( stack )->cnt;
     130   300000003 : }
     131             : 
     132             : FD_FN_PURE static inline ulong
     133   300000000 : STACK_(avail)( STACK_T const * stack ) {
     134   300000000 :   STACK_(private_t) const * hdr = STACK_(private_const_hdr_from_stack)( stack );
     135   300000000 :   return hdr->max - hdr->cnt;
     136   300000000 : }
     137             : 
     138             : FD_FN_PURE static inline int
     139   300000000 : STACK_(full)( STACK_T const * stack ) {
     140   300000000 :   STACK_(private_t) const * hdr = STACK_(private_const_hdr_from_stack)( stack );
     141   300000000 :   return hdr->max==hdr->cnt;
     142   300000000 : }
     143             : 
     144             : FD_FN_PURE static inline int
     145   300000000 : STACK_(empty)( STACK_T const * stack ) {
     146   300000000 :   return !STACK_(private_const_hdr_from_stack)( stack )->cnt;
     147   300000000 : }
     148             : 
     149             : static inline STACK_T *
     150             : STACK_(push)( STACK_T * stack,
     151    66667296 :               STACK_T   ele ) {
     152    66667296 :   STACK_(private_t) * hdr = STACK_(private_hdr_from_stack)( stack );
     153    66667296 :   hdr->stack[ hdr->cnt++ ] = ele;
     154    66667296 :   return stack;
     155    66667296 : }
     156             : 
     157             : static inline STACK_T
     158    66682113 : STACK_(pop)( STACK_T * stack ) {
     159    66682113 :   STACK_(private_t) * hdr = STACK_(private_hdr_from_stack)( stack );
     160    66682113 :   return hdr->stack[ --hdr->cnt ];
     161    66682113 : }
     162             : 
     163             : FD_FN_PURE static inline STACK_T *
     164    66678048 : STACK_(peek)( STACK_T * stack ) {
     165    66678048 :   STACK_(private_t) * hdr = STACK_(private_hdr_from_stack)( stack );
     166    66678048 :   return hdr->stack + (hdr->cnt-1UL);
     167    66678048 : }
     168             : 
     169             : FD_FN_PURE static inline STACK_T const *
     170    66645321 : STACK_(peek_const)( STACK_T const * stack ) {
     171    66645321 :   STACK_(private_t) const * hdr = STACK_(private_const_hdr_from_stack)( stack );
     172    66645321 :   return hdr->stack + (hdr->cnt-1UL);
     173    66645321 : }
     174             : 
     175    66678048 : static inline STACK_T * STACK_(insert)    ( STACK_T * stack ) { STACK_(private_hdr_from_stack)( stack )->cnt++;     return stack; }
     176    66645321 : static inline STACK_T * STACK_(remove)    ( STACK_T * stack ) { STACK_(private_hdr_from_stack)( stack )->cnt--;     return stack; }
     177        4548 : static inline STACK_T * STACK_(remove_all)( STACK_T * stack ) { STACK_(private_hdr_from_stack)( stack )->cnt = 0UL; return stack; }
     178             : 
     179             : FD_PROTOTYPES_END
     180             : 
     181             : #undef STACK_
     182             : 
     183             : #undef STACK_T
     184             : #undef STACK_NAME
     185             :