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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
|
/*
* dlist.h
*
* Copyright (C) 2003 Eric J Bohm
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library 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
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
*/
#ifndef _DLIST_H_
#define _DLIST_H_
/* Double linked list header.
* navigate your list with DLIST_PREV and DLIST_NEXT. These are macros
* so function call overhead is minimized.
* Supports perl style push, pop, shift, unshift list semantics.
* You allocate the data and give dlist the pointer. If your data is
* complex set the dlist->del_func to a an appropriate delete using
* dlist_new_with_delete. Your delete function must match
(void * )(del(void *)
*Otherwise dlist will just use free.
* NOTE: The small amount of pain involved in doing that allows us to
* avoid copy in copy out semantics.
* Dlist uses an internal mark pointer to keep track of where you are
* in the list.
* insert and delete take a directional parameter. Where direction
* corresponds to the direction in which you want the list to go.
* true direction corresponded to progressing forward in the last
* false to regressing in the list.
* so a dlist_insert(yourlist,item,1) will insert it after the mark
* so a dlist_insert(yourlist,item,0) will insert it before the mark
* any insert will move the mark to the new node regardless of the direction.
* Just use the dlist_(insert|delete)_(before|after) macros if you do not want
* to think about it.
*/
#include <stddef.h>
typedef struct dl_node {
struct dl_node *prev;
struct dl_node *next;
void *data;
} DL_node;
typedef struct dlist {
DL_node *marker;
unsigned long count;
size_t data_size;
void (*del_func)(void *);
DL_node headnode;
DL_node *head;
} Dlist;
Dlist *dlist_new(size_t datasize);
Dlist *dlist_new_with_delete(size_t datasize,void (*del_func)(void*));
void *_dlist_mark_move(Dlist *list,int direction);
void *dlist_mark(Dlist *);
void dlist_start(Dlist *);
void dlist_end(Dlist *);
void dlist_move(struct dlist *source, struct dlist *dest, struct dl_node *target,int direction);
void *dlist_insert(Dlist *,void *,int) ;
void *dlist_insert_sorted(struct dlist *list, void *new_elem, int (*sorter)(void *, void *));
void dlist_delete(Dlist *,int);
void dlist_push(Dlist *,void *);
void dlist_unshift(Dlist *,void *);
void dlist_unshift_sorted(Dlist *,void *,int (*sorter)(void *, void *));
void *dlist_pop(Dlist *);
void *dlist_shift(Dlist *);
void dlist_destroy(Dlist *);
int _dlist_merge(struct dlist *listsource, struct dlist *listdest, unsigned int passcount, int (*compare)(void *, void *));
void *dlist_find_custom(struct dlist *list, void *target, int (*comp)(void *, void *));
void dlist_sort_custom(struct dlist *list, int (*compare)(void *, void *));
void _dlist_swap(struct dlist *list, struct dl_node *a, struct dl_node *b);
void dlist_transform(struct dlist *list, void (*node_operation)(void *));
/*
* _dlist_remove is for internal use only
* _dlist_mark_move is for internal use only
*/
void *_dlist_remove(struct dlist *,struct dl_node *,int );
void *_dlist_insert_dlnode(struct dlist *list,struct dl_node *new_node,int direction);
#define dlist_prev(A) _dlist_mark_move((A),0)
#define dlist_next(A) _dlist_mark_move((A),1)
#define dlist_insert_before(A,B) dlist_insert((A),(B),0)
#define dlist_insert_after(A,B) dlist_insert((A),(B),1)
#define dlist_delete_before(A) dlist_delete((A),0)
#define dlist_delete_after(A) dlist_delete((A),1)
/**
* provide for loop header which iterates the mark from start to end
* list: the dlist pointer, use dlist_mark(list) to get iterator
*/
#define dlist_for_each(list) \
for(dlist_start(list),dlist_next(list); \
(list)->marker!=(list)->head;dlist_next(list))
/**
* provide for loop header which iterates the mark from end to start
* list: the dlist pointer, use dlist_mark(list) to get iterator
*/
#define dlist_for_each_rev(list) \
for(dlist_end(list),dlist_prev(list); \
(list)->marker!=(list)->head;dlist_prev(list))
/**
* provide for loop header which iterates through the list without moving mark
* list: the dlist_pointer
* iterator: dl_node pointer to iterate
*/
#define dlist_for_each_nomark(list,iterator) \
for((iterator)=(list)->head->next; (iterator)!=(list)->head; \
(iterator)=(iterator)->next)
/**
* provide for loop header which iterates through the list without moving mark
* in reverse
* list: the dlist_pointer
* iterator: dl_node pointer to iterate
*/
#define dlist_for_each_nomark_rev(list,iterator) \
for((iterator)=(list)->head->prev; (iterator)!=(list)->head; \
(iterator)=(iterator)->prev)
/**
* provide for loop header which iterates through the list providing a
* data iterator
* list: the dlist pointer
* data_iterator: the pointer of type datatype to iterate
* datatype: actual type of the contents in the dl_node->data
*/
#define dlist_for_each_data(list,data_iterator,datatype) \
for(dlist_start(list), (data_iterator)=(datatype *) dlist_next(list); \
(list)->marker!=(list)->head;(data_iterator)=(datatype *) dlist_next(list))
/**
* provide for loop header which iterates through the list providing a
* data iterator in reverse
* list: the dlist pointer
* data_iterator: the pointer of type datatype to iterate
* datatype: actual type of the contents in the dl_node->data
*/
#define dlist_for_each_data_rev(list,data_iterator,datatype) \
for(dlist_end(list), (data_iterator)=(datatype *) dlist_prev(list); \
(list)->marker!=(list)->head;(data_iterator)=(datatype *) dlist_prev(list))
/**
* provide for loop header which iterates through the list providing a
* data iterator without moving the mark
* list: the dlist pointer
* iterator: the dl_node pointer to iterate
* data_iterator: the pointer of type datatype to iterate
* datatype: actual type of the contents in the dl_node->data
*/
#define dlist_for_each_data_nomark(list,iterator,data_iterator,datatype) \
for((iterator)=(list)->head->next, (data_iterator)=(datatype *) (iterator)->data; \
(iterator)!=(list)->head;(iterator)=(iterator)->next,(data_iterator)=(datatype *) (iterator))
/**
* provide for loop header which iterates through the list providing a
* data iterator in reverse without moving the mark
* list: the dlist pointer
* iterator: the dl_node pointer to iterate
* data_iterator: the pointer of type datatype to iterate
* datatype: actual type of the contents in the dl_node->data
*/
#define dlist_for_each_data_nomark_rev(list,iterator, data_iterator,datatype) \
for((iterator)=(list)->head->prev, (data_iterator)=(datatype *) (iterator)->data; \
(iterator)!=(list)->head;(iterator)=(iterator)->prev,(data_iterator)=(datatype *) (iterator))
#endif /* _DLIST_H_ */
|
