1
/***********************************************************************
2
A double-linked list. This differs from the one in ut0lst.h in that in this
3
one, each list node contains a pointer to the data, whereas the one in
4
ut0lst.h uses a strategy where the list pointers are embedded in the data
7
Use this one when you need to store arbitrary data in the list where you
8
can't embed the list pointers in the data, if a data item needs to be
9
stored in multiple lists, etc.
11
Note about the memory management: ib_list_t is a fixed-size struct whose
12
allocation/deallocation is done through ib_list_create/ib_list_free, but the
13
memory for the list nodes is allocated through a user-given memory heap,
14
which can either be the same for all nodes or vary per node. Most users will
15
probably want to create a memory heap to store the item-specific data, and
16
pass in this same heap to the list node creation functions, thus
17
automatically freeing the list node when the item's heap is freed.
19
************************************************************************/
27
typedef struct ib_list_struct ib_list_t;
28
typedef struct ib_list_node_struct ib_list_node_t;
29
typedef struct ib_list_helper_struct ib_list_helper_t;
31
/********************************************************************
32
Create a new list using mem_alloc. Lists created with this function must be
33
freed with ib_list_free. */
41
/********************************************************************
42
Create a new list using the given heap. ib_list_free MUST NOT BE CALLED for
43
lists created with this function. */
49
mem_heap_t* heap); /* in: memory heap to use */
51
/********************************************************************
57
ib_list_t* list); /* in: list */
59
/********************************************************************
60
Add the data to the start of the list. */
65
/* out: new list node*/
66
ib_list_t* list, /* in: list */
67
void* data, /* in: data */
68
mem_heap_t* heap); /* in: memory heap to use */
70
/********************************************************************
71
Add the data to the end of the list. */
76
/* out: new list node*/
77
ib_list_t* list, /* in: list */
78
void* data, /* in: data */
79
mem_heap_t* heap); /* in: memory heap to use */
81
/********************************************************************
82
Add the data after the indicated node. */
87
/* out: new list node*/
88
ib_list_t* list, /* in: list */
89
ib_list_node_t* prev_node, /* in: node preceding new node (can
91
void* data, /* in: data */
92
mem_heap_t* heap); /* in: memory heap to use */
94
/********************************************************************
95
Remove the node from the list. */
100
ib_list_t* list, /* in: list */
101
ib_list_node_t* node); /* in: node to remove */
103
/********************************************************************
104
Get the first node in the list. */
109
/* out: first node, or NULL */
110
ib_list_t* list); /* in: list */
112
/********************************************************************
113
Get the last node in the list. */
118
/* out: last node, or NULL */
119
ib_list_t* list); /* in: list */
122
struct ib_list_struct {
123
ib_list_node_t* first; /* first node */
124
ib_list_node_t* last; /* last node */
125
ibool is_heap_list; /* TRUE if this list was
126
allocated through a heap */
130
struct ib_list_node_struct {
131
ib_list_node_t* prev; /* previous node */
132
ib_list_node_t* next; /* next node */
133
void* data; /* user data */
136
/* Quite often, the only additional piece of data you need is the per-item
137
memory heap, so we have this generic struct available to use in those
139
struct ib_list_helper_struct {
140
mem_heap_t* heap; /* memory heap */
141
void* data; /* user data */
145
#include "ut0list.ic"