Subversion Repositories HelenOS

Rev

Rev 365 | Rev 430 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

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