From owner-svn-src-user@FreeBSD.ORG Tue Feb 28 13:28:50 2012 Return-Path: Delivered-To: svn-src-user@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 9837F1065674; Tue, 28 Feb 2012 13:28:50 +0000 (UTC) (envelope-from gabor@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id 7CD578FC1B; Tue, 28 Feb 2012 13:28:50 +0000 (UTC) Received: from svn.freebsd.org (localhost [127.0.0.1]) by svn.freebsd.org (8.14.4/8.14.4) with ESMTP id q1SDSoOO072696; Tue, 28 Feb 2012 13:28:50 GMT (envelope-from gabor@svn.freebsd.org) Received: (from gabor@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id q1SDSofq072694; Tue, 28 Feb 2012 13:28:50 GMT (envelope-from gabor@svn.freebsd.org) Message-Id: <201202281328.q1SDSofq072694@svn.freebsd.org> From: Gabor Kovesdan Date: Tue, 28 Feb 2012 13:28:50 +0000 (UTC) To: src-committers@freebsd.org, svn-src-user@freebsd.org X-SVN-Group: user MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r232251 - user/gabor/tre-integration/contrib/tre/lib X-BeenThere: svn-src-user@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "SVN commit messages for the experimental " user" src tree" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 28 Feb 2012 13:28:50 -0000 Author: gabor Date: Tue Feb 28 13:28:50 2012 New Revision: 232251 URL: http://svn.freebsd.org/changeset/base/232251 Log: - Fix some shifts in the Wu-Manber algorithms - Actually update shifts if there is a lower one for the same fragment - Fix saving patterns - Initialize some pointers with NULL and avoid segfaults Modified: user/gabor/tre-integration/contrib/tre/lib/tre-mfastmatch.c Modified: user/gabor/tre-integration/contrib/tre/lib/tre-mfastmatch.c ============================================================================== --- user/gabor/tre-integration/contrib/tre/lib/tre-mfastmatch.c Tue Feb 28 13:19:34 2012 (r232250) +++ user/gabor/tre-integration/contrib/tre/lib/tre-mfastmatch.c Tue Feb 28 13:28:50 2012 (r232251) @@ -58,8 +58,12 @@ for (int i = 1; i < nr; i++) \ wm->m_field = siz_arr[i] < wm->m_field ? siz_arr[i] : wm->m_field; \ \ - wm->sh_field = hashtable_init((wm->m_field - 1) * nr * 2, WM_B * \ - char_size, sizeof(wmentry_t)); \ + /* + * m - WM_B + 1 fragment per pattern plus extra space to reduce \ + * collisions. \ + */ \ + wm->sh_field = hashtable_init((wm->m_field - WM_B + 1) * nr * 2, \ + WM_B * char_size, sizeof(wmentry_t)); \ if (!wm->sh_field) \ { \ ret = REG_ESPACE; \ @@ -73,7 +77,7 @@ \ /* First fragment, treat special because it is a prefix */ \ ret = hashtable_get(wm->sh_field, pat_arr[i], entry); \ - sh = siz_arr[i] - WM_B; \ + sh = wm->m_field - WM_B; \ switch (ret) \ { \ case HASH_NOTFOUND: \ @@ -88,14 +92,15 @@ case HASH_OK: \ entry->shift = entry->shift < sh ? entry->shift : sh; \ entry->pref_list[entry->pref++] = i; \ + ret = hashtable_put(wm->sh_field, pat_arr[i], entry); \ if (ret != HASH_UPDATED) \ FAIL; \ } \ /* Intermediate fragments, only shift calculated */ \ - for (int j = 1; j < siz_arr[i] - WM_B; j++) \ + for (int j = 1; j < wm->m_field - WM_B; j++) \ { \ ret = hashtable_get(wm->sh_field, &pat_arr[i][j], entry); \ - sh = siz_arr[i] - WM_B - j; \ + sh = wm->m_field - WM_B - j; \ switch (ret) \ { \ case HASH_NOTFOUND: \ @@ -109,11 +114,13 @@ break; \ case HASH_OK: \ entry->shift = entry->shift < sh ? entry->shift : sh; \ + ret = hashtable_put(wm->sh_field, &pat_arr[i][j], \ + entry); \ if (ret != HASH_UPDATED) \ FAIL; \ } \ } \ - ret = hashtable_get(wm->sh_field, &pat_arr[i][n[i] - WM_B], \ + ret = hashtable_get(wm->sh_field, &pat_arr[i][wm->m_field - WM_B],\ entry); \ switch (ret) \ { \ @@ -122,36 +129,43 @@ entry->suff = 1; \ entry->pref = 0; \ entry->suff_list[0] = i; \ - ret = hashtable_put(wm->sh_field, &pat_arr[i][n[i] - WM_B], \ - entry); \ + ret = hashtable_put(wm->sh_field, &pat_arr[i][wm->m_field - \ + WM_B], entry); \ if (ret != HASH_OK) \ FAIL; \ case HASH_OK: \ entry->shift = entry->shift < sh ? entry->shift : sh; \ entry->suff_list[entry->suff++] = i; \ + ret = hashtable_put(wm->sh_field, &pat_arr[i][wm->m_field - \ + WM_B], entry); \ if (ret != HASH_UPDATED) \ FAIL; \ } \ } \ xfree(entry); -#define _SAVE_PATTERNS(dst, s, type) \ +#define _SAVE_PATTERNS(src, ss, dst, ds, type) \ do \ { \ ALLOC(dst, sizeof(type *) * nr); \ - ALLOC(s, sizeof(size_t) * nr); \ + ALLOC(ds, sizeof(size_t) * nr); \ for (int i = 0; i < nr; i++) \ { \ - ALLOC(dst[i], n[i] * sizeof(type)); \ - memcpy(dst[i], regex[i], n[i] * sizeof(type)); \ - s[i] = n[i]; \ + ALLOC(dst[i], ss[i] * sizeof(type)); \ + memcpy(dst[i], src[i], ss[i] * sizeof(type)); \ + ds[i] = ss[i]; \ } \ } while (0); +#ifdef TRE_WCHAR #define SAVE_PATTERNS \ - _SAVE_PATTERNS(wm->pat, wm->siz, char) + _SAVE_PATTERNS(bregex, bn, wm->pat, wm->siz, char) #define SAVE_PATTERNS_WIDE \ - _SAVE_PATTERNS(wm->wpat, wm->wsiz, tre_char_t) + _SAVE_PATTERNS(regex, n, wm->wpat, wm->wsiz, tre_char_t) +#else +#define SAVE_PATTERNS \ + _SAVE_PATTERNS(regex, n, wm->pat, wm->siz, char) +#endif #ifdef TRE_WCHAR #define PROC_WM(pat_arr, size_arr) \ @@ -177,15 +191,15 @@ tre_wmcomp(wmsearch_t *wm, size_t nr, co wmentry_t *entry = NULL; int ret; #ifdef TRE_WCHAR - char **bregex; - size_t *bn; + char **bregex = NULL; + size_t *bn = NULL; #endif ALLOC(wm, sizeof(wmsearch_t)); + wm->wshift = NULL; + wm->shift = NULL; #ifdef TRE_WCHAR - PROC_WM_WIDE(regex, n); - ALLOC(bregex, sizeof(char *) * nr); ALLOC(bn, sizeof(size_t) * nr); @@ -205,21 +219,33 @@ tre_wmcomp(wmsearch_t *wm, size_t nr, co wm->pat = bregex; wm->siz = bn; + + PROC_WM_WIDE(regex, n); PROC_WM(bregex, bn); + SAVE_PATTERNS_WIDE; + SAVE_PATTERNS; + for (int i = 0; i < nr; i++) xfree(bregex[i]); xfree(bregex); - - SAVE_PATTERNS; - SAVE_PATTERNS_WIDE; + xfree(bn); #else PROC_WM(regex, n); SAVE_PATTERNS; #endif return REG_OK; + fail: #ifdef TRE_WCHAR + if (bn) + xfree(bn); + if (bregex) + { + for (int i = 0; i < nr; i++) + xfree(bregex[i]); + xfree(bregex); + } if (wm->wshift) hashtable_free(wm->wshift); #endif