Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changeset 36795edf in mainline


Ignore:
Timestamp:
2021-03-12T19:16:51Z (6 months ago)
Author:
Martin Decky <martin@…>
Branches:
lfn, master
Children:
a85d5c6
Parents:
17fac946
Message:

Improve lists and other data structures

Provide more standard-compliant member_to_inst implementation that uses
offsetof. Avoid potential undefined behavior in list_foreach and
list_foreach_rev by avoiding assinging an unaligned pointer value. Use
size_t instead of unsigned long for list length.

Files:
2 added
15 edited

Legend:

Unmodified
Added
Removed
  • kernel/generic/include/adt/hash_table.h

    r17fac946 r36795edf  
    4141#include <stdbool.h>
    4242#include <macros.h>
     43#include <member.h>
    4344
    4445/** Opaque hash table link type. */
  • kernel/generic/include/adt/list.h

    r17fac946 r36795edf  
    3838
    3939#include <assert.h>
     40#include <macros.h>
     41#include <member.h>
    4042#include <stdbool.h>
    4143#include <stddef.h>
     44#include <stdint.h>
    4245#include <trace.h>
    4346
     
    8992
    9093#define list_get_instance(link, type, member) \
    91         ((type *) (((void *)(link)) - list_link_to_void(&(((type *) NULL)->member))))
     94        member_to_inst(link, type, member)
    9295
    9396#define list_foreach(list, member, itype, iterator) \
    94         for (itype *iterator = NULL; iterator == NULL; iterator = (itype *) 1) \
     97        for (itype *iterator = NULL; iterator == NULL; iterator = &((itype *) NULL)[1]) \
    9598                for (link_t *_link = (list).head.next; \
    9699                    iterator = list_get_instance(_link, itype, member), \
     
    98101
    99102#define list_foreach_rev(list, member, itype, iterator) \
    100         for (itype *iterator = NULL; iterator == NULL; iterator = (itype *) 1) \
     103        for (itype *iterator = NULL; iterator == NULL; iterator = &((itype *) NULL)[1]) \
    101104                for (link_t *_link = (list).head.prev; \
    102105                    iterator = list_get_instance(_link, itype, member), \
     
    375378 *
    376379 */
    377 static inline link_t *list_nth(const list_t *list, unsigned long n)
    378 {
    379         unsigned long cnt = 0;
     380static inline link_t *list_nth(const list_t *list, size_t n)
     381{
     382        size_t cnt = 0;
    380383
    381384        link_t *link = list_first(list);
     
    391394}
    392395
    393 /** Verify that argument type is a pointer to link_t (at compile time).
    394  *
    395  * This can be used to check argument type in a macro.
    396  */
    397 static inline const void *list_link_to_void(const link_t *link)
    398 {
    399         return link;
    400 }
    401 
    402396/** Determine if link is used.
    403397 *
  • kernel/generic/include/adt/odict.h

    r17fac946 r36795edf  
    3737
    3838#include <errno.h>
     39#include <member.h>
    3940#include <stdbool.h>
    4041#include <stddef.h>
     
    4243
    4344#define odict_get_instance(odlink, type, member) \
    44         ((type *)( (void *)(odlink) - ((void *) &((type *) NULL)->member)))
     45        member_to_inst(odlink, type, member)
    4546
    4647extern void odict_initialize(odict_t *, odgetkey_t, odcmp_t);
  • kernel/generic/include/macros.h

    r17fac946 r36795edf  
    160160        })
    161161
    162 #define member_to_inst(ptr_member, type, member_identif) \
    163         ((type *) (((void *) (ptr_member)) - \
    164             ((void *) &(((type *) 0)->member_identif))))
    165 
    166162/** Get the size of an array in array elements
    167163 *
  • uspace/drv/bus/usb/ehci/hc.c

    r17fac946 r36795edf  
    358358                fibril_mutex_lock(&hc->guard);
    359359
    360                 usb_log_debug2("HC(%p): Scanning %lu pending endpoints", hc,
     360                usb_log_debug2("HC(%p): Scanning %zu pending endpoints", hc,
    361361                    list_count(&hc->pending_endpoints));
    362362                list_foreach_safe(hc->pending_endpoints, current, next) {
  • uspace/drv/bus/usb/uhci/hc.h

    r17fac946 r36795edf  
    4141#include <fibril.h>
    4242#include <macros.h>
     43#include <member.h>
    4344#include <stdbool.h>
    4445#include <ddi.h>
  • uspace/drv/bus/usb/vhc/vhcd.h

    r17fac946 r36795edf  
    4141#include <async.h>
    4242#include <macros.h>
     43#include <member.h>
    4344
    4445#include <usb/host/hcd.h>
  • uspace/drv/bus/usb/xhci/hc.h

    r17fac946 r36795edf  
    3838
    3939#include <fibril_synch.h>
     40#include <member.h>
    4041#include <usb/host/usb_transfer_batch.h>
    4142#include <usb/host/utility.h>
  • uspace/lib/c/generic/adt/hash_table.c

    r17fac946 r36795edf  
    5252#include <adt/list.h>
    5353#include <assert.h>
     54#include <member.h>
    5455#include <stdlib.h>
    5556#include <str.h>
  • uspace/lib/c/generic/adt/list.c

    r17fac946 r36795edf  
    4141#include <adt/list.h>
    4242#include <stdbool.h>
     43#include <stdint.h>
    4344
    4445/** Check for membership
     
    100101 * @return              Number of items in the list.
    101102 */
    102 unsigned long list_count(const list_t *list)
     103size_t list_count(const list_t *list)
    103104{
    104         unsigned long count = 0;
     105        size_t count = 0;
    105106
    106107        link_t *link = list_first(list);
  • uspace/lib/c/include/adt/hash_table.h

    r17fac946 r36795edf  
    4141#include <stdbool.h>
    4242#include <macros.h>
     43#include <member.h>
    4344
    4445/** Opaque hash table link type. */
  • uspace/lib/c/include/adt/list.h

    r17fac946 r36795edf  
    3838
    3939#include <assert.h>
     40#include <member.h>
    4041#include <stdbool.h>
    4142#include <stddef.h>
     
    8586
    8687#define list_get_instance(link, type, member) \
    87         ((type *) (((void *)(link)) - list_link_to_void(&(((type *) NULL)->member))))
     88        member_to_inst(link, type, member)
    8889
    8990#define list_foreach(list, member, itype, iterator) \
    90         for (itype *iterator = NULL; iterator == NULL; iterator = (itype *) 1) \
     91        for (itype *iterator = NULL; iterator == NULL; iterator = &((itype *) NULL)[1]) \
    9192                for (link_t *_link = (list).head.next; \
    9293                    iterator = list_get_instance(_link, itype, member), \
     
    9495
    9596#define list_foreach_rev(list, member, itype, iterator) \
    96         for (itype *iterator = NULL; iterator == NULL; iterator = (itype *) 1) \
     97        for (itype *iterator = NULL; iterator == NULL; iterator = &((itype *) NULL)[1]) \
    9798                for (link_t *_link = (list).head.prev; \
    9899                    iterator = list_get_instance(_link, itype, member), \
     
    154155extern bool list_member(const link_t *, const list_t *);
    155156extern void list_splice(list_t *, link_t *);
    156 extern unsigned long list_count(const list_t *);
     157extern size_t list_count(const list_t *);
    157158
    158159/** Returns true if the link is definitely part of a list. False if not sure. */
     
    394395 *
    395396 */
    396 static inline link_t *list_nth(const list_t *list, unsigned long n)
    397 {
    398         unsigned long cnt = 0;
     397static inline link_t *list_nth(const list_t *list, size_t n)
     398{
     399        size_t cnt = 0;
    399400
    400401        link_t *link = list_first(list);
  • uspace/lib/c/include/macros.h

    r17fac946 r36795edf  
    5555            | ((((uint64_t) (up)) & 0xffffffff) << 32))
    5656
    57 #define member_to_inst(ptr_member, type, member_identif) \
    58         ((type *) (((void *) (ptr_member)) - \
    59             ((void *) &(((type *) 0)->member_identif))))
    60 
    6157#define _paddname(line)     PADD_ ## line ## __
    6258#define _padd(width, line, n)  uint ## width ## _t _paddname(line) [n]
  • uspace/lib/nic/src/nic_addr_db.c

    r17fac946 r36795edf  
    3535 * @brief Generic hash-set based database of addresses
    3636 */
     37
    3738#include "nic_addr_db.h"
    3839#include <assert.h>
     
    4142#include <errno.h>
    4243#include <mem.h>
     44#include <member.h>
    4345#include <adt/hash_table.h>
    4446#include <macros.h>
  • uspace/srv/audio/hound/hound_ctx.c

    r17fac946 r36795edf  
    403403                return ENOMEM;
    404404        }
    405         log_verbose("CTX: %p: Mixing %lu streams", ctx,
     405        log_verbose("CTX: %p: Mixing %zu streams", ctx,
    406406            list_count(&ctx->streams));
    407407        pcm_format_silence(buffer, size, &source->format);
     
    413413                        log_warning("Not enough data in stream buffer");
    414414        }
    415         log_verbose("CTX: %p. Pushing audio to %lu connections", ctx,
     415        log_verbose("CTX: %p. Pushing audio to %zu connections", ctx,
    416416            list_count(&source->connections));
    417417        list_foreach(source->connections, source_link, connection_t, conn) {
Note: See TracChangeset for help on using the changeset viewer.