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
|
#ifndef LIST_H
#define LIST_H
#include <stdlib.h>
struct ListElmt {
void *data;
struct ListElmt *next;
};
struct List {
int size;
int (*match)(const void *key1, const void *key2);
void (*destroy)(void *data);
struct ListElmt *head, *tail;
}
/*
* Initializes a linked list
* List: Linked list to initialize
* destructor: helper to destruct and free data allocated for the list
*/
void list_init(List *list, void (*destroy)(void *data));
/*
* Destroy a linked list, its elements and calls its destructor.
* May or may not free memory, depends on its desctructor.
*/
void list_destroy(List *list);
/*
* Insert a new element AFTER 'element'. If 'element is NULL, the new element is
* inserted at the head of the list. The new element contains a pointer to
* 'data', so, its pointer should remain valid as long as the element remains in
* the list. It's caller's responsibility to manage storage associated with data.
* Return: 0 if successful, negative otherwise
*/
int list_ins_next(List *list, ListElmt *element, const void *data);
/*
* Remove the element just after 'element', if NULL, remove the element at the
* list head. Upon return, 'data' points to the data stored in the removed
* element. It's caller's responsibility to manage storage associated with data.
* Return: 0 if successful, negative otherwise
*/
int list_rem_next(List *list, ListElmt *element, void **data);
#define list_size(list) ((list)->size)
#define list_head(list) ((list)->head)
#define list_tail(list) ((list)->tail)
/* Return: 1 if the element is at the head of the list, 0 otherwise */
#define list_is_head(list, element) ((element) == ((list)->head) ? 1 : 0)
/* Return: 1 if the element is at the tail of the list, 0 otherwise */
#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)
/* Return: Data stored in the element */
#define list_data(element) ((element)->data)
/* Return: Element following the specified element */
#define list_next(element) ((element)->next)
#endif /* LIST_H */
#ifndef DLIST_H
#define DLIST_H
/* Doubly Linked List implementation */
/* doubly-linked list elements */
struct DListElmt {
void *data;
struct DListElmt *prev;
struct DListElmt *next;
};
/* doubly-linked list structure */
struct DList {
int size;
int (*match)(const void *key1, const void *key2);
void (*destroy)(void *data);
struct DlistElmt *head, *tail;
};
/* Public interface */
void dlist_init(struct Dlist *List, void (*destroy)(void *data));
void dlist_destroy(struct DList *list);
int dlist_ins_next(struct DList *list, struct DListElmt *element,
const void *data);
int dlist_ins_prev(struct DList *list, struct DListElmt *element,
const void *data);
int dlist_remove(struct DList *list, struct DListElmt *element, void **data);
#define dlist_size(list) ((list)->size)
#define dlist_head(list) ((list)->head)
#define dlist_tail(list) ((list)->tail)
#define dlist_is_head(element) ((element)->prev == NULL ? 1 : 0)
#define dlist_is_tail(element) ((element)->next == NULL ? 1 : 0)
#define dlist_data(element) ((element)->data)
#define dlist_next(element) ((element)->next)
#define dlist_prev(element) ((element)->prev)
#endif /* DLIST_H */
|
