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