[RFC 00/34] ptrlist rework with iterator

[RFC 00/34] ptrlist rework with iterator

[Luc Van Oostenryck]

Here is some patches reworking the whole ptrlist API
which move all the logic currently present in the macros
in a small set of primitive functions using an iterator
structure.

It's in the state I left it in November.
It's OK for the testsuite and IIRC was fine when using
on the kernel too.
I didn't saw any appreciable speed change when using it.

By no means will this solve our current problem with the
nested list walking but it is, IMO, a much cleaner base
to work on.


Luc Van Oostenryck (34):
  ptrlist: simplify DO_FOR_EACH/DO_END_FOR_EACH
  ptrlist: simplify DO_FOR_EACH_REVERSE/...
  ptrlist: simplify DO_NEXT link walking
  ptrlist: add helper __PTR_STRIP_TAG()
  ptrlist: introduce the ptr_list iterator structure
  ptrlist: add ptr_cur_entry() to get iterator's current entry
  ptrlist: add forward iterator
  ptrlist: let first_ptr_list() use the iterator API
  ptrlist: add backward iterator
  ptrlist: let lastst_ptr_list() use the iterator API
  ptrlist: mechanically replace head-list-nr triplets by an iterator struct
  ptrlist: simplify initialization of DO_REVERSE()'s cursor
  ptrlist: abstract away iterator initialization
  ptrlist: CUR_ENTRY/CUR_ENTRY_NOTAG
  ptrlist: use iterator API for PREPARE/NEXT_PTR_LIST()
  ptrlist: use iterator API for RESET_PTR_LIST()
  ptrlist: use iterator for FOR_EACH_PTR()
  ptrlist: use iterator for FOR_EACH_PTR_REVERSE()
  ptrlist: remove unneeded DO_INIT()
  ptrlist: use the iterator API for DO_INSERT_CURRENT()
  ptrlist: extract ptr_cur_insert from ptrlist.h
  ptrlist: simplify ptr_cur_insert()
  ptrlist: use the iterator API for DO_DELETE_CURRENT()
  ptrlist: extract prt_cur_delete() from ptrlist.h
  ptrlist: let delete_ptr_list() use the iterator API
  ptrlist: let replace_ptr_list_entry() use the iterator API
  ptrlist: let concat_ptr_list() use the iterator API
  ptrlist: let undo_ptr_list_last() use the iterator API
  ptrlist: let delete_ptr_list_last() use the iterator API
  ptrlist: simplify common case for __add_ptr_list()
  ptrlist: explicitely tagged
  ptrlist: tag/notag common case
  ptrlist: drop the now unneeded _NOTAG versions
  ptrlist: addr vs entry

 c2xml.c          |   4 +-
 compile.c        |   4 +-
 ctags.c          |   4 +-
 example.c        |  20 ++--
 graph.c          |   8 +-
 obfuscate.c      |   4 +-
 ptrlist.c        | 217 ++++++++++++++++++++++++++++++++---------
 ptrlist.h        | 286 ++++++++++++++++++++++---------------------------------
 sparse-llvm.c    |   4 +-
 sparse.c         |   4 +-
 test-dissect.c   |   4 +-
 test-inspect.c   |   4 +-
 test-lexing.c    |   4 +-
 test-linearize.c |   4 +-
 test-parsing.c   |   4 +-
 test-unssa.c     |   4 +-
 16 files changed, 323 insertions(+), 256 deletions(-)

-- 
2.13.0

[PATCH 01/34] ptrlist: simplify DO_FOR_EACH/DO_END_FOR_EACH

[Luc Van Oostenryck]

---
 ptrlist.h | 17 ++++++-----------
 1 file changed, 6 insertions(+), 11 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index d09be2f51..9ffbc6e18 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -156,19 +156,14 @@ static inline void *last_ptr_list(struct ptr_list *list)
 	struct ptr_list *__head = (struct ptr_list *) (head);				\
 	struct ptr_list *__list = __head;						\
 	CHECK_TYPE(head,ptr);								\
-	if (__head) {									\
-		do { int __nr;								\
-			for (__nr = 0; __nr < __list->nr; __nr++) {			\
-				do {							\
-					ptr = PTR_ENTRY(__list,__nr);			\
-					do {
+	if (!__head) break;								\
+	do { int __nr;									\
+		for (__nr = 0; __nr < __list->nr; __nr++) {				\
+			ptr = PTR_ENTRY(__list,__nr);					\
 
 #define DO_END_FOR_EACH(ptr, __head, __list, __nr)					\
-					} while (0);					\
-				} while (0);						\
-			}								\
-		} while ((__list = __list->next) != __head);				\
-	}										\
+		}									\
+	} while ((__list = __list->next) != __head);					\
 } while (0)
 
 #define DO_FOR_EACH_REVERSE(head, ptr, __head, __list, __nr, PTR_ENTRY) do {		\
-- 
2.13.0

[PATCH 02/34] ptrlist: simplify DO_FOR_EACH_REVERSE/...

[Luc Van Oostenryck]

---
 ptrlist.h | 34 +++++++++++++---------------------
 1 file changed, 13 insertions(+), 21 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index 9ffbc6e18..9bdce843d 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -170,22 +170,17 @@ static inline void *last_ptr_list(struct ptr_list *list)
 	struct ptr_list *__head = (struct ptr_list *) (head);				\
 	struct ptr_list *__list = __head;						\
 	CHECK_TYPE(head,ptr);								\
-	if (__head) {									\
-		do { int __nr;								\
-			__list = __list->prev;						\
-			__nr = __list->nr;						\
-			while (--__nr >= 0) {						\
-				do {							\
-					ptr = PTR_ENTRY(__list,__nr);			\
-					do {
+	if (!__head) break;								\
+	do { int __nr;									\
+		__list = __list->prev;							\
+		__nr = __list->nr;							\
+		while (--__nr >= 0) {							\
+			ptr = PTR_ENTRY(__list,__nr);					\
 
 
 #define DO_END_FOR_EACH_REVERSE(ptr, __head, __list, __nr)				\
-					} while (0);					\
-				} while (0);						\
-			}								\
-		} while (__list != __head);						\
-	}										\
+		}									\
+	} while (__list != __head);							\
 } while (0)
 
 #define DO_REVERSE(ptr, __head, __list, __nr, new, __newhead,				\
@@ -195,15 +190,12 @@ static inline void *last_ptr_list(struct ptr_list *list)
 	int __newnr = __nr;								\
 	new = ptr;									\
 	goto __inside##new;								\
-	if (1) {									\
-		do {									\
-			__newlist = __newlist->prev;					\
-			__newnr = __newlist->nr;					\
+	do {										\
+		__newlist = __newlist->prev;						\
+		__newnr = __newlist->nr;						\
 	__inside##new:									\
-			while (--__newnr >= 0) {					\
-				do {							\
-					new = PTR_ENTRY(__newlist,__newnr);		\
-					do {
+		while (--__newnr >= 0) {						\
+			new = PTR_ENTRY(__newlist,__newnr);				\
 
 #define RECURSE_PTR_REVERSE(ptr, new)							\
 	DO_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr,				\
-- 
2.13.0

[PATCH 03/34] ptrlist: simplify DO_NEXT link walking

[Luc Van Oostenryck]

---
 ptrlist.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index 9bdce843d..7ecf2b529 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -118,10 +118,10 @@ static inline void *last_ptr_list(struct ptr_list *list)
 			if (++__nr < __list->nr) {					\
 				ptr = PTR_ENTRY(__list,__nr);				\
 			} else {							\
-				__list = __list->next;					\
 				ptr = NULL;						\
-				while (__list->nr == 0 && __list != __head)		\
+				do							\
 					__list = __list->next;				\
+				while (__list->nr == 0 && __list != __head);		\
 				if (__list != __head) {					\
 					__nr = 0;					\
 					ptr = PTR_ENTRY(__list,0);			\
-- 
2.13.0

[PATCH 04/34] ptrlist: add helper __PTR_STRIP_TAG()

[Luc Van Oostenryck]

---
 ptrlist.h | 11 +++++++++--
 1 file changed, 9 insertions(+), 2 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index 7ecf2b529..93de46c0b 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -62,8 +62,15 @@ extern int linearize_ptr_list(struct ptr_list *, void **, int);
 #define free_ptr_list(list) \
 	do { VRFY_PTR_LIST(*(list)); __free_ptr_list((struct ptr_list **)(list)); } while (0)
 
-#define PTR_ENTRY_NOTAG(h,i)	((h)->list[i])
-#define PTR_ENTRY(h,i)	(void *)(~3UL & (unsigned long)PTR_ENTRY_NOTAG(h,i))
+static inline void *__ptr_entry(const struct ptr_list *l, unsigned int i)
+{
+	return l->list[i];
+}
+
+#define PTR_ENTRY_NOTAG(h,i)	__ptr_entry(h, i)
+#define __PTR_STRIP_TAG(ptr)	(void *)(~3UL & (unsigned long)(ptr))
+#define __PTR_KEEP_TAG(ptr)	(ptr)
+#define PTR_ENTRY(h,i)		__PTR_STRIP_TAG(PTR_ENTRY_NOTAG(h,i))
 
 static inline void *first_ptr_list(struct ptr_list *list)
 {
-- 
2.13.0

[PATCH 05/34] ptrlist: introduce the ptr_list iterator structure

[Luc Van Oostenryck]

---
 ptrlist.h | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/ptrlist.h b/ptrlist.h
index 93de46c0b..e308f437c 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -31,6 +31,12 @@ struct ptr_list {
 	void *list[LIST_NODE_NR];
 };
 
+struct ptr_cur {
+	struct ptr_list *h;	/* head of the list */
+	struct ptr_list *l;	/* current block */
+	int n;			/* current index on the curent block */
+};
+
 #define ptr_list_empty(x) ((x) == NULL)
 
 void * undo_ptr_list_last(struct ptr_list **head);
-- 
2.13.0

[PATCH 06/34] ptrlist: add ptr_cur_entry() to get iterator's current entry

[Luc Van Oostenryck]

---
 ptrlist.h | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/ptrlist.h b/ptrlist.h
index e308f437c..d271f9e04 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -73,6 +73,11 @@ static inline void *__ptr_entry(const struct ptr_list *l, unsigned int i)
 	return l->list[i];
 }
 
+static inline void *ptr_cur_entry(const struct ptr_cur *cur)
+{
+	return __ptr_entry(cur->l, cur->n);
+}
+
 #define PTR_ENTRY_NOTAG(h,i)	__ptr_entry(h, i)
 #define __PTR_STRIP_TAG(ptr)	(void *)(~3UL & (unsigned long)(ptr))
 #define __PTR_KEEP_TAG(ptr)	(ptr)
-- 
2.13.0

[PATCH 07/34] ptrlist: add forward iterator

[Luc Van Oostenryck]

---
 ptrlist.c | 27 +++++++++++++++++++++++++++
 ptrlist.h |  3 +++
 2 files changed, 30 insertions(+)

diff --git a/ptrlist.c b/ptrlist.c
index 5dc1117c5..5798aec43 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -246,3 +246,30 @@ void __free_ptr_list(struct ptr_list **listp)
 
 	*listp = NULL;
 }
+
+
+int ptr_cur_next(struct ptr_cur *cur)
+{
+	do {
+		struct ptr_list *curl = cur->l;
+
+		if (++cur->n < curl->nr)
+			return 1;
+
+		cur->l = curl->next;
+		cur->n = -1;
+	} while (cur->l != cur->h);
+
+	return 0;
+}
+
+int ptr_cur_beg(struct ptr_cur *cur, struct ptr_list *head)
+{
+	if (!head)
+		return 0;
+
+	cur->h = head;
+	cur->l = head;
+	cur->n = -1;
+	return 1;
+}
diff --git a/ptrlist.h b/ptrlist.h
index d271f9e04..ff38538cb 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -51,6 +51,9 @@ extern void __free_ptr_list(struct ptr_list **);
 extern int ptr_list_size(struct ptr_list *);
 extern int linearize_ptr_list(struct ptr_list *, void **, int);
 
+int ptr_cur_beg(struct ptr_cur *cur, struct ptr_list *head);
+int ptr_cur_next(struct ptr_cur *cur);
+
 /*
  * Hey, who said that you can't do overloading in C?
  *
-- 
2.13.0

[PATCH 08/34] ptrlist: let first_ptr_list() use the iterator API

[Luc Van Oostenryck]

---
 ptrlist.h | 15 ++++++---------
 1 file changed, 6 insertions(+), 9 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index ff38538cb..b46967c58 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -86,19 +86,16 @@ static inline void *ptr_cur_entry(const struct ptr_cur *cur)
 #define __PTR_KEEP_TAG(ptr)	(ptr)
 #define PTR_ENTRY(h,i)		__PTR_STRIP_TAG(PTR_ENTRY_NOTAG(h,i))
 
+
 static inline void *first_ptr_list(struct ptr_list *list)
 {
-	struct ptr_list *head = list;
+	struct ptr_cur cur;
 
-	if (!list)
+	if (!ptr_cur_beg(&cur, list))
 		return NULL;

[PATCH 09/34] ptrlist: add backward iterator

[Luc Van Oostenryck]

---
 ptrlist.c | 32 ++++++++++++++++++++++++++++++++
 ptrlist.h |  2 ++
 2 files changed, 34 insertions(+)

diff --git a/ptrlist.c b/ptrlist.c
index 5798aec43..031c53262 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -273,3 +273,35 @@ int ptr_cur_beg(struct ptr_cur *cur, struct ptr_list *head)
 	cur->n = -1;
 	return 1;
 }
+
+int ptr_cur_prev(struct ptr_cur *cur)
+{
+	do {
+		struct ptr_list *curl = cur->l;
+
+		if (--cur->n >= 0)
+			return 1;
+
+		if (curl == cur->h)
+			break;
+		curl = curl->prev;
+		cur->l = curl;
+		cur->n = curl->nr;
+	} while (1);
+
+	return 0;
+}
+
+int ptr_cur_end(struct ptr_cur *cur, struct ptr_list *head)
+{
+	struct ptr_list *prev;
+
+	if (!head)
+		return 0;
+
+	prev = head->prev;
+	cur->h = head;
+	cur->l = prev;
+	cur->n = prev->nr;
+	return 1;
+}
diff --git a/ptrlist.h b/ptrlist.h
index b46967c58..883cca952 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -53,6 +53,8 @@ extern int linearize_ptr_list(struct ptr_list *, void **, int);
 
 int ptr_cur_beg(struct ptr_cur *cur, struct ptr_list *head);
 int ptr_cur_next(struct ptr_cur *cur);
+int ptr_cur_end(struct ptr_cur *cur, struct ptr_list *head);
+int ptr_cur_prev(struct ptr_cur *cur);
 
 /*
  * Hey, who said that you can't do overloading in C?
-- 
2.13.0

[PATCH 10/34] ptrlist: let lastst_ptr_list() use the iterator API

[Luc Van Oostenryck]

---
 ptrlist.h | 14 +++++---------
 1 file changed, 5 insertions(+), 9 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index 883cca952..f856a54eb 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -102,17 +102,13 @@ static inline void *first_ptr_list(struct ptr_list *list)
 
 static inline void *last_ptr_list(struct ptr_list *list)
 {
-	struct ptr_list *head = list;
+	struct ptr_cur cur;
 
-	if (!list)
+	if (!ptr_cur_end(&cur, list))
+		return NULL;
+	if (!ptr_cur_prev(&cur))
 		return NULL;
-	list = list->prev;
-	while (list->nr == 0) {
-		if (list == head)
-			return NULL;
-		list = list->prev;
-	}
-	return PTR_ENTRY(list, list->nr-1);
+	return __PTR_STRIP_TAG(ptr_cur_entry(&cur));
 }
 
 #define PTR_DEREF(__head, idx, PTR_ENTRY) ({						\
-- 
2.13.0

[PATCH 11/34] ptrlist: mechanically replace head-list-nr triplets by an iterator struct

[Luc Van Oostenryck]

---
 ptrlist.h | 174 ++++++++++++++++++++++++++++++--------------------------------
 1 file changed, 84 insertions(+), 90 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index f856a54eb..8941c339a 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -111,180 +111,174 @@ static inline void *last_ptr_list(struct ptr_list *list)
 	return __PTR_STRIP_TAG(ptr_cur_entry(&cur));
 }
 
-#define PTR_DEREF(__head, idx, PTR_ENTRY) ({						\
-	struct ptr_list *__list = __head;						\
-	while (__list && __list->nr == 0) {						\
-		__list = __list->next;							\
-		if (__list == __head)							\
-			__list = NULL;							\
-	}										\
-	__list ? PTR_ENTRY(__list, idx) : NULL;						\
-})
-
-#define DO_PREPARE(head, ptr, __head, __list, __nr, PTR_ENTRY)				\
+#define DO_PREPARE(head, ptr, __cur, PTR_ENTRY)						\
 	do {										\
-		struct ptr_list *__head = (struct ptr_list *) (head);			\
-		struct ptr_list *__list = __head;					\
-		int __nr = 0;								\
+		struct ptr_cur __cur;							\
+		__cur.h = (struct ptr_list *) (head);					\
+		__cur.l = __cur.h;							\
+		__cur.n = 0;								\
 		CHECK_TYPE(head,ptr);							\
-		ptr = PTR_DEREF(__head, 0, PTR_ENTRY);					\
+		if (__cur.h) ptr = PTR_ENTRY(__cur.h, 0);				\
+		else ptr = NULL
 
-#define DO_NEXT(ptr, __head, __list, __nr, PTR_ENTRY)					\
+#define DO_NEXT(ptr, __cur, PTR_ENTRY)							\
 		if (ptr) {								\
-			if (++__nr < __list->nr) {					\
-				ptr = PTR_ENTRY(__list,__nr);				\
+			if (++__cur.n < __cur.l->nr) {					\
+				ptr = PTR_ENTRY(__cur.l,__cur.n);			\
 			} else {							\
 				ptr = NULL;						\
 				do							\
-					__list = __list->next;				\
-				while (__list->nr == 0 && __list != __head);		\
-				if (__list != __head) {					\
-					__nr = 0;					\
-					ptr = PTR_ENTRY(__list,0);			\
+					__cur.l = __cur.l->next;			\
+				while (__cur.l->nr == 0 && __cur.l != __cur.h);		\
+				if (__cur.l != __cur.h) {				\
+					__cur.n = 0;					\
+					ptr = PTR_ENTRY(__cur.l,0);			\
 				}							\
 			}								\
 		}
 
-#define DO_RESET(ptr, __head, __list, __nr, PTR_ENTRY)					\
+#define DO_RESET(ptr, __cur, PTR_ENTRY)						\
 	do {										\
-		__nr = 0;								\
-		__list = __head;							\
-		if (__head) ptr = PTR_DEREF(__head, 0, PTR_ENTRY);			\
+		__cur.n = 0;								\
+		__cur.l = __cur.h;							\
+		if (__cur.h) ptr = PTR_ENTRY(__cur.h, 0);				\
 	} while (0)
 
-#define DO_FINISH(ptr, __head, __list, __nr)						\
-		(void)(__nr); /* Sanity-check nesting */				\
+#define DO_FINISH(ptr, __cur)								\
+		(void)(__cur.n); /* Sanity-check nesting */				\
 	} while (0)
 
 #define PREPARE_PTR_LIST(head, ptr) \
-	DO_PREPARE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY)
+	DO_PREPARE(head, ptr, __cur##ptr, PTR_ENTRY)
 
 #define NEXT_PTR_LIST(ptr) \
-	DO_NEXT(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY)
+	DO_NEXT(ptr, __cur##ptr, PTR_ENTRY)
 
 #define RESET_PTR_LIST(ptr) \
-	DO_RESET(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY)
+	DO_RESET(ptr, __cur##ptr, PTR_ENTRY)
 
 #define FINISH_PTR_LIST(ptr) \
-	DO_FINISH(ptr, __head##ptr, __list##ptr, __nr##ptr)
+	DO_FINISH(ptr, __cur##ptr)
 
-#define DO_FOR_EACH(head, ptr, __head, __list, __nr, PTR_ENTRY) do {			\
-	struct ptr_list *__head = (struct ptr_list *) (head);				\
-	struct ptr_list *__list = __head;						\
+#define DO_FOR_EACH(head, ptr, __cur, PTR_ENTRY) do {					\
+	struct ptr_cur __cur;								\
+	__cur.h = (struct ptr_list *) (head);						\
+	__cur.l = __cur.h;								\
 	CHECK_TYPE(head,ptr);								\
-	if (!__head) break;								\
-	do { int __nr;									\
-		for (__nr = 0; __nr < __list->nr; __nr++) {				\
-			ptr = PTR_ENTRY(__list,__nr);					\
+	if (!__cur.h) break;								\
+	do {										\
+		for (__cur.n = 0; __cur.n < __cur.l->nr; __cur.n++) {			\
+			ptr = PTR_ENTRY(__cur.l,__cur.n);				\
 
-#define DO_END_FOR_EACH(ptr, __head, __list, __nr)					\
+#define DO_END_FOR_EACH(ptr, __cur)							\
 		}									\
-	} while ((__list = __list->next) != __head);					\
+	} while ((__cur.l = __cur.l->next) != __cur.h);					\
 } while (0)
 
-#define DO_FOR_EACH_REVERSE(head, ptr, __head, __list, __nr, PTR_ENTRY) do {		\
-	struct ptr_list *__head = (struct ptr_list *) (head);				\
-	struct ptr_list *__list = __head;						\
+#define DO_FOR_EACH_REVERSE(head, ptr, __cur, PTR_ENTRY) do {				\
+	struct ptr_cur __cur;								\
+	__cur.h = (struct ptr_list *) (head);						\
+	__cur.l = __cur.h;								\
 	CHECK_TYPE(head,ptr);								\
-	if (!__head) break;								\
-	do { int __nr;									\
-		__list = __list->prev;							\
-		__nr = __list->nr;							\
-		while (--__nr >= 0) {							\
-			ptr = PTR_ENTRY(__list,__nr);					\
+	if (!__cur.h) break;								\
+	do {										\
+		__cur.l = __cur.l->prev;						\
+		__cur.n = __cur.l->nr;							\
+		while (--__cur.n >= 0) {						\
+			ptr = PTR_ENTRY(__cur.l,__cur.n);				\
 
 
-#define DO_END_FOR_EACH_REVERSE(ptr, __head, __list, __nr)				\
+#define DO_END_FOR_EACH_REVERSE(ptr, __cur)						\
 		}									\
-	} while (__list != __head);							\
+	} while (__cur.l != __cur.h);							\
 } while (0)
 
-#define DO_REVERSE(ptr, __head, __list, __nr, new, __newhead,				\
-		   __newlist, __newnr, PTR_ENTRY) do { 					\
-	struct ptr_list *__newhead = __head;						\
-	struct ptr_list *__newlist = __list;						\
-	int __newnr = __nr;								\
+#define DO_REVERSE(ptr, __cur, new, __newcur, PTR_ENTRY) do {				\
+	struct ptr_cur __newcur;							\
+	__newcur.h = __cur.h;								\
+	__newcur.l = __cur.l;								\
+	__newcur.n = __cur.n;								\
 	new = ptr;									\
 	goto __inside##new;								\
 	do {										\
-		__newlist = __newlist->prev;						\
-		__newnr = __newlist->nr;						\
+		__newcur.l = __newcur.l->prev;						\
+		__newcur.n = __newcur.l->nr;						\
 	__inside##new:									\
-		while (--__newnr >= 0) {						\
-			new = PTR_ENTRY(__newlist,__newnr);				\
+		while (--__newcur.n >= 0) {						\
+			new = PTR_ENTRY(__newcur.l,__newcur.n);				\
 
 #define RECURSE_PTR_REVERSE(ptr, new)							\
-	DO_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr,				\
-		   new, __head##new, __list##new, __nr##new, PTR_ENTRY)
+	DO_REVERSE(ptr, __cur##ptr,							\
+		   new, __cur##new, PTR_ENTRY)
 
-#define DO_THIS_ADDRESS(ptr, __head, __list, __nr)					\
-	((__typeof__(&(ptr))) (__list->list + __nr))
+#define DO_THIS_ADDRESS(ptr, __cur)							\
+	((__typeof__(&(ptr))) (__cur.l->list + __cur.n))
 
 #define FOR_EACH_PTR(head, ptr) \
-	DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY)
+	DO_FOR_EACH(head, ptr, __cur##ptr, PTR_ENTRY)
 
 #define END_FOR_EACH_PTR(ptr) \
-	DO_END_FOR_EACH(ptr, __head##ptr, __list##ptr, __nr##ptr)
+	DO_END_FOR_EACH(ptr, __cur##ptr)
 
 #define FOR_EACH_PTR_NOTAG(head, ptr) \
-	DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_NOTAG)
+	DO_FOR_EACH(head, ptr, __cur##ptr, PTR_ENTRY_NOTAG)
 
 #define END_FOR_EACH_PTR_NOTAG(ptr) END_FOR_EACH_PTR(ptr)
 
 #define FOR_EACH_PTR_REVERSE(head, ptr) \
-	DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY)
+	DO_FOR_EACH_REVERSE(head, ptr, __cur##ptr, PTR_ENTRY)
 
 #define END_FOR_EACH_PTR_REVERSE(ptr) \
-	DO_END_FOR_EACH_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr)
+	DO_END_FOR_EACH_REVERSE(ptr, __cur##ptr)
 
 #define FOR_EACH_PTR_REVERSE_NOTAG(head, ptr) \
-	DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_NOTAG)
+	DO_FOR_EACH_REVERSE(head, ptr, __cur##ptr, PTR_ENTRY_NOTAG)
 
 #define END_FOR_EACH_PTR_REVERSE_NOTAG(ptr) END_FOR_EACH_PTR_REVERSE(ptr)
 
 #define THIS_ADDRESS(ptr) \
-	DO_THIS_ADDRESS(ptr, __head##ptr, __list##ptr, __nr##ptr)
+	DO_THIS_ADDRESS(ptr, __cur##ptr)
 
 extern void split_ptr_list_head(struct ptr_list *);
 
-#define DO_SPLIT(ptr, __head, __list, __nr) do {					\
-	split_ptr_list_head(__list);							\
-	if (__nr >= __list->nr) {							\
-		__nr -= __list->nr;							\
-		__list = __list->next;							\
+#define DO_SPLIT(ptr, __cur) do {							\
+	split_ptr_list_head(__cur.l);							\
+	if (__cur.n >= __cur.l->nr) {							\
+		__cur.n -= __cur.l->nr;							\
+		__cur.l = __cur.l->next;						\
 	};										\
 } while (0)
 
-#define DO_INSERT_CURRENT(new, ptr, __head, __list, __nr) do {				\
+#define DO_INSERT_CURRENT(new, ptr, __cur) do {						\
 	void **__this, **__last;							\
-	if (__list->nr == LIST_NODE_NR)							\
-		DO_SPLIT(ptr, __head, __list, __nr);					\
-	__this = __list->list + __nr;							\
-	__last = __list->list + __list->nr - 1;						\
+	if (__cur.l->nr == LIST_NODE_NR)						\
+		DO_SPLIT(ptr, __cur);							\
+	__this = __cur.l->list + __cur.n;						\
+	__last = __cur.l->list + __cur.l->nr - 1;					\
 	while (__last >= __this) {							\
 		__last[1] = __last[0];							\
 		__last--;								\
 	}										\
 	*__this = (new);								\
-	__list->nr++;									\
+	__cur.l->nr++;									\
 } while (0)
 
 #define INSERT_CURRENT(new, ptr) \
-	DO_INSERT_CURRENT(new, ptr, __head##ptr, __list##ptr, __nr##ptr)
+	DO_INSERT_CURRENT(new, ptr, __cur##ptr)
 
-#define DO_DELETE_CURRENT(ptr, __head, __list, __nr) do {				\
-	void **__this = __list->list + __nr;						\
-	void **__last = __list->list + __list->nr - 1;					\
+#define DO_DELETE_CURRENT(ptr, __cur) do {						\
+	void **__this = __cur.l->list + __cur.n;					\
+	void **__last = __cur.l->list + __cur.l->nr - 1;				\
 	while (__this < __last) {							\
 		__this[0] = __this[1];							\
 		__this++;								\
 	}										\
 	*__this = (void *)0xf0f0f0f0;							\
-	__list->nr--; __nr--;								\
+	__cur.l->nr--; __cur.n--;							\
 } while (0)
 
 #define DELETE_CURRENT_PTR(ptr) \
-	DO_DELETE_CURRENT(ptr, __head##ptr, __list##ptr, __nr##ptr)
+	DO_DELETE_CURRENT(ptr, __cur##ptr)
 
 #define REPLACE_CURRENT_PTR(ptr, new_ptr)						\
 	do { *THIS_ADDRESS(ptr) = (new_ptr); } while (0)
-- 
2.13.0

[PATCH 12/34] ptrlist: simplify initialization of DO_REVERSE()'s cursor

[Luc Van Oostenryck]

---
 ptrlist.h | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index 8941c339a..0d17237f5 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -194,10 +194,7 @@ static inline void *last_ptr_list(struct ptr_list *list)
 } while (0)
 
 #define DO_REVERSE(ptr, __cur, new, __newcur, PTR_ENTRY) do {				\
-	struct ptr_cur __newcur;							\
-	__newcur.h = __cur.h;								\
-	__newcur.l = __cur.l;								\
-	__newcur.n = __cur.n;								\
+	struct ptr_cur __newcur = __cur;						\
 	new = ptr;									\
 	goto __inside##new;								\
 	do {										\
-- 
2.13.0

[PATCH 13/34] ptrlist: abstract away iterator initialization

[Luc Van Oostenryck]

---
 ptrlist.h | 20 +++++++++++++-------
 1 file changed, 13 insertions(+), 7 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index 0d17237f5..91019e7c5 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -111,13 +111,21 @@ static inline void *last_ptr_list(struct ptr_list *list)
 	return __PTR_STRIP_TAG(ptr_cur_entry(&cur));
 }
 
+static inline void ptr_cur_init(struct ptr_cur *cur, struct ptr_list *head)
+{
+	cur->h = head;
+	cur->l = head;
+	cur->n = 0;
+}
+
+#define DO_INIT(cur, head)	\
+	ptr_cur_init(&cur, (struct ptr_list *) head)
+
 #define DO_PREPARE(head, ptr, __cur, PTR_ENTRY)						\
 	do {										\
 		struct ptr_cur __cur;							\
-		__cur.h = (struct ptr_list *) (head);					\
-		__cur.l = __cur.h;							\
-		__cur.n = 0;								\
 		CHECK_TYPE(head,ptr);							\
+		DO_INIT(__cur, head);							\
 		if (__cur.h) ptr = PTR_ENTRY(__cur.h, 0);				\
 		else ptr = NULL
 
@@ -162,9 +170,8 @@ static inline void *last_ptr_list(struct ptr_list *list)
 
 #define DO_FOR_EACH(head, ptr, __cur, PTR_ENTRY) do {					\
 	struct ptr_cur __cur;								\
-	__cur.h = (struct ptr_list *) (head);						\
-	__cur.l = __cur.h;								\
 	CHECK_TYPE(head,ptr);								\
+	DO_INIT(__cur, head);								\
 	if (!__cur.h) break;								\
 	do {										\
 		for (__cur.n = 0; __cur.n < __cur.l->nr; __cur.n++) {			\
@@ -177,9 +184,8 @@ static inline void *last_ptr_list(struct ptr_list *list)
 
 #define DO_FOR_EACH_REVERSE(head, ptr, __cur, PTR_ENTRY) do {				\
 	struct ptr_cur __cur;								\
-	__cur.h = (struct ptr_list *) (head);						\
-	__cur.l = __cur.h;								\
 	CHECK_TYPE(head,ptr);								\
+	DO_INIT(__cur, head);								\
 	if (!__cur.h) break;								\
 	do {										\
 		__cur.l = __cur.l->prev;						\
-- 
2.13.0

[PATCH 14/34] ptrlist: CUR_ENTRY/CUR_ENTRY_NOTAG

[Luc Van Oostenryck]

---
 ptrlist.h | 44 +++++++++++++++++++++++---------------------
 1 file changed, 23 insertions(+), 21 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index 91019e7c5..7c8fefe42 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -87,6 +87,8 @@ static inline void *ptr_cur_entry(const struct ptr_cur *cur)
 #define __PTR_STRIP_TAG(ptr)	(void *)(~3UL & (unsigned long)(ptr))
 #define __PTR_KEEP_TAG(ptr)	(ptr)
 #define PTR_ENTRY(h,i)		__PTR_STRIP_TAG(PTR_ENTRY_NOTAG(h,i))
+#define CUR_ENTRY_NOTAG(cur)	ptr_cur_entry(cur)
+#define CUR_ENTRY(cur)		__PTR_STRIP_TAG(CUR_ENTRY_NOTAG(cur))
 
 
 static inline void *first_ptr_list(struct ptr_list *list)
@@ -121,18 +123,18 @@ static inline void ptr_cur_init(struct ptr_cur *cur, struct ptr_list *head)
 #define DO_INIT(cur, head)	\
 	ptr_cur_init(&cur, (struct ptr_list *) head)
 
-#define DO_PREPARE(head, ptr, __cur, PTR_ENTRY)						\
+#define DO_PREPARE(head, ptr, __cur, CUR_ENTRY)						\
 	do {										\
 		struct ptr_cur __cur;							\
 		CHECK_TYPE(head,ptr);							\
 		DO_INIT(__cur, head);							\
-		if (__cur.h) ptr = PTR_ENTRY(__cur.h, 0);				\
+		if (__cur.h) ptr = CUR_ENTRY(&__cur);					\
 		else ptr = NULL
 
-#define DO_NEXT(ptr, __cur, PTR_ENTRY)							\
+#define DO_NEXT(ptr, __cur, CUR_ENTRY)							\
 		if (ptr) {								\
 			if (++__cur.n < __cur.l->nr) {					\
-				ptr = PTR_ENTRY(__cur.l,__cur.n);			\
+				ptr = CUR_ENTRY(&__cur);				\
 			} else {							\
 				ptr = NULL;						\
 				do							\
@@ -140,16 +142,16 @@ static inline void ptr_cur_init(struct ptr_cur *cur, struct ptr_list *head)
 				while (__cur.l->nr == 0 && __cur.l != __cur.h);		\
 				if (__cur.l != __cur.h) {				\
 					__cur.n = 0;					\
-					ptr = PTR_ENTRY(__cur.l,0);			\
+					ptr = CUR_ENTRY(&__cur);				\
 				}							\
 			}								\
 		}
 
-#define DO_RESET(ptr, __cur, PTR_ENTRY)						\
+#define DO_RESET(ptr, __cur, CUR_ENTRY)						\
 	do {										\
 		__cur.n = 0;								\
 		__cur.l = __cur.h;							\
-		if (__cur.h) ptr = PTR_ENTRY(__cur.h, 0);				\
+		if (__cur.h) ptr = CUR_ENTRY(&__cur);					\
 	} while (0)
 
 #define DO_FINISH(ptr, __cur)								\
@@ -157,32 +159,32 @@ static inline void ptr_cur_init(struct ptr_cur *cur, struct ptr_list *head)
 	} while (0)
 
 #define PREPARE_PTR_LIST(head, ptr) \
-	DO_PREPARE(head, ptr, __cur##ptr, PTR_ENTRY)
+	DO_PREPARE(head, ptr, __cur##ptr, CUR_ENTRY)
 
 #define NEXT_PTR_LIST(ptr) \
-	DO_NEXT(ptr, __cur##ptr, PTR_ENTRY)
+	DO_NEXT(ptr, __cur##ptr, CUR_ENTRY)
 
 #define RESET_PTR_LIST(ptr) \
-	DO_RESET(ptr, __cur##ptr, PTR_ENTRY)
+	DO_RESET(ptr, __cur##ptr, CUR_ENTRY)
 
 #define FINISH_PTR_LIST(ptr) \
 	DO_FINISH(ptr, __cur##ptr)
 
-#define DO_FOR_EACH(head, ptr, __cur, PTR_ENTRY) do {					\
+#define DO_FOR_EACH(head, ptr, __cur, CUR_ENTRY) do {					\
 	struct ptr_cur __cur;								\
 	CHECK_TYPE(head,ptr);								\
 	DO_INIT(__cur, head);								\
 	if (!__cur.h) break;								\
 	do {										\
 		for (__cur.n = 0; __cur.n < __cur.l->nr; __cur.n++) {			\
-			ptr = PTR_ENTRY(__cur.l,__cur.n);				\
+			ptr = CUR_ENTRY(&__cur);					\
 
 #define DO_END_FOR_EACH(ptr, __cur)							\
 		}									\
 	} while ((__cur.l = __cur.l->next) != __cur.h);					\
 } while (0)
 
-#define DO_FOR_EACH_REVERSE(head, ptr, __cur, PTR_ENTRY) do {				\
+#define DO_FOR_EACH_REVERSE(head, ptr, __cur, CUR_ENTRY) do {				\
 	struct ptr_cur __cur;								\
 	CHECK_TYPE(head,ptr);								\
 	DO_INIT(__cur, head);								\
@@ -191,7 +193,7 @@ static inline void ptr_cur_init(struct ptr_cur *cur, struct ptr_list *head)
 		__cur.l = __cur.l->prev;						\
 		__cur.n = __cur.l->nr;							\
 		while (--__cur.n >= 0) {						\
-			ptr = PTR_ENTRY(__cur.l,__cur.n);				\
+			ptr = CUR_ENTRY(&__cur);					\
 
 
 #define DO_END_FOR_EACH_REVERSE(ptr, __cur)						\
@@ -199,7 +201,7 @@ static inline void ptr_cur_init(struct ptr_cur *cur, struct ptr_list *head)
 	} while (__cur.l != __cur.h);							\
 } while (0)
 
-#define DO_REVERSE(ptr, __cur, new, __newcur, PTR_ENTRY) do {				\
+#define DO_REVERSE(ptr, __cur, new, __newcur, CUR_ENTRY) do {				\
 	struct ptr_cur __newcur = __cur;						\
 	new = ptr;									\
 	goto __inside##new;								\
@@ -208,34 +210,34 @@ static inline void ptr_cur_init(struct ptr_cur *cur, struct ptr_list *head)
 		__newcur.n = __newcur.l->nr;						\
 	__inside##new:									\
 		while (--__newcur.n >= 0) {						\
-			new = PTR_ENTRY(__newcur.l,__newcur.n);				\
+			new = CUR_ENTRY(&__newcur);					\
 
 #define RECURSE_PTR_REVERSE(ptr, new)							\
 	DO_REVERSE(ptr, __cur##ptr,							\
-		   new, __cur##new, PTR_ENTRY)
+		   new, __cur##new, CUR_ENTRY)
 
 #define DO_THIS_ADDRESS(ptr, __cur)							\
 	((__typeof__(&(ptr))) (__cur.l->list + __cur.n))
 
 #define FOR_EACH_PTR(head, ptr) \
-	DO_FOR_EACH(head, ptr, __cur##ptr, PTR_ENTRY)
+	DO_FOR_EACH(head, ptr, __cur##ptr, CUR_ENTRY)
 
 #define END_FOR_EACH_PTR(ptr) \
 	DO_END_FOR_EACH(ptr, __cur##ptr)
 
 #define FOR_EACH_PTR_NOTAG(head, ptr) \
-	DO_FOR_EACH(head, ptr, __cur##ptr, PTR_ENTRY_NOTAG)
+	DO_FOR_EACH(head, ptr, __cur##ptr, CUR_ENTRY_NOTAG)
 
 #define END_FOR_EACH_PTR_NOTAG(ptr) END_FOR_EACH_PTR(ptr)
 
 #define FOR_EACH_PTR_REVERSE(head, ptr) \
-	DO_FOR_EACH_REVERSE(head, ptr, __cur##ptr, PTR_ENTRY)
+	DO_FOR_EACH_REVERSE(head, ptr, __cur##ptr, CUR_ENTRY)
 
 #define END_FOR_EACH_PTR_REVERSE(ptr) \
 	DO_END_FOR_EACH_REVERSE(ptr, __cur##ptr)
 
 #define FOR_EACH_PTR_REVERSE_NOTAG(head, ptr) \
-	DO_FOR_EACH_REVERSE(head, ptr, __cur##ptr, PTR_ENTRY_NOTAG)
+	DO_FOR_EACH_REVERSE(head, ptr, __cur##ptr, CUR_ENTRY_NOTAG)
 
 #define END_FOR_EACH_PTR_REVERSE_NOTAG(ptr) END_FOR_EACH_PTR_REVERSE(ptr)
 
-- 
2.13.0

[PATCH 15/34] ptrlist: use iterator API for PREPARE/NEXT_PTR_LIST()

[Luc Van Oostenryck]

---
 ptrlist.h | 26 +++++++++-----------------
 1 file changed, 9 insertions(+), 17 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index 7c8fefe42..32773b378 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -127,25 +127,17 @@ static inline void ptr_cur_init(struct ptr_cur *cur, struct ptr_list *head)
 	do {										\
 		struct ptr_cur __cur;							\
 		CHECK_TYPE(head,ptr);							\
-		DO_INIT(__cur, head);							\
-		if (__cur.h) ptr = CUR_ENTRY(&__cur);					\
-		else ptr = NULL
+		if (!ptr_cur_beg(&__cur, (struct ptr_list *)head) ||			\
+		    !ptr_cur_next(&__cur)) ptr = NULL;					\
+		else ptr = CUR_ENTRY(&__cur);
 
 #define DO_NEXT(ptr, __cur, CUR_ENTRY)							\
-		if (ptr) {								\
-			if (++__cur.n < __cur.l->nr) {					\
-				ptr = CUR_ENTRY(&__cur);				\
-			} else {							\
-				ptr = NULL;						\
-				do							\
-					__cur.l = __cur.l->next;			\
-				while (__cur.l->nr == 0 && __cur.l != __cur.h);		\
-				if (__cur.l != __cur.h) {				\
-					__cur.n = 0;					\
-					ptr = CUR_ENTRY(&__cur);				\
-				}							\
-			}								\
-		}
+	if (ptr) {									\
+		if (ptr_cur_next(&__cur))						\
+			ptr = CUR_ENTRY(&__cur);					\
+		else									\
+			ptr = NULL;							\
+	}
 
 #define DO_RESET(ptr, __cur, CUR_ENTRY)						\
 	do {										\
-- 
2.13.0

[PATCH 16/34] ptrlist: use iterator API for RESET_PTR_LIST()

[Luc Van Oostenryck]

---
 ptrlist.h | 8 +++-----
 1 file changed, 3 insertions(+), 5 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index 32773b378..728f29593 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -140,11 +140,9 @@ static inline void ptr_cur_init(struct ptr_cur *cur, struct ptr_list *head)
 	}
 
 #define DO_RESET(ptr, __cur, CUR_ENTRY)						\
-	do {										\
-		__cur.n = 0;								\
-		__cur.l = __cur.h;							\
-		if (__cur.h) ptr = CUR_ENTRY(&__cur);					\
-	} while (0)
+	if (!ptr_cur_beg(&__cur, (struct ptr_list *)head) ||				\
+	    !ptr_cur_next(&__cur)) ptr = NULL;						\
+	else ptr = CUR_ENTRY(&__cur);
 
 #define DO_FINISH(ptr, __cur)								\
 		(void)(__cur.n); /* Sanity-check nesting */				\
-- 
2.13.0

[PATCH 17/34] ptrlist: use iterator for FOR_EACH_PTR()

[Luc Van Oostenryck]

---
 ptrlist.h | 12 +++++-------
 1 file changed, 5 insertions(+), 7 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index 728f29593..d8b96304f 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -163,15 +163,13 @@ static inline void ptr_cur_init(struct ptr_cur *cur, struct ptr_list *head)
 #define DO_FOR_EACH(head, ptr, __cur, CUR_ENTRY) do {					\
 	struct ptr_cur __cur;								\
 	CHECK_TYPE(head,ptr);								\
-	DO_INIT(__cur, head);								\
-	if (!__cur.h) break;								\
-	do {										\
-		for (__cur.n = 0; __cur.n < __cur.l->nr; __cur.n++) {			\
-			ptr = CUR_ENTRY(&__cur);					\
+	if (!head) break;								\
+	ptr_cur_beg(&__cur, (struct ptr_list *)head);					\
+	while (ptr_cur_next(&__cur)) {							\
+		ptr = CUR_ENTRY(&__cur);
 
 #define DO_END_FOR_EACH(ptr, __cur)							\
-		}									\
-	} while ((__cur.l = __cur.l->next) != __cur.h);					\
+	}										\
 } while (0)
 
 #define DO_FOR_EACH_REVERSE(head, ptr, __cur, CUR_ENTRY) do {				\
-- 
2.13.0

[PATCH 18/34] ptrlist: use iterator for FOR_EACH_PTR_REVERSE()

[Luc Van Oostenryck]

---
 ptrlist.h | 25 +++++++------------------
 1 file changed, 7 insertions(+), 18 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index d8b96304f..c3538a260 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -175,30 +175,19 @@ static inline void ptr_cur_init(struct ptr_cur *cur, struct ptr_list *head)
 #define DO_FOR_EACH_REVERSE(head, ptr, __cur, CUR_ENTRY) do {				\
 	struct ptr_cur __cur;								\
 	CHECK_TYPE(head,ptr);								\
-	DO_INIT(__cur, head);								\
-	if (!__cur.h) break;								\
-	do {										\
-		__cur.l = __cur.l->prev;						\
-		__cur.n = __cur.l->nr;							\
-		while (--__cur.n >= 0) {						\
-			ptr = CUR_ENTRY(&__cur);					\
-
+	if (!head) break;								\
+	ptr_cur_end(&__cur, (struct ptr_list *)head);					\
+	while (ptr_cur_prev(&__cur)) {							\
+		ptr = CUR_ENTRY(&__cur);
 
 #define DO_END_FOR_EACH_REVERSE(ptr, __cur)						\
-		}									\
-	} while (__cur.l != __cur.h);							\
+	}										\
 } while (0)
 
 #define DO_REVERSE(ptr, __cur, new, __newcur, CUR_ENTRY) do {				\
 	struct ptr_cur __newcur = __cur;						\
-	new = ptr;									\
-	goto __inside##new;								\
-	do {										\
-		__newcur.l = __newcur.l->prev;						\
-		__newcur.n = __newcur.l->nr;						\
-	__inside##new:									\
-		while (--__newcur.n >= 0) {						\
-			new = CUR_ENTRY(&__newcur);					\
+	while (ptr_cur_prev(&__newcur)) {						\
+		new = CUR_ENTRY(&__newcur);
 
 #define RECURSE_PTR_REVERSE(ptr, new)							\
 	DO_REVERSE(ptr, __cur##ptr,							\
-- 
2.13.0

[PATCH 19/34] ptrlist: remove unneeded DO_INIT()

[Luc Van Oostenryck]

---
 ptrlist.h | 12 +-----------
 1 file changed, 1 insertion(+), 11 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index c3538a260..0e6d30b99 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -113,18 +113,8 @@ static inline void *last_ptr_list(struct ptr_list *list)
 	return __PTR_STRIP_TAG(ptr_cur_entry(&cur));
 }
 
-static inline void ptr_cur_init(struct ptr_cur *cur, struct ptr_list *head)
-{
-	cur->h = head;
-	cur->l = head;
-	cur->n = 0;
-}
-
-#define DO_INIT(cur, head)	\
-	ptr_cur_init(&cur, (struct ptr_list *) head)

[PATCH 20/34] ptrlist: use the iterator API for DO_INSERT_CURRENT()

[Luc Van Oostenryck]

---
 ptrlist.h | 42 ++++++++++++++++++++++--------------------
 1 file changed, 22 insertions(+), 20 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index 0e6d30b99..ab2b13a3c 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -213,27 +213,29 @@ do {										\
 
 extern void split_ptr_list_head(struct ptr_list *);
 
-#define DO_SPLIT(ptr, __cur) do {							\
-	split_ptr_list_head(__cur.l);							\
-	if (__cur.n >= __cur.l->nr) {							\
-		__cur.n -= __cur.l->nr;							\
-		__cur.l = __cur.l->next;						\
-	};										\
-} while (0)
+static inline void ptr_cur_insert(struct ptr_cur *cur, void *new, void *ptr)
+{
+	void **this, **last;
+
+	if (cur->l->nr == LIST_NODE_NR) {
+		split_ptr_list_head(cur->l);
+		if (cur->n >= cur->l->nr) {
+			cur->n -= cur->l->nr;
+			cur->l = cur->l->next;
+		}
+	}
+	this = cur->l->list + cur->n;
+	last = cur->l->list + cur->l->nr - 1;
+	while (last >= this) {
+		last[1] = last[0];
+		last--;
+	}
+	*this = (new);
+	cur->l->nr++;
+}
 
-#define DO_INSERT_CURRENT(new, ptr, __cur) do {						\
-	void **__this, **__last;							\
-	if (__cur.l->nr == LIST_NODE_NR)						\
-		DO_SPLIT(ptr, __cur);							\
-	__this = __cur.l->list + __cur.n;						\
-	__last = __cur.l->list + __cur.l->nr - 1;					\
-	while (__last >= __this) {							\
-		__last[1] = __last[0];							\
-		__last--;								\
-	}										\
-	*__this = (new);								\
-	__cur.l->nr++;									\
-} while (0)
+#define DO_INSERT_CURRENT(new, ptr, __cur) \
+	ptr_cur_insert(&__cur, new, ptr)
 
 #define INSERT_CURRENT(new, ptr) \
 	DO_INSERT_CURRENT(new, ptr, __cur##ptr)
-- 
2.13.0

[PATCH 21/34] ptrlist: extract ptr_cur_insert from ptrlist.h

[Luc Van Oostenryck]

---
 ptrlist.c | 21 +++++++++++++++++++++
 ptrlist.h | 22 +---------------------
 2 files changed, 22 insertions(+), 21 deletions(-)

diff --git a/ptrlist.c b/ptrlist.c
index 031c53262..03a93db03 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -305,3 +305,24 @@ int ptr_cur_end(struct ptr_cur *cur, struct ptr_list *head)
 	cur->n = prev->nr;
 	return 1;
 }
+
+void ptr_cur_insert(struct ptr_cur *cur, void *new, void *ptr)
+{
+	void **this, **last;
+
+	if (cur->l->nr == LIST_NODE_NR) {
+		split_ptr_list_head(cur->l);
+		if (cur->n >= cur->l->nr) {
+			cur->n -= cur->l->nr;
+			cur->l = cur->l->next;
+		}
+	}
+	this = cur->l->list + cur->n;
+	last = cur->l->list + cur->l->nr - 1;
+	while (last >= this) {
+		last[1] = last[0];
+		last--;
+	}
+	*this = new;
+	cur->l->nr++;
+}
diff --git a/ptrlist.h b/ptrlist.h
index ab2b13a3c..26697c62f 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -55,6 +55,7 @@ int ptr_cur_beg(struct ptr_cur *cur, struct ptr_list *head);
 int ptr_cur_next(struct ptr_cur *cur);
 int ptr_cur_end(struct ptr_cur *cur, struct ptr_list *head);
 int ptr_cur_prev(struct ptr_cur *cur);
+void ptr_cur_insert(struct ptr_cur *cur, void *new, void *ptr);
 
 /*
  * Hey, who said that you can't do overloading in C?
@@ -213,27 +214,6 @@ do {										\
 
 extern void split_ptr_list_head(struct ptr_list *);
 
-static inline void ptr_cur_insert(struct ptr_cur *cur, void *new, void *ptr)
-{
-	void **this, **last;
-
-	if (cur->l->nr == LIST_NODE_NR) {
-		split_ptr_list_head(cur->l);
-		if (cur->n >= cur->l->nr) {
-			cur->n -= cur->l->nr;
-			cur->l = cur->l->next;
-		}
-	}
-	this = cur->l->list + cur->n;
-	last = cur->l->list + cur->l->nr - 1;
-	while (last >= this) {
-		last[1] = last[0];
-		last--;
-	}
-	*this = (new);
-	cur->l->nr++;
-}

[PATCH 22/34] ptrlist: simplify ptr_cur_insert()

[Luc Van Oostenryck]

---
 ptrlist.c | 17 +++++++++--------
 1 file changed, 9 insertions(+), 8 deletions(-)

diff --git a/ptrlist.c b/ptrlist.c
index 03a93db03..c7d049616 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -308,21 +308,22 @@ int ptr_cur_end(struct ptr_cur *cur, struct ptr_list *head)
 
 void ptr_cur_insert(struct ptr_cur *cur, void *new, void *ptr)
 {
+	struct ptr_list *curl = cur->l;
 	void **this, **last;
 
-	if (cur->l->nr == LIST_NODE_NR) {
-		split_ptr_list_head(cur->l);
-		if (cur->n >= cur->l->nr) {
-			cur->n -= cur->l->nr;
-			cur->l = cur->l->next;
+	if (curl->nr == LIST_NODE_NR) {
+		split_ptr_list_head(curl);
+		if (cur->n >= curl->nr) {
+			cur->n -= curl->nr;
+			curl = curl->next;
 		}
 	}
-	this = cur->l->list + cur->n;
-	last = cur->l->list + cur->l->nr - 1;
+	this = curl->list + cur->n;
+	last = curl->list + curl->nr - 1;
 	while (last >= this) {
 		last[1] = last[0];
 		last--;
 	}
 	*this = new;
-	cur->l->nr++;
+	curl->nr++;
 }
-- 
2.13.0

[PATCH 23/34] ptrlist: use the iterator API for DO_DELETE_CURRENT()

[Luc Van Oostenryck]

---
 ptrlist.h | 26 ++++++++++++++++----------
 1 file changed, 16 insertions(+), 10 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index 26697c62f..c27a68f38 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -220,16 +220,22 @@ extern void split_ptr_list_head(struct ptr_list *);
 #define INSERT_CURRENT(new, ptr) \
 	DO_INSERT_CURRENT(new, ptr, __cur##ptr)
 
-#define DO_DELETE_CURRENT(ptr, __cur) do {						\
-	void **__this = __cur.l->list + __cur.n;					\
-	void **__last = __cur.l->list + __cur.l->nr - 1;				\
-	while (__this < __last) {							\
-		__this[0] = __this[1];							\
-		__this++;								\
-	}										\
-	*__this = (void *)0xf0f0f0f0;							\
-	__cur.l->nr--; __cur.n--;							\
-} while (0)
+static inline void ptr_cur_delete(struct ptr_cur *cur, void *ptr)
+{
+	void **this = cur->l->list + cur->n;
+	void **last = cur->l->list + cur->l->nr - 1;
+
+	while (this < last) {
+		this[0] = this[1];
+		this++;
+	}
+	*this = (void *)0xf0f0f0f0;
+	cur->l->nr--;
+	cur->n--;
+}
+
+#define DO_DELETE_CURRENT(ptr, __cur) \
+	ptr_cur_delete(&__cur, ptr)
 
 #define DELETE_CURRENT_PTR(ptr) \
 	DO_DELETE_CURRENT(ptr, __cur##ptr)
-- 
2.13.0

[PATCH 24/34] ptrlist: extract prt_cur_delete() from ptrlist.h

[Luc Van Oostenryck]

---
 ptrlist.c | 15 +++++++++++++++
 ptrlist.h | 15 +--------------
 2 files changed, 16 insertions(+), 14 deletions(-)

diff --git a/ptrlist.c b/ptrlist.c
index c7d049616..c532dbaac 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -327,3 +327,18 @@ void ptr_cur_insert(struct ptr_cur *cur, void *new, void *ptr)
 	*this = new;
 	curl->nr++;
 }
+
+void ptr_cur_delete(struct ptr_cur *cur, void *ptr)
+{
+	struct ptr_list *curl = cur->l;
+	void **this = curl->list + cur->n;
+	void **last = curl->list + curl->nr - 1;
+
+	while (this < last) {
+		this[0] = this[1];
+		this++;
+	}
+	*this = (void *)0xf0f0f0f0;
+	curl->nr--;
+	cur->n--;
+}
diff --git a/ptrlist.h b/ptrlist.h
index c27a68f38..c1d53632d 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -56,6 +56,7 @@ int ptr_cur_next(struct ptr_cur *cur);
 int ptr_cur_end(struct ptr_cur *cur, struct ptr_list *head);
 int ptr_cur_prev(struct ptr_cur *cur);
 void ptr_cur_insert(struct ptr_cur *cur, void *new, void *ptr);
+void ptr_cur_delete(struct ptr_cur *cur, void *ptr);
 
 /*
  * Hey, who said that you can't do overloading in C?
@@ -220,20 +221,6 @@ extern void split_ptr_list_head(struct ptr_list *);
 #define INSERT_CURRENT(new, ptr) \
 	DO_INSERT_CURRENT(new, ptr, __cur##ptr)
 
-static inline void ptr_cur_delete(struct ptr_cur *cur, void *ptr)
-{
-	void **this = cur->l->list + cur->n;
-	void **last = cur->l->list + cur->l->nr - 1;
-
-	while (this < last) {
-		this[0] = this[1];
-		this++;
-	}
-	*this = (void *)0xf0f0f0f0;
-	cur->l->nr--;
-	cur->n--;
-}

[PATCH 25/34] ptrlist: let delete_ptr_list() use the iterator API

[Luc Van Oostenryck]

---
 ptrlist.c | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

diff --git a/ptrlist.c b/ptrlist.c
index c532dbaac..95ff319db 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -150,15 +150,19 @@ void **__add_ptr_list(struct ptr_list **listp, void *ptr, unsigned long tag)
 
 int delete_ptr_list_entry(struct ptr_list **list, void *entry, int count)
 {
-	void *ptr;
+	struct ptr_cur cur;
 
-	FOR_EACH_PTR(*list, ptr) {
+	if (!ptr_cur_beg(&cur, *list))
+                goto out;
+
+	while (ptr_cur_next(&cur)) {
+		void *ptr = cur.l->list[cur.n];
 		if (ptr == entry) {
-			DELETE_CURRENT_PTR(ptr);
+			ptr_cur_delete(&cur, ptr);
 			if (!--count)
 				goto out;
 		}
-	} END_FOR_EACH_PTR(ptr);
+	}
 	assert(count <= 0);
 out:
 	pack_ptr_list(list);
-- 
2.13.0

[PATCH 26/34] ptrlist: let replace_ptr_list_entry() use the iterator API

[Luc Van Oostenryck]

---
 ptrlist.c | 14 +++++++++-----
 1 file changed, 9 insertions(+), 5 deletions(-)

diff --git a/ptrlist.c b/ptrlist.c
index 95ff319db..cdc4ae4b0 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -171,15 +171,19 @@ out:
 
 int replace_ptr_list_entry(struct ptr_list **list, void *old_ptr, void *new_ptr, int count)
 {
-	void *ptr;
+	struct ptr_cur cur;
+
+	if (!ptr_cur_beg(&cur, *list))
+                goto out;
 
-	FOR_EACH_PTR(*list, ptr) {
-		if (ptr==old_ptr) {
-			REPLACE_CURRENT_PTR(ptr, new_ptr);
+	while (ptr_cur_next(&cur)) {
+		void **this = &cur.l->list[cur.n];
+		if (*this == old_ptr) {
+			*this = new_ptr;
 			if (!--count)
 				goto out;
 		}
-	}END_FOR_EACH_PTR(ptr);
+	}
 	assert(count <= 0);
 out:
 	return count;
-- 
2.13.0

[PATCH 27/34] ptrlist: let concat_ptr_list() use the iterator API

[Luc Van Oostenryck]

---
 ptrlist.c | 11 +++++++----
 1 file changed, 7 insertions(+), 4 deletions(-)

diff --git a/ptrlist.c b/ptrlist.c
index cdc4ae4b0..b4fb3fd6e 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -232,10 +232,13 @@ void * delete_ptr_list_last(struct ptr_list **head)
 
 void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
 {
-	void *entry;
-	FOR_EACH_PTR(a, entry) {
-		add_ptr_list(b, entry);
-	} END_FOR_EACH_PTR(entry);
+	struct ptr_cur cur;
+
+	if (!ptr_cur_beg(&cur, a))
+                return;
+
+	while (ptr_cur_next(&cur))
+		__add_ptr_list(b, ptr_cur_entry(&cur), 0);
 }
 
 void __free_ptr_list(struct ptr_list **listp)
-- 
2.13.0

[PATCH 28/34] ptrlist: let undo_ptr_list_last() use the iterator API

[Luc Van Oostenryck]

---
 ptrlist.c | 23 +++++++++--------------
 1 file changed, 9 insertions(+), 14 deletions(-)

diff --git a/ptrlist.c b/ptrlist.c
index b4fb3fd6e..bae5512f3 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -192,22 +192,17 @@ out:
 /* This removes the last entry, but doesn't pack the ptr list */
 void * undo_ptr_list_last(struct ptr_list **head)
 {
-	struct ptr_list *last, *first = *head;
+	struct ptr_cur cur;
+	void *ptr;
 
-	if (!first)
+	if (!ptr_cur_end(&cur, *head) || !ptr_cur_prev(&cur))
 		return NULL;
-	last = first;
-	do {
-		last = last->prev;
-		if (last->nr) {
-			void *ptr;
-			int nr = --last->nr;
-			ptr = last->list[nr];
-			last->list[nr] = (void *)0xf1f1f1f1;
-			return ptr;
-		}
-	} while (last != first);
-	return NULL;
+
+	ptr = cur.l->list[cur.n];
+	cur.l->list[cur.n--] = (void *)0xf1f1f1f1;
+	cur.l->nr--;
+
+	return ptr;
 }
 
 void * delete_ptr_list_last(struct ptr_list **head)
-- 
2.13.0

[PATCH 29/34] ptrlist: let delete_ptr_list_last() use the iterator API

[Luc Van Oostenryck]

---
 ptrlist.c | 23 ++++++++++++-----------
 1 file changed, 12 insertions(+), 11 deletions(-)

diff --git a/ptrlist.c b/ptrlist.c
index bae5512f3..1957baf1f 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -207,20 +207,21 @@ void * undo_ptr_list_last(struct ptr_list **head)
 
 void * delete_ptr_list_last(struct ptr_list **head)
 {
-	void *ptr = NULL;
-	struct ptr_list *last, *first = *head;
+	struct ptr_cur cur;
+	void *ptr;
 
-	if (!first)
+	if (!ptr_cur_end(&cur, *head) || !ptr_cur_prev(&cur))
 		return NULL;
-	last = first->prev;
-	if (last->nr)
-		ptr = last->list[--last->nr];
-	if (last->nr <=0) {
-		first->prev = last->prev;
-		last->prev->next = first;
-		if (last == first)
+
+	ptr = ptr_cur_entry(&cur);
+	if (--cur.l->nr == 0) {
+		if (cur.l == cur.h)
 			*head = NULL;
-		__free_ptrlist(last);
+		else {
+			cur.h->prev = cur.l->prev;
+			cur.l->prev->next = cur.h;
+		}
+		__free_ptrlist(cur.l);
 	}
 	return ptr;
 }
-- 
2.13.0

[PATCH 30/34] ptrlist: simplify common case for __add_ptr_list()

[Luc Van Oostenryck]

The vast majority of pointer list use non-tagged pointer,
the core library and the sparse tool doesn't use them
(in fact only 'example.c' use them).

The current functions to add a pointer to a ptr_list suppose
that all pointers are tagged and in the case of non-word-aligned
pointers (strings) it create a a fake tag consiting of the last
2 bits.

This patch siplify the situation by separating the common case
(non-tagged or non-word-aligned pointers) which ignore the presence
of a tag and make another version which check and combien the tag
with the pointer before calling the common case.
---
 ptrlist.c | 30 +++++++++++++++++++++++-------
 ptrlist.h | 11 +++++------
 2 files changed, 28 insertions(+), 13 deletions(-)

diff --git a/ptrlist.c b/ptrlist.c
index 1957baf1f..95447eaea 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -114,18 +114,19 @@ void split_ptr_list_head(struct ptr_list *head)
 	memset(head->list + old, 0xf0, nr * sizeof(void *));
 }
 
-void **__add_ptr_list(struct ptr_list **listp, void *ptr, unsigned long tag)
+/*
+ * Add 'ptr' to 'listp'.
+ * 'ptr' can be a tagged pointer, a non-tagged one or a
+ * non-word-aligned one, it doesn't matter.
+ * Returns the address where 'ptr' was stored.
+ */
+void **__add_ptr_list(struct ptr_list **listp, void *ptr)
 {
 	struct ptr_list *list = *listp;
 	struct ptr_list *last = NULL; /* gcc complains needlessly */
 	void **ret;
 	int nr;
 
-	/* The low two bits are reserved for tags */
-	assert((3 & (unsigned long)ptr) == 0);
-	assert((~3 & tag) == 0);
-	ptr = (void *)(tag | (unsigned long)ptr);
-
 	if (!list || (nr = (last = list->prev)->nr) >= LIST_NODE_NR) {
 		struct ptr_list *newlist = __alloc_ptrlist(0);
 		if (!list) {
@@ -148,6 +149,21 @@ void **__add_ptr_list(struct ptr_list **listp, void *ptr, unsigned long tag)
 	return ret;
 }
 
+/*
+ * Add 'ptr' to 'listp' and tag it with 'tag'
+ * 'ptr' must be a non-tagged word-aligned pointer.
+ * Returns the address where 'ptr' was stored.
+ */
+void **__add_ptr_list_tag(struct ptr_list **listp, void *ptr, unsigned long tag)
+{
+	/* The low two bits are reserved for tags */
+	assert((3 & (unsigned long)ptr) == 0);
+	assert((~3 & tag) == 0);
+	ptr = (void *)(tag | (unsigned long)ptr);
+
+	return __add_ptr_list(listp, ptr);
+}
+
 int delete_ptr_list_entry(struct ptr_list **list, void *entry, int count)
 {
 	struct ptr_cur cur;
@@ -234,7 +250,7 @@ void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
                 return;
 
 	while (ptr_cur_next(&cur))
-		__add_ptr_list(b, ptr_cur_entry(&cur), 0);
+		__add_ptr_list(b, ptr_cur_entry(&cur));
 }
 
 void __free_ptr_list(struct ptr_list **listp)
diff --git a/ptrlist.h b/ptrlist.h
index c1d53632d..9e16adb36 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -45,7 +45,8 @@ int delete_ptr_list_entry(struct ptr_list **, void *, int);
 int replace_ptr_list_entry(struct ptr_list **, void *old, void *new, int);
 extern void sort_list(struct ptr_list **, int (*)(const void *, const void *));
 
-extern void **__add_ptr_list(struct ptr_list **, void *, unsigned long);
+extern void **__add_ptr_list(struct ptr_list **, void *);
+extern void **__add_ptr_list_tag(struct ptr_list **, void *, unsigned long);
 extern void concat_ptr_list(struct ptr_list *a, struct ptr_list **b);
 extern void __free_ptr_list(struct ptr_list **);
 extern int ptr_list_size(struct ptr_list *);
@@ -65,13 +66,11 @@ void ptr_cur_delete(struct ptr_cur *cur, void *ptr);
  * extensions..
  */
 #define add_ptr_list_tag(list,entry,tag) \
-	MKTYPE(*(list), (CHECK_TYPE(*(list),(entry)),__add_ptr_list((struct ptr_list **)(list), (entry), (tag))))
+	MKTYPE(*(list), (CHECK_TYPE(*(list),(entry)),__add_ptr_list_tag((struct ptr_list **)(list), (entry), (tag))))
 #define add_ptr_list_notag(list,entry)										\
-	MKTYPE(*(list), (CHECK_TYPE(*(list),(entry)),__add_ptr_list((struct ptr_list **)(list),			\
-								    (void *)((unsigned long)(entry) & ~3UL), 	\
-								    (unsigned long)(entry) & 3)))
+	MKTYPE(*(list), (CHECK_TYPE(*(list),(entry)),__add_ptr_list((struct ptr_list **)(list),	 (entry))))
 #define add_ptr_list(list,entry) \
-	add_ptr_list_tag(list,entry,0)
+	add_ptr_list_notag(list,entry)
 #define free_ptr_list(list) \
 	do { VRFY_PTR_LIST(*(list)); __free_ptr_list((struct ptr_list **)(list)); } while (0)
 
-- 
2.13.0

[PATCH 31/34] ptrlist: explicitely tagged

[Luc Van Oostenryck]

---
 example.c | 20 ++++++++++----------
 ptrlist.h |  4 ++++
 2 files changed, 14 insertions(+), 10 deletions(-)

diff --git a/example.c b/example.c
index 691e0f97c..41ee712fe 100644
--- a/example.c
+++ b/example.c
@@ -394,7 +394,7 @@ static void flush_reg(struct bb_state *state, struct hardreg *reg)
 		return;
 	reg->dead = 0;
 	reg->used = 1;
-	FOR_EACH_PTR(reg->contains, pseudo) {
+	FOR_EACH_TAGGED_PTR(reg->contains, pseudo) {
 		if (CURRENT_TAG(pseudo) & TAG_DEAD)
 			continue;
 		if (!(CURRENT_TAG(pseudo) & TAG_DIRTY))
@@ -447,7 +447,7 @@ static void mark_reg_dead(struct bb_state *state, pseudo_t pseudo, struct hardre
 {
 	pseudo_t p;
 
-	FOR_EACH_PTR(reg->contains, p) {
+	FOR_EACH_TAGGED_PTR(reg->contains, p) {
 		if (p != pseudo)
 			continue;
 		if (CURRENT_TAG(p) & TAG_DEAD)
@@ -532,7 +532,7 @@ static struct hardreg *find_in_reg(struct bb_state *state, pseudo_t pseudo)
 		pseudo_t p;
 
 		reg = hardregs + i;
-		FOR_EACH_PTR(reg->contains, p) {
+		FOR_EACH_TAGGED_PTR(reg->contains, p) {
 			if (p == pseudo) {
 				last_reg = i;
 				output_comment(state, "found pseudo %s in reg %s (busy=%d)", show_pseudo(pseudo), reg->name, reg->busy);
@@ -872,7 +872,7 @@ static void kill_dead_reg(struct hardreg *reg)
 	if (reg->dead) {
 		pseudo_t p;
 		
-		FOR_EACH_PTR(reg->contains, p) {
+		FOR_EACH_TAGGED_PTR(reg->contains, p) {
 			if (CURRENT_TAG(p) & TAG_DEAD) {
 				DELETE_CURRENT_PTR(p);
 				reg->dead--;
@@ -912,7 +912,7 @@ static void generate_binop(struct bb_state *state, struct instruction *insn)
 static int is_dead_reg(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
 {
 	pseudo_t p;
-	FOR_EACH_PTR(reg->contains, p) {
+	FOR_EACH_TAGGED_PTR(reg->contains, p) {
 		if (p == pseudo)
 			return CURRENT_TAG(p) & TAG_DEAD;
 	} END_FOR_EACH_PTR(p);
@@ -1007,7 +1007,7 @@ static void kill_pseudo(struct bb_state *state, pseudo_t pseudo)
 		pseudo_t p;
 
 		reg = hardregs + i;
-		FOR_EACH_PTR(reg->contains, p) {
+		FOR_EACH_TAGGED_PTR(reg->contains, p) {
 			if (p != pseudo)
 				continue;
 			if (CURRENT_TAG(p) & TAG_DEAD)
@@ -1544,7 +1544,7 @@ static void fill_output(struct bb_state *state, pseudo_t pseudo, struct storage
 		struct hardreg *reg = hardregs + i;
 		pseudo_t p;
 
-		FOR_EACH_PTR(reg->contains, p) {
+		FOR_EACH_TAGGED_PTR(reg->contains, p) {
 			if (p == pseudo) {
 				write_reg_to_storage(state, reg, pseudo, out);
 				return;
@@ -1652,7 +1652,7 @@ static void generate_output_storage(struct bb_state *state)
 			int flushme = 0;
 
 			reg->busy = REG_FIXED;
-			FOR_EACH_PTR(reg->contains, p) {
+			FOR_EACH_TAGGED_PTR(reg->contains, p) {
 				if (p == entry->pseudo) {
 					flushme = -100;
 					continue;
@@ -1949,9 +1949,9 @@ int main(int argc, char **argv)
 
 	compile(sparse_initialize(argc, argv, &filelist));
 	dbg_dead = 1;
-	FOR_EACH_PTR_NOTAG(filelist, file) {
+	FOR_EACH_PTR(filelist, file) {
 		compile(sparse(file));
-	} END_FOR_EACH_PTR_NOTAG(file);
+	} END_FOR_EACH_PTR(file);
 	return 0;
 }
 
diff --git a/ptrlist.h b/ptrlist.h
index 9e16adb36..1a0d7225c 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -190,6 +190,10 @@ do {										\
 #define FOR_EACH_PTR(head, ptr) \
 	DO_FOR_EACH(head, ptr, __cur##ptr, CUR_ENTRY)
 
+#define FOR_EACH_TAGGED_PTR(head, ptr) \
+	FOR_EACH_PTR(head, ptr) \
+	ptr = __PTR_STRIP_TAG(ptr);
+
 #define END_FOR_EACH_PTR(ptr) \
 	DO_END_FOR_EACH(ptr, __cur##ptr)
 
-- 
2.13.0

[PATCH 32/34] ptrlist: tag/notag common case

[Luc Van Oostenryck]

---
 ptrlist.h | 43 +++++++++++++++++++++----------------------
 1 file changed, 21 insertions(+), 22 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index 1a0d7225c..1796f8466 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -84,10 +84,9 @@ static inline void *ptr_cur_entry(const struct ptr_cur *cur)
 	return __ptr_entry(cur->l, cur->n);
 }
 
-#define PTR_ENTRY_NOTAG(h,i)	__ptr_entry(h, i)
 #define __PTR_STRIP_TAG(ptr)	(void *)(~3UL & (unsigned long)(ptr))
 #define __PTR_KEEP_TAG(ptr)	(ptr)
-#define PTR_ENTRY(h,i)		__PTR_STRIP_TAG(PTR_ENTRY_NOTAG(h,i))
+#define PTR_ENTRY(h,i)		__PTR_STRIP_TAG(__ptr_entry(h,i))
 #define CUR_ENTRY_NOTAG(cur)	ptr_cur_entry(cur)
 #define CUR_ENTRY(cur)		__PTR_STRIP_TAG(CUR_ENTRY_NOTAG(cur))
 
@@ -114,81 +113,81 @@ static inline void *last_ptr_list(struct ptr_list *list)
 	return __PTR_STRIP_TAG(ptr_cur_entry(&cur));
 }
 
-#define DO_PREPARE(head, ptr, __cur, CUR_ENTRY)						\
+#define DO_PREPARE(head, ptr, __cur)						\
 do {										\
 		struct ptr_cur __cur;							\
 		CHECK_TYPE(head,ptr);							\
 		if (!ptr_cur_beg(&__cur, (struct ptr_list *)head) ||			\
 		    !ptr_cur_next(&__cur)) ptr = NULL;					\
-		else ptr = CUR_ENTRY(&__cur);
+		else ptr = ptr_cur_entry(&__cur);
 
-#define DO_NEXT(ptr, __cur, CUR_ENTRY)							\
+#define DO_NEXT(ptr, __cur)							\
 	if (ptr) {									\
 		if (ptr_cur_next(&__cur))						\
-			ptr = CUR_ENTRY(&__cur);					\
+			ptr = ptr_cur_entry(&__cur);					\
 		else									\
 			ptr = NULL;							\
 	}
 
-#define DO_RESET(ptr, __cur, CUR_ENTRY)						\
+#define DO_RESET(ptr, __cur)								\
 	if (!ptr_cur_beg(&__cur, (struct ptr_list *)head) ||				\
 	    !ptr_cur_next(&__cur)) ptr = NULL;						\
-	else ptr = CUR_ENTRY(&__cur);
+	else ptr = ptr_cur_entry(&__cur);
 
 #define DO_FINISH(ptr, __cur)								\
 		(void)(__cur.n); /* Sanity-check nesting */				\
 	} while (0)
 
 #define PREPARE_PTR_LIST(head, ptr) \
-	DO_PREPARE(head, ptr, __cur##ptr, CUR_ENTRY)
+	DO_PREPARE(head, ptr, __cur##ptr)
 
 #define NEXT_PTR_LIST(ptr) \
-	DO_NEXT(ptr, __cur##ptr, CUR_ENTRY)
+	DO_NEXT(ptr, __cur##ptr)
 
 #define RESET_PTR_LIST(ptr) \
-	DO_RESET(ptr, __cur##ptr, CUR_ENTRY)
+	DO_RESET(ptr, __cur##ptr)
 
 #define FINISH_PTR_LIST(ptr) \
 	DO_FINISH(ptr, __cur##ptr)
 
-#define DO_FOR_EACH(head, ptr, __cur, CUR_ENTRY) do {					\
+#define DO_FOR_EACH(head, ptr, __cur) do {						\
 	struct ptr_cur __cur;								\
 	CHECK_TYPE(head,ptr);								\
 	if (!head) break;								\
 	ptr_cur_beg(&__cur, (struct ptr_list *)head);					\
 	while (ptr_cur_next(&__cur)) {							\
-		ptr = CUR_ENTRY(&__cur);
+		ptr = ptr_cur_entry(&__cur);
 
 #define DO_END_FOR_EACH(ptr, __cur)							\
 	}										\
 } while (0)
 
-#define DO_FOR_EACH_REVERSE(head, ptr, __cur, CUR_ENTRY) do {				\
+#define DO_FOR_EACH_REVERSE(head, ptr, __cur) do {					\
 	struct ptr_cur __cur;								\
 	CHECK_TYPE(head,ptr);								\
 	if (!head) break;								\
 	ptr_cur_end(&__cur, (struct ptr_list *)head);					\
 	while (ptr_cur_prev(&__cur)) {							\
-		ptr = CUR_ENTRY(&__cur);
+		ptr = ptr_cur_entry(&__cur);
 
 #define DO_END_FOR_EACH_REVERSE(ptr, __cur)						\
 	}										\
 } while (0)
 
-#define DO_REVERSE(ptr, __cur, new, __newcur, CUR_ENTRY) do {				\
+#define DO_REVERSE(ptr, __cur, new, __newcur) do {					\
 	struct ptr_cur __newcur = __cur;						\
 	while (ptr_cur_prev(&__newcur)) {						\
-		new = CUR_ENTRY(&__newcur);
+		new = ptr_cur_entry(&__newcur);
 
 #define RECURSE_PTR_REVERSE(ptr, new)							\
 	DO_REVERSE(ptr, __cur##ptr,							\
-		   new, __cur##new, CUR_ENTRY)
+		   new, __cur##new)
 
 #define DO_THIS_ADDRESS(ptr, __cur)							\
 	((__typeof__(&(ptr))) (__cur.l->list + __cur.n))
 
 #define FOR_EACH_PTR(head, ptr) \
-	DO_FOR_EACH(head, ptr, __cur##ptr, CUR_ENTRY)
+	DO_FOR_EACH(head, ptr, __cur##ptr)
 
 #define FOR_EACH_TAGGED_PTR(head, ptr) \
 	FOR_EACH_PTR(head, ptr) \
@@ -198,18 +197,18 @@ do {										\
 	DO_END_FOR_EACH(ptr, __cur##ptr)
 
 #define FOR_EACH_PTR_NOTAG(head, ptr) \
-	DO_FOR_EACH(head, ptr, __cur##ptr, CUR_ENTRY_NOTAG)
+	FOR_EACH_PTR(head, ptr)
 
 #define END_FOR_EACH_PTR_NOTAG(ptr) END_FOR_EACH_PTR(ptr)
 
 #define FOR_EACH_PTR_REVERSE(head, ptr) \
-	DO_FOR_EACH_REVERSE(head, ptr, __cur##ptr, CUR_ENTRY)
+	DO_FOR_EACH_REVERSE(head, ptr, __cur##ptr)
 
 #define END_FOR_EACH_PTR_REVERSE(ptr) \
 	DO_END_FOR_EACH_REVERSE(ptr, __cur##ptr)
 
 #define FOR_EACH_PTR_REVERSE_NOTAG(head, ptr) \
-	DO_FOR_EACH_REVERSE(head, ptr, __cur##ptr, CUR_ENTRY_NOTAG)
+	FOR_EACH_REVERSE(head, ptr)
 
 #define END_FOR_EACH_PTR_REVERSE_NOTAG(ptr) END_FOR_EACH_PTR_REVERSE(ptr)
 
-- 
2.13.0

[PATCH 33/34] ptrlist: drop the now unneeded _NOTAG versions

[Luc Van Oostenryck]

---
 c2xml.c          |  4 ++--
 compile.c        |  4 ++--
 ctags.c          |  4 ++--
 graph.c          |  8 ++++----
 obfuscate.c      |  4 ++--
 ptrlist.h        | 10 ----------
 sparse-llvm.c    |  4 ++--
 sparse.c         |  4 ++--
 test-dissect.c   |  4 ++--
 test-inspect.c   |  4 ++--
 test-lexing.c    |  4 ++--
 test-linearize.c |  4 ++--
 test-parsing.c   |  4 ++--
 test-unssa.c     |  4 ++--
 14 files changed, 28 insertions(+), 38 deletions(-)

diff --git a/c2xml.c b/c2xml.c
index c45d5818a..1a24c3a81 100644
--- a/c2xml.c
+++ b/c2xml.c
@@ -318,12 +318,12 @@ int main(int argc, char **argv)
 */
 	symlist = sparse_initialize(argc, argv, &filelist);
 
-	FOR_EACH_PTR_NOTAG(filelist, file) {
+	FOR_EACH_PTR(filelist, file) {
 		examine_symbol_list(file, symlist);
 		sparse_keep_tokens(file);
 		examine_symbol_list(file, file_scope->symbols);
 		examine_symbol_list(file, global_scope->symbols);
-	} END_FOR_EACH_PTR_NOTAG(file);
+	} END_FOR_EACH_PTR(file);
 
 
 	xmlSaveFormatFileEnc("-", doc, "UTF-8", 1);
diff --git a/compile.c b/compile.c
index eeb996abd..7c16d5b55 100644
--- a/compile.c
+++ b/compile.c
@@ -59,7 +59,7 @@ int main(int argc, char **argv)
 	bits_in_bool = 8;
 
 	clean_up_symbols(sparse_initialize(argc, argv, &filelist));
-	FOR_EACH_PTR_NOTAG(filelist, file) {
+	FOR_EACH_PTR(filelist, file) {
 		struct symbol_list *list;
 		const char *basename = strrchr(file, '/');
 		basename = basename ?  basename+1 : file;
@@ -70,7 +70,7 @@ int main(int argc, char **argv)
 		emit_unit_begin(basename);
 		clean_up_symbols(list);
 		emit_unit_end();
-	} END_FOR_EACH_PTR_NOTAG(file);
+	} END_FOR_EACH_PTR(file);
 
 #if 0
 	// And show the allocation statistics
diff --git a/ctags.c b/ctags.c
index 9ec6b3c37..6cf8d29be 100644
--- a/ctags.c
+++ b/ctags.c
@@ -216,10 +216,10 @@ int main(int argc, char **argv)
 	char *file;
 
 	examine_symbol_list(sparse_initialize(argc, argv, &filelist));
-	FOR_EACH_PTR_NOTAG(filelist, file) {
+	FOR_EACH_PTR(filelist, file) {
 		sparse(file);
 		examine_symbol_list(file_scope->symbols);
-	} END_FOR_EACH_PTR_NOTAG(file);
+	} END_FOR_EACH_PTR(file);
 	examine_symbol_list(global_scope->symbols);
 	sort_list((struct ptr_list **)&taglist, cmp_sym);
 	show_tags(taglist);
diff --git a/graph.c b/graph.c
index 8cbc22027..4b7ca489b 100644
--- a/graph.c
+++ b/graph.c
@@ -172,7 +172,7 @@ int main(int argc, char **argv)
 
 	/* Linearize all symbols, graph internal basic block
 	 * structures and intra-file calls */
-	FOR_EACH_PTR_NOTAG(filelist, file) {
+	FOR_EACH_PTR(filelist, file) {
 
 		fsyms = sparse(file);
 		concat_symbol_list(fsyms, &all_syms);
@@ -187,15 +187,15 @@ int main(int argc, char **argv)
 				graph_ep(sym->ep);
 				graph_calls(sym->ep, 1);
 			}
-		} END_FOR_EACH_PTR_NOTAG(sym);
+		} END_FOR_EACH_PTR(sym);
 
-	} END_FOR_EACH_PTR_NOTAG(file);
+	} END_FOR_EACH_PTR(file);
 
 	/* Graph inter-file calls */
 	FOR_EACH_PTR(all_syms, sym) {
 		if (sym->ep)
 			graph_calls(sym->ep, 0);
-	} END_FOR_EACH_PTR_NOTAG(sym);
+	} END_FOR_EACH_PTR(sym);
 
 	printf("}\n");
 	return 0;
diff --git a/obfuscate.c b/obfuscate.c
index 18cbd0eef..998eda643 100644
--- a/obfuscate.c
+++ b/obfuscate.c
@@ -69,8 +69,8 @@ int main(int argc, char **argv)
 	char *file;
 
 	emit_symbol_list(sparse_initialize(argc, argv, &filelist));
-	FOR_EACH_PTR_NOTAG(filelist, file) {
+	FOR_EACH_PTR(filelist, file) {
 		emit_symbol_list(sparse(file));
-	} END_FOR_EACH_PTR_NOTAG(file);
+	} END_FOR_EACH_PTR(file);
 	return 0;
 }
diff --git a/ptrlist.h b/ptrlist.h
index 1796f8466..263e68d01 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -196,22 +196,12 @@ do {										\
 #define END_FOR_EACH_PTR(ptr) \
 	DO_END_FOR_EACH(ptr, __cur##ptr)
 
-#define FOR_EACH_PTR_NOTAG(head, ptr) \
-	FOR_EACH_PTR(head, ptr)
-
-#define END_FOR_EACH_PTR_NOTAG(ptr) END_FOR_EACH_PTR(ptr)
-
 #define FOR_EACH_PTR_REVERSE(head, ptr) \
 	DO_FOR_EACH_REVERSE(head, ptr, __cur##ptr)
 
 #define END_FOR_EACH_PTR_REVERSE(ptr) \
 	DO_END_FOR_EACH_REVERSE(ptr, __cur##ptr)
 
-#define FOR_EACH_PTR_REVERSE_NOTAG(head, ptr) \
-	FOR_EACH_REVERSE(head, ptr)
-
-#define END_FOR_EACH_PTR_REVERSE_NOTAG(ptr) END_FOR_EACH_PTR_REVERSE(ptr)
-
 #define THIS_ADDRESS(ptr) \
 	DO_THIS_ADDRESS(ptr, __cur##ptr)
 
diff --git a/sparse-llvm.c b/sparse-llvm.c
index 29fb65f15..447a97977 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -1153,12 +1153,12 @@ int main(int argc, char **argv)
 
 	/* need ->phi_users */
 	dbg_dead = 1;
-	FOR_EACH_PTR_NOTAG(filelist, file) {
+	FOR_EACH_PTR(filelist, file) {
 		symlist = sparse(file);
 		if (die_if_error)
 			return 1;
 		compile(module, symlist);
-	} END_FOR_EACH_PTR_NOTAG(file);
+	} END_FOR_EACH_PTR(file);
 
 	LLVMVerifyModule(module, LLVMPrintMessageAction, NULL);
 
diff --git a/sparse.c b/sparse.c
index bceacd94e..0b074a063 100644
--- a/sparse.c
+++ b/sparse.c
@@ -299,9 +299,9 @@ int main(int argc, char **argv)
 
 	// Expand, linearize and show it.
 	check_symbols(sparse_initialize(argc, argv, &filelist));
-	FOR_EACH_PTR_NOTAG(filelist, file) {
+	FOR_EACH_PTR(filelist, file) {
 		check_symbols(sparse(file));
-	} END_FOR_EACH_PTR_NOTAG(file);
+	} END_FOR_EACH_PTR(file);
 
 	report_stats();
 	return 0;
diff --git a/test-dissect.c b/test-dissect.c
index 862318f81..266148be0 100644
--- a/test-dissect.c
+++ b/test-dissect.c
@@ -88,10 +88,10 @@ int main(int argc, char **argv)
 
 	sparse_initialize(argc, argv, &filelist);
 
-	FOR_EACH_PTR_NOTAG(filelist, file) {
+	FOR_EACH_PTR(filelist, file) {
 		dotc_stream = input_stream_nr;
 		dissect(__sparse(file), &reporter);
-	} END_FOR_EACH_PTR_NOTAG(file);
+	} END_FOR_EACH_PTR(file);
 
 	return 0;
 }
diff --git a/test-inspect.c b/test-inspect.c
index e437e1124..63754cb3c 100644
--- a/test-inspect.c
+++ b/test-inspect.c
@@ -32,11 +32,11 @@ int main(int argc, char **argv)
 
 	gtk_init(&argc,&argv);
 	expand_symbols(sparse_initialize(argc, argv, &filelist));
-	FOR_EACH_PTR_NOTAG(filelist, file) {
+	FOR_EACH_PTR(filelist, file) {
 		struct symbol_list *syms = sparse(file);
 		expand_symbols(syms);
 		concat_symbol_list(syms, &view_syms);
-	} END_FOR_EACH_PTR_NOTAG(file);
+	} END_FOR_EACH_PTR(file);
 	treeview_main(view_syms);
 	return 0;
 }
diff --git a/test-lexing.c b/test-lexing.c
index 5c7ab2adf..a26398635 100644
--- a/test-lexing.c
+++ b/test-lexing.c
@@ -41,9 +41,9 @@ int main(int argc, char **argv)
 
 	preprocess_only = 1;
 	sparse_initialize(argc, argv, &filelist);
-	FOR_EACH_PTR_NOTAG(filelist, file) {
+	FOR_EACH_PTR(filelist, file) {
 		sparse(file);
-	} END_FOR_EACH_PTR_NOTAG(file);
+	} END_FOR_EACH_PTR(file);
 	show_identifier_stats();
 	return 0;
 }
diff --git a/test-linearize.c b/test-linearize.c
index fe0673bef..3f29eecd3 100644
--- a/test-linearize.c
+++ b/test-linearize.c
@@ -58,9 +58,9 @@ int main(int argc, char **argv)
 	char *file;
 
 	clean_up_symbols(sparse_initialize(argc, argv, &filelist));
-	FOR_EACH_PTR_NOTAG(filelist, file) {
+	FOR_EACH_PTR(filelist, file) {
 		clean_up_symbols(sparse(file));
-	} END_FOR_EACH_PTR_NOTAG(file);
+	} END_FOR_EACH_PTR(file);
 
 	report_stats();
 	return 0;
diff --git a/test-parsing.c b/test-parsing.c
index 7642205af..c5bc42e19 100644
--- a/test-parsing.c
+++ b/test-parsing.c
@@ -64,7 +64,7 @@ int main(int argc, char **argv)
 	printf("\n\n");
 #endif
 
-	FOR_EACH_PTR_NOTAG(filelist, file) {
+	FOR_EACH_PTR(filelist, file) {
 		list = sparse(file);
 
 		// Simplification
@@ -75,7 +75,7 @@ int main(int argc, char **argv)
 		show_symbol_list(list, "\n\n");
 		printf("\n\n");
 #endif
-	} END_FOR_EACH_PTR_NOTAG(file);
+	} END_FOR_EACH_PTR(file);
 
 #if 0
 	// And show the allocation statistics
diff --git a/test-unssa.c b/test-unssa.c
index 240d99601..3d0a82b7c 100644
--- a/test-unssa.c
+++ b/test-unssa.c
@@ -78,9 +78,9 @@ int main(int argc, char **argv)
 	char *file;
 
 	compile(sparse_initialize(argc, argv, &filelist));
-	FOR_EACH_PTR_NOTAG(filelist, file) {
+	FOR_EACH_PTR(filelist, file) {
 		compile(sparse(file));
-	} END_FOR_EACH_PTR_NOTAG(file);
+	} END_FOR_EACH_PTR(file);
 
 	report_stats();
 	return 0;
-- 
2.13.0

[PATCH 34/34] ptrlist: addr vs entry

[Luc Van Oostenryck]

---
 ptrlist.c | 46 ++++++++++++++++++++++++++-------------------
 ptrlist.h | 64 +++++++++++++++++++++++++++++++++------------------------------
 2 files changed, 61 insertions(+), 49 deletions(-)

diff --git a/ptrlist.c b/ptrlist.c
index 95447eaea..90c3b81d7 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -167,14 +167,14 @@ void **__add_ptr_list_tag(struct ptr_list **listp, void *ptr, unsigned long tag)
 int delete_ptr_list_entry(struct ptr_list **list, void *entry, int count)
 {
 	struct ptr_cur cur;
+	void **this;
 
 	if (!ptr_cur_beg(&cur, *list))
                 goto out;
 
-	while (ptr_cur_next(&cur)) {
-		void *ptr = cur.l->list[cur.n];
-		if (ptr == entry) {
-			ptr_cur_delete(&cur, ptr);
+	while ((this = ptr_cur_next(&cur))) {
+		if (*this == entry) {
+			ptr_cur_delete(&cur, *this);
 			if (!--count)
 				goto out;
 		}
@@ -188,12 +188,12 @@ out:
 int replace_ptr_list_entry(struct ptr_list **list, void *old_ptr, void *new_ptr, int count)
 {
 	struct ptr_cur cur;
+	void **this;
 
 	if (!ptr_cur_beg(&cur, *list))
                 goto out;
 
-	while (ptr_cur_next(&cur)) {
-		void **this = &cur.l->list[cur.n];
+	while ((this = ptr_cur_next(&cur))) {
 		if (*this == old_ptr) {
 			*this = new_ptr;
 			if (!--count)
@@ -209,14 +209,18 @@ out:
 void * undo_ptr_list_last(struct ptr_list **head)
 {
 	struct ptr_cur cur;
+	void **this;
 	void *ptr;
 
-	if (!ptr_cur_end(&cur, *head) || !ptr_cur_prev(&cur))
+	if (!ptr_cur_end(&cur, *head))
+		return NULL;
+	if (!(this = ptr_cur_prev(&cur)))
 		return NULL;
 
-	ptr = cur.l->list[cur.n];
-	cur.l->list[cur.n--] = (void *)0xf1f1f1f1;
+	ptr = *this;
+	*this = (void *)0xf1f1f1f1;
 	cur.l->nr--;
+	cur.n--;
 
 	return ptr;
 }
@@ -224,12 +228,15 @@ void * undo_ptr_list_last(struct ptr_list **head)
 void * delete_ptr_list_last(struct ptr_list **head)
 {
 	struct ptr_cur cur;
+	void **this;
 	void *ptr;
 
-	if (!ptr_cur_end(&cur, *head) || !ptr_cur_prev(&cur))
+	if (!ptr_cur_end(&cur, *head))
+		return NULL;
+	if (!(this = ptr_cur_prev(&cur)))
 		return NULL;
 
-	ptr = ptr_cur_entry(&cur);
+	ptr = *this;
 	if (--cur.l->nr == 0) {
 		if (cur.l == cur.h)
 			*head = NULL;
@@ -245,12 +252,13 @@ void * delete_ptr_list_last(struct ptr_list **head)
 void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
 {
 	struct ptr_cur cur;
+	void **this;
 
 	if (!ptr_cur_beg(&cur, a))
                 return;
 
-	while (ptr_cur_next(&cur))
-		__add_ptr_list(b, ptr_cur_entry(&cur));
+	while ((this = ptr_cur_next(&cur)))
+		__add_ptr_list(b, *this);
 }
 
 void __free_ptr_list(struct ptr_list **listp)
@@ -271,19 +279,19 @@ void __free_ptr_list(struct ptr_list **listp)
 }
 
 
-int ptr_cur_next(struct ptr_cur *cur)
+void **ptr_cur_next(struct ptr_cur *cur)
 {
 	do {
 		struct ptr_list *curl = cur->l;
 
 		if (++cur->n < curl->nr)
-			return 1;
+			return &curl->list[cur->n];
 
 		cur->l = curl->next;
 		cur->n = -1;
 	} while (cur->l != cur->h);
 
-	return 0;
+	return NULL;
 }
 
 int ptr_cur_beg(struct ptr_cur *cur, struct ptr_list *head)
@@ -297,13 +305,13 @@ int ptr_cur_beg(struct ptr_cur *cur, struct ptr_list *head)
 	return 1;
 }
 
-int ptr_cur_prev(struct ptr_cur *cur)
+void **ptr_cur_prev(struct ptr_cur *cur)
 {
 	do {
 		struct ptr_list *curl = cur->l;
 
 		if (--cur->n >= 0)
-			return 1;
+			return &curl->list[cur->n];
 
 		if (curl == cur->h)
 			break;
@@ -312,7 +320,7 @@ int ptr_cur_prev(struct ptr_cur *cur)
 		cur->n = curl->nr;
 	} while (1);
 
-	return 0;
+	return NULL;
 }
 
 int ptr_cur_end(struct ptr_cur *cur, struct ptr_list *head)
diff --git a/ptrlist.h b/ptrlist.h
index 263e68d01..d71b8bfcf 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -53,9 +53,9 @@ extern int ptr_list_size(struct ptr_list *);
 extern int linearize_ptr_list(struct ptr_list *, void **, int);
 
 int ptr_cur_beg(struct ptr_cur *cur, struct ptr_list *head);
-int ptr_cur_next(struct ptr_cur *cur);
+void **ptr_cur_next(struct ptr_cur *cur);
 int ptr_cur_end(struct ptr_cur *cur, struct ptr_list *head);
-int ptr_cur_prev(struct ptr_cur *cur);
+void **ptr_cur_prev(struct ptr_cur *cur);
 void ptr_cur_insert(struct ptr_cur *cur, void *new, void *ptr);
 void ptr_cur_delete(struct ptr_cur *cur, void *ptr);
 
@@ -113,81 +113,85 @@ static inline void *last_ptr_list(struct ptr_list *list)
 	return __PTR_STRIP_TAG(ptr_cur_entry(&cur));
 }
 
-#define DO_PREPARE(head, ptr, __cur)						\
+#define DO_PREPARE(head, ptr, __cur, __addr)					\
 do {										\
 		struct ptr_cur __cur;							\
+		void ** __addr;								\
 		CHECK_TYPE(head,ptr);							\
 		if (!ptr_cur_beg(&__cur, (struct ptr_list *)head) ||			\
-		    !ptr_cur_next(&__cur)) ptr = NULL;					\
-		else ptr = ptr_cur_entry(&__cur);
+		    !(__addr = ptr_cur_next(&__cur))) ptr = NULL;			\
+		else ptr = *__addr;
 
-#define DO_NEXT(ptr, __cur)							\
+#define DO_NEXT(ptr, __cur, __addr)							\
 	if (ptr) {									\
-		if (ptr_cur_next(&__cur))						\
-			ptr = ptr_cur_entry(&__cur);					\
+		if ((__addr = ptr_cur_next(&__cur)))					\
+			ptr = *__addr;							\
 		else									\
 			ptr = NULL;							\
 	}
 
-#define DO_RESET(ptr, __cur)								\
-	if (!ptr_cur_beg(&__cur, (struct ptr_list *)head) ||				\
-	    !ptr_cur_next(&__cur)) ptr = NULL;						\
-	else ptr = ptr_cur_entry(&__cur);
+#define DO_RESET(ptr, __cur, __addr)							\
+	if (!ptr_cur_beg(&__cur, __cur.h) ||						\
+	    !(__addr = ptr_cur_next(&__cur))) ptr = NULL;				\
+	else ptr = *__addr;
 
 #define DO_FINISH(ptr, __cur)								\
 		(void)(__cur.n); /* Sanity-check nesting */				\
 	} while (0)
 
 #define PREPARE_PTR_LIST(head, ptr) \
-	DO_PREPARE(head, ptr, __cur##ptr)
+	DO_PREPARE(head, ptr, __cur##ptr, __addr##ptr)
 
 #define NEXT_PTR_LIST(ptr) \
-	DO_NEXT(ptr, __cur##ptr)
+	DO_NEXT(ptr, __cur##ptr, __addr##ptr)
 
 #define RESET_PTR_LIST(ptr) \
-	DO_RESET(ptr, __cur##ptr)
+	DO_RESET(ptr, __cur##ptr, __addr##ptr)
 
 #define FINISH_PTR_LIST(ptr) \
 	DO_FINISH(ptr, __cur##ptr)
 
-#define DO_FOR_EACH(head, ptr, __cur) do {						\
+#define DO_FOR_EACH(head, ptr, __cur, __addr) do {					\
 	struct ptr_cur __cur;								\
+	void **__addr;									\
 	CHECK_TYPE(head,ptr);								\
 	if (!head) break;								\
 	ptr_cur_beg(&__cur, (struct ptr_list *)head);					\
-	while (ptr_cur_next(&__cur)) {							\
-		ptr = ptr_cur_entry(&__cur);
+	while ((__addr = ptr_cur_next(&__cur))) {					\
+		ptr = *__addr;
 
 #define DO_END_FOR_EACH(ptr, __cur)							\
 	}										\
 } while (0)
 
-#define DO_FOR_EACH_REVERSE(head, ptr, __cur) do {					\
+#define DO_FOR_EACH_REVERSE(head, ptr, __cur, __addr) do {				\
 	struct ptr_cur __cur;								\
+	void **__addr;									\
 	CHECK_TYPE(head,ptr);								\
 	if (!head) break;								\
 	ptr_cur_end(&__cur, (struct ptr_list *)head);					\
-	while (ptr_cur_prev(&__cur)) {							\
-		ptr = ptr_cur_entry(&__cur);
+	while ((__addr = ptr_cur_prev(&__cur))) {					\
+		ptr = *__addr;
 
 #define DO_END_FOR_EACH_REVERSE(ptr, __cur)						\
 	}										\
 } while (0)
 
-#define DO_REVERSE(ptr, __cur, new, __newcur) do {					\
+#define DO_REVERSE(ptr, __cur, new, __newcur, __newaddr) do {				\
 	struct ptr_cur __newcur = __cur;						\
-	while (ptr_cur_prev(&__newcur)) {						\
-		new = ptr_cur_entry(&__newcur);
+	void **__newaddr;								\
+	while ((__newaddr = ptr_cur_prev(&__newcur))) {					\
+		new = *__newaddr;
 
 #define RECURSE_PTR_REVERSE(ptr, new)							\
 	DO_REVERSE(ptr, __cur##ptr,							\
-		   new, __cur##new)
+		   new, __cur##new, __newaddr##ptr)
 
-#define DO_THIS_ADDRESS(ptr, __cur)							\
-	((__typeof__(&(ptr))) (__cur.l->list + __cur.n))
+#define DO_THIS_ADDRESS(ptr, __addr)							\
+	((__typeof__(&(ptr))) (__addr))
 
 #define FOR_EACH_PTR(head, ptr) \
-	DO_FOR_EACH(head, ptr, __cur##ptr)
+	DO_FOR_EACH(head, ptr, __cur##ptr, __addr##ptr)
 
 #define FOR_EACH_TAGGED_PTR(head, ptr) \
 	FOR_EACH_PTR(head, ptr) \
@@ -197,13 +201,13 @@ do {										\
 	DO_END_FOR_EACH(ptr, __cur##ptr)
 
 #define FOR_EACH_PTR_REVERSE(head, ptr) \
-	DO_FOR_EACH_REVERSE(head, ptr, __cur##ptr)
+	DO_FOR_EACH_REVERSE(head, ptr, __cur##ptr, __addr##ptr)
 
 #define END_FOR_EACH_PTR_REVERSE(ptr) \
 	DO_END_FOR_EACH_REVERSE(ptr, __cur##ptr)
 
 #define THIS_ADDRESS(ptr) \
-	DO_THIS_ADDRESS(ptr, __cur##ptr)
+	DO_THIS_ADDRESS(ptr, __addr##ptr)
 
 extern void split_ptr_list_head(struct ptr_list *);
 
-- 
2.13.0

Re: [RFC 00/34] ptrlist rework with iterator

[Luc Van Oostenryck]

I forgot to say that the series is also available at:
    git://github.com/lucvoo/sparse.git ptrlist-iterator

-- Luc

Re: [RFC 00/34] ptrlist rework with iterator

[Christopher Li]

On Fri, Jul 7, 2017 at 6:39 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Here is some patches reworking the whole ptrlist API
> which move all the logic currently present in the macros
> in a small set of primitive functions using an iterator
> structure.

I am not considering it for this release for sure.

Actually, NACK on the function based iterator API.

There is no much of a real function enhancement.
And it is a big slow down.

I actually like Linus' macro based implementation. I want
to keep it that way.

It looks very clean on the caller side. It perform extremely
fast. All the internal variable will easy promote to register.
I am all about using code to squeezing very last bit of performance
out of the hardware. The Linus' ptrlist does an amazing job.

Now the function based iterator:

The loop variable will have to keep in the struct member.
It does not inline well. On each function call, the compiler have
to sync loop variable into the memory based struct.
Take a look at the machine code it generated. It is no where
near as good as the original one. The benchmark confirms
that as well.

Here is the program just iterate over a long list for many times
with some condition testing inside the list item.

With Linus' ptrlist:
$ time ./test-ptrlist
sum 4992000000

real 0m9.071s
user 0m9.028s
sys 0m0.002s


Exactly same program with your iterator:
$ time ./test-ptrlist
sum 4992000000

real 0m31.601s
user 0m31.320s
sys 0m0.003s

That is 344% slow down. I have another test, for just the loop
iteration part with nop inside the loop. That is 10x speed difference.

Just make it out there, I am not willing to take a pure cosmetic
change with like 0.1% performance penalty. So NACK on this.

I feel sorry you have spent some many time on this. If I know
earlier I would have tell you that is not going to work. I actually
try that myself long time ago and find out Linus' ptrlist is very
hard to beat in terms of raw performance.


The git branh for this test prgram is at:

https://git.kernel.org/pub/scm/devel/sparse/chrisl/sparse.git/log/?h=test-ptrlist

Here is the test program. Sorry gmail cause some white space
damage to the code.

Chris


/*
 * sparse ptrlist abuse
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include <assert.h>

#include "lib.h"
#include "symbol.h"
#include "expression.h"
#include "linearize.h"
#include "flow.h"
#include "storage.h"
#include "target.h"



int main(int argc, char **argv)
{
struct string_list *filelist = NULL;
struct symbol_list *syms = NULL;
struct symbol *sym = (struct symbol *)0x10;
unsigned long sum = 0;

sparse_initialize(argc, argv, &filelist);
for (int i= 0; i < 10000; i++, sym++)
add_symbol(&syms, sym);

for (int i= 0; i < 100; i++) {
for (int j= 0; j < 10000; j++) {
FOR_EACH_PTR(syms, sym) {
if ((unsigned long) sym & 0x1000)
sum ++;
} END_FOR_EACH_PTR(sym);
}
}
printf("sum %ld\n", sum);
return 0;
}

Re: [PATCH 01/34] ptrlist: simplify DO_FOR_EACH/DO_END_FOR_EACH

[Christopher Li]

On Fri, Jul 7, 2017 at 6:39 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> -       if (__head) {                                                                   \
> -               do { int __nr;                                                          \
> -                       for (__nr = 0; __nr < __list->nr; __nr++) {                     \
> -                               do {                                                    \
> -                                       ptr = PTR_ENTRY(__list,__nr);                   \
> -                                       do {
> +       if (!__head) break;                                                             \
> +       do { int __nr;                                                                  \
> +               for (__nr = 0; __nr < __list->nr; __nr++) {                             \
> +                       ptr = PTR_ENTRY(__list,__nr);                                   \
>
>  #define DO_END_FOR_EACH(ptr, __head, __list, __nr)                                     \
> -                                       } while (0);                                    \
> -                               } while (0);                                            \
> -                       }                                                               \
> -               } while ((__list = __list->next) != __head);                            \
> -       }                                                                               \
> +               }                                                                       \
> +       } while ((__list = __list->next) != __head);                                    \
>  } while (0)

I think the extra "do {} while (0)" is there to prevent the FOR_EACH
paring with END_FOR_EACH_REVERSE() and vise versa.

Chris

Re: [RFC 00/34] ptrlist rework with iterator

[Luc Van Oostenryck]

On Sat, Jul 08, 2017 at 08:13:15AM -0700, Christopher Li wrote:
> On Fri, Jul 7, 2017 at 6:39 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > Here is some patches reworking the whole ptrlist API
> > which move all the logic currently present in the macros
> > in a small set of primitive functions using an iterator
> > structure.
> 
> I am not considering it for this release for sure.

It was, of course, not meant for.
 
> Actually, NACK on the function based iterator API.
> 
> There is no much of a real function enhancement.
> And it is a big slow down.

See below.
 
> I actually like Linus' macro based implementation. I want
> to keep it that way.

No problem.
 
> It looks very clean on the caller side. It perform extremely
> fast. All the internal variable will easy promote to register.

But since all real use of the macros will call some functions
inside the loops all those nice registers will need to be pushed
on the stack.

> I am all about using code to squeezing very last bit of performance
> out of the hardware.

Sure.
Of course, I prefer for now to focus on correctness and
robustness instead of hypothetical micro-performance. Hence
all the fixes, the changes in the testsuite and all the other
testing I made. And don't take me wrong, I've done my share of
timing and profiling, as I'm *very* performance conscious.
 
> Now the function based iterator:
> 
...
> 
> Here is the program just iterate over a long list for many times
> with some condition testing inside the list item.

This sort of artificial benchmark doesn't mean anything, you
should know that. What you need to measure is how the stuff is
really used to see the real effect on cache and generated code.
The we can talk about timing, slowdown & performance.
Have you done this and seen a significative difference?
(I did it, of course, and there wasn't anything significative,
all witihn the noise of the measurements).

Also, in November while I was fixing the problem with empty
blocks, Linus himself said about the ptrlist macros:
	"Some of those inlines look large enough that I wonder
	 how much sense they make as inlines any more"
And indeed, having all those levels of looping inline/in macros
is quite questionnable regarding the quality of the code that can
be generated and impact on i-cache.

It was Linus' remark and combined the issue and the complexity/subtility
which motivated me to see what else can be done with these lists.
But well ...

-- Luc

Re: [RFC 00/34] ptrlist rework with iterator

[Christopher Li]

On Sat, Jul 8, 2017 at 11:50 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>> It looks very clean on the caller side. It perform extremely
>> fast. All the internal variable will easy promote to register.
>
> But since all real use of the macros will call some functions
> inside the loops all those nice registers will need to be pushed
> on the stack.

Yes, if the loop need to external functions. Those register will
sync to memory. There is also a lot of loops that don't need to.

I am looking at simple.c just because I have it open in my editor.

I count 5 ptrlist loop without function calls, 1 with. Simple.c might
not be typical because it is likely doing more small stuff. But it
give an example the loop without function call is not rare at all.

>
> This sort of artificial benchmark doesn't mean anything, you
> should know that. What you need to measure is how the stuff is

I really don't like what you are suggesting. It is fair and straight
compare. Artificial benchmark usually means pick the workload
to make certain number look good and ignore the other workload
which numbers that looks bad.

I thing in this case, it is one sided. If you still think my test is artificial
and put your ptrlist iteration in unfair situation. I encourage you come
up with an artificial test which let your version of ptrlist iterator come
out favorable in performance number. If we can't find such case,
then it means it is universal not artificial.

> really used to see the real effect on cache and generated code.
> The we can talk about timing, slowdown & performance.
> Have you done this and seen a significative difference?
> (I did it, of course, and there wasn't anything significative,
> all witihn the noise of the measurements).

For the record, I did run your code with kernel source checking.
"wasn't anything significative" by itself was not good enough to
accept the patch. Such a big rewrite of such fundamental building
block better have good enough reason for it. I don't see a lot
of up side to justify it. I definitely see the down side in performance.


>
> Also, in November while I was fixing the problem with empty
> blocks, Linus himself said about the ptrlist macros:
>         "Some of those inlines look large enough that I wonder
>          how much sense they make as inlines any more"
> And indeed, having all those levels of looping inline/in macros
> is quite questionnable regarding the quality of the code that can
> be generated and impact on i-cache.

Maybe he mean just take out the inline keyword and let those
ptr_xxx function stay as function not inline function?

Anyway, if there is more specific code we can discuss. I can
take a look at what needs to be done as well. It doesn't have
to be a big rewrite, especially the performance number is very
hard for me to swallow.

> It was Linus' remark and combined the issue and the complexity/subtility
> which motivated me to see what else can be done with these lists.

The thing is, put those variable in to struct members does not magically
make it clean and less complex. I consider those change cosmetic.
Different people have different preference. It is hard to make every one happy
on how the code should look. I am reluctant to take *pure* cosmetic change
without real functional impact. The performance number here is a deal
breaker for me. There might be other ways to improve it. This is not it.

Chris

Re: [RFC 00/34] ptrlist rework with iterator

[Luc Van Oostenryck]

On Sun, Jul 09, 2017 at 01:25:36AM -0700, Christopher Li wrote:
> On Sat, Jul 8, 2017 at 11:50 PM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote:
> >> It looks very clean on the caller side. It perform extremely
> >> fast. All the internal variable will easy promote to register.
> >
> > But since all real use of the macros will call some functions
> > inside the loops all those nice registers will need to be pushed
> > on the stack.
> 
> Yes, if the loop need to external functions. Those register will
> sync to memory. There is also a lot of loops that don't need to.
> 
> I am looking at simple.c just because I have it open in my editor.
> 
> I count 5 ptrlist loop without function calls, 1 with. Simple.c might
> not be typical because it is likely doing more small stuff. But it
> give an example the loop without function call is not rare at all.

Non-typical example are not very interesting. But yes, some of these
loops doesn't have calls inside. 

> > This sort of artificial benchmark doesn't mean anything, you
> > should know that. What you need to measure is how the stuff is
> 
> I really don't like what you are suggesting. It is fair and straight
> compare. Artificial benchmark usually means pick the workload
> to make certain number look good and ignore the other workload
> which numbers that looks bad.

What you describe is what I would call a 'made-up' benchmark.
It's not what I meant. I just meant 'artificial' as opposing to 'real'.
In other words, not the real (sparse) code with a 'real' workload
(as usually used with sparse, like a kernel compile/checking).

> I thing in this case, it is one sided. If you still think my test is artificial
> and put your ptrlist iteration in unfair situation. I encourage you come
> up with an artificial test which let your version of ptrlist iterator come
> out favorable in performance number. If we can't find such case,
> then it means it is universal not artificial.

I wasn't objecting against the fairness but about the meaningness.
And I certainly won't waste my time to create such 'artificial' benchmark.
 
> > really used to see the real effect on cache and generated code.
> > The we can talk about timing, slowdown & performance.
> > Have you done this and seen a significative difference?
> > (I did it, of course, and there wasn't anything significative,
> > all witihn the noise of the measurements).
> 
> For the record, I did run your code with kernel source checking.
> "wasn't anything significative" by itself was not good enough to
> accept the patch. Such a big rewrite of such fundamental building
> block better have good enough reason for it. I don't see a lot
> of up side to justify it. I definitely see the down side in performance.

And what was this slow down you saw? 5%, 1%, less than 1%? 
It would help to have some number. Like I said above, when
I did the test any speed difference I saw was within the
noise.

> > Also, in November while I was fixing the problem with empty
> > blocks, Linus himself said about the ptrlist macros:
> >         "Some of those inlines look large enough that I wonder
> >          how much sense they make as inlines any more"
> > And indeed, having all those levels of looping inline/in macros
> > is quite questionnable regarding the quality of the code that can
> > be generated and impact on i-cache.
> 
> Maybe he mean just take out the inline keyword and let those
> ptr_xxx function stay as function not inline function?

I think he specically was talking about the code in the macros
but I could be wrong, of course.
 
> ... the performance number is very
> hard for me to swallow.

I understand it, indeed.
You're talking here about the perf number of your small benchmark.
Right?
 
> > It was Linus' remark and combined the issue and the complexity/subtility
> > which motivated me to see what else can be done with these lists.
> 
> The thing is, put those variable in to struct members does not magically
> make it clean and less complex.

Nobody was talking about magic. Do you really believe that this
rework is just about 'put those variable in to struct member'?

If it wasn't clear enough, moving the vars in a struct is just
a side-effect without any interest in itself.
What this rework is all about is to move all the logic into a
small set of primitive functions with minimal interactions
interaction with external and where problems, changes,
debugging, ... can much more easily be done.
And being more i-cache friendly is the second goal.

> I consider those change cosmetic.

Too bad.

> Different people have different preference. It is hard to make every one happy
> on how the code should look. I am reluctant to take *pure* cosmetic change
> without real functional impact. The performance number here is a deal
> breaker for me. There might be other ways to improve it. This is not it.

Yes, yes. I understand. Performance. Performance.
There is also usability, correctness, robustness, maintainability.

And talking about being happy, I really think that the first ones
to be happy should be the users.


Anyway, I posted this series for review, as a starting point to see
where further development can go.
Your "NACK on the function based iterator API" is all what really matter here.

-- Luc

Re: [RFC 00/34] ptrlist rework with iterator

[Dibyendu Majumdar]

Hi,

On 9 July 2017 at 10:52, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote:
> On Sun, Jul 09, 2017 at 01:25:36AM -0700, Christopher Li wrote:
>> For the record, I did run your code with kernel source checking.
>> "wasn't anything significative" by itself was not good enough to
>> accept the patch. Such a big rewrite of such fundamental building
>> block better have good enough reason for it. I don't see a lot
>> of up side to justify it. I definitely see the down side in performance.
>
> And what was this slow down you saw? 5%, 1%, less than 1%?
> It would help to have some number. Like I said above, when
> I did the test any speed difference I saw was within the
> noise.
>

As I am using a function based iterator in dmr_C this discussion is of
interest. I agree with Luc that micro benchmarks are not very useful.
Is there data on what the performance impact is on running sparse
against say the Linux kernel. Is there statistically significant
difference?

I personally think that the trade-off for more understandable and
supportable code here is worth it as really the performance difference
if extremely small should not be of great importance to a tool like
sparse which is a development tool, and not something you are running
to handle production workload.

My approach in dmr_C allows me to switch between the macro based
implementation and the function based implementation, primarily so
that when I get failures I can check if the failures are due to the
changes I made. But this has the drawback of maintaining two versions.

Anyway just wanted to put my vote for the changes proposed by Luc.

Regards
Dibyendu