1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
/*
* BIRD Library -- Linked Lists
*
* (c) 1998 Martin Mares <mj@ucw.cz>
*
* Can be freely distributed and used under the terms of the GNU GPL.
*/
#ifndef _BIRD_LISTS_H_
#define _BIRD_LISTS_H_
/*
* I admit the list structure is very tricky and also somewhat awkward,
* but it's both efficient and easy to manipulate once one understands the
* basic trick: The list head always contains two synthetic nodes which are
* always present in the list: the head and the tail. But as the `next'
* entry of the tail and the `prev' entry of the head are both NULL, the
* nodes can overlap each other:
*
* head head_node.next
* null head_node.prev tail_node.next
* tail tail_node.prev
*/
#include <string.h> // size_t
typedef struct node {
struct node *next, *prev;
} node;
typedef struct list { /* In fact two overlayed nodes */
struct node *head, *null, *tail;
} list;
#define NODE (node *)
#define HEAD(list) ((void *)((list).head))
#define TAIL(list) ((void *)((list).tail))
#define WALK_LIST(n,list) for(n=HEAD(list);(NODE (n))->next; \
n=(void *)((NODE (n))->next))
#define WALK_LIST_DELSAFE(n,nxt,list) \
for(n=HEAD(list); (nxt=(void *)((NODE (n))->next)); n=(void *) nxt)
/* WALK_LIST_FIRST supposes that called code removes each processed node */
#define WALK_LIST_FIRST(n,list) \
while(n=HEAD(list), (NODE (n))->next)
#define WALK_LIST_BACKWARDS(n,list) for(n=TAIL(list);(NODE (n))->prev; \
n=(void *)((NODE (n))->prev))
#define WALK_LIST_BACKWARDS_DELSAFE(n,prv,list) \
for(n=TAIL(list); prv=(void *)((NODE (n))->prev); n=(void *) prv)
#define EMPTY_LIST(list) (!(list).head->next)
/*! \brief Free every node in the list. */
#define WALK_LIST_FREE(list) \
do { \
node *n=0,*nxt=0; \
WALK_LIST_DELSAFE(n,nxt,list) { \
free(n); \
} \
init_list(&list); \
} while(0)
void add_tail(list *, node *);
void add_head(list *, node *);
void rem_node(node *);
void add_tail_list(list *, list *);
void init_list(list *);
void insert_node(node *, node *);
void list_dup(list *dst, list *src, size_t itemsz);
size_t list_size(const list *);
/*!
* \brief List item for string lists.
*/
typedef struct strnode_t {
node n;
char *str;
} strnode_t;
/*! \todo This is broken atm.
#ifndef _BIRD_LISTS_C_
#define LIST_INLINE extern inline
#include "knot/lib/lists.c"
#undef LIST_INLINE
#else
#define LIST_INLINE
#endif
*/
#define LIST_INLINE
#endif
|
