NVMLib  very early alpha
A library to optimally use a Hybrid RAM setup.
free_slot_list.h
Go to the documentation of this file.
1 // SPDX-License-Identifier: BSD-3-Clause
2 /* Copyright 2016, Intel Corporation */
3 /*
4  * pmemobj_list.h -- macro definitions for persistent
5  * singly linked list and tail queue
6  */
7 
8 #ifndef PMEMOBJ_LISTS_H
9 #define PMEMOBJ_LISTS_H
10 
11 #include <libpmemobj.h>
12 
13 /*
14  * This file defines two types of persistent data structures:
15  * singly-linked lists and tail queue.
16  *
17  * All macros defined in this file must be used within libpmemobj
18  * transactional API. Following snippet presents example of usage:
19  *
20  * TX_BEGIN(pop) {
21  * POBJ_TAILQ_INIT(head);
22  * } TX_ONABORT {
23  * abort();
24  * } TX_END
25  *
26  * SLIST TAILQ
27  * _HEAD + +
28  * _ENTRY + +
29  * _INIT + +
30  * _EMPTY + +
31  * _FIRST + +
32  * _NEXT + +
33  * _PREV - +
34  * _LAST - +
35  * _FOREACH + +
36  * _FOREACH_REVERSE - +
37  * _INSERT_HEAD + +
38  * _INSERT_BEFORE - +
39  * _INSERT_AFTER + +
40  * _INSERT_TAIL - +
41  * _MOVE_ELEMENT_HEAD - +
42  * _MOVE_ELEMENT_TAIL - +
43  * _REMOVE_HEAD + -
44  * _REMOVE + +
45  * _REMOVE_FREE + +
46  * _SWAP_HEAD_TAIL - +
47  */
48 
49 /*
50  * Singly-linked List definitions.
51  */
52 #define POBJ_SLIST_HEAD(name, type)\
53 struct name {\
54  TOID(type) pe_first;\
55 }
56 
57 #define POBJ_SLIST_ENTRY(type)\
58 struct {\
59  TOID(type) pe_next;\
60 }
61 
62 /*
63  * Singly-linked List access methods.
64  */
65 #define POBJ_SLIST_EMPTY(head) (TOID_IS_NULL((head)->pe_first))
66 #define POBJ_SLIST_FIRST(head) ((head)->pe_first)
67 #define POBJ_SLIST_NEXT(elm, field) (D_RO(elm)->field.pe_next)
68 
69 /*
70  * Singly-linked List functions.
71  */
72 #define POBJ_SLIST_INIT(head) do {\
73  TX_ADD_DIRECT(&(head)->pe_first);\
74  TOID_ASSIGN((head)->pe_first, MEMOID_NULL);\
75 } while (0)
76 
77 #define POBJ_SLIST_INSERT_HEAD(head, elm, field) do {\
78  TOID_TYPEOF(elm) *elm_ptr = D_RW(elm);\
79  TX_ADD_DIRECT(&elm_ptr->field.pe_next);\
80  elm_ptr->field.pe_next = (head)->pe_first;\
81  TX_SET_DIRECT(head, pe_first, elm);\
82 } while (0)
83 
84 #define POBJ_SLIST_INSERT_AFTER(slistelm, elm, field) do {\
85  TOID_TYPEOF(slistelm) *slistelm_ptr = D_RW(slistelm);\
86  TOID_TYPEOF(elm) *elm_ptr = D_RW(elm);\
87  TX_ADD_DIRECT(&elm_ptr->field.pe_next);\
88  elm_ptr->field.pe_next = slistelm_ptr->field.pe_next;\
89  TX_ADD_DIRECT(&slistelm_ptr->field.pe_next);\
90  slistelm_ptr->field.pe_next = elm;\
91 } while (0)
92 
93 #define POBJ_SLIST_REMOVE_HEAD(head, field) do {\
94  TX_ADD_DIRECT(&(head)->pe_first);\
95  (head)->pe_first = D_RO((head)->pe_first)->field.pe_next;\
96 } while (0)
97 
98 #define POBJ_SLIST_REMOVE(head, elm, field) do {\
99  if (TOID_EQUALS((head)->pe_first, elm)) {\
100  POBJ_SLIST_REMOVE_HEAD(head, field);\
101  } else {\
102  TOID_TYPEOF(elm) *curelm_ptr = D_RW((head)->pe_first);\
103  while (!TOID_EQUALS(curelm_ptr->field.pe_next, elm))\
104  curelm_ptr = D_RW(curelm_ptr->field.pe_next);\
105  TX_ADD_DIRECT(&curelm_ptr->field.pe_next);\
106  curelm_ptr->field.pe_next = D_RO(elm)->field.pe_next;\
107  }\
108 } while (0)
109 
110 #define POBJ_SLIST_REMOVE_FREE(head, elm, field) do {\
111  POBJ_SLIST_REMOVE(head, elm, field);\
112  TX_FREE(elm);\
113 } while (0)
114 
115 #define POBJ_SLIST_FOREACH(var, head, field)\
116  for ((var) = POBJ_SLIST_FIRST(head);\
117  !TOID_IS_NULL(var);\
118  var = POBJ_SLIST_NEXT(var, field))
119 
120 /*
121  * Tail-queue definitions.
122  */
123 #define POBJ_TAILQ_ENTRY(type)\
124 struct {\
125  TOID(type) pe_next;\
126  TOID(type) pe_prev;\
127 }
128 
129 #define POBJ_TAILQ_HEAD(name, type)\
130 struct name {\
131  TOID(type) pe_first;\
132  TOID(type) pe_last;\
133 }
134 
135 /*
136  * Tail-queue access methods.
137  */
138 #define POBJ_TAILQ_FIRST(head) ((head)->pe_first)
139 #define POBJ_TAILQ_LAST(head) ((head)->pe_last)
140 
141 #define POBJ_TAILQ_EMPTY(head) (TOID_IS_NULL((head)->pe_first))
142 #define POBJ_TAILQ_NEXT(elm, field) (D_RO(elm)->field.pe_next)
143 #define POBJ_TAILQ_PREV(elm, field) (D_RO(elm)->field.pe_prev)
144 
145 /*
146  * Tail-queue List internal methods.
147  */
148 #define _POBJ_SWAP_PTR(elm, field) do {\
149  TOID_TYPEOF(elm) *elm_ptr = D_RW(elm);\
150  TX_ADD_DIRECT(&elm_ptr->field);\
151  __typeof__(elm) temp = elm_ptr->field.pe_prev;\
152  elm_ptr->field.pe_prev = elm_ptr->field.pe_next;\
153  elm_ptr->field.pe_next = temp;\
154 } while (0)
155 
156 /*
157  * Tail-queue functions.
158  */
159 #define POBJ_TAILQ_SWAP_HEAD_TAIL(head, field) do {\
160  __typeof__((head)->pe_first) temp = (head)->pe_first;\
161  TX_ADD_DIRECT(head);\
162  (head)->pe_first = (head)->pe_last;\
163  (head)->pe_last = temp;\
164 } while (0)
165 
166 #define POBJ_TAILQ_FOREACH(var, head, field)\
167  for ((var) = POBJ_TAILQ_FIRST(head);\
168  !TOID_IS_NULL(var);\
169  var = POBJ_TAILQ_NEXT(var, field))
170 
171 #define POBJ_TAILQ_FOREACH_REVERSE(var, head, field)\
172  for ((var) = POBJ_TAILQ_LAST(head);\
173  !TOID_IS_NULL(var);\
174  var = POBJ_TAILQ_PREV(var, field))
175 
176 #define POBJ_TAILQ_INIT(head) do {\
177  TX_ADD_FIELD_DIRECT(head, pe_first);\
178  TOID_ASSIGN((head)->pe_first, MEMOID_NULL);\
179  TX_ADD_FIELD_DIRECT(head, pe_last);\
180  TOID_ASSIGN((head)->pe_last, MEMOID_NULL);\
181 } while (0)
182 
183 #define POBJ_TAILQ_INSERT_HEAD(head, elm, field) do {\
184  TOID_TYPEOF(elm) *elm_ptr = D_RW(elm);\
185  if (TOID_IS_NULL((head)->pe_first)) {\
186  TX_ADD_DIRECT(&elm_ptr->field);\
187  elm_ptr->field.pe_prev = (head)->pe_first;\
188  elm_ptr->field.pe_next = (head)->pe_first;\
189  TX_ADD_DIRECT(head);\
190  (head)->pe_first = elm;\
191  (head)->pe_last = elm;\
192  } else {\
193  TOID_TYPEOF(elm) *first = D_RW((head)->pe_first);\
194  TX_ADD_DIRECT(&elm_ptr->field);\
195  elm_ptr->field.pe_next = (head)->pe_first;\
196  elm_ptr->field.pe_prev = first->field.pe_prev;\
197  TX_ADD_DIRECT(&first->field.pe_prev);\
198  first->field.pe_prev = elm;\
199  TX_SET_DIRECT(head, pe_first, elm);\
200  }\
201 } while (0)
202 
203 #define POBJ_TAILQ_INSERT_TAIL(head, elm, field) do {\
204  TOID_TYPEOF(elm) *elm_ptr = D_RW(elm);\
205  if (TOID_IS_NULL((head)->pe_last)) {\
206  TX_ADD_DIRECT(&elm_ptr->field);\
207  elm_ptr->field.pe_prev = (head)->pe_last;\
208  elm_ptr->field.pe_next = (head)->pe_last;\
209  TX_ADD_DIRECT(head);\
210  (head)->pe_first = elm;\
211  (head)->pe_last = elm;\
212  } else {\
213  TOID_TYPEOF(elm) *last = D_RW((head)->pe_last);\
214  TX_ADD_DIRECT(&elm_ptr->field);\
215  elm_ptr->field.pe_prev = (head)->pe_last;\
216  elm_ptr->field.pe_next = last->field.pe_next;\
217  TX_ADD_DIRECT(&last->field.pe_next);\
218  last->field.pe_next = elm;\
219  TX_SET_DIRECT(head, pe_last, elm);\
220  }\
221 } while (0)
222 
223 #define POBJ_TAILQ_INSERT_AFTER(head, listelm, elm, field) do {\
224  TOID_TYPEOF(elm) *elm_ptr = D_RW(elm);\
225  TOID_TYPEOF(listelm) *listelm_ptr = D_RW(listelm);\
226  TX_ADD_DIRECT(&elm_ptr->field);\
227  elm_ptr->field.pe_prev = listelm;\
228  elm_ptr->field.pe_next = listelm_ptr->field.pe_next;\
229  if (TOID_IS_NULL(listelm_ptr->field.pe_next)) {\
230  TX_SET_DIRECT(head, pe_last, elm);\
231  } else {\
232  TOID_TYPEOF(elm) *next = D_RW(listelm_ptr->field.pe_next);\
233  TX_ADD_DIRECT(&next->field.pe_prev);\
234  next->field.pe_prev = elm;\
235  }\
236  TX_ADD_DIRECT(&listelm_ptr->field.pe_next);\
237  listelm_ptr->field.pe_next = elm;\
238 } while (0)
239 
240 #define POBJ_TAILQ_INSERT_BEFORE(head, listelm, elm, field) do {\
241  TOID_TYPEOF(elm) *elm_ptr = D_RW(elm);\
242  TOID_TYPEOF(listelm) *listelm_ptr = D_RW(listelm);\
243  TX_ADD_DIRECT(&elm_ptr->field);\
244  elm_ptr->field.pe_next = listelm;\
245  elm_ptr->field.pe_prev = listelm_ptr->field.pe_prev;\
246  if (TOID_IS_NULL(listelm_ptr->field.pe_prev)) {\
247  TX_SET_DIRECT(head, pe_first, elm);\
248  } else {\
249  TOID_TYPEOF(elm) *prev = D_RW(listelm_ptr->field.pe_prev);\
250  TX_ADD_DIRECT(&prev->field.pe_next);\
251  prev->field.pe_next = elm; \
252  }\
253  TX_ADD_DIRECT(&listelm_ptr->field.pe_prev);\
254  listelm_ptr->field.pe_prev = elm;\
255 } while (0)
256 
257 #define POBJ_TAILQ_REMOVE(head, elm, field) do {\
258  TOID_TYPEOF(elm) *elm_ptr = D_RW(elm);\
259  if (TOID_IS_NULL(elm_ptr->field.pe_prev) &&\
260  TOID_IS_NULL(elm_ptr->field.pe_next)) {\
261  TX_ADD_DIRECT(head);\
262  (head)->pe_first = elm_ptr->field.pe_prev;\
263  (head)->pe_last = elm_ptr->field.pe_next;\
264  } else {\
265  if (TOID_IS_NULL(elm_ptr->field.pe_prev)) {\
266  TX_SET_DIRECT(head, pe_first, elm_ptr->field.pe_next);\
267  TOID_TYPEOF(elm) *next = D_RW(elm_ptr->field.pe_next);\
268  TX_ADD_DIRECT(&next->field.pe_prev);\
269  next->field.pe_prev = elm_ptr->field.pe_prev;\
270  } else {\
271  TOID_TYPEOF(elm) *prev = D_RW(elm_ptr->field.pe_prev);\
272  TX_ADD_DIRECT(&prev->field.pe_next);\
273  prev->field.pe_next = elm_ptr->field.pe_next;\
274  }\
275  if (TOID_IS_NULL(elm_ptr->field.pe_next)) {\
276  TX_SET_DIRECT(head, pe_last, elm_ptr->field.pe_prev);\
277  TOID_TYPEOF(elm) *prev = D_RW(elm_ptr->field.pe_prev);\
278  TX_ADD_DIRECT(&prev->field.pe_next);\
279  prev->field.pe_next = elm_ptr->field.pe_next;\
280  } else {\
281  TOID_TYPEOF(elm) *next = D_RW(elm_ptr->field.pe_next);\
282  TX_ADD_DIRECT(&next->field.pe_prev);\
283  next->field.pe_prev = elm_ptr->field.pe_prev;\
284  }\
285  }\
286 } while (0)
287 
288 #define POBJ_TAILQ_REMOVE_FREE(head, elm, field) do {\
289  POBJ_TAILQ_REMOVE(head, elm, field);\
290  TX_FREE(elm);\
291 } while (0)
292 
293 /*
294  * 2 cases: only two elements, the rest possibilities
295  * including that elm is the last one
296  */
297 #define POBJ_TAILQ_MOVE_ELEMENT_HEAD(head, elm, field) do {\
298  TOID_TYPEOF(elm) *elm_ptr = D_RW(elm);\
299  if (TOID_EQUALS((head)->pe_last, elm) &&\
300  TOID_EQUALS(D_RO((head)->pe_first)->field.pe_next, elm)) {\
301  _POBJ_SWAP_PTR(elm, field);\
302  _POBJ_SWAP_PTR((head)->pe_first, field);\
303  POBJ_TAILQ_SWAP_HEAD_TAIL(head, field);\
304  } else {\
305  TOID_TYPEOF(elm) *prev = D_RW(elm_ptr->field.pe_prev);\
306  TX_ADD_DIRECT(&prev->field.pe_next);\
307  prev->field.pe_next = elm_ptr->field.pe_next;\
308  if (TOID_EQUALS((head)->pe_last, elm)) {\
309  TX_SET_DIRECT(head, pe_last, elm_ptr->field.pe_prev);\
310  } else {\
311  TOID_TYPEOF(elm) *next = D_RW(elm_ptr->field.pe_next);\
312  TX_ADD_DIRECT(&next->field.pe_prev);\
313  next->field.pe_prev = elm_ptr->field.pe_prev;\
314  }\
315  TX_ADD_DIRECT(&elm_ptr->field);\
316  elm_ptr->field.pe_prev = D_RO((head)->pe_first)->field.pe_prev;\
317  elm_ptr->field.pe_next = (head)->pe_first;\
318  TOID_TYPEOF(elm) *first = D_RW((head)->pe_first);\
319  TX_ADD_DIRECT(&first->field.pe_prev);\
320  first->field.pe_prev = elm;\
321  TX_SET_DIRECT(head, pe_first, elm);\
322  }\
323 } while (0)
324 
325 #define POBJ_TAILQ_MOVE_ELEMENT_TAIL(head, elm, field) do {\
326  TOID_TYPEOF(elm) *elm_ptr = D_RW(elm);\
327  if (TOID_EQUALS((head)->pe_first, elm) &&\
328  TOID_EQUALS(D_RO((head)->pe_last)->field.pe_prev, elm)) {\
329  _POBJ_SWAP_PTR(elm, field);\
330  _POBJ_SWAP_PTR((head)->pe_last, field);\
331  POBJ_TAILQ_SWAP_HEAD_TAIL(head, field);\
332  } else {\
333  TOID_TYPEOF(elm) *next = D_RW(elm_ptr->field.pe_next);\
334  TX_ADD_DIRECT(&next->field.pe_prev);\
335  next->field.pe_prev = elm_ptr->field.pe_prev;\
336  if (TOID_EQUALS((head)->pe_first, elm)) {\
337  TX_SET_DIRECT(head, pe_first, elm_ptr->field.pe_next);\
338  } else { \
339  TOID_TYPEOF(elm) *prev = D_RW(elm_ptr->field.pe_prev);\
340  TX_ADD_DIRECT(&prev->field.pe_next);\
341  prev->field.pe_next = elm_ptr->field.pe_next;\
342  }\
343  TX_ADD_DIRECT(&elm_ptr->field);\
344  elm_ptr->field.pe_prev = (head)->pe_last;\
345  elm_ptr->field.pe_next = D_RO((head)->pe_last)->field.pe_next;\
346  __typeof__(elm_ptr) last = D_RW((head)->pe_last);\
347  TX_ADD_DIRECT(&last->field.pe_next);\
348  last->field.pe_next = elm;\
349  TX_SET_DIRECT(head, pe_last, elm);\
350  } \
351 } while (0)
352 
353 #endif /* PMEMOBJ_LISTS_H */