Line data    Source code

       1             : #ifndef HEADER_fd_src_util_list_fd_list_h
       2             : #define HEADER_fd_src_util_list_fd_list_h
       3             : 
       4             : #include "../../util/fd_util.h"
       5             : 
       6             : /* An implementation of an intrusive doubly-linked list.
       7             : 
       8             :    -----
       9             :    1    / 0x0  = 0
      10             :    -----
      11             :    5    / 0x4  = 4
      12             :    -----
      13             :    3    / 0x8  = 8
      14             :    -----
      15             :    2    / 0x12 = 12
      16             :    -----
      17             :    4    / 0x16 = 16
      18             :    -----
      19             : 
      20             :    tag : 1  -> 2  -> 3  -> 4  -> 5
      21             :    curr: 0  -> 12 -> 8  -> 16 -> 4
      22             :    prev: /  <- 0  <- 12 <- 8  <- 16
      23             :    next: 12 -> 8  -> 16 -> 4  -> /
      24             : 
      25             :    TODO generalize to a tmpl data structure? */
      26             : typedef struct fd_list fd_list_t; /* forward decl */
      27             : struct fd_list {
      28             :   ulong tag; /* TODO generic */
      29             :   /* below all are offsets from the sentinel */
      30             :   ulong curr;
      31             :   ulong prev;
      32             :   ulong next;
      33             : };
      34             : 
      35           3 : #define FD_LIST_ALIGN ( 32UL ) /* 2-nodes per L1 cache line */
      36             : 
      37             : ulong
      38             : fd_list_align( void );
      39             : 
      40             : ulong
      41             : fd_list_footprint( ulong max );
      42             : 
      43             : void *
      44             : fd_list_new( void * mem, ulong max );
      45             : 
      46             : fd_list_t *
      47             : fd_list_join( void * mem );
      48             : 
      49             : fd_list_t *
      50             : fd_list_prev( fd_list_t * curr );
      51             : 
      52             : fd_list_t *
      53             : fd_list_next( fd_list_t * curr );
      54             : 
      55             : fd_list_t *
      56             : fd_list_sentinel( fd_list_t * list );
      57             : 
      58             : fd_list_t *
      59             : fd_list_head( fd_list_t * list );
      60             : 
      61             : fd_list_t *
      62             : fd_list_tail( fd_list_t * list );
      63             : 
      64             : int
      65             : fd_list_is_empty( fd_list_t * list );
      66             : 
      67             : /* a list can insert an element directly after itself */
      68             : fd_list_t *
      69             : fd_list_insert( fd_list_t * curr, fd_list_t * new );
      70             : 
      71             : /* a list can remove itself */
      72             : fd_list_t *
      73             : fd_list_remove( fd_list_t * new );
      74             : 
      75             : fd_list_t *
      76             : fd_list_push_back( fd_list_t * list, fd_list_t * new );
      77             : 
      78             : fd_list_t *
      79             : fd_list_pop_front( fd_list_t * list );
      80             : 
      81             : #endif /* HEADER_fd_src_util_list_fd_list_h */