← Back to branch summary

~galfy/helenos/bird-port-mainline

« back to all changes in this revision

Viewing changes to kernel/generic/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:
kernel/generic/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 genericadt
 
30
 * @{
 
31
 */
 
32
/** @file
 
33
 */
 
34
 
 
35
#ifndef KERN_LIST_H_
 
36
#define KERN_LIST_H_
 
37
 
 
38
#include <arch/types.h>
 
39
#include <typedefs.h>
 
40
 
 
41
/** Doubly linked list head and link type. */
 
42
typedef struct link {
 
43
        struct link *prev;      /**< Pointer to the previous item in the list. */
 
44
        struct link *next;      /**< Pointer to the next item in the list. */
 
45
} link_t;
 
46
 
 
47
/** Declare and initialize statically allocated list.
 
48
 *
 
49
 * @param name Name of the new statically allocated list.
 
50
 */
 
51
#define LIST_INITIALIZE(name) \
 
52
        link_t name = { .prev = &name, .next = &name }
 
53
 
 
54
/** Initialize doubly-linked circular list link
 
55
 *
 
56
 * Initialize doubly-linked list link.
 
57
 *
 
58
 * @param link Pointer to link_t structure to be initialized.
 
59
 */
 
60
static inline void link_initialize(link_t *link)
 
61
{
 
62
        link->prev = NULL;
 
63
        link->next = NULL;
 
64
}
 
65
 
 
66
/** Initialize doubly-linked circular list
 
67
 *
 
68
 * Initialize doubly-linked circular list.
 
69
 *
 
70
 * @param head Pointer to link_t structure representing head of the list.
 
71
 */
 
72
static inline void list_initialize(link_t *head)
 
73
{
 
74
        head->prev = head;
 
75
        head->next = head;
 
76
}
 
77
 
 
78
/** Add item to the beginning of doubly-linked circular list
 
79
 *
 
80
 * Add item to the beginning of doubly-linked circular list.
 
81
 *
 
82
 * @param link Pointer to link_t structure to be added.
 
83
 * @param head Pointer to link_t structure representing head of the list.
 
84
 */
 
85
static inline void list_prepend(link_t *link, link_t *head)
 
86
{
 
87
        link->next = head->next;
 
88
        link->prev = head;
 
89
        head->next->prev = link;
 
90
        head->next = link;
 
91
}
 
92
 
 
93
/** Add item to the end of doubly-linked circular list
 
94
 *
 
95
 * Add item to the end of doubly-linked circular list.
 
96
 *
 
97
 * @param link Pointer to link_t structure to be added.
 
98
 * @param head Pointer to link_t structure representing head of the list.
 
99
 */
 
100
static inline void list_append(link_t *link, link_t *head)
 
101
{
 
102
        link->prev = head->prev;
 
103
        link->next = head;
 
104
        head->prev->next = link;
 
105
        head->prev = link;
 
106
}
 
107
 
 
108
/** Remove item from doubly-linked circular list
 
109
 *
 
110
 * Remove item from doubly-linked circular list.
 
111
 *
 
112
 * @param link  Pointer to link_t structure to be removed from the list it is
 
113
 *              contained in.
 
114
 */
 
115
static inline void list_remove(link_t *link)
 
116
{
 
117
        link->next->prev = link->prev;
 
118
        link->prev->next = link->next;
 
119
        link_initialize(link);
 
120
}
 
121
 
 
122
/** Query emptiness of doubly-linked circular list
 
123
 *
 
124
 * Query emptiness of doubly-linked circular list.
 
125
 *
 
126
 * @param head Pointer to link_t structure representing head of the list.
 
127
 */
 
128
static inline bool list_empty(link_t *head)
 
129
{
 
130
        return head->next == head ? true : false;
 
131
}
 
132
 
 
133
 
 
134
/** Split or concatenate headless doubly-linked circular list
 
135
 *
 
136
 * Split or concatenate headless doubly-linked circular list.
 
137
 *
 
138
 * Note that the algorithm works both directions:
 
139
 * concatenates splitted lists and splits concatenated lists.
 
140
 *
 
141
 * @param part1 Pointer to link_t structure leading the first (half of the
 
142
 *              headless) list.
 
143
 * @param part2 Pointer to link_t structure leading the second (half of the
 
144
 *              headless) list. 
 
145
 */
 
146
static inline void headless_list_split_or_concat(link_t *part1, link_t *part2)
 
147
{
 
148
        link_t *hlp;
 
149
 
 
150
        part1->prev->next = part2;
 
151
        part2->prev->next = part1;      
 
152
        hlp = part1->prev;
 
153
        part1->prev = part2->prev;
 
154
        part2->prev = hlp;
 
155
}
 
156
 
 
157
 
 
158
/** Split headless doubly-linked circular list
 
159
 *
 
160
 * Split headless doubly-linked circular list.
 
161
 *
 
162
 * @param part1 Pointer to link_t structure leading the first half of the
 
163
 *              headless list.
 
164
 * @param part2 Pointer to link_t structure leading the second half of the
 
165
 *              headless list. 
 
166
 */
 
167
static inline void headless_list_split(link_t *part1, link_t *part2)
 
168
{
 
169
        headless_list_split_or_concat(part1, part2);
 
170
}
 
171
 
 
172
/** Concatenate two headless doubly-linked circular lists
 
173
 *
 
174
 * Concatenate two headless doubly-linked circular lists.
 
175
 *
 
176
 * @param part1 Pointer to link_t structure leading the first headless list.
 
177
 * @param part2 Pointer to link_t structure leading the second headless list.
 
178
 */
 
179
static inline void headless_list_concat(link_t *part1, link_t *part2)
 
180
{
 
181
        headless_list_split_or_concat(part1, part2);
 
182
}
 
183
 
 
184
#define list_get_instance(link, type, member) \
 
185
        ((type *)(((uint8_t *)(link)) - ((uint8_t *)&(((type *)NULL)->member))))
 
186
 
 
187
extern bool list_member(const link_t *link, const link_t *head);
 
188
extern void list_concat(link_t *head1, link_t *head2);
 
189
 
 
190
#endif
 
191
 
 
192
/** @}
 
193
 */