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 <luc.vanoostenryck@xxxxxxxxx>
---
linearize.h | 7 ++++++-
ptrlist.c | 19 +++++++++++++++++++
ptrlist.h | 2 ++
simplify.c | 2 +-
4 files changed, 28 insertions(+), 2 deletions(-)
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;
}
--
2.18.0
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
