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 << 046 << 047 #define list_get_head_named(list,prev,next) \ 044 #define list_get_head_named(list,prev,next) \ 048 (list) 045 (list) 049 046 050 #define list_get_tail_named(list,prev,next) \ 047 #define list_get_tail_named(list,prev,next) \ 051 ((list)?((list)->prev):NULL) 048 ((list)?((list)->prev):NULL) 052 049 053 /* Internal macro : insert before the head == 050 /* Internal macro : insert before the head == insert at tail */ 054 #define __list_insert_atleft_named(before_this 051 #define __list_insert_atleft_named(before_this,item,prev,next) ({ \ 055 (before_this)->prev->next = (item); \ 052 (before_this)->prev->next = (item); \ 056 (item)->prev = (before_this)->prev; \ 053 (item)->prev = (before_this)->prev; \ 057 (before_this)->prev = (item); \ 054 (before_this)->prev = (item); \ 058 (item)->next = (before_this); \ 055 (item)->next = (before_this); \ 059 }) 056 }) 060 057 061 /* @note Before_this and item are expected to 058 /* @note Before_this and item are expected to be valid ! */ 062 #define list_insert_before_named(list,before_t 059 #define list_insert_before_named(list,before_this,item,prev,next) ({ \ 063 __list_insert_atleft_named(before_this,item 060 __list_insert_atleft_named(before_this,item,prev,next); \ 064 if ((list) == (before_this)) (list) = (item 061 if ((list) == (before_this)) (list) = (item); \ 065 }) 062 }) 066 063 067 /** @note After_this and item are expected to 064 /** @note After_this and item are expected to be valid ! */ 068 #define list_insert_after_named(list,after_thi 065 #define list_insert_after_named(list,after_this,item,prev,next) ({ \ 069 (after_this)->next->prev = (item); \ 066 (after_this)->next->prev = (item); \ 070 (item)->next = (after_this)->next; \ 067 (item)->next = (after_this)->next; \ 071 (after_this)->next = (item); \ 068 (after_this)->next = (item); \ 072 (item)->prev = (after_this); \ 069 (item)->prev = (after_this); \ 073 }) 070 }) 074 071 075 #define list_add_head_named(list,item,prev,nex 072 #define list_add_head_named(list,item,prev,next) ({ \ 076 if (list) \ 073 if (list) \ 077 list_insert_before_named(list,list,item,pr 074 list_insert_before_named(list,list,item,prev,next); \ 078 else \ 075 else \ 079 list_singleton_named(list,item,prev,next); 076 list_singleton_named(list,item,prev,next); \ 080 (list) = (item); \ 077 (list) = (item); \ 081 }) 078 }) 082 079 083 #define list_add_tail_named(list,item,prev,nex 080 #define list_add_tail_named(list,item,prev,next) ({ \ 084 if (list) \ 081 if (list) \ 085 __list_insert_atleft_named(list,item,prev, 082 __list_insert_atleft_named(list,item,prev,next); \ 086 else \ 083 else \ 087 list_singleton_named(list,item,prev,next); 084 list_singleton_named(list,item,prev,next); \ 088 }) 085 }) 089 086 090 /** @note NO check whether item really is in l 087 /** @note NO check whether item really is in list ! */ 091 #define list_delete_named(list,item,prev,next) 088 #define list_delete_named(list,item,prev,next) ({ \ 092 if ( ((item)->next == (item)) && ((item)->pr 089 if ( ((item)->next == (item)) && ((item)->prev == (item)) ) \ 093 (item)->next = (item)->prev = (list) = NUL 090 (item)->next = (item)->prev = (list) = NULL; \ 094 else { \ 091 else { \ 095 (item)->prev->next = (item)->next; \ 092 (item)->prev->next = (item)->next; \ 096 (item)->next->prev = (item)->prev; \ 093 (item)->next->prev = (item)->prev; \ 097 if ((item) == (list)) (list) = (item)->nex 094 if ((item) == (list)) (list) = (item)->next; \ 098 (item)->prev = (item)->next = NULL; \ 095 (item)->prev = (item)->next = NULL; \ 099 } \ 096 } \ 100 }) 097 }) 101 098 102 #define list_pop_head_named(list,prev,next) ({ 099 #define list_pop_head_named(list,prev,next) ({ \ 103 typeof(list) __ret_elt = (list); \ 100 typeof(list) __ret_elt = (list); \ 104 list_delete_named(list,__ret_elt,prev,next); 101 list_delete_named(list,__ret_elt,prev,next); \ 105 __ret_elt; }) 102 __ret_elt; }) 106 103 107 /** Loop statement that iterates through all o 104 /** Loop statement that iterates through all of its elements, from 108 head to tail */ 105 head to tail */ 109 #define list_foreach_forward_named(list,iterat 106 #define list_foreach_forward_named(list,iterator,nb_elements,prev,next) \ 110 for (nb_elements=0, (iterator) = (list 107 for (nb_elements=0, (iterator) = (list) ; \ 111 (iterator) && (!nb_elements || (( 108 (iterator) && (!nb_elements || ((iterator) != (list))) ; \ 112 nb_elements++, (iterator) = (iter 109 nb_elements++, (iterator) = (iterator)->next ) 113 110 114 /** Loop statement that iterates through all o 111 /** Loop statement that iterates through all of its elements, from 115 tail back to head */ 112 tail back to head */ 116 #define list_foreach_backward_named(list,itera 113 #define list_foreach_backward_named(list,iterator,nb_elements,prev,next) \ 117 for (nb_elements=0, (iterator) = list_ 114 for (nb_elements=0, (iterator) = list_get_tail_named(list,prev,next) ; \ 118 (iterator) && (!nb_elements || \ 115 (iterator) && (!nb_elements || \ 119 ((iterator) != list_get_tail_na 116 ((iterator) != list_get_tail_named(list,prev,next))) ; \ 120 nb_elements++, (iterator) = (iter 117 nb_elements++, (iterator) = (iterator)->prev ) 121 118 122 #define list_foreach_named list_foreach_forwar 119 #define list_foreach_named list_foreach_forward_named 123 120 124 /** True when we exitted early from the foreac 121 /** True when we exitted early from the foreach loop (ie break) */ 125 #define list_foreach_early_break(list,iterator 122 #define list_foreach_early_break(list,iterator,nb_elements) \ 126 ((list) && ( \ 123 ((list) && ( \ 127 ((list) != (iterator)) || \ 124 ((list) != (iterator)) || \ 128 ( ((list) == (iterator)) && (nb_elements = 125 ( ((list) == (iterator)) && (nb_elements == 0)) )) 129 126 130 /** Loop statement that also removes the item !! 127 /** Loop statement that also removes the item at each iteration */ 131 body of the loop is allowed to delete the << 132 memory. */ << 133 #define list_collapse_named(list,iterator,prev 128 #define list_collapse_named(list,iterator,prev,next) \ 134 for ( ; ({ ((iterator) = (list)) ; \ 129 for ( ; ({ ((iterator) = (list)) ; \ 135 if (list) list_delete_named 130 if (list) list_delete_named(list,iterator,prev,next) ; \ 136 (iterator); }) ; ) 131 (iterator); }) ; ) 137 132 138 133 139 /* 134 /* 140 * the same macros : assume that the prev and 135 * the same macros : assume that the prev and next fields are really 141 * named "prev" and "next" 136 * named "prev" and "next" 142 */ 137 */ 143 138 144 #define list_init(list) \ 139 #define list_init(list) \ 145 list_init_named(list,prev,next) 140 list_init_named(list,prev,next) 146 141 147 #define list_singleton(list,item) \ 142 #define list_singleton(list,item) \ 148 list_singleton_named(list,item,prev,next) 143 list_singleton_named(list,item,prev,next) 149 144 150 #define list_is_empty(list) \ 145 #define list_is_empty(list) \ 151 list_is_empty_named(list,prev,next) 146 list_is_empty_named(list,prev,next) 152 << 153 #define list_is_singleton(list) \ << 154 list_is_singleton_named(list,prev,next) << 155 147 156 #define list_get_head(list) \ 148 #define list_get_head(list) \ 157 list_get_head_named(list,prev,next) \ 149 list_get_head_named(list,prev,next) \ 158 150 159 #define list_get_tail(list) \ 151 #define list_get_tail(list) \ 160 list_get_tail_named(list,prev,next) \ 152 list_get_tail_named(list,prev,next) \ 161 153 162 /* @note Before_this and item are expected to 154 /* @note Before_this and item are expected to be valid ! */ 163 #define list_insert_after(list,after_this,item 155 #define list_insert_after(list,after_this,item) \ 164 list_insert_after_named(list,after_this,item 156 list_insert_after_named(list,after_this,item,prev,next) 165 157 166 /* @note After_this and item are expected to b 158 /* @note After_this and item are expected to be valid ! */ 167 #define list_insert_before(list,before_this,it 159 #define list_insert_before(list,before_this,item) \ 168 list_insert_before_named(list,before_this,it 160 list_insert_before_named(list,before_this,item,prev,next) 169 161 170 #define list_add_head(list,item) \ 162 #define list_add_head(list,item) \ 171 list_add_head_named(list,item,prev,next) 163 list_add_head_named(list,item,prev,next) 172 164 173 #define list_add_tail(list,item) \ 165 #define list_add_tail(list,item) \ 174 list_add_tail_named(list,item,prev,next) 166 list_add_tail_named(list,item,prev,next) 175 167 176 /* @note NO check whether item really is in li 168 /* @note NO check whether item really is in list ! */ 177 #define list_delete(list,item) \ 169 #define list_delete(list,item) \ 178 list_delete_named(list,item,prev,next) 170 list_delete_named(list,item,prev,next) 179 171 180 #define list_pop_head(list) \ 172 #define list_pop_head(list) \ 181 list_pop_head_named(list,prev,next) 173 list_pop_head_named(list,prev,next) 182 174 183 #define list_foreach_forward(list,iterator,nb_ 175 #define list_foreach_forward(list,iterator,nb_elements) \ 184 list_foreach_forward_named(list,iterator,nb_ 176 list_foreach_forward_named(list,iterator,nb_elements,prev,next) 185 177 186 #define list_foreach_backward(list,iterator,nb 178 #define list_foreach_backward(list,iterator,nb_elements) \ 187 list_foreach_backward_named(list,iterator,nb 179 list_foreach_backward_named(list,iterator,nb_elements,prev,next) 188 180 189 #define list_foreach list_foreach_forward 181 #define list_foreach list_foreach_forward 190 182 191 #define list_collapse(list,iterator) \ 183 #define list_collapse(list,iterator) \ 192 list_collapse_named(list,iterator,prev,next) 184 list_collapse_named(list,iterator,prev,next) 193 185 194 #endif /* _SOS_LIST_H_ */ 186 #endif /* _SOS_LIST_H_ */
| [ source navigation ] | [ diff markup ] | [ identifier search ] | [ general search ] |