Changeset a33f0a6 in mainline for uspace/lib/c/include/adt/list.h


Ignore:
Timestamp:
2011-08-03T17:34:57Z (13 years ago)
Author:
Oleg Romanenko <romanenko.oleg@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
1940326
Parents:
52a79081 (diff), 3fab770 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge from mainline

File:
1 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/c/include/adt/list.h

    r52a79081 ra33f0a6  
    11/*
    22 * Copyright (c) 2001-2004 Jakub Jermar
     3 * Copyright (c) 2011 Jiri Svoboda
    34 * All rights reserved.
    45 *
    … …  
    3637#define LIBC_LIST_H_
    3738
     39#include <assert.h>
    3840#include <unistd.h>
    3941
    40 /** Doubly linked list head and link type. */
     42/** Doubly linked list link. */
    4143typedef struct link {
    4244        struct link *prev;  /**< Pointer to the previous item in the list. */
    … …  
    4446} link_t;
    4547
     48/** Doubly linked list. */
     49typedef struct list {
     50        link_t head;  /**< List head. Does not have any data. */
     51} list_t;
     52
    4653/** Declare and initialize statically allocated list.
    4754 *
    4855 * @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)
    5475
    5576/** Initialize doubly-linked circular list link
    … …  
    5879 *
    5980 * @param link Pointer to link_t structure to be initialized.
     81 *
    6082 */
    6183static inline void link_initialize(link_t *link)
    … …  
    6991 * Initialize doubly-linked circular list.
    7092 *
    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 */
     96static 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 */
     105static 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 */
     116static 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;
    77122}
    78123
    … …  
    82127 *
    83128 * @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 */
     132static inline void list_prepend(link_t *link, list_t *list)
     133{
     134        list_insert_after(link, &list->head);
    92135}
    93136
    … …  
    97140 *
    98141 * @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 */
     145static inline void list_append(link_t *link, list_t *list)
     146{
     147        list_insert_before(link, &list->head);
    119148}
    120149
    … …  
    123152 * Remove item from doubly-linked circular list.
    124153 *
    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 *
    126157 */
    127158static inline void list_remove(link_t *link)
    … …  
    136167 * Query emptiness of doubly-linked circular list.
    137168 *
    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 */
     172static 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 */
     185static 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 */
     198static inline link_t *list_last(list_t *list)
     199{
     200        return ((list->head.prev == &list->head) ? NULL : list->head.prev);
     201}
    145202
    146203/** Split or concatenate headless doubly-linked circular list
    … …  
    151208 * concatenates splitted lists and splits concatenated lists.
    152209 *
    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 *
    155215 */
    156216static inline void headless_list_split_or_concat(link_t *part1, link_t *part2)
    … …  
    165225}
    166226
    167 
    168227/** Split headless doubly-linked circular list
    169228 *
    170229 * Split headless doubly-linked circular list.
    171230 *
    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 *
    174236 */
    175237static inline void headless_list_split(link_t *part1, link_t *part2)
    … …  
    182244 * Concatenate two headless doubly-linked circular lists.
    183245 *
    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 *
    186251 */
    187252static inline void headless_list_concat(link_t *part1, link_t *part2)
    … …  
    190255}
    191256
    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 */
     266static 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
     280extern int list_member(const link_t *, const list_t *);
     281extern void list_concat(list_t *, list_t *);
     282extern unsigned int list_count(const list_t *);
    197283
    198284#endif
Note: See TracChangeset for help on using the changeset viewer.