[augeas-devel] augeas: master - * src/fa.c: cache hash values in the state
David Lutterkort
lutter at fedoraproject.org
Thu Feb 19 20:13:05 UTC 2009
Gitweb: http://git.fedorahosted.org/git/augeas.git?p=augeas.git;a=commitdiff;h=5ab6b8b1ce374039ad20c6844a929f0d00c2addb
Commit: 5ab6b8b1ce374039ad20c6844a929f0d00c2addb
Parent: c53f5d8586b709242b91c47ead51f768a126188b
Author: David Lutterkort <lutter at redhat.com>
AuthorDate: Wed Feb 18 22:41:17 2009 -0800
Committer: David Lutterkort <lutter at redhat.com>
CommitterDate: Thu Feb 19 12:11:58 2009 -0800
* src/fa.c: cache hash values in the state
This gives about a 15% performance improvement in typechecking
the logrotate lens
---
src/fa.c | 19 +++++++++----------
1 files changed, 9 insertions(+), 10 deletions(-)
diff --git a/src/fa.c b/src/fa.c
index f9d3258..9bb8876 100644
--- a/src/fa.c
+++ b/src/fa.c
@@ -62,6 +62,7 @@ struct fa {
states so that we can free the list when we need to free the state */
struct state {
struct state *next;
+ hash_val_t hash;
unsigned int accept : 1;
unsigned int live : 1;
unsigned int reachable : 1;
@@ -178,6 +179,8 @@ struct re {
/* A map from a set of states to a state. */
typedef hash_t state_set_hash;
+static hash_val_t ptr_hash(const void *p);
+
static const int array_initial_size = 4;
static const int array_max_expansion = 128;
@@ -325,6 +328,7 @@ static struct state *make_state(void) {
struct state *s;
if (ALLOC(s) == -1)
return NULL;
+ s->hash = ptr_hash(s);
return s;
}
@@ -659,18 +663,12 @@ static hash_val_t ptr_hash(const void *p) {
typedef hash_t state_triple_hash;
static hash_val_t pair_hash(const void *key) {
- struct state *const *pair = key;
- return ptr_hash(pair[0]) + ptr_hash(pair[1]);
+ register struct state *const *pair = key;
+ return pair[0]->hash + pair[1]->hash;
}
static int pair_cmp(const void *key1, const void *key2) {
- struct state *const *pair1 = key1;
- struct state *const *pair2 = key2;
-
- if (pair1[0] < pair2[0] ||
- (pair1[0] == pair2[0] && pair1[1] < pair2[1]))
- return -1;
- return pair1[1] == pair2[1] ? 0 : 1;
+ return memcmp(key1, key2, 2*sizeof(struct state *));
}
static void state_triple_node_free(hnode_t *node, ATTRIBUTE_UNUSED void *ctx) {
@@ -925,7 +923,7 @@ static hash_val_t set_hash(const void *key) {
const struct state_set *set = key;
for (int i = 0; i < set->used; i++) {
- hash += ptr_hash(set->states[i]);
+ hash += set->states[i]->hash;
}
return hash;
}
@@ -1957,6 +1955,7 @@ struct fa *fa_intersect(struct fa *fa1, struct fa *fa2) {
}
}
}
+ fa->deterministic = fa1->deterministic && fa2->deterministic;
done:
state_set_free(worklist);
state_triple_free(newstates);
More information about the augeas-devel
mailing list