1

#ifndef CHAIN_H

     2

#define CHAIN_H

     3

     4

/**

     5

 * @file

     6

 *

     7

 * Defines a brain-dead auto-allocated linked list for simple uses.

     8

 */

     9

#include "error.h"

    10

#include <sys/queue.h>

    11

#include <stdlib.h>

    12

#include <stdbool.h>

    13

    14

/**

    15

 * Header entry to embed a chain_item

    16

 */

    17

#define CHAIN_ITEM_HEADER(type) TAILQ_ENTRY(type) _chain_list

    18

    19

/**

    20

 * Header entry to embed a chain_head

    21

 */

    22

#define CHAIN_HEAD_TYPE(head_type, item_type) \

    23

    struct head_type {  \

    24

        TAILQ_HEAD(head_type ## _head, item_type) head;  \

    25

    }

    26

    27

/**

    28

 * Generic chain_head type

    29

 */

    30

struct _chain_item {

    31

   TAILQ_ENTRY(_chain_item) _chain_list;

    32

};

    33

    34

TAILQ_HEAD(_chain_head, _chain_item);

    35

    36

/**

    37

 * Cast to a chain_item

    38

 */

    39

#define CHAIN_CAST_ITEM(item_ptr) &(item_ptr)->_chain_list

    40

    41

/**

    42

 * Ref the head struct from the given chain_head

    43

 */

    44

#define CHAIN_DEREF_HEAD(head_ptr) &(head_ptr)->head

    45

    46

/**

    47

 * Cast to a generic _chain_head

    48

 */

    49

#define CHAIN_HEAD_GENERIC(head_ptr) (struct _chain_head *) CHAIN_DEREF_HEAD(head_ptr)

    50

    51

/**

    52

 * Evaluates to the type of the given CHAIN_HEAD

    53

 */

    54

#define CHAIN_TYPE(head_ptr) typeof (*TAILQ_FIRST(CHAIN_DEREF_HEAD(head_ptr)))

    55

    56

    57

    58

/**

    59

 * Initialize a chain_head to be empty

    60

 */

    61

#define CHAIN_INIT(head_ptr) TAILQ_INIT(CHAIN_DEREF_HEAD(head_ptr))

    62

    63

    64

/**

    65

 * Return the first item in the chain as a pointer of the correct type

    66

 */

    67

#define CHAIN_FIRST(head_ptr) TAILQ_FIRST(CHAIN_DEREF_HEAD(head_ptr))

    68

    69

/**

    70

 * Return the item after the given item

    71

 */

    72

#define CHAIN_NEXT(item_ptr) TAILQ_NEXT(item_ptr, _chain_list)

    73

    74

    75

    76

/**

    77

 * Allocate a new chain_item of the given type, adding it to the beginning of the list, and returning a calloc'd

    78

 * struct of the given type.

    79

 */

    80

#define CHAIN_ADD_HEAD(head_ptr) (CHAIN_TYPE(head_ptr) *) _chain_add(CHAIN_HEAD_GENERIC(head_ptr), false, sizeof (*CHAIN_TYPE(head_ptr)))

    81

    82

/**

    83

 * Same as CHAIN_ADD_HEAD, except this adds the new item to the end of the list.

    84

 */

    85

#define CHAIN_ADD_TAIL(head_ptr) (CHAIN_TYPE(head_ptr) *) _chain_add(CHAIN_HEAD_GENERIC(head_ptr), true,  sizeof (CHAIN_TYPE(head_ptr)))

    86

    87

    88

    89

/**

    90

 * Iterate over the items in a chain

    91

 */

    92

#define CHAIN_FOREACH(head_ptr, item_ptr) TAILQ_FOREACH(item_ptr, CHAIN_DEREF_HEAD(head_ptr), _chain_list)

    93

    94

/**

    95

 * Safely iterate over the items in a chain, such that the iterated-over item can be removed without breaking the chain

    96

 */

    97

#define CHAIN_FOREACH_SAFE(head_ptr, item_ptr) \

    98

    for (   \

    99

            typeof (item_ptr) _chain_next = CHAIN_FIRST(head_ptr); \

   100

            ((void) ((item_ptr = _chain_next) && (_chain_next = CHAIN_NEXT(_chain_next)))), item_ptr; \

   101

            (void) 0  \

   102

    )

   103

   104

   105

/**

   106

 * Remove an item from the list and free it.

   107

 */

   108

#define CHAIN_DELETE(head_ptr, item_ptr) \

   109

    do {    \

   110

        TAILQ_REMOVE(CHAIN_DEREF_HEAD(head_ptr), item_ptr, _chain_list);    \

   111

        free(item_ptr); \

   112

    } while (0);

   113

   114

/**

   115

 * Delete the items from the chain for which the given predicate matches

   116

 */

   117

#define CHAIN_DELETE_WHICH(head_ptr, item_ptr, predicate) \

   118

    do {    \

   119

        CHAIN_FOREACH_SAFE(head_ptr, item_ptr)  \

   120

            if (predicate)  \

   121

                CHAIN_DELETE(head_ptr, item_ptr);   \

   122

    } while (0)

   123

   124

/**

   125

 * Delete all items from the chain

   126

 */

   127

#define CHAIN_CLEAR(head_ptr) \

   128

    do {    \

   129

        CHAIN_TYPE(head_ptr) *_chain_item;   \

   130

        CHAIN_FOREACH_SAFE(head_ptr, _chain_item)   \

   131

           free(_chain_item);   \

   132

    } while (0);

   133

   134

   135

   136

void *_chain_add (struct _chain_head *head, bool tail, size_t size);

   137

   138

#endif