← Back to branch summary

~galfy/helenos/bird-port-mainline

« back to all changes in this revision

Viewing changes to uspace/lib/libc/include/adt/list.h

  • Committer: Martin Decky
  • Date: 2009-08-04 11:19:19 UTC
  • Revision ID: martin@uranus.dsrg.hide.ms.mff.cuni.cz-20090804111919-evyclddlr3v5lhmp
Initial import

Show diffs side-by-side

added added

removed removed

Lines of Context:
uspace/lib/libc/include/adt/list.h
 
1
/*
 
2
 * Copyright (c) 2001-2004 Jakub Jermar
 
3
 * All rights reserved.
 
4
 *
 
5
 * Redistribution and use in source and binary forms, with or without
 
6
 * modification, are permitted provided that the following conditions
 
7
 * are met:
 
8
 *
 
9
 * - Redistributions of source code must retain the above copyright
 
10
 *   notice, this list of conditions and the following disclaimer.
 
11
 * - Redistributions in binary form must reproduce the above copyright
 
12
 *   notice, this list of conditions and the following disclaimer in the
 
13
 *   documentation and/or other materials provided with the distribution.
 
14
 * - The name of the author may not be used to endorse or promote products
 
15
 *   derived from this software without specific prior written permission.
 
16
 *
 
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 
18
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 
19
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 
20
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 
21
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 
22
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 
23
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 
24
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 
25
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 
26
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
27
 */
 
28
 
 
29
/** @addtogroup libc
 
30
 * @{
 
31
 */
 
32
/** @file
 
33
 */
 
34
 
 
35
#ifndef LIBC_LIST_H_
 
36
#define LIBC_LIST_H_
 
37
 
 
38
#include <unistd.h>
 
39
 
 
40
/** Doubly linked list head and link type. */
 
41
typedef struct link {
 
42
        struct link *prev;  /**< Pointer to the previous item in the list. */
 
43
        struct link *next;  /**< Pointer to the next item in the list. */
 
44
} link_t;
 
45
 
 
46
/** Declare and initialize statically allocated list.
 
47
 *
 
48
 * @param name Name of the new statically allocated list.
 
49
 */
 
50
#define LIST_INITIALIZE(name)  link_t name = { \
 
51
        .prev = &name, \
 
52
        .next = &name \
 
53
}
 
54
 
 
55
/** Initialize doubly-linked circular list link
 
56
 *
 
57
 * Initialize doubly-linked list link.
 
58
 *
 
59
 * @param link Pointer to link_t structure to be initialized.
 
60
 */
 
61
static inline void link_initialize(link_t *link)
 
62
{
 
63
        link->prev = NULL;
 
64
        link->next = NULL;
 
65
}
 
66
 
 
67
/** Initialize doubly-linked circular list
 
68
 *
 
69
 * Initialize doubly-linked circular list.
 
70
 *
 
71
 * @param head Pointer to link_t structure representing head of the list.
 
72
 */
 
73
static inline void list_initialize(link_t *head)
 
74
{
 
75
        head->prev = head;
 
76
        head->next = head;
 
77
}
 
78
 
 
79
/** Add item to the beginning of doubly-linked circular list
 
80
 *
 
81
 * Add item to the beginning of doubly-linked circular list.
 
82
 *
 
83
 * @param link Pointer to link_t structure to be added.
 
84
 * @param head Pointer to link_t structure representing head of the list.
 
85
 */
 
86
static inline void list_prepend(link_t *link, link_t *head)
 
87
{
 
88
        link->next = head->next;
 
89
        link->prev = head;
 
90
        head->next->prev = link;
 
91
        head->next = link;
 
92
}
 
93
 
 
94
/** Add item to the end of doubly-linked circular list
 
95
 *
 
96
 * Add item to the end of doubly-linked circular list.
 
97
 *
 
98
 * @param link Pointer to link_t structure to be added.
 
99
 * @param head Pointer to link_t structure representing head of the list.
 
100
 */
 
101
static inline void list_append(link_t *link, link_t *head)
 
102
{
 
103
        link->prev = head->prev;
 
104
        link->next = head;
 
105
        head->prev->next = link;
 
106
        head->prev = link;
 
107
}
 
108
 
 
109
/** Insert item before another item in doubly-linked circular list. */
 
110
static inline void list_insert_before(link_t *l, link_t *r)
 
111
{
 
112
        list_append(l, r);
 
113
}
 
114
 
 
115
/** Insert item after another item in doubly-linked circular list. */
 
116
static inline void list_insert_after(link_t *r, link_t *l)
 
117
{
 
118
        list_prepend(l, r);
 
119
}
 
120
 
 
121
/** Remove item from doubly-linked circular list
 
122
 *
 
123
 * Remove item from doubly-linked circular list.
 
124
 *
 
125
 * @param link Pointer to link_t structure to be removed from the list it is contained in.
 
126
 */
 
127
static inline void list_remove(link_t *link)
 
128
{
 
129
        link->next->prev = link->prev;
 
130
        link->prev->next = link->next;
 
131
        link_initialize(link);
 
132
}
 
133
 
 
134
/** Query emptiness of doubly-linked circular list
 
135
 *
 
136
 * Query emptiness of doubly-linked circular list.
 
137
 *
 
138
 * @param head Pointer to link_t structure representing head of the list.
 
139
 */
 
140
static inline int list_empty(link_t *head)
 
141
{
 
142
        return ((head->next == head) ? 1 : 0);
 
143
}
 
144
 
 
145
 
 
146
/** Split or concatenate headless doubly-linked circular list
 
147
 *
 
148
 * Split or concatenate headless doubly-linked circular list.
 
149
 *
 
150
 * Note that the algorithm works both directions:
 
151
 * concatenates splitted lists and splits concatenated lists.
 
152
 *
 
153
 * @param part1 Pointer to link_t structure leading the first (half of the headless) list.
 
154
 * @param part2 Pointer to link_t structure leading the second (half of the headless) list. 
 
155
 */
 
156
static inline void headless_list_split_or_concat(link_t *part1, link_t *part2)
 
157
{
 
158
        part1->prev->next = part2;
 
159
        part2->prev->next = part1;
 
160
        
 
161
        link_t *hlp = part1->prev;
 
162
        
 
163
        part1->prev = part2->prev;
 
164
        part2->prev = hlp;
 
165
}
 
166
 
 
167
 
 
168
/** Split headless doubly-linked circular list
 
169
 *
 
170
 * Split headless doubly-linked circular list.
 
171
 *
 
172
 * @param part1 Pointer to link_t structure leading the first half of the headless list.
 
173
 * @param part2 Pointer to link_t structure leading the second half of the headless list. 
 
174
 */
 
175
static inline void headless_list_split(link_t *part1, link_t *part2)
 
176
{
 
177
        headless_list_split_or_concat(part1, part2);
 
178
}
 
179
 
 
180
/** Concatenate two headless doubly-linked circular lists
 
181
 *
 
182
 * Concatenate two headless doubly-linked circular lists.
 
183
 *
 
184
 * @param part1 Pointer to link_t structure leading the first headless list.
 
185
 * @param part2 Pointer to link_t structure leading the second headless list. 
 
186
 */
 
187
static inline void headless_list_concat(link_t *part1, link_t *part2)
 
188
{
 
189
        headless_list_split_or_concat(part1, part2);
 
190
}
 
191
 
 
192
#define list_get_instance(link, type, member)  ((type *) (((void *)(link)) - ((void *) &(((type *) NULL)->member))))
 
193
 
 
194
extern int list_member(const link_t *link, const link_t *head);
 
195
extern void list_concat(link_t *head1, link_t *head2);
 
196
extern unsigned int list_count(const link_t *link);
 
197
 
 
198
#endif
 
199
 
 
200
/** @}
 
201
 */