1
by brian
clean slate |
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
|
|
5 |
items themselves.
|
|
6 |
||
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.
|
|
10 |
||
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.
|
|
18 |
||
19 |
************************************************************************/
|
|
20 |
||
21 |
||
22 |
#ifndef IB_LIST_H
|
|
23 |
#define IB_LIST_H
|
|
24 |
||
25 |
#include "mem0mem.h" |
|
26 |
||
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; |
|
30 |
||
31 |
/********************************************************************
|
|
32 |
Create a new list using mem_alloc. Lists created with this function must be
|
|
33 |
freed with ib_list_free. */
|
|
34 |
||
35 |
ib_list_t* |
|
36 |
ib_list_create(void); |
|
37 |
/*=================*/
|
|
38 |
/* out: list */
|
|
39 |
||
40 |
||
41 |
/********************************************************************
|
|
42 |
Create a new list using the given heap. ib_list_free MUST NOT BE CALLED for
|
|
43 |
lists created with this function. */
|
|
44 |
||
45 |
ib_list_t* |
|
46 |
ib_list_create_heap( |
|
47 |
/*================*/
|
|
48 |
/* out: list */
|
|
49 |
mem_heap_t* heap); /* in: memory heap to use */ |
|
50 |
||
51 |
/********************************************************************
|
|
52 |
Free a list. */
|
|
53 |
||
54 |
void
|
|
55 |
ib_list_free( |
|
56 |
/*=========*/
|
|
57 |
ib_list_t* list); /* in: list */ |
|
58 |
||
59 |
/********************************************************************
|
|
60 |
Add the data to the start of the list. */
|
|
61 |
||
62 |
ib_list_node_t* |
|
63 |
ib_list_add_first( |
|
64 |
/*==============*/
|
|
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 */ |
|
69 |
||
70 |
/********************************************************************
|
|
71 |
Add the data to the end of the list. */
|
|
72 |
||
73 |
ib_list_node_t* |
|
74 |
ib_list_add_last( |
|
75 |
/*=============*/
|
|
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 */ |
|
80 |
||
81 |
/********************************************************************
|
|
82 |
Add the data after the indicated node. */
|
|
83 |
||
84 |
ib_list_node_t* |
|
85 |
ib_list_add_after( |
|
86 |
/*==============*/
|
|
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 |
|
90 |
be NULL) */ |
|
91 |
void* data, /* in: data */ |
|
92 |
mem_heap_t* heap); /* in: memory heap to use */ |
|
93 |
||
94 |
/********************************************************************
|
|
95 |
Remove the node from the list. */
|
|
96 |
||
97 |
void
|
|
98 |
ib_list_remove( |
|
99 |
/*===========*/
|
|
100 |
ib_list_t* list, /* in: list */ |
|
101 |
ib_list_node_t* node); /* in: node to remove */ |
|
102 |
||
103 |
/********************************************************************
|
|
104 |
Get the first node in the list. */
|
|
105 |
UNIV_INLINE
|
|
106 |
ib_list_node_t* |
|
107 |
ib_list_get_first( |
|
108 |
/*==============*/
|
|
109 |
/* out: first node, or NULL */
|
|
110 |
ib_list_t* list); /* in: list */ |
|
111 |
||
112 |
/********************************************************************
|
|
113 |
Get the last node in the list. */
|
|
114 |
UNIV_INLINE
|
|
115 |
ib_list_node_t* |
|
116 |
ib_list_get_last( |
|
117 |
/*=============*/
|
|
118 |
/* out: last node, or NULL */
|
|
119 |
ib_list_t* list); /* in: list */ |
|
120 |
||
121 |
/* 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 */
|
|
127 |
};
|
|
128 |
||
129 |
/* A list node. */
|
|
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 */ |
|
134 |
};
|
|
135 |
||
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
|
|
138 |
cases. */
|
|
139 |
struct ib_list_helper_struct { |
|
140 |
mem_heap_t* heap; /* memory heap */ |
|
141 |
void* data; /* user data */ |
|
142 |
};
|
|
143 |
||
144 |
#ifndef UNIV_NONINL
|
|
145 |
#include "ut0list.ic" |
|
146 |
#endif
|
|
147 |
||
148 |
#endif
|