Changeset b72efe8 in mainline for uspace/lib/c


Ignore:
Timestamp:
2011-06-19T14:38:59Z (14 years ago)
Author:
Jiri Svoboda <jiri@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
74464e8
Parents:
1d1bb0f
Message:

Separate list_t typedef from link_t (user-space part).

  • list_t represents lists
  • Use list_first(), list_last(), list_empty() where appropriate
  • Use list_foreach() where possible
  • assert_link_not_used()
  • usb_hid_report_path_free() shall not unlink the path, caller must do it
Location:
uspace/lib/c
Files:
15 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/c/generic/adt/hash_table.c

    r1d1bb0f rb72efe8  
    6161        assert(max_keys > 0);
    6262       
    63         h->entry = malloc(m * sizeof(link_t));
     63        h->entry = malloc(m * sizeof(list_t));
    6464        if (!h->entry)
    6565                return false;
    6666       
    67         memset((void *) h->entry, 0,  m * sizeof(link_t));
     67        memset((void *) h->entry, 0,  m * sizeof(list_t));
    6868       
    6969        hash_count_t i;
    … …  
    123123        assert(chain < h->entries);
    124124       
    125         link_t *cur;
    126         for (cur = h->entry[chain].next; cur != &h->entry[chain];
    127             cur = cur->next) {
     125        list_foreach(h->entry[chain], cur) {
    128126                if (h->op->compare(key, h->max_keys, cur)) {
    129127                        /*
    … …  
    153151        assert(keys <= h->max_keys);
    154152       
    155         link_t *cur;
    156        
    157153        if (keys == h->max_keys) {
     154                link_t *cur;
     155               
    158156                /*
    159157                 * All keys are known, hash_table_find() can be used to find the
    … …  
    176174        hash_index_t chain;
    177175        for (chain = 0; chain < h->entries; chain++) {
    178                 for (cur = h->entry[chain].next; cur != &h->entry[chain];
     176                link_t *cur;
     177               
     178                for (cur = h->entry[chain].head.next; cur != &h->entry[chain].head;
    179179                    cur = cur->next) {
    180180                        if (h->op->compare(key, keys, cur)) {
    … …  
    203203{
    204204        hash_index_t bucket;
    205         link_t *cur;
    206205       
    207206        for (bucket = 0; bucket < h->entries; bucket++) {
    208                 for (cur = h->entry[bucket].next; cur != &h->entry[bucket];
    209                     cur = cur->next) {
     207                list_foreach(h->entry[bucket], cur) {
    210208                        f(cur, arg);
    211209                }

  • uspace/lib/c/generic/adt/list.c

    r1d1bb0f rb72efe8  
    3030 * @{
    3131 */
    32 /** @file
     32
     33/**
     34 * @file
     35 * @brief       Functions completing doubly linked circular list implementaion.
     36 *
     37 * This file contains some of the functions implementing doubly linked circular lists.
     38 * However, this ADT is mostly implemented in @ref list.h.
    3339 */
    3440
    3541#include <adt/list.h>
    36 
     42#include <bool.h>
    3743
    3844/** Check for membership
    3945 *
    40  * Check whether link is contained in the list head.
    41  * The membership is defined as pointer equivalence.
     46 * Check whether link is contained in a list.
     47 * Membership is defined as pointer equivalence.
    4248 *
    43  * @param link Item to look for.
    44  * @param head List to look in.
     49 * @param link  Item to look for.
     50 * @param list  List to look in.
    4551 *
    4652 * @return true if link is contained in head, false otherwise.
    4753 *
    4854 */
    49 int list_member(const link_t *link, const link_t *head)
     55int list_member(const link_t *link, const list_t *list)
    5056{
    51         int found = 0;
    52         link_t *hlp = head->next;
     57        bool found = false;
     58        link_t *hlp = list->head.next;
    5359       
    54         while (hlp != head) {
     60        while (hlp != &list->head) {
    5561                if (hlp == link) {
    56                         found = 1;
     62                        found = true;
    5763                        break;
    5864                }
    … …  
    6369}
    6470
    65 
    6671/** Concatenate two lists
    6772 *
    68  * Concatenate lists head1 and head2, producing a single
    69  * list head1 containing items from both (in head1, head2
    70  * order) and empty list head2.
     73 * Concatenate lists @a list1 and @a list2, producing a single
     74 * list @a list1 containing items from both (in @a list1, @a list2
     75 * order) and empty list @a list2.
    7176 *
    72  * @param head1 First list and concatenated output
    73  * @param head2 Second list and empty output.
     77 * @param list1         First list and concatenated output
     78 * @param list2         Second list and empty output.
    7479 *
    7580 */
    76 void list_concat(link_t *head1, link_t *head2)
     81void list_concat(list_t *list1, list_t *list2)
    7782{
    78         if (list_empty(head2))
     83        if (list_empty(list2))
    7984                return;
    80        
    81         head2->next->prev = head1->prev;
    82         head2->prev->next = head1;
    83         head1->prev->next = head2->next;
    84         head1->prev = head2->prev;
    85         list_initialize(head2);
     85
     86        list2->head.next->prev = list1->head.prev;
     87        list2->head.prev->next = &list1->head;
     88        list1->head.prev->next = list2->head.next;
     89        list1->head.prev = list2->head.prev;
     90        list_initialize(list2);
    8691}
    87 
    8892
    8993/** Count list items
    … …  
    9195 * Return the number of items in the list.
    9296 *
    93  * @param link List to count.
    94  *
    95  * @return Number of items in the list.
    96  *
     97 * @param list          List to count.
     98 * @return              Number of items in the list.
    9799 */
    98 unsigned int list_count(const link_t *link)
     100unsigned int list_count(const list_t *list)
    99101{
    100102        unsigned int count = 0;
    101         link_t *hlp = link->next;
    102103       
    103         while (hlp != link) {
     104        list_foreach(*list, link) {
    104105                count++;
    105                 hlp = hlp->next;
    106106        }
    107107       

  • uspace/lib/c/generic/adt/prodcons.c

    r1d1bb0f rb72efe8  
    6161                fibril_condvar_wait(&pc->cv, &pc->mtx);
    6262       
    63         link_t *head = pc->list.next;
     63        link_t *head = list_first(&pc->list);
    6464        list_remove(head);
    6565       

  • uspace/lib/c/generic/async.c

    r1d1bb0f rb72efe8  
    160160       
    161161        /** Messages that should be delivered to this fibril. */
    162         link_t msg_queue;
     162        list_t msg_queue;
    163163       
    164164        /** Identification of the opening call. */
    … …  
    361361        wd->to_event.inlist = true;
    362362       
    363         link_t *tmp = timeout_list.next;
    364         while (tmp != &timeout_list) {
     363        link_t *tmp = timeout_list.head.next;
     364        while (tmp != &timeout_list.head) {
    365365                awaiter_t *cur
    366366                    = list_get_instance(tmp, awaiter_t, to_event.link);
    … …  
    372372        }
    373373       
    374         list_append(&wd->to_event.link, tmp);
     374        list_insert_before(&wd->to_event.link, tmp);
    375375}
    376376
    … …  
    569569        }
    570570       
    571         msg_t *msg = list_get_instance(conn->msg_queue.next, msg_t, link);
     571        msg_t *msg = list_get_instance(list_first(&conn->msg_queue), msg_t, link);
    572572        list_remove(&msg->link);
    573573       
    … …  
    675675        while (!list_empty(&fibril_connection->msg_queue)) {
    676676                msg_t *msg =
    677                     list_get_instance(fibril_connection->msg_queue.next, msg_t,
    678                     link);
     677                    list_get_instance(list_first(&fibril_connection->msg_queue),
     678                    msg_t, link);
    679679               
    680680                list_remove(&msg->link);
    … …  
    806806        futex_down(&async_futex);
    807807       
    808         link_t *cur = timeout_list.next;
    809         while (cur != &timeout_list) {
     808        link_t *cur = list_first(&timeout_list);
     809        while (cur != NULL) {
    810810                awaiter_t *waiter =
    811811                    list_get_instance(cur, awaiter_t, to_event.link);
    … …  
    813813                if (tv_gt(&waiter->to_event.expires, &tv))
    814814                        break;
    815                
    816                 cur = cur->next;
    817815               
    818816                list_remove(&waiter->to_event.link);
    … …  
    828826                        fibril_add_ready(waiter->fid);
    829827                }
     828               
     829                cur = list_first(&timeout_list);
    830830        }
    831831       
    … …  
    854854                suseconds_t timeout;
    855855                if (!list_empty(&timeout_list)) {
    856                         awaiter_t *waiter = list_get_instance(timeout_list.next,
    857                             awaiter_t, to_event.link);
     856                        awaiter_t *waiter = list_get_instance(
     857                            list_first(&timeout_list), awaiter_t, to_event.link);
    858858                       
    859859                        struct timeval tv;
    … …  
    17311731                 */
    17321732                exch = (async_exch_t *)
    1733                     list_get_instance(sess->exch_list.next, async_exch_t, sess_link);
     1733                    list_get_instance(list_first(&sess->exch_list),
     1734                    async_exch_t, sess_link);
     1735               
    17341736                list_remove(&exch->sess_link);
    17351737                list_remove(&exch->global_link);
    … …  
    17431745                        exch = (async_exch_t *) malloc(sizeof(async_exch_t));
    17441746                        if (exch != NULL) {
    1745                                 list_initialize(&exch->sess_link);
    1746                                 list_initialize(&exch->global_link);
     1747                                link_initialize(&exch->sess_link);
     1748                                link_initialize(&exch->global_link);
    17471749                                exch->sess = sess;
    17481750                                exch->phone = sess->phone;
    … …  
    17611763                                exch = (async_exch_t *) malloc(sizeof(async_exch_t));
    17621764                                if (exch != NULL) {
    1763                                         list_initialize(&exch->sess_link);
    1764                                         list_initialize(&exch->global_link);
     1765                                        link_initialize(&exch->sess_link);
     1766                                        link_initialize(&exch->global_link);
    17651767                                        exch->sess = sess;
    17661768                                        exch->phone = phone;
    … …  
    17741776                                 */
    17751777                                exch = (async_exch_t *)
    1776                                     list_get_instance(inactive_exch_list.next, async_exch_t,
    1777                                     global_link);
     1778                                    list_get_instance(list_first(&inactive_exch_list),
     1779                                    async_exch_t, global_link);
     1780                               
    17781781                                list_remove(&exch->sess_link);
    17791782                                list_remove(&exch->global_link);

  • uspace/lib/c/generic/devman.c

    r1d1bb0f rb72efe8  
    3535 */
    3636
     37#include <adt/list.h>
    3738#include <str.h>
    3839#include <ipc/services.h>
    … …  
    231232        }
    232233       
    233         link_t *link = match_ids->ids.next;
    234234        match_id_t *match_id = NULL;
    235235       
    236         while (link != &match_ids->ids) {
     236        list_foreach(match_ids->ids, link) {
    237237                match_id = list_get_instance(link, match_id_t, link);
    238238               
    … …  
    255255                        return retval;
    256256                }
    257                
    258                 link = link->next;
    259257        }
    260258       

  • uspace/lib/c/generic/fibril.c

    r1d1bb0f rb72efe8  
    222222        fibril_t *dstf;
    223223        if ((stype == FIBRIL_TO_MANAGER) || (stype == FIBRIL_FROM_DEAD)) {
    224                 dstf = list_get_instance(manager_list.next, fibril_t, link);
     224                dstf = list_get_instance(list_first(&manager_list), fibril_t,
     225                    link);
    225226                if (serialization_count && stype == FIBRIL_TO_MANAGER) {
    226227                        serialized_threads++;
    … …  
    233234        } else {
    234235                if (!list_empty(&serialized_list)) {
    235                         dstf = list_get_instance(serialized_list.next, fibril_t,
    236                             link);
     236                        dstf = list_get_instance(list_first(&serialized_list),
     237                            fibril_t, link);
    237238                        serialized_threads--;
    238239                } else {
    239                         dstf = list_get_instance(ready_list.next, fibril_t,
    240                             link);
     240                        dstf = list_get_instance(list_first(&ready_list),
     241                            fibril_t, link);
    241242                }
    242243        }
    … …  
    326327       
    327328        if (!list_empty(&manager_list))
    328                 list_remove(manager_list.next);
     329                list_remove(list_first(&manager_list));
    329330       
    330331        futex_up(&fibril_futex);

  • uspace/lib/c/generic/fibril_synch.c

    r1d1bb0f rb72efe8  
    148148                fibril_t *f;
    149149       
    150                 assert(!list_empty(&fm->waiters));
    151                 tmp = fm->waiters.next;
     150                tmp = list_first(&fm->waiters);
     151                assert(tmp != NULL);
    152152                wdp = list_get_instance(tmp, awaiter_t, wu_event.link);
    153153                wdp->active = true;
    … …  
    279279       
    280280        while (!list_empty(&frw->waiters)) {
    281                 link_t *tmp = frw->waiters.next;
     281                link_t *tmp = list_first(&frw->waiters);
    282282                awaiter_t *wdp;
    283283                fibril_t *f;
    … …  
    422422        futex_down(&async_futex);
    423423        while (!list_empty(&fcv->waiters)) {
    424                 tmp = fcv->waiters.next;
     424                tmp = list_first(&fcv->waiters);
    425425                wdp = list_get_instance(tmp, awaiter_t, wu_event.link);
    426426                list_remove(&wdp->wu_event.link);

  • uspace/lib/c/generic/io/io.c

    r1d1bb0f rb72efe8  
    127127void __stdio_done(void)
    128128{
    129         link_t *link = files.next;
    130        
    131         while (link != &files) {
    132                 FILE *file = list_get_instance(link, FILE, link);
     129        while (!list_empty(&files)) {
     130                FILE *file = list_get_instance(list_first(&files), FILE, link);
    133131                fclose(file);
    134                 link = files.next;
    135132        }
    136133}

  • uspace/lib/c/generic/ipc.c

    r1d1bb0f rb72efe8  
    458458        while (!list_empty(&queued_calls)) {
    459459                async_call_t *call =
    460                     list_get_instance(queued_calls.next, async_call_t, list);
     460                    list_get_instance(list_first(&queued_calls), async_call_t, list);
    461461                ipc_callid_t callid =
    462462                    ipc_call_async_internal(call->u.msg.phoneid, &call->u.msg.data);
    … …  
    511511       
    512512        link_t *item;
    513         for (item = dispatched_calls.next; item != &dispatched_calls;
     513        for (item = dispatched_calls.head.next; item != &dispatched_calls.head;
    514514            item = item->next) {
    515515                async_call_t *call =

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

    r1d1bb0f rb72efe8  
    7575/** Hash table structure. */
    7676typedef struct {
    77         link_t *entry;
     77        list_t *entry;
    7878        hash_count_t entries;
    7979        hash_count_t max_keys;

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

    r1d1bb0f rb72efe8  
    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 *
    … …  
    5057 */
    5158#define LIST_INITIALIZE(name) \
    52         link_t name = { \
    53                 .prev = &name, \
    54                 .next = &name \
     59        list_t name = { \
     60                .head = { \
     61                        .prev = &(name).head, \
     62                        .next = &(name).head \
     63                } \
    5564        }
    5665
    … …  
    5968
    6069#define list_foreach(list, iterator) \
    61         for (link_t *iterator = (list).next; \
    62             iterator != &(list); iterator = iterator->next)
     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)
    6375
    6476/** Initialize doubly-linked circular list link
    … …  
    7991 * Initialize doubly-linked circular list.
    8092 *
    81  * @param list Pointer to link_t structure representing the list.
    82  *
    83  */
    84 static inline void list_initialize(link_t *list)
    85 {
    86         list->prev = list;
    87         list->next = list;
     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;
    88122}
    89123
    … …  
    93127 *
    94128 * @param link Pointer to link_t structure to be added.
    95  * @param list Pointer to link_t structure representing the list.
    96  *
    97  */
    98 static 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;
     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);
    104135}
    105136
    … …  
    109140 *
    110141 * @param link Pointer to link_t structure to be added.
    111  * @param list Pointer to link_t structure representing the list.
    112  *
    113  */
    114 static 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  */
    125 static 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  */
    133 static inline void list_insert_after(link_t *link, link_t *list)
    134 {
    135         list_prepend(list, link);
     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);
    136148}
    137149
    … …  
    155167 * Query emptiness of doubly-linked circular list.
    156168 *
    157  * @param list Pointer to link_t structure representing the list.
    158  *
    159  */
    160 static 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.
     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.
    168180 *
    169181 * @return Head item of the list.
    … …  
    171183 *
    172184 */
    173 static inline link_t *list_head(link_t *list)
    174 {
    175         return ((list->next == list) ? NULL : list->next);
     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);
    176201}
    177202
    … …  
    230255}
    231256
    232 /** Get n-th item of a list.
     257/** Get n-th item in a list.
    233258 *
    234259 * @param list Pointer to link_t structure representing the list.
    … …  
    239264 *
    240265 */
    241 static inline link_t *list_nth(link_t *list, unsigned int n)
     266static inline link_t *list_nth(list_t *list, unsigned int n)
    242267{
    243268        unsigned int cnt = 0;
    … …  
    253278}
    254279
    255 extern int list_member(const link_t *, const link_t *);
    256 extern void list_concat(link_t *, link_t *);
    257 extern unsigned int list_count(const link_t *);
     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 *);
    258283
    259284#endif

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

    r1d1bb0f rb72efe8  
    4242        fibril_mutex_t mtx;
    4343        fibril_condvar_t cv;
    44         link_t list;
     44        list_t list;
    4545} prodcons_t;
    4646

  • uspace/lib/c/include/async.h

    r1d1bb0f rb72efe8  
    9999typedef struct {
    100100        /** List of inactive exchanges */
    101         link_t exch_list;
     101        list_t exch_list;
    102102       
    103103        /** Exchange management style */

  • uspace/lib/c/include/fibril_synch.h

    r1d1bb0f rb72efe8  
    4545        fibril_owner_info_t oi;  /**< Keep this the first thing. */
    4646        int counter;
    47         link_t waiters;
     47        list_t waiters;
    4848} fibril_mutex_t;
    4949
    … …  
    5555                .counter = 1, \
    5656                .waiters = { \
    57                         .prev = &name.waiters, \
    58                         .next = &name.waiters, \
     57                        .head = { \
     58                                .prev = &(name).waiters.head, \
     59                                .next = &(name).waiters.head, \
     60                        } \
    5961                } \
    6062        }
    … …  
    6769        unsigned writers;
    6870        unsigned readers;
    69         link_t waiters;
     71        list_t waiters;
    7072} fibril_rwlock_t;
    7173
    … …  
    7880                .writers = 0, \
    7981                .waiters = { \
    80                         .prev = &name.waiters, \
    81                         .next = &name.waiters, \
     82                        .head = { \
     83                                .prev = &(name).waiters.head, \
     84                                .next = &(name).waiters.head, \
     85                        } \
    8286                } \
    8387        }
    … …  
    8791
    8892typedef struct {
    89         link_t waiters;
     93        list_t waiters;
    9094} fibril_condvar_t;
    9195
    … …  
    9397        { \
    9498                .waiters = { \
    95                         .next = &name.waiters, \
    96                         .prev = &name.waiters, \
     99                        .head = { \
     100                                .next = &(name).waiters.head, \
     101                                .prev = &(name).waiters.head, \
     102                        } \
    97103                } \
    98104        }

  • uspace/lib/c/include/ipc/devman.h

    r1d1bb0f rb72efe8  
    7272 */
    7373typedef struct match_id_list {
    74         link_t ids;
     74        list_t ids;
    7575} match_id_list_t;
    7676
    … …  
    9595{
    9696        match_id_t *mid = NULL;
    97         link_t *link = ids->ids.next;
     97        link_t *link = ids->ids.head.next;
    9898       
    99         while (link != &ids->ids) {
     99        while (link != &ids->ids.head) {
    100100                mid = list_get_instance(link, match_id_t,link);
    101101                if (mid->score < id->score) {
    102102                        break;
    103                 }       
     103                }
    104104                link = link->next;
    105105        }
    … …  
    118118        match_id_t *id;
    119119       
    120         while(!list_empty(&ids->ids)) {
    121                 link = ids->ids.next;
    122                 list_remove(link);             
     120        while (!list_empty(&ids->ids)) {
     121                link = list_first(&ids->ids);
     122                list_remove(link);
    123123                id = list_get_instance(link, match_id_t, link);
    124                 delete_match_id(id);           
    125         }       
     124                delete_match_id(id);
     125        }
    126126}
    127127
Note: See TracChangeset for help on using the changeset viewer.