Merge branch 'lukeshu/generics'

2 files changed, 129 insertions, 69 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);                                         \