From a363faae46e3d9a89b61879aac4ca2532436e001 Mon Sep 17 00:00:00 2001 From: Dan Carpenter Date: Fri, 27 Jan 2017 12:00:42 +0300 Subject: [PATCH] avl: add a short cut for when there are no states It's quite common for a check to have no states. This provides a quick way to verify it instead of searching the complete hash tree. Signed-off-by: Dan Carpenter --- avl.c | 9 ++++++++- avl.h | 1 + 2 files changed, 9 insertions(+), 1 deletion(-) diff --git a/avl.c b/avl.c index f87ceb0e..e6bd620c 100644 --- a/avl.c +++ b/avl.c @@ -56,7 +56,7 @@ int unfree_stree; #define bal(side) ((side) == 0 ? -1 : 1) #define side(bal) ((bal) == 1 ? 1 : 0) -struct stree *avl_new(void) +static struct stree *avl_new(void) { struct stree *avl = malloc(sizeof(*avl)); @@ -65,6 +65,7 @@ struct stree *avl_new(void) avl->root = NULL; avl->base_stree = NULL; + avl->has_states = calloc(num_checks + 1, sizeof(char)); avl->count = 0; avl->stree_id = 0; avl->references = 1; @@ -97,6 +98,9 @@ struct sm_state *avl_lookup(const struct stree *avl, const struct sm_state *sm) if (!avl) return NULL; + if (sm->owner != USHRT_MAX && + !avl->has_states[sm->owner]) + return NULL; found = lookup(avl, avl->root, sm); if (!found) return NULL; @@ -138,6 +142,9 @@ bool avl_insert(struct stree **avl, const struct sm_state *sm) *avl = clone_stree_real(*avl); } old_count = (*avl)->count; + /* fortunately we never call get_state() on "unnull_path" */ + if (sm->owner != USHRT_MAX) + (*avl)->has_states[sm->owner] = 1; insert_sm(*avl, &(*avl)->root, sm); return (*avl)->count != old_count; } diff --git a/avl.h b/avl.h index d8f3c515..50c90cda 100644 --- a/avl.h +++ b/avl.h @@ -34,6 +34,7 @@ typedef struct AvlIter AvlIter; struct stree { AvlNode *root; struct stree *base_stree; + char *has_states; size_t count; int stree_id; int references; -- 2.11.4.GIT