Changes in uspace/lib/c/include/adt/list.h [63f8966:b72efe8] in mainline
- File:
-
- 1 edited
-
uspace/lib/c/include/adt/list.h (modified) (13 diffs)
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/c/include/adt/list.h
r63f8966 rb72efe8 1 1 /* 2 2 * Copyright (c) 2001-2004 Jakub Jermar 3 * Copyright (c) 2011 Jiri Svoboda 3 4 * All rights reserved. 4 5 * … … 36 37 #define LIBC_LIST_H_ 37 38 39 #include <assert.h> 38 40 #include <unistd.h> 39 41 40 /** Doubly linked list head and link type. */42 /** Doubly linked list link. */ 41 43 typedef struct link { 42 44 struct link *prev; /**< Pointer to the previous item in the list. */ … … 44 46 } link_t; 45 47 48 /** Doubly linked list. */ 49 typedef struct list { 50 link_t head; /**< List head. Does not have any data. */ 51 } list_t; 52 46 53 /** Declare and initialize statically allocated list. 47 54 * 48 55 * @param name Name of the new statically allocated list. 49 */ 50 #define LIST_INITIALIZE(name) link_t name = { \ 51 .prev = &name, \ 52 .next = &name \ 53 } 56 * 57 */ 58 #define LIST_INITIALIZE(name) \ 59 list_t name = { \ 60 .head = { \ 61 .prev = &(name).head, \ 62 .next = &(name).head \ 63 } \ 64 } 65 66 #define list_get_instance(link, type, member) \ 67 ((type *) (((void *)(link)) - ((void *) &(((type *) NULL)->member)))) 68 69 #define list_foreach(list, iterator) \ 70 for (link_t *iterator = (list).head.next; \ 71 iterator != &(list).head; iterator = iterator->next) 72 73 #define assert_link_not_used(link) \ 74 assert((link)->prev == NULL && (link)->next == NULL) 54 75 55 76 /** Initialize doubly-linked circular list link … … 58 79 * 59 80 * @param link Pointer to link_t structure to be initialized. 81 * 60 82 */ 61 83 static inline void link_initialize(link_t *link) … … 69 91 * Initialize doubly-linked circular list. 70 92 * 71 * @param head Pointer to link_t structure representing head of the list. 72 */ 73 static inline void list_initialize(link_t *head) 74 { 75 head->prev = head; 76 head->next = head; 93 * @param list Pointer to list_t structure. 94 * 95 */ 96 static inline void list_initialize(list_t *list) 97 { 98 list->head.prev = &list->head; 99 list->head.next = &list->head; 100 } 101 102 /** Insert item before another item in doubly-linked circular list. 103 * 104 */ 105 static inline void list_insert_before(link_t *lnew, link_t *lold) 106 { 107 lnew->next = lold; 108 lnew->prev = lold->prev; 109 lold->prev->next = lnew; 110 lold->prev = lnew; 111 } 112 113 /** Insert item after another item in doubly-linked circular list. 114 * 115 */ 116 static inline void list_insert_after(link_t *lnew, link_t *lold) 117 { 118 lnew->prev = lold; 119 lnew->next = lold->next; 120 lold->next->prev = lnew; 121 lold->next = lnew; 77 122 } 78 123 … … 82 127 * 83 128 * @param link Pointer to link_t structure to be added. 84 * @param head Pointer to link_t structure representing head of the list. 85 */ 86 static inline void list_prepend(link_t *link, link_t *head) 87 { 88 link->next = head->next; 89 link->prev = head; 90 head->next->prev = link; 91 head->next = link; 129 * @param list Pointer to list_t structure. 130 * 131 */ 132 static inline void list_prepend(link_t *link, list_t *list) 133 { 134 list_insert_after(link, &list->head); 92 135 } 93 136 … … 97 140 * 98 141 * @param link Pointer to link_t structure to be added. 99 * @param head Pointer to link_t structure representing head of the list. 100 */ 101 static inline void list_append(link_t *link, link_t *head) 102 { 103 link->prev = head->prev; 104 link->next = head; 105 head->prev->next = link; 106 head->prev = link; 107 } 108 109 /** Insert item before another item in doubly-linked circular list. */ 110 static inline void list_insert_before(link_t *l, link_t *r) 111 { 112 list_append(l, r); 113 } 114 115 /** Insert item after another item in doubly-linked circular list. */ 116 static inline void list_insert_after(link_t *r, link_t *l) 117 { 118 list_prepend(l, r); 142 * @param list Pointer to list_t structure. 143 * 144 */ 145 static inline void list_append(link_t *link, list_t *list) 146 { 147 list_insert_before(link, &list->head); 119 148 } 120 149 … … 123 152 * Remove item from doubly-linked circular list. 124 153 * 125 * @param link Pointer to link_t structure to be removed from the list it is contained in. 154 * @param link Pointer to link_t structure to be removed from the list 155 * it is contained in. 156 * 126 157 */ 127 158 static inline void list_remove(link_t *link) … … 136 167 * Query emptiness of doubly-linked circular list. 137 168 * 138 * @param head Pointer to link_t structure representing head of the list. 139 */ 140 static inline int list_empty(link_t *head) 141 { 142 return ((head->next == head) ? 1 : 0); 143 } 144 169 * @param list Pointer to lins_t structure. 170 * 171 */ 172 static inline int list_empty(list_t *list) 173 { 174 return (list->head.next == &list->head); 175 } 176 177 /** Get first item in list. 178 * 179 * @param list Pointer to list_t structure. 180 * 181 * @return Head item of the list. 182 * @return NULL if the list is empty. 183 * 184 */ 185 static inline link_t *list_first(list_t *list) 186 { 187 return ((list->head.next == &list->head) ? NULL : list->head.next); 188 } 189 190 /** Get last item in list. 191 * 192 * @param list Pointer to list_t structure. 193 * 194 * @return Head item of the list. 195 * @return NULL if the list is empty. 196 * 197 */ 198 static inline link_t *list_last(list_t *list) 199 { 200 return ((list->head.prev == &list->head) ? NULL : list->head.prev); 201 } 145 202 146 203 /** Split or concatenate headless doubly-linked circular list … … 151 208 * concatenates splitted lists and splits concatenated lists. 152 209 * 153 * @param part1 Pointer to link_t structure leading the first (half of the headless) list. 154 * @param part2 Pointer to link_t structure leading the second (half of the headless) list. 210 * @param part1 Pointer to link_t structure leading the first 211 * (half of the headless) list. 212 * @param part2 Pointer to link_t structure leading the second 213 * (half of the headless) list. 214 * 155 215 */ 156 216 static inline void headless_list_split_or_concat(link_t *part1, link_t *part2) … … 165 225 } 166 226 167 168 227 /** Split headless doubly-linked circular list 169 228 * 170 229 * Split headless doubly-linked circular list. 171 230 * 172 * @param part1 Pointer to link_t structure leading the first half of the headless list. 173 * @param part2 Pointer to link_t structure leading the second half of the headless list. 231 * @param part1 Pointer to link_t structure leading 232 * the first half of the headless list. 233 * @param part2 Pointer to link_t structure leading 234 * the second half of the headless list. 235 * 174 236 */ 175 237 static inline void headless_list_split(link_t *part1, link_t *part2) … … 182 244 * Concatenate two headless doubly-linked circular lists. 183 245 * 184 * @param part1 Pointer to link_t structure leading the first headless list. 185 * @param part2 Pointer to link_t structure leading the second headless list. 246 * @param part1 Pointer to link_t structure leading 247 * the first headless list. 248 * @param part2 Pointer to link_t structure leading 249 * the second headless list. 250 * 186 251 */ 187 252 static inline void headless_list_concat(link_t *part1, link_t *part2) … … 190 255 } 191 256 192 #define list_get_instance(link, type, member) ((type *) (((void *)(link)) - ((void *) &(((type *) NULL)->member)))) 193 194 extern int list_member(const link_t *link, const link_t *head); 195 extern void list_concat(link_t *head1, link_t *head2); 196 extern unsigned int list_count(const link_t *link); 257 /** Get n-th item in a list. 258 * 259 * @param list Pointer to link_t structure representing the list. 260 * @param n Item number (indexed from zero). 261 * 262 * @return n-th item of the list. 263 * @return NULL if no n-th item found. 264 * 265 */ 266 static inline link_t *list_nth(list_t *list, unsigned int n) 267 { 268 unsigned int cnt = 0; 269 270 list_foreach(*list, link) { 271 if (cnt == n) 272 return link; 273 274 cnt++; 275 } 276 277 return NULL; 278 } 279 280 extern int list_member(const link_t *, const list_t *); 281 extern void list_concat(list_t *, list_t *); 282 extern unsigned int list_count(const list_t *); 197 283 198 284 #endif
Note:
See TracChangeset
for help on using the changeset viewer.
