svn commit: r225309 - user/gabor/tre-integration/contrib/tre/lib
Gabor Kovesdan
gabor at FreeBSD.org
Thu Sep 1 13:36:30 UTC 2011
Author: gabor
Date: Thu Sep 1 13:36:29 2011
New Revision: 225309
URL: http://svn.freebsd.org/changeset/base/225309
Log:
- Merge improvements from BSD grep:
* More verbose debug output
* Fixes for hashtable.c to avoid infinite loop
* Allocate more space for hash table to avoid hash collision and be more
efficient
Modified:
user/gabor/tre-integration/contrib/tre/lib/hashtable.c
user/gabor/tre-integration/contrib/tre/lib/tre-fastmatch.c
Modified: user/gabor/tre-integration/contrib/tre/lib/hashtable.c
==============================================================================
--- user/gabor/tre-integration/contrib/tre/lib/hashtable.c Thu Sep 1 06:12:16 2011 (r225308)
+++ user/gabor/tre-integration/contrib/tre/lib/hashtable.c Thu Sep 1 13:36:29 2011 (r225309)
@@ -29,6 +29,7 @@
#include <string.h>
#include "hashtable.h"
+#include "tre-internal.h"
/*
@@ -58,6 +59,10 @@ hashtable
{
hashtable *tbl;
+ DPRINT(("hashtable_init: table_size %lu, key_size %lu, value_size %lu\n",
+ (unsigned long)table_size, (unsigned long)key_size,
+ (unsigned long)value_size));
+
tbl = malloc(sizeof(hashtable));
if (tbl == NULL)
goto mem1;
@@ -76,6 +81,7 @@ hashtable
mem2:
free(tbl);
mem1:
+ DPRINT(("hashtable_init: allocation failed\n"));
errno = ENOMEM;
return (NULL);
}
@@ -98,9 +104,13 @@ hashtable_put(hashtable *tbl, const void
uint32_t hash = 0;
if (tbl->table_size == tbl->usage)
- return (HASH_FULL);
+ {
+ DPRINT(("hashtable_put: hashtable is full\n"));
+ return (HASH_FULL);
+ }
hash = hash32_buf(key, tbl->key_size, hash) % tbl->table_size;
+ DPRINT(("hashtable_put: calculated hash %lu\n", hash));
/*
* On hash collision entries are inserted at the next free space,
@@ -108,13 +118,21 @@ hashtable_put(hashtable *tbl, const void
* with the same key (and update it) or we find a free space.
*/
for(;;)
- if (tbl->entries[hash] == NULL)
- break;
- else if (memcmp(tbl->entries[hash]->key, key, tbl->key_size) == 0)
- {
- memcpy(tbl->entries[hash]->value, value, tbl->value_size);
- return (HASH_UPDATED);
- }
+ {
+ if (tbl->entries[hash] == NULL)
+ break;
+ else if (memcmp(tbl->entries[hash]->key, key, tbl->key_size) == 0)
+ {
+ memcpy(tbl->entries[hash]->value, value, tbl->value_size);
+ DPRINT(("hashtable_put: effective location is %lu, "
+ "entry updated\n", hash));
+ return (HASH_UPDATED);
+ }
+ if (++hash == tbl->table_size)
+ hash = 0;
+ }
+
+ DPRINT(("hashtable_put: effective location is %lu\n", hash));
tbl->entries[hash] = malloc(sizeof(hashtable_entry));
if (tbl->entries[hash] == NULL)
@@ -141,6 +159,8 @@ hashtable_put(hashtable *tbl, const void
memcpy(tbl->entries[hash]->value, value, tbl->value_size);
tbl->usage++;
+ DPRINT(("hashtable_put: entry successfully inserted\n"));
+
return (HASH_OK);
mem3:
@@ -148,6 +168,7 @@ mem3:
mem2:
free(tbl->entries[hash]);
mem1:
+ DPRINT(("hashtable_put: insertion failed\n"));
return (HASH_FAIL);
}
@@ -163,9 +184,13 @@ static hashtable_entry
if (tbl->entries[hash] == NULL)
return (NULL);
else if (memcmp(key, tbl->entries[hash]->key, tbl->key_size) == 0)
- return (&tbl->entries[hash]);
+ {
+ DPRINT(("hashtable_lookup: entry found at location %lu\n", hash));
+ return (&tbl->entries[hash]);
+ }
- hash = (hash == tbl->table_size) ? 0 : hash + 1;
+ if (++hash == tbl->table_size)
+ hash = 0;
}
}
@@ -182,9 +207,13 @@ hashtable_get(hashtable *tbl, const void
entry = hashtable_lookup(tbl, key);
if (entry == NULL)
- return (HASH_NOTFOUND);
+ {
+ DPRINT(("hashtable_get: entry is not available in the hashtable\n"));
+ return (HASH_NOTFOUND);
+ }
memcpy(value, (*entry)->value, tbl->value_size);
+ DPRINT(("hashtable_get: entry successfully copied into output buffer\n"));
return (HASH_OK);
}
@@ -200,7 +229,10 @@ hashtable_remove(hashtable *tbl, const v
entry = hashtable_lookup(tbl, key);
if (entry == NULL)
- return (HASH_NOTFOUND);
+ {
+ DPRINT(("hashtable_remove: entry is not available in the hashtable\n"));
+ return (HASH_NOTFOUND);
+ }
free((*entry)->key);
free((*entry)->value);
@@ -208,6 +240,7 @@ hashtable_remove(hashtable *tbl, const v
*entry = NULL;
tbl->usage--;
+ DPRINT(("hashtable_remove: entry successfully removed\n"));
return (HASH_OK);
}
@@ -228,4 +261,5 @@ hashtable_free(hashtable *tbl)
}
free(tbl->entries);
+ DPRINT(("hashtable_free: resources are successfully freed\n"));
}
Modified: user/gabor/tre-integration/contrib/tre/lib/tre-fastmatch.c
==============================================================================
--- user/gabor/tre-integration/contrib/tre/lib/tre-fastmatch.c Thu Sep 1 06:12:16 2011 (r225308)
+++ user/gabor/tre-integration/contrib/tre/lib/tre-fastmatch.c Thu Sep 1 13:36:29 2011 (r225309)
@@ -146,7 +146,7 @@ static int fastcmp(const void *, const v
gs = fg->bmGs[mismatch]; \
} \
bc = (r == HASH_OK) ? bc : fg->defBc; \
- DPRINT(("tre_fast_match: mismatch on character %lc," \
+ DPRINT(("tre_fast_match: mismatch on character %lc, " \
"BC %d, GS %d\n", \
((tre_char_t *)startptr)[mismatch + 1], bc, gs)); \
break; \
@@ -159,7 +159,7 @@ static int fastcmp(const void *, const v
gs = fg->sbmGs[mismatch]; \
} \
bc = fg->qsBc[((unsigned char *)startptr)[mismatch + 1]]; \
- DPRINT(("tre_fast_match: mismatch on character %c," \
+ DPRINT(("tre_fast_match: mismatch on character %c, " \
"BC %d, GS %d\n", \
((unsigned char *)startptr)[mismatch + 1], bc, gs)); \
} \
@@ -216,6 +216,7 @@ static int fastcmp(const void *, const v
char c = islower(fg->pattern[i]) ? toupper(fg->pattern[i]) \
: tolower(fg->pattern[i]); \
fg->qsBc[(unsigned)c] = fg->len - i; \
+ DPRINT(("BC shift for char %c is %d\n", c, fg->len - i)); \
} \
}
@@ -233,8 +234,8 @@ static int fastcmp(const void *, const v
fg->defBc = fg->wlen - fg->hasdot; \
\
/* Preprocess pattern. */ \
- fg->qsBc_table = hashtable_init(fg->wlen * 4, sizeof(tre_char_t), \
- sizeof(int)); \
+ fg->qsBc_table = hashtable_init(fg->wlen * (fg->icase ? 8 : 4), \
+ sizeof(tre_char_t), sizeof(int)); \
if (!fg->qsBc_table) \
FAIL_COMP(REG_ESPACE); \
for (unsigned int i = fg->hasdot + 1; i < fg->wlen; i++) \
@@ -254,6 +255,8 @@ static int fastcmp(const void *, const v
r = hashtable_put(fg->qsBc_table, &wc, &k); \
if ((r == HASH_FAIL) || (r == HASH_FULL)) \
FAIL_COMP(REG_ESPACE); \
+ DPRINT(("BC shift for wide char %lc is %d\n", wc, \
+ fg->wlen - i)); \
} \
}
More information about the svn-src-user
mailing list