[v2,2/5] add ptr_list_empty()

Commit Message

Luc Van Oostenryck July 25, 2018, 8:44 p.m. UTC

Sometimes we need to know if a list is empty, for example, in
order to determine if a pseudo has some users or not.

Currently, this is done using ptr_list_size(), which always
walks the whole list but the needed answer can be returned as
soon as it's known that the list contains at least one element.

Add the helper ptr_list_empty() and use it for has_users().

This gives a speedup up to 18% on some pathological workloads.

Signed-off-by: Luc Van Oostenryck <[e-mail]>
---
 linearize.h |  7 ++++++-
 ptrlist.c   | 19 +++++++++++++++++++
 ptrlist.h   |  2 ++
 simplify.c  |  2 +-
 4 files changed, 28 insertions(+), 2 deletions(-)

Patch

diff --git a/linearize.h b/linearize.h
index 092e1ac23..de42e718d 100644
--- a/linearize.h
+++ b/linearize.h
@@ -333,9 +333,14 @@  static inline int pseudo_user_list_size(struct pseudo_user_list *list)
 	return ptr_list_size((struct ptr_list *)list);
 }
 
+static inline bool pseudo_user_list_empty(struct pseudo_user_list *list)
+{
+	return ptr_list_empty((struct ptr_list *)list);
+}
+
 static inline int has_users(pseudo_t p)
 {
-	return pseudo_user_list_size(p->users) != 0;
+	return !pseudo_user_list_empty(p->users);
 }
 
 static inline struct pseudo_user *alloc_pseudo_user(struct instruction *insn, pseudo_t *pp)
diff --git a/ptrlist.c b/ptrlist.c
index 684aff8c5..356785dfc 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -36,6 +36,25 @@  int ptr_list_size(struct ptr_list *head)
 	return nr;
 }
 
+///
+// test if a list is empty
+// @head: the head of the list
+// @return: ``true`` if the list is empty, ``false`` otherwise.
+bool ptr_list_empty(const struct ptr_list *head)
+{
+	const struct ptr_list *list = head;
+
+	if (!head)
+		return true;
+
+	do {
+		if (list->nr - list->rm)
+			return false;
+	} while ((list = list->next) != head);
+
+	return true;
+}
+
 ///
 // get the first element of a ptrlist
 // @head: the head of the list
diff --git a/ptrlist.h b/ptrlist.h
index 46a9baee2..f145bc5f1 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -2,6 +2,7 @@ 
 #define PTR_LIST_H
 
 #include <stdlib.h>
+#include <stdbool.h>
 
 /*
  * Generic pointer list manipulation code. 
@@ -37,6 +38,7 @@  extern void sort_list(struct ptr_list **, int (*)(const void *, const void *));
 extern void concat_ptr_list(struct ptr_list *a, struct ptr_list **b);
 extern void copy_ptr_list(struct ptr_list **h, struct ptr_list *t);
 extern int ptr_list_size(struct ptr_list *);
+extern bool ptr_list_empty(const struct ptr_list *head);
 extern int linearize_ptr_list(struct ptr_list *, void **, int);
 extern void *first_ptr_list(struct ptr_list *);
 extern void *last_ptr_list(struct ptr_list *);
diff --git a/simplify.c b/simplify.c
index 741b1272c..4dc24a505 100644
--- a/simplify.c
+++ b/simplify.c
@@ -179,7 +179,7 @@  static int delete_pseudo_user_list_entry(struct pseudo_user_list **list, pseudo_
 	} END_FOR_EACH_PTR(pu);
 	assert(count <= 0);
 out:
-	if (pseudo_user_list_size(*list) == 0)
+	if (pseudo_user_list_empty(*list))
 		*list = NULL;
 	return count;
 }