SimpleOS

LXR

Navigation



Site hébergé par : enix

The LXR Cross Referencer for SOS

source navigation ]
diff markup ]
identifier search ]
general search ]
 
 
Article:1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 6.5 ] [ 7 ] [ 7.5 ] [ 8 ] [ 9 ] [ 9.5 ]

001 /* Copyright (C) 2001  David Decotigny
002  
003    This program is free software; you can redistribute it and/or
004    modify it under the terms of the GNU General Public License
005    as published by the Free Software Foundation; either version 2
006    of the License, or (at your option) any later version.
007     
008    This program is distributed in the hope that it will be useful,
009    but WITHOUT ANY WARRANTY; without even the implied warranty of
010    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
011    GNU General Public License for more details.
012     
013    You should have received a copy of the GNU General Public License
014    along with this program; if not, write to the Free Software
015    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
016    USA.
017 */
018 #ifndef _SOS_LIST_H_
019 #define _SOS_LIST_H_
020 
021 /**
022  * @file list.h
023  *
024  * Circular doubly-linked lists implementation entirely based on C
025  * macros
026  */
027 
028 
029 /* *_named are used when next and prev links are not exactly next
030    and prev. For instance when we have next_in_team, prev_in_team,
031    prev_global and next_global */
032 
033 #define list_init_named(list,prev,next) \
034   ((list) = NULL)
035 
036 #define list_singleton_named(list,item,prev,next) ({ \
037   (item)->next = (item)->prev = (item); \
038   (list) = (item); \
039 })
040 
041 #define list_is_empty_named(list,prev,next) \
042   ((list) == NULL)
043 
044 #define list_is_singleton_named(list,prev,next) \
045   ( ((list) != NULL) && ((list)->prev == (list)->next) && ((list) == (list)->next) )
046 
047 #define list_get_head_named(list,prev,next) \
048   (list)
049 
050 #define list_get_tail_named(list,prev,next) \
051   ((list)?((list)->prev):NULL)
052 
053 /* Internal macro : insert before the head == insert at tail */
054 #define __list_insert_atleft_named(before_this,item,prev,next) ({ \
055    (before_this)->prev->next = (item); \
056    (item)->prev = (before_this)->prev; \
057    (before_this)->prev = (item); \
058    (item)->next = (before_this); \
059 })
060 
061 /* @note Before_this and item are expected to be valid ! */
062 #define list_insert_before_named(list,before_this,item,prev,next) ({ \
063    __list_insert_atleft_named(before_this,item,prev,next); \
064    if ((list) == (before_this)) (list) = (item); \
065 })    
066 
067 /** @note After_this and item are expected to be valid ! */
068 #define list_insert_after_named(list,after_this,item,prev,next) ({ \
069    (after_this)->next->prev = (item); \
070    (item)->next = (after_this)->next; \
071    (after_this)->next = (item); \
072    (item)->prev = (after_this); \
073 })
074 
075 #define list_add_head_named(list,item,prev,next) ({ \
076   if (list) \
077     list_insert_before_named(list,list,item,prev,next); \
078   else \
079     list_singleton_named(list,item,prev,next); \
080   (list) = (item); \
081 })
082 
083 #define list_add_tail_named(list,item,prev,next) ({ \
084   if (list) \
085     __list_insert_atleft_named(list,item,prev,next); \
086   else \
087     list_singleton_named(list,item,prev,next); \
088 })
089 
090 /** @note NO check whether item really is in list ! */
091 #define list_delete_named(list,item,prev,next) ({ \
092   if ( ((item)->next == (item)) && ((item)->prev == (item)) ) \
093     (item)->next = (item)->prev = (list) = NULL; \
094   else { \
095     (item)->prev->next = (item)->next; \
096     (item)->next->prev = (item)->prev; \
097     if ((item) == (list)) (list) = (item)->next; \
098     (item)->prev = (item)->next = NULL; \
099   } \
100 })
101 
102 #define list_pop_head_named(list,prev,next) ({ \
103   typeof(list) __ret_elt = (list); \
104   list_delete_named(list,__ret_elt,prev,next); \
105   __ret_elt; })
106 
107 /** Loop statement that iterates through all of its elements, from
108     head to tail */
109 #define list_foreach_forward_named(list,iterator,nb_elements,prev,next) \
110         for (nb_elements=0, (iterator) = (list) ; \
111              (iterator) && (!nb_elements || ((iterator) != (list))) ; \
112              nb_elements++, (iterator) = (iterator)->next )
113 
114 /** Loop statement that iterates through all of its elements, from
115     tail back to head */
116 #define list_foreach_backward_named(list,iterator,nb_elements,prev,next) \
117         for (nb_elements=0, (iterator) = list_get_tail_named(list,prev,next) ; \
118              (iterator) && (!nb_elements || \
119                ((iterator) != list_get_tail_named(list,prev,next))) ; \
120              nb_elements++, (iterator) = (iterator)->prev )
121 
122 #define list_foreach_named list_foreach_forward_named
123 
124 /** True when we exitted early from the foreach loop (ie break) */
125 #define list_foreach_early_break(list,iterator,nb_elements) \
126   ((list) && ( \
127     ((list) != (iterator)) || \
128     ( ((list) == (iterator)) && (nb_elements == 0)) ))
129 
130 /** Loop statement that also removes the item at each iteration. The
131     body of the loop is allowed to delete the iterator element from
132     memory. */
133 #define list_collapse_named(list,iterator,prev,next) \
134         for ( ; ({ ((iterator) = (list)) ; \
135                    if (list) list_delete_named(list,iterator,prev,next) ; \
136                    (iterator); }) ; )
137 
138 
139 /*
140  * the same macros : assume that the prev and next fields are really
141  * named "prev" and "next"
142  */
143 
144 #define list_init(list) \
145   list_init_named(list,prev,next)
146 
147 #define list_singleton(list,item) \
148   list_singleton_named(list,item,prev,next)
149 
150 #define list_is_empty(list) \
151   list_is_empty_named(list,prev,next)
152 
153 #define list_is_singleton(list) \
154   list_is_singleton_named(list,prev,next)
155 
156 #define list_get_head(list) \
157   list_get_head_named(list,prev,next) \
158 
159 #define list_get_tail(list) \
160   list_get_tail_named(list,prev,next) \
161 
162 /* @note Before_this and item are expected to be valid ! */
163 #define list_insert_after(list,after_this,item) \
164   list_insert_after_named(list,after_this,item,prev,next)
165 
166 /* @note After_this and item are expected to be valid ! */
167 #define list_insert_before(list,before_this,item) \
168   list_insert_before_named(list,before_this,item,prev,next)
169 
170 #define list_add_head(list,item) \
171   list_add_head_named(list,item,prev,next)
172 
173 #define list_add_tail(list,item) \
174   list_add_tail_named(list,item,prev,next)
175 
176 /* @note NO check whether item really is in list ! */
177 #define list_delete(list,item) \
178   list_delete_named(list,item,prev,next)
179 
180 #define list_pop_head(list) \
181   list_pop_head_named(list,prev,next)
182 
183 #define list_foreach_forward(list,iterator,nb_elements) \
184   list_foreach_forward_named(list,iterator,nb_elements,prev,next)
185 
186 #define list_foreach_backward(list,iterator,nb_elements) \
187   list_foreach_backward_named(list,iterator,nb_elements,prev,next)
188 
189 #define list_foreach list_foreach_forward
190 
191 #define list_collapse(list,iterator) \
192   list_collapse_named(list,iterator,prev,next)
193 
194 #endif /* _SOS_LIST_H_ */

source navigation ] diff markup ] identifier search ] general search ]