summaryrefslogtreecommitdiff
path: root/libmisc
diff options
context:
space:
mode:
Diffstat (limited to 'libmisc')
-rw-r--r--libmisc/include/libmisc/linkedlist.h112
-rw-r--r--libmisc/include/libmisc/map.h86
-rw-r--r--libmisc/linkedlist.c14
-rw-r--r--libmisc/map.c73
4 files changed, 176 insertions, 109 deletions
diff --git a/libmisc/include/libmisc/linkedlist.h b/libmisc/include/libmisc/linkedlist.h
index 8adef66..e8c65db 100644
--- a/libmisc/include/libmisc/linkedlist.h
+++ b/libmisc/include/libmisc/linkedlist.h
@@ -7,40 +7,102 @@
#ifndef _LIBMISC_LINKEDLIST_H_
#define _LIBMISC_LINKEDLIST_H_
-#include <libmisc/assert.h>
-#include <libmisc/macro.h>
+/* low-level (intrusive) singly linked list ***********************************/
-/* singly linked list *********************************************************/
+struct _slist_node {
+ struct _slist_node *rear;
+};
-typedef struct _lm_sll_node {
- struct _lm_sll_node *rear;
-} lm_sll_node;
+struct _slist_root {
+ struct _slist_node *front, *rear;
+};
-typedef struct {
- lm_sll_node *front, *rear;
-} lm_sll_root;
+void _slist_push_to_rear(struct _slist_root *root, struct _slist_node *node);
+void _slist_pop_from_front(struct _slist_root *root);
-#define lm_sll_node_cast(node_typ, node_ptr) \
- LM_CAST_FIELD_TO_STRUCT(node_typ, lm_sll_node, node_ptr)
+/* low-level (intrusive) doubly linked list ***********************************/
-void lm_sll_push_to_rear(lm_sll_root *root, lm_sll_node *node);
-void lm_sll_pop_from_front(lm_sll_root *root);
+struct _dlist_node {
+ struct _dlist_node *front, *rear;
+};
-/* doubly linked list *********************************************************/
+struct _dlist_root {
+ struct _dlist_node *front, *rear;
+};
-typedef struct _lm_dll_node {
- struct _lm_dll_node *front, *rear;
-} lm_dll_node;
+void _dlist_push_to_rear(struct _dlist_root *root, struct _dlist_node *node);
+void _dlist_remove(struct _dlist_root *root, struct _dlist_node *node);
+void _dlist_pop_from_front(struct _dlist_root *root);
-typedef struct {
- lm_dll_node *front, *rear;
-} lm_dll_root;
+/* singly linked list (non-intrusive) *****************************************/
-#define lm_dll_node_cast(node_typ, node_ptr) \
- LM_CAST_FIELD_TO_STRUCT(node_typ, lm_dll_node, node_ptr)
+#define SLIST_DECLARE(NAME) \
+ struct NAME##_node; \
+ struct NAME { \
+ struct NAME##_node *front, *rear; \
+ struct NAME *_slist_root_typ[0]; \
+ }
-void lm_dll_push_to_rear(lm_dll_root *root, lm_dll_node *node);
-void lm_dll_remove(lm_dll_root *root, lm_dll_node *node);
-void lm_dll_pop_from_front(lm_dll_root *root);
+#define SLIST_DECLARE_NODE(NAME, VAL_T) \
+ struct NAME##_node { \
+ struct NAME##_node *rear; \
+ VAL_T val; \
+ }
+
+#define slist_push_to_rear(ROOT, NODE) { \
+ /* These temporary variables are to get the compiler to check \
+ * the types. */ \
+ typeof(*(ROOT)->_slist_root_typ[0]) *_rootp = ROOT; \
+ typeof(*_rootp->front) *_nodep = NODE; \
+ _slist_push_to_rear((struct _slist_root *)_rootp, \
+ (struct _slist_node *)_nodep); \
+} while(0)
+
+#define slist_pop_from_front(ROOT) { \
+ /* This temporary variables are to get the compiler to check \
+ * the type. */ \
+ typeof(*(ROOT)->_slist_root_typ[0]) *_rootp = ROOT; \
+ _slist_pop_from_front((struct _slist_root *)_rootp); \
+} while(0)
+
+/* doubly linked list (non-intrusive) *****************************************/
+
+#define DLIST_DECLARE(NAME) \
+ struct NAME##_node; \
+ struct NAME { \
+ struct NAME##_node *front, *rear; \
+ struct NAME *_dlist_root_typ[0]; \
+ }
+
+#define DLIST_DECLARE_NODE(NAME, VAL_T) \
+ struct NAME##_node { \
+ struct NAME##_node *front, *rear; \
+ VAL_T val; \
+ }
+
+#define dlist_push_to_rear(ROOT, NODE) { \
+ /* These temporary variables are to get the compiler to check \
+ * the types. */ \
+ typeof(*(ROOT)->_dlist_root_typ[0]) *_rootp = ROOT; \
+ typeof(*_rootp->front) *_nodep = NODE; \
+ _dlist_push_to_rear((struct _dlist_root *)_rootp, \
+ (struct _dlist_node *)_nodep); \
+} while(0)
+
+#define dlist_remove(ROOT, NODE) { \
+ /* These temporary variables are to get the compiler to check \
+ * the types. */ \
+ typeof(*(ROOT)->_dlist_root_typ[0]) *_rootp = ROOT; \
+ typeof(*_rootp->front) *_nodep = NODE; \
+ _dlist_remove((struct _dlist_root *)_rootp, \
+ (struct _dlist_node *)_nodep); \
+} while(0)
+
+#define dlist_pop_from_front(ROOT) { \
+ /* This temporary variables are to get the compiler to check \
+ * the type. */ \
+ typeof(*(ROOT)->_dlist_root_typ[0]) *_rootp = ROOT; \
+ _dlist_pop_from_front((struct _dlist_root *)_rootp); \
+} while(0)
#endif /* _LIBMISC_LINKEDLIST_H_ */
diff --git a/libmisc/include/libmisc/map.h b/libmisc/include/libmisc/map.h
index f846f57..41ac069 100644
--- a/libmisc/include/libmisc/map.h
+++ b/libmisc/include/libmisc/map.h
@@ -15,12 +15,14 @@
/* Type ***********************************************************************/
+DLIST_DECLARE(_map_kv_list);
+
struct _map {
- size_t len;
- size_t nbuckets;
- lm_dll_root *buckets;
+ size_t len;
+ size_t nbuckets;
+ struct _map_kv_list *buckets;
- unsigned iterating;
+ unsigned int iterating;
size_t sizeof_kv;
size_t offsetof_k, sizeof_k;
@@ -30,25 +32,26 @@ struct _map {
/**
* MAP_DECLARE(MAPNAME, KEY_T, VAL_T) declares `struct MAPNAME`.
*/
-#define MAP_DECLARE(MAPNAME, KEY_T, VAL_T) \
- struct MAPNAME { \
- struct _map core; \
- struct { \
- lm_dll_node; \
- uint8_t flags; \
- KEY_T key; \
- VAL_T val; \
- } kv_typ[0]; \
+#define MAP_DECLARE(MAPNAME, KEY_T, VAL_T) \
+ struct _##MAPNAME##_kv { \
+ uint8_t flags; \
+ KEY_T key; \
+ VAL_T val; \
+ }; \
+ DLIST_DECLARE_NODE(_##MAPNAME##_kv_list, struct _##MAPNAME##_kv); \
+ struct MAPNAME { \
+ struct _map core; \
+ struct _##MAPNAME##_kv_list_node kv_typ[0]; \
}
-#define _map_init(M) do { \
- if (!(M)->core.sizeof_kv) { \
- (M)->core.sizeof_kv = sizeof((M)->kv_typ[0]); \
- (M)->core.sizeof_k = sizeof((M)->kv_typ[0].key); \
- (M)->core.sizeof_v = sizeof((M)->kv_typ[0].val); \
- (M)->core.offsetof_k = offsetof(typeof((M)->kv_typ[0]), key); \
- (M)->core.offsetof_v = offsetof(typeof((M)->kv_typ[0]), val); \
- } \
+#define _map_init(M) do { \
+ if (!(M)->core.sizeof_kv) { \
+ (M)->core.sizeof_kv = sizeof((M)->kv_typ[0]); \
+ (M)->core.sizeof_k = sizeof((M)->kv_typ[0].val.key); \
+ (M)->core.sizeof_v = sizeof((M)->kv_typ[0].val.val); \
+ (M)->core.offsetof_k = offsetof(typeof((M)->kv_typ[0]), val.key); \
+ (M)->core.offsetof_v = offsetof(typeof((M)->kv_typ[0]), val.val); \
+ } \
} while(0)
/* Methods ********************************************************************/
@@ -64,8 +67,8 @@ struct _map {
*/
#define map_load(M, K) ({ \
_map_init(M); \
- typeof((M)->kv_typ[0].key) _k = K; \
- (typeof((M)->kv_typ[0].val)*)_map_load(&(M)->core, &_k); \
+ typeof((M)->kv_typ[0].val.key) _k = K; \
+ (typeof((M)->kv_typ[0].val.val)*)_map_load(&(M)->core, &_k); \
})
void *_map_load(struct _map *m, void *kp);
@@ -73,10 +76,10 @@ void *_map_load(struct _map *m, void *kp);
* map_del(map, key) ensures that `key` is not present in `map`.
* Returns whether `key` was in `map` before the call.
*/
-#define map_del(M, K) ({ \
- _map_init(M); \
- typeof((M)->kv_typ[0].key) _k = K; \
- _map_del(&(M)->core, &_k); \
+#define map_del(M, K) ({ \
+ _map_init(M); \
+ typeof((M)->kv_typ[0].val.key) _k = K; \
+ _map_del(&(M)->core, &_k); \
})
bool _map_del(struct _map *m, void *kp);
@@ -84,11 +87,11 @@ bool _map_del(struct _map *m, void *kp);
* map_store(map, key, val) sets a value in the map. Returns a
* pointer to the map's copy of `val`.
*/
-#define map_store(M, K, ...) ({ \
- _map_init(M); \
- typeof((M)->kv_typ[0].key) _k = K; \
- typeof((M)->kv_typ[0].val) _v = __VA_ARGS__; \
- (typeof((M)->kv_typ[0].val)*)_map_store(&(M)->core, &_k, &_v); \
+#define map_store(M, K, ...) ({ \
+ _map_init(M); \
+ typeof((M)->kv_typ[0].val.key) _k = K; \
+ typeof((M)->kv_typ[0].val.val) _v = __VA_ARGS__; \
+ (typeof((M)->kv_typ[0].val.val)*)_map_store(&(M)->core, &_k, &_v); \
})
void *_map_store(struct _map *m, void *kp, void *vp);
@@ -100,18 +103,13 @@ void _map_free(struct _map *m);
/* Iteration ******************************************************************/
-struct _map_kv {
- lm_dll_node;
- uint8_t flags;
-};
-
struct _map_iter {
- struct _map *m;
- void *keyp;
- void **valpp;
+ struct _map *m;
+ void *keyp;
+ void **valpp;
- size_t i;
- struct _map_kv *kv;
+ size_t i;
+ struct _map_kv_list_node *kv;
};
/**
@@ -128,8 +126,8 @@ struct _map_iter {
#define MAP_FOREACH(M, KNAME, VNAME) _MAP_FOREACH(__COUNTER__, M, KNAME, VNAME)
#define _MAP_FOREACH(CNT, M, KNAME, VNAME) \
for (bool _once_##CNT = true; _once_##CNT;) \
- for (typeof((M)->kv_typ[0].key) KNAME; _once_##CNT;) \
- for (typeof((M)->kv_typ[0].val) *VNAME; _once_##CNT;) \
+ for (typeof((M)->kv_typ[0].val.key) KNAME; _once_##CNT;) \
+ for (typeof((M)->kv_typ[0].val.val) *VNAME; _once_##CNT;) \
for ( \
struct _map_iter _iter_##CNT = ({ \
_map_init(M); \
diff --git a/libmisc/linkedlist.c b/libmisc/linkedlist.c
index 5fe0977..71a0aa9 100644
--- a/libmisc/linkedlist.c
+++ b/libmisc/linkedlist.c
@@ -6,11 +6,13 @@
#include <stddef.h> /* for NULL */
+#include <libmisc/assert.h>
+
#include <libmisc/linkedlist.h>
/* singly linked list *********************************************************/
-void lm_sll_push_to_rear(lm_sll_root *root, lm_sll_node *node) {
+void _slist_push_to_rear(struct _slist_root *root, struct _slist_node *node) {
assert(root);
node->rear = NULL;
if (root->rear)
@@ -20,7 +22,7 @@ void lm_sll_push_to_rear(lm_sll_root *root, lm_sll_node *node) {
root->rear = node;
}
-void lm_sll_pop_from_front(lm_sll_root *root) {
+void _slist_pop_from_front(struct _slist_root *root) {
assert(root);
assert(root->front);
root->front = root->front->rear;
@@ -30,7 +32,7 @@ void lm_sll_pop_from_front(lm_sll_root *root) {
/* doubly linked list *********************************************************/
-void lm_dll_push_to_rear(lm_dll_root *root, lm_dll_node *node) {
+void _dlist_push_to_rear(struct _dlist_root *root, struct _dlist_node *node) {
assert(root);
assert(node);
node->front = root->rear;
@@ -42,7 +44,7 @@ void lm_dll_push_to_rear(lm_dll_root *root, lm_dll_node *node) {
root->rear = node;
}
-void lm_dll_remove(lm_dll_root *root, lm_dll_node *node) {
+void _dlist_remove(struct _dlist_root *root, struct _dlist_node *node) {
assert(root);
assert(node);
if (node->front)
@@ -55,8 +57,8 @@ void lm_dll_remove(lm_dll_root *root, lm_dll_node *node) {
root->rear = node->front;
}
-void lm_dll_pop_from_front(lm_dll_root *root) {
+void _dlist_pop_from_front(struct _dlist_root *root) {
assert(root);
assert(root->front);
- lm_dll_remove(root, root->front);
+ _dlist_remove(root, root->front);
}
diff --git a/libmisc/map.c b/libmisc/map.c
index bb8a2d2..7629c8c 100644
--- a/libmisc/map.c
+++ b/libmisc/map.c
@@ -16,14 +16,19 @@
/* Internal utilities *********************************************************/
-#define cast(n) lm_dll_node_cast(struct _map_kv, n)
-
-static inline void *_map_kv_keyp(struct _map *m, struct _map_kv *kv) {
+struct _map_kv {
+ uint8_t flags;
+ /* opaque key; */
+ /* opaque val; */
+};
+DLIST_DECLARE_NODE(_map_kv_list, struct _map_kv);
+
+static inline void *_map_kv_keyp(struct _map *m, struct _map_kv_list_node *kv) {
assert(m);
assert(kv);
return ((void*)kv)+m->offsetof_k;
}
-static inline void *_map_kv_valp(struct _map *m, struct _map_kv *kv) {
+static inline void *_map_kv_valp(struct _map *m, struct _map_kv_list_node *kv) {
assert(m);
assert(kv);
return ((void*)kv)+m->offsetof_v;
@@ -31,8 +36,8 @@ static inline void *_map_kv_valp(struct _map *m, struct _map_kv *kv) {
static inline void _map_lookup(struct _map *m, void *keyp,
hash_t *ret_hash,
- lm_dll_root **ret_bucket,
- struct _map_kv **ret_kv) {
+ struct _map_kv_list **ret_bucket,
+ struct _map_kv_list_node **ret_kv) {
assert(m);
assert(keyp);
assert(ret_hash);
@@ -45,8 +50,8 @@ static inline void _map_lookup(struct _map *m, void *keyp,
return;
}
*ret_bucket = &m->buckets[*ret_hash % m->nbuckets];
- for (struct _map_kv *kv = cast((*ret_bucket)->front); kv; kv = cast(kv->rear)) {
- if (!(kv->flags & FLAG_DEL) &&
+ for (struct _map_kv_list_node *kv = (*ret_bucket)->front; kv; kv = kv->rear) {
+ if (!(kv->val.flags & FLAG_DEL) &&
memcmp(_map_kv_keyp(m, kv), keyp, m->sizeof_k) == 0) {
*ret_kv = kv;
return;
@@ -58,13 +63,13 @@ static inline void _map_lookup(struct _map *m, void *keyp,
static inline void _map_resize(struct _map *m, size_t new_nbuckets) {
assert(m);
assert(new_nbuckets);
- lm_dll_root *new_buckets = calloc(new_nbuckets, sizeof(lm_dll_root));
+ struct _map_kv_list *new_buckets = calloc(new_nbuckets, sizeof(struct _map_kv_list));
for (size_t i = 0; i < m->nbuckets; i++) {
while (m->buckets[i].front) {
- struct _map_kv *kv = cast(m->buckets[i].front);
- lm_dll_pop_from_front(&m->buckets[i]);
+ struct _map_kv_list_node *kv = m->buckets[i].front;
+ dlist_pop_from_front(&m->buckets[i]);
hash_t h = hash(_map_kv_keyp(m, kv), m->sizeof_k);
- lm_dll_push_to_rear(&new_buckets[h % new_nbuckets], kv);
+ dlist_push_to_rear(&new_buckets[h % new_nbuckets], kv);
}
}
m->nbuckets = new_nbuckets;
@@ -91,8 +96,8 @@ void *_map_load(struct _map *m, void *keyp) {
assert(keyp);
hash_t h;
- lm_dll_root *bucket;
- struct _map_kv *kv;
+ struct _map_kv_list *bucket;
+ struct _map_kv_list_node *kv;
_map_lookup(m, keyp, &h, &bucket, &kv);
if (!kv)
@@ -105,16 +110,16 @@ bool _map_del(struct _map *m, void *keyp) {
assert(keyp);
hash_t h;
- lm_dll_root *bucket;
- struct _map_kv *kv;
+ struct _map_kv_list *bucket;
+ struct _map_kv_list_node *kv;
_map_lookup(m, keyp, &h, &bucket, &kv);
if (!kv)
return false;
- if (kv->flags & FLAG_ITER) {
- kv->flags |= FLAG_DEL;
+ if (kv->val.flags & FLAG_ITER) {
+ kv->val.flags |= FLAG_DEL;
} else {
- lm_dll_remove(bucket, kv);
+ dlist_remove(bucket, kv);
free(kv);
}
m->len--;
@@ -127,12 +132,12 @@ void *_map_store(struct _map *m, void *keyp, void *valp) {
assert(valp);
hash_t h;
- lm_dll_root *bucket;
- struct _map_kv *old;
+ struct _map_kv_list *bucket;
+ struct _map_kv_list_node *old;
_map_lookup(m, keyp, &h, &bucket, &old);
if (old) {
- lm_dll_remove(bucket, old);
+ dlist_remove(bucket, old);
free(old);
m->len--;
}
@@ -141,10 +146,10 @@ void *_map_store(struct _map *m, void *keyp, void *valp) {
h = hash(keyp, m->sizeof_k);
bucket = &m->buckets[h % m->nbuckets];
}
- struct _map_kv *kv = calloc(1, m->sizeof_kv);
+ struct _map_kv_list_node *kv = calloc(1, m->sizeof_kv);
memcpy(_map_kv_keyp(m, kv), keyp, m->sizeof_k);
memcpy(_map_kv_valp(m, kv), valp, m->sizeof_v);
- lm_dll_push_to_rear(bucket, kv);
+ dlist_push_to_rear(bucket, kv);
return _map_kv_valp(m, kv);
}
@@ -153,8 +158,8 @@ void _map_free(struct _map *m) {
for (size_t i = 0; i < m->nbuckets; i++) {
while (m->buckets[i].front) {
- struct _map_kv *kv = cast(m->buckets[i].front);
- lm_dll_pop_from_front(&m->buckets[i]);
+ struct _map_kv_list_node *kv = m->buckets[i].front;
+ dlist_pop_from_front(&m->buckets[i]);
free(kv);
}
}
@@ -199,14 +204,14 @@ bool _map_iter_next(struct _map_iter *state) {
return false;
while (!state->m->buckets[state->i].front)
state->i++;
- state->kv = cast(state->m->buckets[state->i].front);
+ state->kv = state->m->buckets[state->i].front;
} else {
- struct _map_kv *old_kv = state->kv;
- state->kv = cast(old_kv->rear);
+ struct _map_kv_list_node *old_kv = state->kv;
+ state->kv = old_kv->rear;
- old_kv->flags &= ~FLAG_ITER;
- if (old_kv->flags & FLAG_DEL) {
- lm_dll_remove(&state->m->buckets[state->i], old_kv);
+ old_kv->val.flags &= ~FLAG_ITER;
+ if (old_kv->val.flags & FLAG_DEL) {
+ dlist_remove(&state->m->buckets[state->i], old_kv);
free(old_kv);
}
@@ -214,10 +219,10 @@ bool _map_iter_next(struct _map_iter *state) {
state->i++;
if (state->i == state->m->nbuckets)
return false;
- state->kv = cast(state->m->buckets[state->i].front);
+ state->kv = state->m->buckets[state->i].front;
}
}
- state->kv->flags |= FLAG_ITER;
+ state->kv->val.flags |= FLAG_ITER;
memcpy(state->keyp, _map_kv_keyp(state->m, state->kv), state->m->sizeof_k);
*(state->valpp) = _map_kv_valp(state->m, state->kv);
return true;
generated by cgit v1.2.3-2-g168b (git 2.25.1) at 2025-04-17 17:44:55 +0000