LCOV - code coverage report
Current view: top level - util/tmpl - fd_queue_dynamic.c (source / functions) Hit Total Coverage
Test: cov.lcov Lines: 102 109 93.6 %
Date: 2024-11-13 11:58:15 Functions: 21 24 87.5 %

          Line data    Source code
       1             : /* Declares a family of functions implementing a single-threaded
       2             :    run-time fixed-capacity queue designed for high performance contexts.
       3             :    Example usage:
       4             : 
       5             :      #define QUEUE_NAME my_queue
       6             :      #define QUEUE_T    my_ele_t
       7             :      #include "util/tmpl/fd_queue.c"
       8             : 
       9             :    This creates the following API for use in the local compilation unit:
      10             : 
      11             :      ulong      my_queue_align    ( void               ); // required byte alignment of a queue
      12             :      ulong      my_queue_footprint( ulong      max     ); // required byte footprint of a queue with max capacity
      13             :      void     * my_queue_new      ( void     * shmem,     // format memory region into a my_queue, my_queue will be empty
      14             :                                     ulong      max     ); // (caller not joined on return, mem has required align/footprint, etc)
      15             :      my_ele_t * my_queue_join     ( void     * shqueue ); // join a my_queue (unlimited joins, etc) (NOT A CAST OF SHQUEUE)
      16             :                                                           // join can be indexed like a normal array with max elements
      17             :      void     * my_queue_leave    ( my_ele_t * queue   ); // leave a my_queue (matched with join, etc) (NOT A CAST OF QUEUE)
      18             :      void     * my_queue_delete   ( void     * shqueue ); // unformat memory (no active joins, etc)
      19             : 
      20             :      // Accessors
      21             : 
      22             :      ulong my_queue_max  ( my_ele_t const * queue ); // returns the max elements that could be in the queue
      23             :      ulong my_queue_cnt  ( my_ele_t const * queue ); // returns the number of elements in the queue, in [0,max]
      24             :      ulong my_queue_avail( my_ele_t const * queue ); // returns max-cnt
      25             :      int   my_queue_empty( my_ele_t const * queue ); // returns 1 if queue is empty and 0 otherwise
      26             :      int   my_queue_full ( my_ele_t const * queue ); // returns 1 if queue is full and 0 otherwise
      27             : 
      28             :      // Simple API
      29             : 
      30             :      my_ele_t * my_queue_push( my_ele_t * queue, my_ele_t ele ); // push ele to queue, returns queue
      31             :      my_ele_t   my_queue_pop ( my_ele_t * queue               ); // pop ele from queue, returns ele
      32             : 
      33             :      // Advanced API for zero-copy usage
      34             : 
      35             :      my_ele_t * my_queue_peek_insert( my_ele_t * queue ); // peeks at most recent insert/push,
      36             :                                                           // returned ptr lifetime is until next op on queue
      37             :      my_ele_t * my_queue_peek_remove( my_ele_t * queue ); // peeks at least recent insert/push,
      38             :                                                           // returned ptr lifetime is until next op on queue
      39             :      my_ele_t * my_queue_insert     ( my_ele_t * queue ); // push uninitialized element, returns queue
      40             :      my_ele_t * my_queue_remove     ( my_ele_t * queue ); // pops queue, returns queue
      41             :      my_ele_t * my_queue_remove_all ( my_ele_t * queue ); // removes all, returns queue, fast O(1)
      42             : 
      43             :      my_ele_t const * my_queue_peek_insert_const( my_ele_t const * queue ); // const version of peek_insert
      44             :      my_ele_t const * my_queue_peek_remove_const( my_ele_t const * queue ); // const version of peek_remove
      45             : 
      46             :    For performance, none of the functions do any error checking.
      47             :    Specifically, the caller promises that max is such that footprint
      48             :    will not overflow 2^64 (e.g. max << (2^64)/sizeof(my_ele_t)), cnt<max
      49             :    for any push or insert operation and cnt>0 for any pop, peek or
      50             :    remove operation (remove_all is fine on an empty queue). */
      51             : 
      52             : #include "../bits/fd_bits.h"
      53             : #include <stddef.h>
      54             : 
      55             : #ifndef QUEUE_NAME
      56             : #error "Define QUEUE_NAME"
      57             : #endif
      58             : 
      59             : #ifndef QUEUE_T
      60             : #error "Define QUEUE_T"
      61             : #endif
      62             : 
      63             : /* Implementation *****************************************************/
      64             : 
      65  4366711167 : #define QUEUE_(x) FD_EXPAND_THEN_CONCAT3(QUEUE_NAME,_,x)
      66             : 
      67             : struct QUEUE_(private) {
      68             :   ulong   max1;  /* Max elements in queue minus 1 */
      69             :   ulong   cnt;   /* Num elements in queue, in [0,max] */
      70             :   ulong   start; /* Index of next to pop,  in [0,max) */
      71             :   ulong   end;   /* Index of next to push, in [0,max) */
      72             :   QUEUE_T queue[ 1 ]; /* Actually max in size */
      73             : };
      74             : 
      75             : typedef struct QUEUE_(private) QUEUE_(private_t);
      76             : 
      77             : FD_PROTOTYPES_BEGIN
      78             : 
      79             : /* private_from_queue returns a pointer to the queue_private given a
      80             :    pointer to the queue. */
      81             : 
      82             : FD_FN_CONST static inline QUEUE_(private_t) *
      83           0 : QUEUE_(private_hdr_from_queue)( QUEUE_T * queue ) {
      84           0 :   return (QUEUE_(private_t) *)( (ulong)queue - offsetof(QUEUE_(private_t), queue) );
      85           0 : }
      86             : 
      87             : /* const-correct version of above */
      88             : 
      89             : FD_FN_CONST static inline QUEUE_(private_t) const *
      90           0 : QUEUE_(private_const_hdr_from_queue)( QUEUE_T const * queue ) {
      91           0 :   return (QUEUE_(private_t) const *)( (ulong)queue - offsetof(QUEUE_(private_t), queue) );
      92           0 : }
      93             : 
      94             : /* These move i to the previous or next slot to i for given max.
      95             :    Input should be in [0,max) and output will be in [0,max). */
      96             : 
      97   200034144 : FD_FN_CONST static inline ulong QUEUE_(private_prev)( ulong i, ulong max1 ) { return fd_ulong_if( i==0UL,  max1, i-1UL ); }
      98   266672778 : FD_FN_CONST static inline ulong QUEUE_(private_next)( ulong i, ulong max1 ) { return fd_ulong_if( i>=max1, 0UL,  i+1UL ); }
      99             : 
     100           0 : FD_FN_CONST static inline ulong QUEUE_(align)( void ) { return alignof(QUEUE_(private_t)); }
     101             : 
     102             : FD_FN_CONST static inline ulong
     103           3 : QUEUE_(footprint)( ulong max ) {
     104           3 :   return fd_ulong_align_up( fd_ulong_align_up( 32UL, alignof(QUEUE_T) ) + sizeof(QUEUE_T)*max, alignof(QUEUE_(private_t)) );
     105           3 : }
     106             : 
     107             : static inline void *
     108             : QUEUE_(new)( void * shmem,
     109           3 :              ulong  max ) {
     110           3 :   QUEUE_(private_t) * hdr = (QUEUE_(private_t) *)shmem;
     111           3 :   hdr->max1  = max-1UL;
     112           3 :   hdr->cnt   = 0UL;
     113           3 :   hdr->start = 0UL;
     114           3 :   hdr->end   = 0UL;
     115           3 :   return hdr;
     116           3 : }
     117             : 
     118             : static inline QUEUE_T *
     119           3 : QUEUE_(join)( void * shqueue ) {
     120           3 :   QUEUE_(private_t) * hdr = (QUEUE_(private_t) *)shqueue;
     121           3 :   return hdr->queue;
     122           3 : } 
     123             : 
     124           3 : static inline void * QUEUE_(leave) ( QUEUE_T * queue   ) { return (void *)QUEUE_(private_hdr_from_queue)( queue ); }
     125           3 : static inline void * QUEUE_(delete)( void *    shqueue ) { return shqueue; }
     126             : 
     127             : FD_FN_PURE static inline ulong
     128   300000003 : QUEUE_(max)( QUEUE_T const * queue ) {
     129   300000003 :   QUEUE_(private_t) const * hdr = QUEUE_(private_const_hdr_from_queue)( queue );
     130   300000003 :   return hdr->max1 + 1UL;
     131   300000003 : }
     132             : 
     133             : FD_FN_PURE static inline ulong
     134   300000003 : QUEUE_(cnt)( QUEUE_T const * queue ) {
     135   300000003 :   QUEUE_(private_t) const * hdr = QUEUE_(private_const_hdr_from_queue)( queue );
     136   300000003 :   return hdr->cnt;
     137   300000003 : }
     138             : 
     139             : FD_FN_PURE static inline ulong
     140   300000000 : QUEUE_(avail)( QUEUE_T const * queue ) {
     141   300000000 :   QUEUE_(private_t) const * hdr = QUEUE_(private_const_hdr_from_queue)( queue );
     142   300000000 :   return hdr->max1 + 1UL - hdr->cnt;
     143   300000000 : }
     144             : 
     145             : FD_FN_PURE static inline int
     146   300000000 : QUEUE_(empty)( QUEUE_T const * queue ) {
     147   300000000 :   return !QUEUE_(private_const_hdr_from_queue)( queue )->cnt;
     148   300000000 : }
     149             : 
     150             : FD_FN_PURE static inline int
     151   300000000 : QUEUE_(full)( QUEUE_T const * queue ) {
     152   300000000 :   QUEUE_(private_t) const * hdr = QUEUE_(private_const_hdr_from_queue)( queue );
     153   300000000 :   return (hdr->max1 + 1UL)==hdr->cnt;
     154   300000000 : }
     155             : 
     156             : static inline QUEUE_T *
     157             : QUEUE_(push)( QUEUE_T * queue,
     158    66667296 :               QUEUE_T   ele ) {
     159    66667296 :   QUEUE_(private_t) * hdr = QUEUE_(private_hdr_from_queue)( queue );
     160    66667296 :   ulong max1 = hdr->max1;
     161    66667296 :   ulong cnt  = hdr->cnt;
     162    66667296 :   ulong end  = hdr->end;
     163    66667296 :   hdr->queue[ end ] = ele;
     164    66667296 :   end = QUEUE_(private_next)( end, max1 );
     165    66667296 :   hdr->cnt = cnt+1UL;
     166    66667296 :   hdr->end = end;
     167    66667296 :   return queue;
     168    66667296 : }
     169             : 
     170             : static inline QUEUE_T
     171    66682113 : QUEUE_(pop)( QUEUE_T * queue ) {
     172    66682113 :   QUEUE_(private_t) * hdr = QUEUE_(private_hdr_from_queue)( queue );
     173    66682113 :   ulong max1  = hdr->max1;
     174    66682113 :   ulong cnt   = hdr->cnt;
     175    66682113 :   ulong start = hdr->start;
     176    66682113 :   QUEUE_T ele = hdr->queue[ start ];
     177    66682113 :   start = QUEUE_(private_next)( start, max1 );
     178    66682113 :   hdr->cnt   = cnt-1UL;
     179    66682113 :   hdr->start = start;
     180    66682113 :   return ele;
     181    66682113 : }
     182             : 
     183             : FD_FN_PURE static inline QUEUE_T *
     184   133356096 : QUEUE_(peek_insert)( QUEUE_T * queue ) {
     185   133356096 :   QUEUE_(private_t) * hdr = QUEUE_(private_hdr_from_queue)( queue );
     186   133356096 :   return hdr->queue + QUEUE_(private_prev)( hdr->end, hdr->max1 );
     187   133356096 : }
     188             : 
     189             : FD_FN_PURE static inline QUEUE_T *
     190    66645321 : QUEUE_(peek_remove)( QUEUE_T * queue ) {
     191    66645321 :   QUEUE_(private_t) * hdr = QUEUE_(private_hdr_from_queue)( queue );
     192    66645321 :   return hdr->queue + hdr->start;
     193    66645321 : }
     194             : 
     195             : FD_FN_PURE static inline QUEUE_T const *
     196    66678048 : QUEUE_(peek_insert_const)( QUEUE_T const * queue ) {
     197    66678048 :   QUEUE_(private_t) const * hdr = QUEUE_(private_const_hdr_from_queue)( queue );
     198    66678048 :   return hdr->queue + QUEUE_(private_prev)( hdr->end, hdr->max1 );
     199    66678048 : }
     200             : 
     201             : FD_FN_PURE static inline QUEUE_T const *
     202    66645321 : QUEUE_(peek_remove_const)( QUEUE_T const * queue ) {
     203    66645321 :   QUEUE_(private_t) const * hdr = QUEUE_(private_const_hdr_from_queue)( queue );
     204    66645321 :   return hdr->queue + hdr->start;
     205    66645321 : }
     206             : 
     207             : static inline QUEUE_T *
     208    66678048 : QUEUE_(insert)( QUEUE_T * queue ) {
     209    66678048 :   QUEUE_(private_t) * hdr = QUEUE_(private_hdr_from_queue)( queue );
     210    66678048 :   ulong max1 = hdr->max1;
     211    66678048 :   ulong cnt  = hdr->cnt;
     212    66678048 :   ulong end  = hdr->end;
     213    66678048 :   hdr->cnt   = cnt + 1UL;
     214    66678048 :   hdr->end   = QUEUE_(private_next)( end, max1 );
     215    66678048 :   return queue;
     216    66678048 : }
     217             : 
     218             : static inline QUEUE_T *
     219    66645321 : QUEUE_(remove)( QUEUE_T * queue ) {
     220    66645321 :   QUEUE_(private_t) * hdr = QUEUE_(private_hdr_from_queue)( queue );
     221    66645321 :   ulong max1  = hdr->max1;
     222    66645321 :   ulong cnt   = hdr->cnt;
     223    66645321 :   ulong start = hdr->start;
     224    66645321 :   hdr->cnt    = cnt - 1UL;
     225    66645321 :   hdr->start  = QUEUE_(private_next)( start, max1 );
     226    66645321 :   return queue;
     227    66645321 : }
     228             : 
     229             : static inline QUEUE_T *
     230        4548 : QUEUE_(remove_all)( QUEUE_T * queue ) {
     231        4548 :   QUEUE_(private_t) * hdr = QUEUE_(private_hdr_from_queue)( queue );
     232        4548 :   hdr->cnt   = 0UL;
     233        4548 :   hdr->start = 0UL;
     234        4548 :   hdr->end   = 0UL;
     235        4548 :   return queue;
     236        4548 : }
     237             : 
     238             : FD_PROTOTYPES_END
     239             : 
     240             : #undef QUEUE_
     241             : 
     242             : #undef QUEUE_T
     243             : #undef QUEUE_NAME
     244             : 

Generated by: LCOV version 1.14