Changeset 0a02653 in mainline


Ignore:
Timestamp:
2011-05-17T15:11:19Z (13 years ago)
Author:
Martin Decky <martin@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
f414851
Parents:
97d42d5
Message:

linked list improvements
port uspace linked list improvements back to kernel

Files:
3 edited

Legend:

Unmodified
Added
Removed

  • kernel/generic/include/adt/list.h

    r97d42d5 r0a02653  
    4141/** Doubly linked list head and link type. */
    4242typedef struct link {
    43         struct link *prev;      /**< Pointer to the previous item in the list. */
    44         struct link *next;      /**< Pointer to the next item in the list. */
     43        struct link *prev;  /**< Pointer to the previous item in the list. */
     44        struct link *next;  /**< Pointer to the next item in the list. */
    4545} link_t;
    4646
    … …  
    4848 *
    4949 * @param name Name of the new statically allocated list.
     50 *
    5051 */
    5152#define LIST_INITIALIZE(name) \
    52         link_t name = { .prev = &name, .next = &name }
     53        link_t name = { \
     54                .prev = &name, \
     55                .next = &name \
     56        }
     57
     58#define list_get_instance(link, type, member) \
     59        ((type *) (((void *)(link)) - ((void *) &(((type *) NULL)->member))))
     60
     61#define list_foreach(list, iterator) \
     62        for (link_t *iterator = (list).next; \
     63            iterator != &(list); iterator = iterator->next)
    5364
    5465/** Initialize doubly-linked circular list link
    … …  
    5768 *
    5869 * @param link Pointer to link_t structure to be initialized.
     70 *
    5971 */
    6072NO_TRACE static inline void link_initialize(link_t *link)
    … …  
    6880 * Initialize doubly-linked circular list.
    6981 *
    70  * @param head Pointer to link_t structure representing head of the list.
    71  */
    72 NO_TRACE static inline void list_initialize(link_t *head)
    73 {
    74         head->prev = head;
    75         head->next = head;
     82 * @param list Pointer to link_t structure representing the list.
     83 *
     84 */
     85NO_TRACE static inline void list_initialize(link_t *list)
     86{
     87        list->prev = list;
     88        list->next = list;
    7689}
    7790
    … …  
    8194 *
    8295 * @param link Pointer to link_t structure to be added.
    83  * @param head Pointer to link_t structure representing head of the list.
    84  */
    85 NO_TRACE static inline void list_prepend(link_t *link, link_t *head)
    86 {
    87         link->next = head->next;
    88         link->prev = head;
    89         head->next->prev = link;
    90         head->next = link;
     96 * @param list Pointer to link_t structure representing the list.
     97 *
     98 */
     99NO_TRACE static inline void list_prepend(link_t *link, link_t *list)
     100{
     101        link->next = list->next;
     102        link->prev = list;
     103        list->next->prev = link;
     104        list->next = link;
    91105}
    92106
    … …  
    96110 *
    97111 * @param link Pointer to link_t structure to be added.
    98  * @param head Pointer to link_t structure representing head of the list.
    99  */
    100 NO_TRACE static inline void list_append(link_t *link, link_t *head)
    101 {
    102         link->prev = head->prev;
    103         link->next = head;
    104         head->prev->next = link;
    105         head->prev = link;
     112 * @param list Pointer to link_t structure representing the list.
     113 *
     114 */
     115NO_TRACE static inline void list_append(link_t *link, link_t *list)
     116{
     117        link->prev = list->prev;
     118        link->next = list;
     119        list->prev->next = link;
     120        list->prev = link;
     121}
     122
     123/** Insert item before another item in doubly-linked circular list.
     124 *
     125 */
     126static inline void list_insert_before(link_t *link, link_t *list)
     127{
     128        list_append(link, list);
     129}
     130
     131/** Insert item after another item in doubly-linked circular list.
     132 *
     133 */
     134static inline void list_insert_after(link_t *link, link_t *list)
     135{
     136        list_prepend(list, link);
    106137}
    107138
    … …  
    110141 * Remove item from doubly-linked circular list.
    111142 *
    112  * @param link  Pointer to link_t structure to be removed from the list it is
    113  *              contained in.
     143 * @param link Pointer to link_t structure to be removed from the list
     144 *             it is contained in.
     145 *
    114146 */
    115147NO_TRACE static inline void list_remove(link_t *link)
    … …  
    124156 * Query emptiness of doubly-linked circular list.
    125157 *
    126  * @param head Pointer to link_t structure representing head of the list.
    127  */
    128 NO_TRACE static inline bool list_empty(link_t *head)
    129 {
    130         return head->next == head ? true : false;
    131 }
    132 
     158 * @param list Pointer to link_t structure representing the list.
     159 *
     160 */
     161NO_TRACE static inline int list_empty(link_t *list)
     162{
     163        return (list->next == list);
     164}
     165
     166/** Get head item of a list.
     167 *
     168 * @param list Pointer to link_t structure representing the list.
     169 *
     170 * @return Head item of the list.
     171 * @return NULL if the list is empty.
     172 *
     173 */
     174static inline link_t *list_head(link_t *list)
     175{
     176        return ((list->next == list) ? NULL : list->next);
     177}
    133178
    134179/** Split or concatenate headless doubly-linked circular list
    … …  
    139184 * concatenates splitted lists and splits concatenated lists.
    140185 *
    141  * @param part1 Pointer to link_t structure leading the first (half of the
    142  *              headless) list.
    143  * @param part2 Pointer to link_t structure leading the second (half of the
    144  *              headless) list.
     186 * @param part1 Pointer to link_t structure leading the first
     187 *              (half of the headless) list.
     188 * @param part2 Pointer to link_t structure leading the second
     189 *              (half of the headless) list.
     190 *
    145191 */
    146192NO_TRACE static inline void headless_list_split_or_concat(link_t *part1, link_t *part2)
    147193{
    148         link_t *hlp;
    149 
    150194        part1->prev->next = part2;
    151         part2->prev->next = part1;     
    152         hlp = part1->prev;
     195        part2->prev->next = part1;
     196       
     197        link_t *hlp = part1->prev;
     198       
    153199        part1->prev = part2->prev;
    154200        part2->prev = hlp;
    155201}
    156202
    157 
    158203/** Split headless doubly-linked circular list
    159204 *
    160205 * Split headless doubly-linked circular list.
    161206 *
    162  * @param part1 Pointer to link_t structure leading the first half of the
    163  *              headless list.
    164  * @param part2 Pointer to link_t structure leading the second half of the
    165  *              headless list.
     207 * @param part1 Pointer to link_t structure leading
     208 *              the first half of the headless list.
     209 * @param part2 Pointer to link_t structure leading
     210 *              the second half of the headless list.
     211 *
    166212 */
    167213NO_TRACE static inline void headless_list_split(link_t *part1, link_t *part2)
    … …  
    174220 * Concatenate two headless doubly-linked circular lists.
    175221 *
    176  * @param part1 Pointer to link_t structure leading the first headless list.
    177  * @param part2 Pointer to link_t structure leading the second headless list.
     222 * @param part1 Pointer to link_t structure leading
     223 *              the first headless list.
     224 * @param part2 Pointer to link_t structure leading
     225 *              the second headless list.
     226 *
    178227 */
    179228NO_TRACE static inline void headless_list_concat(link_t *part1, link_t *part2)
    … …  
    182231}
    183232
    184 #define list_get_instance(link, type, member) \
    185         ((type *)(((uint8_t *)(link)) - ((uint8_t *)&(((type *)NULL)->member))))
    186 
    187 extern bool list_member(const link_t *link, const link_t *head);
    188 extern void list_concat(link_t *head1, link_t *head2);
     233/** Get n-th item of a list.
     234 *
     235 * @param list Pointer to link_t structure representing the list.
     236 * @param n    Item number (indexed from zero).
     237 *
     238 * @return n-th item of the list.
     239 * @return NULL if no n-th item found.
     240 *
     241 */
     242static inline link_t *list_nth(link_t *list, unsigned int n)
     243{
     244        unsigned int cnt = 0;
     245       
     246        list_foreach(*list, link) {
     247                if (cnt == n)
     248                        return link;
     249               
     250                cnt++;
     251        }
     252       
     253        return NULL;
     254}
     255
     256extern int list_member(const link_t *, const link_t *);
     257extern void list_concat(link_t *, link_t *);
     258extern unsigned int list_count(const link_t *);
    189259
    190260#endif

  • kernel/generic/src/adt/list.c

    r97d42d5 r0a02653  
    5252 *
    5353 */
    54 bool list_member(const link_t *link, const link_t *head)
     54int list_member(const link_t *link, const link_t *head)
    5555{
    5656        bool found = false;

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

    r97d42d5 r0a02653  
    4949 *
    5050 */
    51 #define LIST_INITIALIZE(name)  link_t name = { \
    52         .prev = &name, \
    53         .next = &name \
    54 }
     51#define LIST_INITIALIZE(name) \
     52        link_t name = { \
     53                .prev = &name, \
     54                .next = &name \
     55        }
     56
     57#define list_get_instance(link, type, member) \
     58        ((type *) (((void *)(link)) - ((void *) &(((type *) NULL)->member))))
     59
     60#define list_foreach(list, iterator) \
     61        for (link_t *iterator = (list).next; \
     62            iterator != &(list); iterator = iterator->next)
    5563
    5664/** Initialize doubly-linked circular list link
    … …  
    7179 * Initialize doubly-linked circular list.
    7280 *
    73  * @param head Pointer to link_t structure representing head of the list.
    74  *
    75  */
    76 static inline void list_initialize(link_t *head)
    77 {
    78         head->prev = head;
    79         head->next = head;
     81 * @param list Pointer to link_t structure representing the list.
     82 *
     83 */
     84static inline void list_initialize(link_t *list)
     85{
     86        list->prev = list;
     87        list->next = list;
    8088}
    8189
    … …  
    8593 *
    8694 * @param link Pointer to link_t structure to be added.
    87  * @param head Pointer to link_t structure representing head of the list.
    88  *
    89  */
    90 static inline void list_prepend(link_t *link, link_t *head)
    91 {
    92         link->next = head->next;
    93         link->prev = head;
    94         head->next->prev = link;
    95         head->next = link;
     95 * @param list Pointer to link_t structure representing the list.
     96 *
     97 */
     98static inline void list_prepend(link_t *link, link_t *list)
     99{
     100        link->next = list->next;
     101        link->prev = list;
     102        list->next->prev = link;
     103        list->next = link;
    96104}
    97105
    … …  
    101109 *
    102110 * @param link Pointer to link_t structure to be added.
    103  * @param head Pointer to link_t structure representing head of the list.
    104  *
    105  */
    106 static inline void list_append(link_t *link, link_t *head)
    107 {
    108         link->prev = head->prev;
    109         link->next = head;
    110         head->prev->next = link;
    111         head->prev = link;
    112 }
    113 
    114 /** Insert item before another item in doubly-linked circular list. */
    115 static inline void list_insert_before(link_t *l, link_t *r)
    116 {
    117         list_append(l, r);
    118 }
    119 
    120 /** Insert item after another item in doubly-linked circular list. */
    121 static inline void list_insert_after(link_t *r, link_t *l)
    122 {
    123         list_prepend(l, r);
     111 * @param list Pointer to link_t structure representing the list.
     112 *
     113 */
     114static inline void list_append(link_t *link, link_t *list)
     115{
     116        link->prev = list->prev;
     117        link->next = list;
     118        list->prev->next = link;
     119        list->prev = link;
     120}
     121
     122/** Insert item before another item in doubly-linked circular list.
     123 *
     124 */
     125static inline void list_insert_before(link_t *link, link_t *list)
     126{
     127        list_append(link, list);
     128}
     129
     130/** Insert item after another item in doubly-linked circular list.
     131 *
     132 */
     133static inline void list_insert_after(link_t *link, link_t *list)
     134{
     135        list_prepend(list, link);
    124136}
    125137
    … …  
    143155 * Query emptiness of doubly-linked circular list.
    144156 *
    145  * @param head Pointer to link_t structure representing head of the list.
    146  *
    147  */
    148 static inline int list_empty(link_t *head)
    149 {
    150         return ((head->next == head) ? 1 : 0);
     157 * @param list Pointer to link_t structure representing the list.
     158 *
     159 */
     160static inline int list_empty(link_t *list)
     161{
     162        return (list->next == list);
     163}
     164
     165/** Get head item of a list.
     166 *
     167 * @param list Pointer to link_t structure representing the list.
     168 *
     169 * @return Head item of the list.
     170 * @return NULL if the list is empty.
     171 *
     172 */
     173static inline link_t *list_head(link_t *list)
     174{
     175        return ((list->next == list) ? NULL : list->next);
    151176}
    152177
    … …  
    205230}
    206231
    207 #define list_get_instance(link, type, member) \
    208         ((type *) (((void *)(link)) - ((void *) &(((type *) NULL)->member))))
    209 
    210 #define list_foreach(list, iterator) \
    211         for (link_t *iterator = (list).next; \
    212             iterator != &(list); iterator = iterator->next)
     232/** Get n-th item of a list.
     233 *
     234 * @param list Pointer to link_t structure representing the list.
     235 * @param n    Item number (indexed from zero).
     236 *
     237 * @return n-th item of the list.
     238 * @return NULL if no n-th item found.
     239 *
     240 */
     241static inline link_t *list_nth(link_t *list, unsigned int n)
     242{
     243        unsigned int cnt = 0;
     244       
     245        list_foreach(*list, link) {
     246                if (cnt == n)
     247                        return link;
     248               
     249                cnt++;
     250        }
     251       
     252        return NULL;
     253}
    213254
    214255extern int list_member(const link_t *, const link_t *);
Note: See TracChangeset for help on using the changeset viewer.