Changeset 36795edf in mainline for uspace/lib/c

Timestamp:

2021-03-12T19:16:51Z (4 years ago)

Author:

Martin Decky <martin@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

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.

Location:

uspace/lib/c

Files:

• generic/adt/hash_table.c (modified) (1 diff)
• generic/adt/list.c (modified) (2 diffs)
• include/adt/hash_table.h (modified) (1 diff)
• include/adt/list.h (modified) (5 diffs)
• include/macros.h (modified) (1 diff)
• include/member.h (added)

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

@@ -52 +52 @@
 #include <adt/list.h>
 #include <assert.h>
+#include <member.h>
 #include <stdlib.h>
 #include <str.h>

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

@@ -41 +41 @@
 #include <adt/list.h>
 #include <stdbool.h>
+#include <stdint.h>
 
 /** Check for membership
@@ -100 +101 @@
  * @return              Number of items in the list.
  */
-unsigned long list_count(const list_t *list)
+size_t list_count(const list_t *list)
 {
-        unsigned long count = 0;
+        size_t count = 0;
 
         link_t *link = list_first(list);

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

@@ -41 +41 @@
 #include <stdbool.h>
 #include <macros.h>
+#include <member.h>
 
 /** Opaque hash table link type. */

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

@@ -38 +38 @@
 
 #include <assert.h>
+#include <member.h>
 #include <stdbool.h>
 #include <stddef.h>
@@ -85 +86 @@
 
 #define list_get_instance(link, type, member) \
-        ((type *) (((void *)(link)) - list_link_to_void(&(((type *) NULL)->member))))
+        member_to_inst(link, type, member)
 
 #define list_foreach(list, member, itype, iterator) \
-        for (itype *iterator = NULL; iterator == NULL; iterator = (itype *) 1) \
+        for (itype *iterator = NULL; iterator == NULL; iterator = &((itype *) NULL)[1]) \
                 for (link_t *_link = (list).head.next; \
                     iterator = list_get_instance(_link, itype, member), \
@@ -94 +95 @@
 
 #define list_foreach_rev(list, member, itype, iterator) \
-        for (itype *iterator = NULL; iterator == NULL; iterator = (itype *) 1) \
+        for (itype *iterator = NULL; iterator == NULL; iterator = &((itype *) NULL)[1]) \
                 for (link_t *_link = (list).head.prev; \
                     iterator = list_get_instance(_link, itype, member), \
@@ -154 +155 @@
 extern bool list_member(const link_t *, const list_t *);
 extern void list_splice(list_t *, link_t *);
-extern unsigned long list_count(const list_t *);
+extern size_t list_count(const list_t *);
 
 /** Returns true if the link is definitely part of a list. False if not sure. */
@@ -394 +395 @@
  *
  */
-static inline link_t *list_nth(const list_t *list, unsigned long n)
-{
-        unsigned long cnt = 0;
+static inline link_t *list_nth(const list_t *list, size_t n)
+{
+        size_t cnt = 0;
 
         link_t *link = list_first(list);

uspace/lib/c/include/macros.h

@@ -55 +55 @@
             | ((((uint64_t) (up)) & 0xffffffff) << 32))
 
-#define member_to_inst(ptr_member, type, member_identif) \
-        ((type *) (((void *) (ptr_member)) - \
-            ((void *) &(((type *) 0)->member_identif))))
-
 #define _paddname(line)     PADD_ ## line ## __
 #define _padd(width, line, n)  uint ## width ## _t _paddname(line) [n]