source: trunk/kernel/libk/list.h @ 608

Last change on this file since 608 was 457, checked in by alain, 6 years ago

This version modifies the exec syscall and fixes a large number of small bugs.
The version number has been updated (0.1)

File size: 9.3 KB
Line 
1/*
2 * list.h - Double circular chained lists, inspired from linux
3 *
4 * Authors Ghassan Almaless  (2008,2009,2010,2011,2012)
5 *         Alain Greiner     (2016)
6 *
7 * Copyright (c) UPMC Sorbonne Universites
8 *
9 * This file is part of ALMOS-MKH     
10 *
11 * ALMOS-MKH is free software; you can redistribute it and/or modify it
12 * under the terms of the GNU General Public License as published by
13 * the Free Software Foundation; version 2.0 of the License.
14 *
15 * ALMOS-MKH is distributed in the hope that it will be useful, but
16 * WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18 * General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with ALMOS-MKH; if not, write to the Free Software Foundation,
22 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
23 */
24
25#ifndef _ALMOS_LIST_H_
26#define _ALMOS_LIST_H_
27
28#include <kernel_config.h>
29#include <hal_kernel_types.h>
30
31#ifndef NULL
32#define NULL (void *) 0
33#endif
34
35
36/***************************************************************************
37 * This macro return an uint32_t that is the offset (number of bytes)
38 * of a field in a structure.
39 * @ type   : structure type
40 * @ member : name of the field
41 **************************************************************************/
42
43#ifndef OFFSETOF
44#define OFFSETOF( type , member ) ((intptr_t) & ((type *)0)->member)
45#endif
46
47////////////////////////////////////////////////////////////////////////////
48////////////////////////////////////////////////////////////////////////////
49//          Double circular linked list functions & macros
50////////////////////////////////////////////////////////////////////////////
51////////////////////////////////////////////////////////////////////////////
52
53/***************************************************************************
54 * This structure defines a Double Circular Linked List entry.
55 * Note : The list root is an extra list-entry_t, that is NOT part
56 *            of the set of linked elements.
57 **************************************************************************/
58
59typedef struct list_entry_s
60{
61        struct list_entry_s * next;
62        struct list_entry_s * pred;
63}
64list_entry_t;
65
66/***************************************************************************
67 * This macro returns a pointer on a structure containing a list_entry_t.
68 ***************************************************************************
69 * @ list_ptr       : pointer on the list_entry
70 * @ container_type : type of the structure containing the list-entry
71 * @ member_name    : name of the list_entry field
72 **************************************************************************/
73
74#define LIST_ELEMENT( list_ptr , container_type , member_name)          \
75        ({const typeof(((container_type*)0)->member_name) *__member_ptr = (list_ptr); \
76        (container_type *)( (char*)__member_ptr - OFFSETOF( container_type , member_name ));})
77
78/***************************************************************************
79 * This macro returns the first element of a rooted double linked list.
80 ***************************************************************************
81 * @ root     : pointer on the list root
82 * @ type     : type of the linked elements
83 * @ member   : name of the list_entry_t field
84 **************************************************************************/
85
86#define LIST_FIRST( root , type , member )              \
87        LIST_ELEMENT( (root)->next , type , member )
88
89/***************************************************************************
90 * This macro returns the last element of a rooted double linked list.
91 ***************************************************************************
92 * @ root     : pointer on the list root
93 * @ type     : type of the linked elements
94 * @ member   : name of the list_entry_t field
95 **************************************************************************/
96
97#define LIST_LAST( root , type , member )               \
98        LIST_ELEMENT( (root)->pred , type , member )
99
100/***************************************************************************
101 * This macro traverse a rooted double linked list in forward order.
102 * WARNING : Don't use 2 LIST_FOREACH in the same function, because the
103 * variable __ptr will be defined twice, wich result in a compilation error.
104 ***************************************************************************
105 * @ root      : pointer on the root list_entry
106 * @ iter      : pointer on a list_entry
107 **************************************************************************/
108
109#define LIST_FOREACH( root , iter ) \
110for( (iter) = (root)->next ;        \
111     (iter) != (root) ;                         \
112     (iter) = (iter)->next )
113       
114/***************************************************************************
115 * This macro traverse a rooted double linked list in backward order.
116 * WARNING : same as the forward traversal
117 ***************************************************************************
118 * @ root      : pointer on the root list_entry
119 * @ iter      : pointer on a list_entry
120 **************************************************************************/
121
122#define LIST_FOREACH_BACKWARD( root , iter )  \
123for( (iter) = (root)->pred ;                  \
124     (iter) != (root) ;                       \
125     (iter) = (iter)->pred )
126
127/***************************************************************************
128 * This function initializes the root of a rooted double linked list.
129 ***************************************************************************
130 * @ root    : pointer on the list root
131 **************************************************************************/
132static inline void list_root_init( list_entry_t * root )
133{
134        root->next = root;
135        root->pred = root;
136}
137
138/***************************************************************************
139 * This function initializes an entry of a rooted double linked list.
140 ***************************************************************************
141 * @ entry   : pointer on the list-entry to be initialized
142 **************************************************************************/
143static inline void list_entry_init( list_entry_t * entry )
144{
145        entry->next = NULL;
146        entry->pred = NULL;
147}
148
149/***************************************************************************
150 * This function inserts a new entry in first place of a double linked list.
151 ***************************************************************************
152 * @ root    : pointer on the list root
153 * @ entry   : pointer on the list-entry to be inserted
154 **************************************************************************/
155static inline void list_add_first( list_entry_t * root, 
156                                   list_entry_t * entry )
157{
158    list_entry_t * pred_entry;
159    list_entry_t * next_entry;
160 
161        pred_entry = root;
162        next_entry = root->next;
163       
164        entry->next = next_entry;
165        entry->pred = pred_entry;
166 
167        pred_entry->next = entry;
168        next_entry->pred = entry;
169}
170
171/***************************************************************************
172 * This function inserts a new entry in last place of a double linked list.
173 ***************************************************************************
174 * @ root    : pointer on the list root
175 * @ entry   : pointer on the list-entry to be inserted
176 **************************************************************************/
177static inline void list_add_last( list_entry_t * root,
178                                  list_entry_t * entry )
179{
180    list_entry_t * pred_entry;
181    list_entry_t * next_entry;
182
183        pred_entry = root->pred;
184        next_entry = root;
185       
186        entry->next = next_entry;
187        entry->pred = pred_entry;
188 
189        pred_entry->next = entry;
190        next_entry->pred = entry;
191}
192
193/***************************************************************************
194 * This function returns true if the list is empty.
195 ***************************************************************************
196 * @ root    : pointer on the list root
197 **************************************************************************/
198static inline bool_t list_is_empty( list_entry_t * root )
199{
200    return ( root == root->next );
201}
202
203/***************************************************************************
204 * This function remove an entry from a rooted double linked list.
205 ***************************************************************************
206 * @ entry : pointer on the entry to be removed.
207 **************************************************************************/
208static inline void list_unlink( list_entry_t * entry )
209{
210        list_entry_t * pred_entry;
211    list_entry_t * next_entry;
212
213        pred_entry = entry->pred;
214        next_entry = entry->next;
215
216        pred_entry->next = entry->next;
217        next_entry->pred = entry->pred;
218}
219
220/***************************************************************************
221 * This function replace an entry in a rooted double linked list.
222 ***************************************************************************
223 * @current  : entry to be removed.
224 * @new      : entry to be introduced.
225 **************************************************************************/
226static inline void list_replace( list_entry_t * current,
227                                 list_entry_t * new )
228{
229    list_entry_t * pred_entry;
230    list_entry_t * next_entry;
231
232        pred_entry = current->pred;
233        next_entry = current->next;
234
235        new->next = next_entry;
236        new->pred = pred_entry;
237
238        pred_entry->next = new;
239        next_entry->pred = new;
240}
241
242
243#endif  /* _ALMOS_LIST_H_ */
Note: See TracBrowser for help on using the repository browser.