Date: Thu, 1 Sep 2011 13:36:30 +0000 (UTC) From: Gabor Kovesdan <gabor@FreeBSD.org> To: src-committers@freebsd.org, svn-src-user@freebsd.org Subject: svn commit: r225309 - user/gabor/tre-integration/contrib/tre/lib Message-ID: <201109011336.p81DaU45053456@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
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)); \ } \ }
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201109011336.p81DaU45053456>