From owner-svn-src-user@FreeBSD.ORG Sun Jun 26 03:38:27 2011 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 379CA106564A; Sun, 26 Jun 2011 03:38:27 +0000 (UTC) (envelope-from adrian@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id 282338FC12; Sun, 26 Jun 2011 03:38:27 +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 p5Q3cRVW034551; Sun, 26 Jun 2011 03:38:27 GMT (envelope-from adrian@svn.freebsd.org) Received: (from adrian@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id p5Q3cRGu034549; Sun, 26 Jun 2011 03:38:27 GMT (envelope-from adrian@svn.freebsd.org) Message-Id: <201106260338.p5Q3cRGu034549@svn.freebsd.org> From: Adrian Chadd Date: Sun, 26 Jun 2011 03:38:27 +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: r223558 - user/adrian/if_ath_tx/sys/dev/ath 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: Sun, 26 Jun 2011 03:38:27 -0000 Author: adrian Date: Sun Jun 26 03:38:26 2011 New Revision: 223558 URL: http://svn.freebsd.org/changeset/base/223558 Log: Disable these locks for now. Witness panics with these enabled. The locks aren't being held here, and I haven't sat down to figure out exactly what has to be locked and what doesn't. Modified: user/adrian/if_ath_tx/sys/dev/ath/if_ath_tx.c Modified: user/adrian/if_ath_tx/sys/dev/ath/if_ath_tx.c ============================================================================== --- user/adrian/if_ath_tx/sys/dev/ath/if_ath_tx.c Sun Jun 26 01:32:46 2011 (r223557) +++ user/adrian/if_ath_tx/sys/dev/ath/if_ath_tx.c Sun Jun 26 03:38:26 2011 (r223558) @@ -1869,7 +1869,7 @@ ath_tx_ampdu_running(struct ath_softc *s { struct ieee80211_tx_ampdu *tap; - ATH_NODE_LOCK_ASSERT(an); +// ATH_NODE_LOCK_ASSERT(an); tap = ath_tx_get_tx_tid(an, tid); if (tap == NULL) @@ -1888,7 +1888,7 @@ ath_tx_ampdu_pending(struct ath_softc *s { struct ieee80211_tx_ampdu *tap; - ATH_NODE_LOCK_ASSERT(an); +// ATH_NODE_LOCK_ASSERT(an); tap = ath_tx_get_tx_tid(an, tid); if (tap == NULL) From owner-svn-src-user@FreeBSD.ORG Sun Jun 26 04:00:50 2011 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 15CE91065670; Sun, 26 Jun 2011 04:00:50 +0000 (UTC) (envelope-from adrian@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id EF9438FC13; Sun, 26 Jun 2011 04:00:49 +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 p5Q40nq6035233; Sun, 26 Jun 2011 04:00:49 GMT (envelope-from adrian@svn.freebsd.org) Received: (from adrian@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id p5Q40nSR035230; Sun, 26 Jun 2011 04:00:49 GMT (envelope-from adrian@svn.freebsd.org) Message-Id: <201106260400.p5Q40nSR035230@svn.freebsd.org> From: Adrian Chadd Date: Sun, 26 Jun 2011 04:00:49 +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: r223559 - user/adrian/if_ath_tx/sys/dev/ath 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: Sun, 26 Jun 2011 04:00:50 -0000 Author: adrian Date: Sun Jun 26 04:00:49 2011 New Revision: 223559 URL: http://svn.freebsd.org/changeset/base/223559 Log: Shuffle around how nodes are unscheduled so the TID in question is known. Doing scheduling per TID is now needed so non-STA modes work well. Modified: user/adrian/if_ath_tx/sys/dev/ath/if_ath_tx.c user/adrian/if_ath_tx/sys/dev/ath/if_athvar.h Modified: user/adrian/if_ath_tx/sys/dev/ath/if_ath_tx.c ============================================================================== --- user/adrian/if_ath_tx/sys/dev/ath/if_ath_tx.c Sun Jun 26 03:38:26 2011 (r223558) +++ user/adrian/if_ath_tx/sys/dev/ath/if_ath_tx.c Sun Jun 26 04:00:49 2011 (r223559) @@ -1399,7 +1399,7 @@ ath_tx_action_frame_override_queue(struc * The node and txnode locks should be held. */ static void -ath_tx_node_sched(struct ath_softc *sc, struct ath_node *an) +ath_tx_node_sched(struct ath_softc *sc, struct ath_node *an, int tid) { ATH_NODE_LOCK_ASSERT(an); ATH_TXNODE_LOCK_ASSERT(sc); @@ -1419,7 +1419,7 @@ ath_tx_node_sched(struct ath_softc *sc, * The node and txnode locks should be held. */ static void -ath_tx_node_unsched(struct ath_softc *sc, struct ath_node *an) +ath_tx_node_unsched(struct ath_softc *sc, struct ath_node *an, int tid) { ATH_NODE_LOCK_ASSERT(an); ATH_TXNODE_LOCK_ASSERT(sc); @@ -1501,7 +1501,7 @@ ath_tx_swq(struct ath_softc *sc, struct /* Bump queued packet counter */ an->an_qdepth++; /* Mark the given node as having packets to dequeue */ - ath_tx_node_sched(sc, an); + ath_tx_node_sched(sc, an, tid); ATH_NODE_UNLOCK(an); ATH_TXNODE_UNLOCK(sc); } @@ -1648,7 +1648,7 @@ ath_tx_tid_cleanup(struct ath_softc *sc, /* Remove any pending hardware TXQ scheduling */ ATH_TXNODE_LOCK(sc); ATH_NODE_LOCK(an); - ath_tx_node_unsched(sc, an); + ath_tx_node_unsched(sc, an, i); ATH_NODE_UNLOCK(an); ATH_TXNODE_UNLOCK(sc); @@ -1783,6 +1783,7 @@ ath_tx_hw_queue(struct ath_softc *sc, st { struct ath_tid *atid; int tid; + int isempty; /* * For now, just queue from all TIDs in order. @@ -1801,15 +1802,34 @@ ath_tx_hw_queue(struct ath_softc *sc, st ath_tx_tid_hw_queue_aggr(sc, an, tid); else ath_tx_tid_hw_queue_norm(sc, an, tid); + + /* + * Check if anything is left in the queue; + * if not, unschedule it. + * Checking this only requires the TXQ lock. + * Unscheduling it requires all the locks. + */ + ATH_TXQ_LOCK(atid); + isempty = (atid->axq_depth == 0); + if (isempty) { + ATH_TXNODE_LOCK(sc); + ATH_NODE_LOCK(an); + ath_tx_node_unsched(sc, an, tid); + ATH_NODE_UNLOCK(an); + ATH_TXNODE_UNLOCK(sc); + } + ATH_TXQ_UNLOCK(atid); } } +#if 0 static int ath_txq_node_qlen(struct ath_softc *sc, struct ath_node *an) { ATH_NODE_LOCK_ASSERT(an); return an->an_qdepth; } +#endif /* * Handle scheduling some packets from whichever nodes have @@ -1825,12 +1845,6 @@ ath_txq_sched(struct ath_softc *sc) STAILQ_FOREACH_SAFE(an, &sc->sc_txnodeq, an_list, next) { /* Try dequeueing packets from the current node */ ath_tx_hw_queue(sc, an); - - /* Are any packets left on the node software queue? Remove */ - ATH_NODE_LOCK(an); - if (! ath_txq_node_qlen(sc, an)) - ath_tx_node_unsched(sc, an); - ATH_NODE_UNLOCK(an); } ATH_TXNODE_UNLOCK(sc); } Modified: user/adrian/if_ath_tx/sys/dev/ath/if_athvar.h ============================================================================== --- user/adrian/if_ath_tx/sys/dev/ath/if_athvar.h Sun Jun 26 03:38:26 2011 (r223558) +++ user/adrian/if_ath_tx/sys/dev/ath/if_athvar.h Sun Jun 26 04:00:49 2011 (r223559) @@ -92,7 +92,7 @@ struct ath_buf; */ struct ath_tid { STAILQ_HEAD(,ath_buf) axq_q; /* pending buffers */ - u_int axq_depth; /* queue depth (stat only) */ + u_int axq_depth; /* SW queue depth */ struct mtx axq_lock; /* lock on queue, tx_buf */ char axq_name[24]; /* e.g. "wlan0_a1_t5" */ struct ath_buf *tx_buf[ATH_TID_MAX_BUFS]; /* active tx buffers, beginning at current BAW */ From owner-svn-src-user@FreeBSD.ORG Mon Jun 27 22:13:15 2011 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 A7FB3106566B; Mon, 27 Jun 2011 22:13:15 +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 97A3D8FC0C; Mon, 27 Jun 2011 22:13:15 +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 p5RMDFre016114; Mon, 27 Jun 2011 22:13:15 GMT (envelope-from gabor@svn.freebsd.org) Received: (from gabor@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id p5RMDFcn016112; Mon, 27 Jun 2011 22:13:15 GMT (envelope-from gabor@svn.freebsd.org) Message-Id: <201106272213.p5RMDFcn016112@svn.freebsd.org> From: Gabor Kovesdan Date: Mon, 27 Jun 2011 22:13:15 +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: r223614 - 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: Mon, 27 Jun 2011 22:13:15 -0000 Author: gabor Date: Mon Jun 27 22:13:15 2011 New Revision: 223614 URL: http://svn.freebsd.org/changeset/base/223614 Log: - Add a simple hashtable implementation. It will be used for fixed string matching algorithms that have good-suffix and bad-character shift tables. For single-byte characters, an array indexed with the character itself is appropriate but for wide characters, this does not work any more because the number of characters are so high. Fortunately, most of the values are the same and there are only n distinct values, where n is the number of distinct characters in the pattern. Making use of this characteristics, it is enough to store the default value and the the value of the distinct characters can go into the hashtable. Added: user/gabor/tre-integration/contrib/tre/lib/hashtable.c (contents, props changed) user/gabor/tre-integration/contrib/tre/lib/hashtable.h (contents, props changed) Added: user/gabor/tre-integration/contrib/tre/lib/hashtable.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ user/gabor/tre-integration/contrib/tre/lib/hashtable.c Mon Jun 27 22:13:15 2011 (r223614) @@ -0,0 +1,159 @@ +/*- + * Copyright (C) 2011 Gabor Kovesdan + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include +#include +#include + +#include "hashtable.h" + +hashtable +*hashtable_init(size_t table_size, size_t key_size, size_t value_size) +{ + hashtable *tbl; + + tbl = malloc(sizeof(hashtable)); + if (tbl == NULL) + return (NULL); + + tbl->entries = calloc(sizeof(hashtable_entry *), table_size); + if (tbl->entries == NULL) { + free(tbl); + return (NULL); + } + + tbl->table_size = table_size; + tbl->usage = 0; + tbl->key_size = key_size; + tbl->value_size = value_size; + + return (tbl); +} + +int +hashtable_put(hashtable *tbl, const void *key, const void *value) +{ + hashtable_entry *entry; + uint32_t hash = 0; + + if (tbl->table_size == tbl->usage) + return (-1); + + hash = hash32_buf(key, tbl->key_size, hash); + hash %= tbl->table_size; + + while (tbl->entries[hash] != NULL) + hash = (hash >= tbl->table_size) ? 0 : hash + 1; + + tbl->entries[hash] = malloc(sizeof(hashtable_entry)); + if (tbl->entries[hash] == NULL) + return (-1); + + tbl->entries[hash]->key = malloc(tbl->key_size); + if (tbl->entries[hash]->key == NULL) { + free(tbl->entries[hash]); + return (-1); + } + + tbl->entries[hash]->value = malloc(tbl->value_size); + if (tbl->entries[hash]->value == NULL) { + free(tbl->entries[hash]->key); + free(tbl->entries[hash]); + return (-1); + } + + memcpy(&tbl->entries[hash]->key, key, tbl->key_size); + memcpy(&tbl->entries[hash]->value, value, tbl->value_size); + tbl->usage++; + + return (0); +} + +static hashtable_entry +*hashtable_lookup(const hashtable *tbl, const void *key) +{ + uint32_t hash = 0; + + hash = hash32_buf(key, tbl->key_size, hash); + hash %= tbl->table_size; + + for (;;) { + if (tbl->entries[hash] == NULL) + return (NULL); + else if (memcmp(key, &tbl->entries[hash]->key, + tbl->key_size) == 0) + return (tbl->entries[hash]); + + hash = (hash == tbl->table_size) ? 0 : hash + 1; + } +} + +int +hashtable_get(hashtable *tbl, const void *key, void *value) +{ + hashtable_entry *entry; + + entry = hashtable_lookup(tbl, key); + if (entry == NULL) + return (-1); + + memcpy(value, &entry->value, tbl->value_size); + return (0); +} + +int +hashtable_remove(hashtable *tbl, const void *key) +{ + hashtable_entry *entry; + + entry = hashtable_lookup(tbl, key); + if (entry == NULL) + return (-1); + +// free(entry->key); +// free(entry->value); + free(entry); + + tbl->usage--; + + return (0); +} + +void +hashtable_free(hashtable *tbl) +{ + + if (tbl == NULL) + return; + + for (int i = 0; i < tbl->table_size; i++) + if (tbl->entries[i] != NULL) { +// free(tbl->entries[i]->key); +// free(tbl->entries[i]->value); +// free(tbl->entries[i]); + } + free(tbl->entries); +} Added: user/gabor/tre-integration/contrib/tre/lib/hashtable.h ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ user/gabor/tre-integration/contrib/tre/lib/hashtable.h Mon Jun 27 22:13:15 2011 (r223614) @@ -0,0 +1,46 @@ +/*- + * Copyright (C) 2011 Gabor Kovesdan + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include + +typedef struct { + void *key; + void *value; +} hashtable_entry; + +typedef struct { + size_t key_size; + size_t table_size; + size_t usage; + size_t value_size; + hashtable_entry **entries; +} hashtable; + +void hashtable_free(hashtable *); +int hashtable_get(hashtable *, const void *, void *); +hashtable *hashtable_init(size_t, size_t, size_t); +int hashtable_put(hashtable *, const void *, const void *); +int hashtable_remove(hashtable *, const void *); From owner-svn-src-user@FreeBSD.ORG Tue Jun 28 01:32:18 2011 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 90C2F106566B; Tue, 28 Jun 2011 01:32:18 +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 818798FC13; Tue, 28 Jun 2011 01:32:18 +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 p5S1WIkD022434; Tue, 28 Jun 2011 01:32:18 GMT (envelope-from gabor@svn.freebsd.org) Received: (from gabor@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id p5S1WIjg022432; Tue, 28 Jun 2011 01:32:18 GMT (envelope-from gabor@svn.freebsd.org) Message-Id: <201106280132.p5S1WIjg022432@svn.freebsd.org> From: Gabor Kovesdan Date: Tue, 28 Jun 2011 01:32:18 +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: r223617 - user/gabor/tre-integration/usr.bin/grep 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 Jun 2011 01:32:18 -0000 Author: gabor Date: Tue Jun 28 01:32:18 2011 New Revision: 223617 URL: http://svn.freebsd.org/changeset/base/223617 Log: - Reduce diffs from HEAD Modified: user/gabor/tre-integration/usr.bin/grep/Makefile Modified: user/gabor/tre-integration/usr.bin/grep/Makefile ============================================================================== --- user/gabor/tre-integration/usr.bin/grep/Makefile Tue Jun 28 00:58:12 2011 (r223616) +++ user/gabor/tre-integration/usr.bin/grep/Makefile Tue Jun 28 01:32:18 2011 (r223617) @@ -2,9 +2,16 @@ # $FreeBSD$ # $OpenBSD: Makefile,v 1.6 2003/06/25 15:00:04 millert Exp $ +.include + +.if ${MK_BSD_GREP} == "yes" PROG= grep +.else +PROG= bsdgrep +.endif SRCS= file.c grep.c queue.c util.c +.if ${MK_BSD_GREP} == "yes" LINKS= ${BINDIR}/grep ${BINDIR}/egrep \ ${BINDIR}/grep ${BINDIR}/fgrep \ ${BINDIR}/grep ${BINDIR}/zgrep \ @@ -16,8 +23,10 @@ MLINKS= grep.1 egrep.1 \ grep.1 zgrep.1 \ grep.1 zegrep.1 \ grep.1 zfgrep.1 +.endif -WARNS?= 6 +bsdgrep.1: grep.1 + cp ${.ALLSRC} ${.TARGET} LDADD= -lz -lbz2 DPADD= ${LIBZ} ${LIBBZ2} From owner-svn-src-user@FreeBSD.ORG Tue Jun 28 15:00:18 2011 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 0E975106564A; Tue, 28 Jun 2011 15:00:18 +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 E7E7A8FC12; Tue, 28 Jun 2011 15:00:17 +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 p5SF0HZo054308; Tue, 28 Jun 2011 15:00:17 GMT (envelope-from gabor@svn.freebsd.org) Received: (from gabor@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id p5SF0HuD054305; Tue, 28 Jun 2011 15:00:17 GMT (envelope-from gabor@svn.freebsd.org) Message-Id: <201106281500.p5SF0HuD054305@svn.freebsd.org> From: Gabor Kovesdan Date: Tue, 28 Jun 2011 15:00:17 +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: r223646 - 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 Jun 2011 15:00:18 -0000 Author: gabor Date: Tue Jun 28 15:00:17 2011 New Revision: 223646 URL: http://svn.freebsd.org/changeset/base/223646 Log: - Avoid multiple inclusions of hashtable.h - Make this code WARNS=6 clean Modified: user/gabor/tre-integration/contrib/tre/lib/hashtable.c user/gabor/tre-integration/contrib/tre/lib/hashtable.h Modified: user/gabor/tre-integration/contrib/tre/lib/hashtable.c ============================================================================== --- user/gabor/tre-integration/contrib/tre/lib/hashtable.c Tue Jun 28 14:40:17 2011 (r223645) +++ user/gabor/tre-integration/contrib/tre/lib/hashtable.c Tue Jun 28 15:00:17 2011 (r223646) @@ -56,7 +56,6 @@ hashtable int hashtable_put(hashtable *tbl, const void *key, const void *value) { - hashtable_entry *entry; uint32_t hash = 0; if (tbl->table_size == tbl->usage) @@ -149,7 +148,7 @@ hashtable_free(hashtable *tbl) if (tbl == NULL) return; - for (int i = 0; i < tbl->table_size; i++) + for (unsigned int i = 0; i < tbl->table_size; i++) if (tbl->entries[i] != NULL) { // free(tbl->entries[i]->key); // free(tbl->entries[i]->value); Modified: user/gabor/tre-integration/contrib/tre/lib/hashtable.h ============================================================================== --- user/gabor/tre-integration/contrib/tre/lib/hashtable.h Tue Jun 28 14:40:17 2011 (r223645) +++ user/gabor/tre-integration/contrib/tre/lib/hashtable.h Tue Jun 28 15:00:17 2011 (r223646) @@ -24,6 +24,9 @@ * SUCH DAMAGE. */ +#ifndef HASHTABLE_H +#define HASHTABLE_H 1 + #include typedef struct { @@ -44,3 +47,5 @@ int hashtable_get(hashtable *, const v hashtable *hashtable_init(size_t, size_t, size_t); int hashtable_put(hashtable *, const void *, const void *); int hashtable_remove(hashtable *, const void *); + +#endif /* HASHTABLE.H */ From owner-svn-src-user@FreeBSD.ORG Tue Jun 28 15:19:46 2011 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 1345C106566B; Tue, 28 Jun 2011 15:19:46 +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 025F18FC15; Tue, 28 Jun 2011 15:19:46 +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 p5SFJjXF054930; Tue, 28 Jun 2011 15:19:45 GMT (envelope-from gabor@svn.freebsd.org) Received: (from gabor@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id p5SFJjkt054928; Tue, 28 Jun 2011 15:19:45 GMT (envelope-from gabor@svn.freebsd.org) Message-Id: <201106281519.p5SFJjkt054928@svn.freebsd.org> From: Gabor Kovesdan Date: Tue, 28 Jun 2011 15:19:45 +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: r223647 - 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 Jun 2011 15:19:46 -0000 Author: gabor Date: Tue Jun 28 15:19:45 2011 New Revision: 223647 URL: http://svn.freebsd.org/changeset/base/223647 Log: - Add fixed string matching code. It is not tested yet but compiles with WARNS=6 and tries to suit TRE's coding style for future upstream submission. This code will be used to match literal and literal + .$^ patterns with a fixed string matching algorithm, which is currently the quick search algorithm but may be switched to Boyer-Moore or some variant if it proves more efficient. This is also a base for heuristical matching, where the heavy regex matching algorithm is only used for smaller contexts that possibly match the regular expression. The code is not integrated yet to TRE, those changes will follow. This code has been refactored from BSD grep. Added: user/gabor/tre-integration/contrib/tre/lib/fastmatch.c (contents, props changed) user/gabor/tre-integration/contrib/tre/lib/fastmatch.h (contents, props changed) Added: user/gabor/tre-integration/contrib/tre/lib/fastmatch.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ user/gabor/tre-integration/contrib/tre/lib/fastmatch.c Tue Jun 28 15:19:45 2011 (r223647) @@ -0,0 +1,368 @@ +/*- + * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav + * Copyright (C) 2008-2011 Gabor Kovesdan + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#ifdef HAVE_CONFIG_H +#include +#endif /* HAVE_CONFIG_H */ +#include +#include +#include +#include +#include +#include + +#include "fastmatch.h" +#include "hashtable.h" +#include "tre.h" +#include "xmalloc.h" + +static int fastcmp(const tre_char_t *, const tre_char_t *, size_t); +static void revstr(tre_char_t *, int); + +#ifdef TRE_WCHAR +#define TRE_CHAR(n) L##n +#else +#define TRE_CHAR(n) n +#endif + +/* + * Returns: -1 on failure, 0 on success + */ +int +tre_fastcomp_literal(fastmatch_t *fg, const tre_char_t *pat, size_t n, int cflags) +{ + + /* Initialize. */ + fg->len = n; + fg->bol = false; + fg->eol = false; + fg->reversed = false; + fg->cflags = cflags; + fg->pattern = xmalloc((n + 1) * sizeof(tre_char_t)); + memcpy(&fg->pattern, pat, n * sizeof(tre_char_t)); + fg->pattern[n] = TRE_CHAR('\0'); + + /* Preprocess pattern. */ +#ifdef TRE_WCHAR + fg->defBc = fg->len; + fg->qsBc = hashtable_init(fg->len, sizeof(tre_char_t), sizeof(int)); + if (fg->qsBc == NULL) + return -1; + for (unsigned int i = 1; i < fg->len; i++) + { + int k = fg->len - i; + hashtable_put(fg->qsBc, &fg->pattern[i], &k); + } +#else + for (i = 0; i <= UCHAR_MAX; i++) + fg->qsBc[i] = fg->len; + for (i = 1; i < fg->len; i++) + fg->qsBc[fg->pattern[i]] = fg->len - i; +#endif + + return 0; +} + +/* + * Returns: -1 on failure, 0 on success + */ +int +tre_fastcomp(fastmatch_t *fg, const tre_char_t *pat, size_t n, int cflags) +{ + int firstHalfDot = -1; + int firstLastHalfDot = -1; + int hasDot = 0; + int lastHalfDot = 0; + + /* Initialize. */ + fg->len = n; + fg->bol = false; + fg->eol = false; + fg->reversed = false; + fg->word = false; + fg->cflags = cflags; + + /* Remove end-of-line character ('$'). */ + if (fg->len > 0 && pat[fg->len - 1] == TRE_CHAR('$')) + { + fg->eol = true; + fg->len--; + } + + /* Remove beginning-of-line character ('^'). */ + if (pat[0] == TRE_CHAR('^')) + { + fg->bol = true; + fg->len--; + pat++; + } + + if (fg->len >= 14 && + memcmp(pat, TRE_CHAR("[[:<:]]"), 7 * sizeof(tre_char_t)) == 0 && + memcmp(pat + fg->len - 7, TRE_CHAR("[[:>:]]"), 7 * sizeof(tre_char_t)) == 0) + { + fg->len -= 14; + pat += 7; + fg->word = true; + } + + /* + * pat has been adjusted earlier to not include '^', '$' or + * the word match character classes at the beginning and ending + * of the string respectively. + */ + fg->pattern = xmalloc((fg->len + 1) * sizeof(tre_char_t)); + memcpy(fg->pattern, pat, fg->len * sizeof(tre_char_t)); + fg->pattern[fg->len] = TRE_CHAR('\0'); + + /* Look for ways to cheat...er...avoid the full regex engine. */ + for (unsigned int i = 0; i < fg->len; i++) { + /* Can still cheat? */ +#ifdef TRE_WCHAR + if ((iswalnum(fg->pattern[i])) || iswspace(fg->pattern[i]) || +#else + if ((isalnum(fg->pattern[i])) || isspace(fg->pattern[i]) || +#endif + (fg->pattern[i] == TRE_CHAR('_')) || (fg->pattern[i] == TRE_CHAR(',')) || + (fg->pattern[i] == TRE_CHAR('=')) || (fg->pattern[i] == TRE_CHAR('-')) || + (fg->pattern[i] == TRE_CHAR(':')) || (fg->pattern[i] == TRE_CHAR('/'))) { + continue; + } else if (fg->pattern[i] == TRE_CHAR('\0')) { + hasDot = i; + if (i < fg->len / 2) { + if (firstHalfDot < 0) + /* Closest dot to the beginning */ + firstHalfDot = i; + } else { + /* Closest dot to the end of the pattern. */ + lastHalfDot = i; + if (firstLastHalfDot < 0) + firstLastHalfDot = i; + } + } else { + /* Free memory and let others know this is empty. */ + free(fg->pattern); + fg->pattern = NULL; + return (-1); + } + } + + /* + * Determine if a reverse search would be faster based on the placement + * of the dots. + */ + if ((!(fg->bol || fg->eol)) && + (lastHalfDot && ((firstHalfDot < 0) || + ((fg->len - (lastHalfDot + 1)) < (size_t)firstHalfDot)))) { + fg->reversed = true; + hasDot = fg->len - (firstHalfDot < 0 ? + firstLastHalfDot : firstHalfDot) - 1; + revstr(fg->pattern, fg->len); + } + + /* + * Normal Quick Search would require a shift based on the position the + * next character after the comparison is within the pattern. With + * wildcards, the position of the last dot effects the maximum shift + * distance. + * The closer to the end the wild card is the slower the search. A + * reverse version of this algorithm would be useful for wildcards near + * the end of the string. + * + * Examples: + * Pattern Max shift + * ------- --------- + * this 5 + * .his 4 + * t.is 3 + * th.s 2 + * thi. 1 + */ + +#ifdef TRE_WCHAR + /* Adjust the shift based on location of the last dot ('.'). */ + fg->defBc = fg->len - hasDot; + + /* Preprocess pattern. */ + fg->qsBc = hashtable_init(fg->len, sizeof(tre_char_t), sizeof(int)); + for (unsigned int i = hasDot + 1; i < fg->len; i++) + { + int k = fg->len - i; + hashtable_put(fg->qsBc, &fg->pattern[i], &k); + } +#else + /* Preprocess pattern. */ + for (unsigned int i = 0; i <= (signed)UCHAR_MAX; i++) + fg->qsBc[i] = fg->len - hasDot; + for (unsigned int i = hasDot + 1; i < fg->len; i++) { + fg->qsBc[fg->pattern[i]] = fg->len - i; + } +#endif + + /* + * Put pattern back to normal after pre-processing to allow for easy + * comparisons later. + */ + if (fg->reversed) + revstr(fg->pattern, fg->len); + + return (0); +} + +int +tre_fastexec(const fastmatch_t *fg, const tre_char_t *data, size_t len, + int nmatch, regmatch_t *pmatch) +{ + unsigned int j; + int cnt = 0; + int ret = REG_NOMATCH; + + /* No point in going farther if we do not have enough data. */ + if (len < fg->len) + return (ret); + + /* Only try once at the beginning or ending of the line. */ + if (fg->bol || fg->eol) { + /* Simple text comparison. */ + if (!((fg->bol && fg->eol) && (len != fg->len))) { + /* Determine where in data to start search at. */ + j = fg->eol ? len - fg->len : 0; + if (fastcmp(fg->pattern, data + j, + fg->len) == -1) { + pmatch->rm_so = j; + pmatch->rm_eo = j + fg->len; + ret = 0; + } + } + } else if (fg->reversed) { + /* Quick Search algorithm. */ + j = len; + do { + if (fastcmp(fg->pattern, data + j - fg->len, + fg->len) == -1) { + if (!(fg->cflags & REG_NOSUB)) + return (0); + pmatch[cnt++].rm_so = j - fg->len; + pmatch[cnt++].rm_eo = j; + nmatch--; + if (nmatch < 1) + return (0); + else { + j -= 2 * fg->len; + continue; + } + } + /* Shift if within bounds, otherwise, we are done. */ + if (((long)j - (long)fg->len - 1) < 0) + break; +#ifdef TRE_WCHAR + { + int k, r; + + r = hashtable_get(fg->qsBc, &data[j - fg->len - 1], &k); + k = (r == 0) ? k : fg->defBc; + j -= k; + } +#else + j -= fg->qsBc[data[j - fg->len - 1]]; +#endif + } while (j >= fg->len); + } else { + /* Quick Search algorithm. */ + j = 0; + do { + if (fastcmp(fg->pattern, data + j, fg->len) == -1) { + if (!(fg->cflags & REG_NOSUB)) + return (0); + pmatch[cnt++].rm_so = j; + pmatch[cnt++].rm_eo = j + fg->len; + nmatch--; + if (nmatch < 1) + return (0); + else { + j += fg->len; + continue; + } + } + + /* Shift if within bounds, otherwise, we are done. */ + if ((j + fg->len) >= len) + break; +#ifdef TRE_WCHAR + { + int k, r; + + r = hashtable_get(fg->qsBc, &data[j + fg->len], &k); + k = (r == 0) ? k : fg->defBc; + j += k; + } +#else + j += fg->qsBc[data[j + fg->len]]; +#endif + } while (j <= (len - fg->len)); + } + return (ret); +} + +void +tre_fastfree(fastmatch_t *fg) +{ + +#ifdef TRE_WCHAR + hashtable_free(fg->qsBc); +#endif + free(fg->pattern); +} + +/* + * Returns: i >= 0 on failure (position that it failed) + * -1 on success + */ +static inline int +fastcmp(const tre_char_t *pat, const tre_char_t *data, size_t len) +{ + + for (unsigned int i = 0; i < len; i++) { + if ((pat[i] == data[i]) || (pat[i] == TRE_CHAR('.'))) + continue; + return (i); + } + return (-1); +} + +static inline void +revstr(tre_char_t *str, int len) +{ + tre_char_t c; + + for (int i = 0; i < len / 2; i++) + { + c = str[i]; + str[i] = str[len - i - 1]; + str[len - i - 1] = c; + } +} Added: user/gabor/tre-integration/contrib/tre/lib/fastmatch.h ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ user/gabor/tre-integration/contrib/tre/lib/fastmatch.h Tue Jun 28 15:19:45 2011 (r223647) @@ -0,0 +1,59 @@ +/*- + * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav + * Copyright (c) 2008-2011 Gabor Kovesdan + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#ifndef FASTMATCH_H +#define FASTMATCH_H 1 + +#include "hashtable.h" +#include "tre.h" + +typedef struct { + size_t len; + tre_char_t *pattern; +#ifdef TRE_WCHAR + int defBc; + hashtable *qsBc; +#else + int qsBc[UCHAR_MAX + 1]; +#endif + /* flags */ + int cflags; + bool bol; + bool eol; + bool reversed; + bool word; +} fastmatch_t; + +int tre_fastcomp_literal(fastmatch_t *preg, const tre_char_t *regex, + size_t, int cflags); +int tre_fastcomp(fastmatch_t *preg, const tre_char_t *regex, size_t, + int cflags); +int tre_fastexec(const fastmatch_t *fg, const tre_char_t *data, + size_t len, int nmatch, regmatch_t *pmatch); +void tre_fastfree(fastmatch_t *preg); + +#endif /* FASTMATCH_H */ From owner-svn-src-user@FreeBSD.ORG Wed Jun 29 01:31:09 2011 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 926711065675; Wed, 29 Jun 2011 01:31:09 +0000 (UTC) (envelope-from obrien@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id 6A8568FC18; Wed, 29 Jun 2011 01:31:09 +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 p5T1V9bW073470; Wed, 29 Jun 2011 01:31:09 GMT (envelope-from obrien@svn.freebsd.org) Received: (from obrien@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id p5T1V9SF073469; Wed, 29 Jun 2011 01:31:09 GMT (envelope-from obrien@svn.freebsd.org) Message-Id: <201106290131.p5T1V9SF073469@svn.freebsd.org> From: "David E. O'Brien" Date: Wed, 29 Jun 2011 01:31:09 +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: r223658 - user/obrien 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: Wed, 29 Jun 2011 01:31:09 -0000 Author: obrien Date: Wed Jun 29 01:31:09 2011 New Revision: 223658 URL: http://svn.freebsd.org/changeset/base/223658 Log: My $USER. Added: user/obrien/ From owner-svn-src-user@FreeBSD.ORG Wed Jun 29 01:32:50 2011 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 DECF6106564A; Wed, 29 Jun 2011 01:32:50 +0000 (UTC) (envelope-from obrien@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id B6AF98FC14; Wed, 29 Jun 2011 01:32: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 p5T1WoIC073555; Wed, 29 Jun 2011 01:32:50 GMT (envelope-from obrien@svn.freebsd.org) Received: (from obrien@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id p5T1WoYh073554; Wed, 29 Jun 2011 01:32:50 GMT (envelope-from obrien@svn.freebsd.org) Message-Id: <201106290132.p5T1WoYh073554@svn.freebsd.org> From: "David E. O'Brien" Date: Wed, 29 Jun 2011 01:32: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: r223659 - user/obrien/libmd-ossl 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: Wed, 29 Jun 2011 01:32:51 -0000 Author: obrien Date: Wed Jun 29 01:32:50 2011 New Revision: 223659 URL: http://svn.freebsd.org/changeset/base/223659 Log: Branch for a WIP Added: - copied from r223658, head/ Directory Properties: user/obrien/libmd-ossl/ (props changed) From owner-svn-src-user@FreeBSD.ORG Wed Jun 29 16:58:27 2011 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 C8C62106566C; Wed, 29 Jun 2011 16:58:27 +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 AE2D48FC0C; Wed, 29 Jun 2011 16:58:27 +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 p5TGwRfH006218; Wed, 29 Jun 2011 16:58:27 GMT (envelope-from gabor@svn.freebsd.org) Received: (from gabor@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id p5TGwRnF006211; Wed, 29 Jun 2011 16:58:27 GMT (envelope-from gabor@svn.freebsd.org) Message-Id: <201106291658.p5TGwRnF006211@svn.freebsd.org> From: Gabor Kovesdan Date: Wed, 29 Jun 2011 16:58:27 +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: r223680 - in user/gabor/tre-integration: contrib/tre/lib lib/libc/regex lib/libregex 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: Wed, 29 Jun 2011 16:58:27 -0000 Author: gabor Date: Wed Jun 29 16:58:27 2011 New Revision: 223680 URL: http://svn.freebsd.org/changeset/base/223680 Log: - Add new files to the build - Let the build system control whether symbols are exported as weak references and build libc with weak references and libregex with normal symbols Modified: user/gabor/tre-integration/contrib/tre/lib/regcomp.c user/gabor/tre-integration/contrib/tre/lib/regerror.c user/gabor/tre-integration/contrib/tre/lib/regexec.c user/gabor/tre-integration/contrib/tre/lib/tre.h user/gabor/tre-integration/lib/libc/regex/Makefile.inc user/gabor/tre-integration/lib/libregex/Makefile Modified: user/gabor/tre-integration/contrib/tre/lib/regcomp.c ============================================================================== --- user/gabor/tre-integration/contrib/tre/lib/regcomp.c Wed Jun 29 16:46:12 2011 (r223679) +++ user/gabor/tre-integration/contrib/tre/lib/regcomp.c Wed Jun 29 16:58:27 2011 (r223680) @@ -18,11 +18,13 @@ #include "tre.h" #include "xmalloc.h" +#ifdef TRE_WEAK_REF __weak_reference(tre_regcomp, regcomp); __weak_reference(tre_regncomp, regncomp); __weak_reference(tre_regwcomp, regwcomp); __weak_reference(tre_regwncomp, regwncomp); __weak_reference(tre_regfree, regfree); +#endif int tre_regncomp(regex_t *preg, const char *regex, size_t n, int cflags) Modified: user/gabor/tre-integration/contrib/tre/lib/regerror.c ============================================================================== --- user/gabor/tre-integration/contrib/tre/lib/regerror.c Wed Jun 29 16:46:12 2011 (r223679) +++ user/gabor/tre-integration/contrib/tre/lib/regerror.c Wed Jun 29 16:58:27 2011 (r223680) @@ -28,7 +28,9 @@ #define gettext(s) s #endif +#ifdef TRE_WEAK_REF __weak_reference(tre_regerror, regerror); +#endif #define _(String) dgettext(PACKAGE, String) #define gettext_noop(String) String Modified: user/gabor/tre-integration/contrib/tre/lib/regexec.c ============================================================================== --- user/gabor/tre-integration/contrib/tre/lib/regexec.c Wed Jun 29 16:46:12 2011 (r223679) +++ user/gabor/tre-integration/contrib/tre/lib/regexec.c Wed Jun 29 16:58:27 2011 (r223680) @@ -48,6 +48,7 @@ char *alloca (); #include "tre.h" #include "xmalloc.h" +#ifdef TRE_WEAK_REF __weak_reference(tre_regexec, regexec); __weak_reference(tre_regnexec, regnexec); __weak_reference(tre_regwexec, regwexec); @@ -57,6 +58,7 @@ __weak_reference(tre_regaexec, regaexec) __weak_reference(tre_reganexec, reganexec); __weak_reference(tre_regawexec, regawexec); __weak_reference(tre_regawnexec, regawnexec); +#endif /* Fills the POSIX.2 regmatch_t array according to the TNFA tag and match endpoint values. */ Modified: user/gabor/tre-integration/contrib/tre/lib/tre.h ============================================================================== --- user/gabor/tre-integration/contrib/tre/lib/tre.h Wed Jun 29 16:46:12 2011 (r223679) +++ user/gabor/tre-integration/contrib/tre/lib/tre.h Wed Jun 29 16:58:27 2011 (r223680) @@ -23,6 +23,24 @@ extern "C" { #endif +#ifndef TRE_WEAK_REF +#define tre_regcomp regcomp +#define tre_regerror regerror +#define tre_regexec regexec +#define tre_regfree regfree +#define tre_regaexec regaexec +#define tre_reganexec reganexec +#define tre_regawexec regawexec +#define tre_regawnexec regawnexec +#define tre_regncomp regncomp +#define tre_regnexec regnexec +#define tre_regwcomp regwcomp +#define tre_regwexec regwexec +#define tre_regwncomp regwncomp +#define tre_regwnexec regwnexec +#define tre_reguexec reguexec +#endif + /* If the we're not using system regex.h, we need to define the structs and enums ourselves. */ Modified: user/gabor/tre-integration/lib/libc/regex/Makefile.inc ============================================================================== --- user/gabor/tre-integration/lib/libc/regex/Makefile.inc Wed Jun 29 16:46:12 2011 (r223679) +++ user/gabor/tre-integration/lib/libc/regex/Makefile.inc Wed Jun 29 16:58:27 2011 (r223680) @@ -3,9 +3,10 @@ .PATH: ${.CURDIR}/../../contrib/tre/lib ${.CURDIR}/regex -CFLAGS+=-DHAVE_CONFIG_H -I${.CURDIR}/../../contrib/tre +CFLAGS+=-DHAVE_CONFIG_H -DTRE_WEAK_REF -I${.CURDIR}/../../contrib/tre -SRCS+= regcomp.c regerror.c regexec.c tre-ast.c tre-compile.c \ +SRCS+= fastmatch.c hashtable.c \ + regcomp.c regerror.c regexec.c tre-ast.c tre-compile.c \ tre-match-approx.c tre-match-backtrack.c tre-match-parallel.c \ tre-mem.c tre-parse.c tre-stack.c xmalloc.c Modified: user/gabor/tre-integration/lib/libregex/Makefile ============================================================================== --- user/gabor/tre-integration/lib/libregex/Makefile Wed Jun 29 16:46:12 2011 (r223679) +++ user/gabor/tre-integration/lib/libregex/Makefile Wed Jun 29 16:58:27 2011 (r223680) @@ -11,7 +11,8 @@ WARNS?= 6 CFLAGS+=-DHAVE_CONFIG_H -I${.CURDIR}/../../contrib/tre/lib \ -I${.CURDIR}/../../include -SRCS= regcomp.c regerror.c regexec.c tre-ast.c tre-compile.c \ +SRCS= fastmatch.c hashtable.c \ + regcomp.c regerror.c regexec.c tre-ast.c tre-compile.c \ tre-match-approx.c tre-match-backtrack.c tre-match-parallel.c \ tre-mem.c tre-parse.c tre-stack.c xmalloc.c From owner-svn-src-user@FreeBSD.ORG Thu Jun 30 14:10:49 2011 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 75973106566B; Thu, 30 Jun 2011 14:10:49 +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 646838FC16; Thu, 30 Jun 2011 14:10:49 +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 p5UEAn5X046957; Thu, 30 Jun 2011 14:10:49 GMT (envelope-from gabor@svn.freebsd.org) Received: (from gabor@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id p5UEAnPJ046950; Thu, 30 Jun 2011 14:10:49 GMT (envelope-from gabor@svn.freebsd.org) Message-Id: <201106301410.p5UEAnPJ046950@svn.freebsd.org> From: Gabor Kovesdan Date: Thu, 30 Jun 2011 14:10:49 +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: r223693 - in user/gabor/tre-integration: contrib/tre/lib include 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: Thu, 30 Jun 2011 14:10:49 -0000 Author: gabor Date: Thu Jun 30 14:10:49 2011 New Revision: 223693 URL: http://svn.freebsd.org/changeset/base/223693 Log: - Plug in the fixed string matching code Modified: user/gabor/tre-integration/contrib/tre/lib/fastmatch.c user/gabor/tre-integration/contrib/tre/lib/fastmatch.h user/gabor/tre-integration/contrib/tre/lib/regexec.c user/gabor/tre-integration/contrib/tre/lib/tre-compile.c user/gabor/tre-integration/contrib/tre/lib/tre.h user/gabor/tre-integration/include/regex.h Modified: user/gabor/tre-integration/contrib/tre/lib/fastmatch.c ============================================================================== --- user/gabor/tre-integration/contrib/tre/lib/fastmatch.c Thu Jun 30 10:56:02 2011 (r223692) +++ user/gabor/tre-integration/contrib/tre/lib/fastmatch.c Thu Jun 30 14:10:49 2011 (r223693) @@ -235,7 +235,7 @@ tre_fastcomp(fastmatch_t *fg, const tre_ int tre_fastexec(const fastmatch_t *fg, const tre_char_t *data, size_t len, - int nmatch, regmatch_t *pmatch) + int nmatch, regmatch_t pmatch[]) { unsigned int j; int cnt = 0; @@ -253,8 +253,10 @@ tre_fastexec(const fastmatch_t *fg, cons j = fg->eol ? len - fg->len : 0; if (fastcmp(fg->pattern, data + j, fg->len) == -1) { - pmatch->rm_so = j; - pmatch->rm_eo = j + fg->len; + if (!(fg->cflags & REG_NOSUB) || (nmatch < 1)) + return 0; + pmatch[cnt].rm_so = j; + pmatch[cnt].rm_eo = j + fg->len; ret = 0; } } @@ -264,7 +266,7 @@ tre_fastexec(const fastmatch_t *fg, cons do { if (fastcmp(fg->pattern, data + j - fg->len, fg->len) == -1) { - if (!(fg->cflags & REG_NOSUB)) + if (!(fg->cflags & REG_NOSUB) || (nmatch < 1)) return (0); pmatch[cnt++].rm_so = j - fg->len; pmatch[cnt++].rm_eo = j; @@ -296,7 +298,7 @@ tre_fastexec(const fastmatch_t *fg, cons j = 0; do { if (fastcmp(fg->pattern, data + j, fg->len) == -1) { - if (!(fg->cflags & REG_NOSUB)) + if (!(fg->cflags & REG_NOSUB) || (nmatch < 1)) return (0); pmatch[cnt++].rm_so = j; pmatch[cnt++].rm_eo = j + fg->len; Modified: user/gabor/tre-integration/contrib/tre/lib/fastmatch.h ============================================================================== --- user/gabor/tre-integration/contrib/tre/lib/fastmatch.h Thu Jun 30 10:56:02 2011 (r223692) +++ user/gabor/tre-integration/contrib/tre/lib/fastmatch.h Thu Jun 30 14:10:49 2011 (r223693) @@ -28,6 +28,8 @@ #ifndef FASTMATCH_H #define FASTMATCH_H 1 +#include + #include "hashtable.h" #include "tre.h" @@ -53,7 +55,7 @@ int tre_fastcomp_literal(fastmatch_t *pr int tre_fastcomp(fastmatch_t *preg, const tre_char_t *regex, size_t, int cflags); int tre_fastexec(const fastmatch_t *fg, const tre_char_t *data, - size_t len, int nmatch, regmatch_t *pmatch); + size_t len, int nmatch, regmatch_t pmatch[]); void tre_fastfree(fastmatch_t *preg); #endif /* FASTMATCH_H */ Modified: user/gabor/tre-integration/contrib/tre/lib/regexec.c ============================================================================== --- user/gabor/tre-integration/contrib/tre/lib/regexec.c Thu Jun 30 10:56:02 2011 (r223692) +++ user/gabor/tre-integration/contrib/tre/lib/regexec.c Thu Jun 30 14:10:49 2011 (r223693) @@ -44,6 +44,7 @@ char *alloca (); #endif /* HAVE_MALLOC_H */ #include +#include "fastmatch.h" #include "tre-internal.h" #include "tre.h" #include "xmalloc.h" @@ -150,10 +151,16 @@ tre_have_approx(const regex_t *preg) static int tre_match(const tre_tnfa_t *tnfa, const void *string, size_t len, tre_str_type_t type, size_t nmatch, regmatch_t pmatch[], - int eflags) + int eflags, void *shortcut) { reg_errcode_t status; int *tags = NULL, eo; + + /* Check if we can cheat with a fixed string */ + if (shortcut != NULL) + return tre_fastexec((fastmatch_t *)shortcut, (const tre_char_t *)string, + len, nmatch, pmatch); + if (tnfa->num_tags > 0 && nmatch > 0) { #ifdef TRE_USE_ALLOCA @@ -222,7 +229,8 @@ tre_regnexec(const regex_t *preg, const size_t slen = (size_t)(pmatch[0].rm_eo - pmatch[0].rm_so); size_t offset = pmatch[0].rm_so; str = &str[offset]; - int ret = tre_match(tnfa, str, slen, type, nmatch, pmatch, eflags); + int ret = tre_match(tnfa, str, slen, type, nmatch, pmatch, eflags, + preg->shortcut); if (!(eflags & REG_NOSUB)) { for (unsigned i = 0; i < nmatch; i++) @@ -235,7 +243,8 @@ tre_regnexec(const regex_t *preg, const } else { - return tre_match(tnfa, str, len, type, nmatch, pmatch, eflags); + return tre_match(tnfa, str, len, type, nmatch, pmatch, eflags, + preg->shortcut); } } @@ -260,7 +269,8 @@ tre_regwnexec(const regex_t *preg, const size_t slen = (size_t)(pmatch[0].rm_eo - pmatch[0].rm_so); size_t offset = pmatch[0].rm_so; str = &str[offset]; - int ret = tre_match(tnfa, str, slen, STR_WIDE, nmatch, pmatch, eflags); + int ret = tre_match(tnfa, str, slen, STR_WIDE, nmatch, pmatch, eflags, + preg->shortcut); if (!(eflags & REG_NOSUB)) { for (unsigned i = 0; i < nmatch; i++) @@ -273,7 +283,8 @@ tre_regwnexec(const regex_t *preg, const } else { - return tre_match(tnfa, str, len, STR_WIDE, nmatch, pmatch, eflags); + return tre_match(tnfa, str, len, STR_WIDE, nmatch, pmatch, eflags, + preg->shortcut); } } @@ -291,7 +302,8 @@ tre_reguexec(const regex_t *preg, const size_t nmatch, regmatch_t pmatch[], int eflags) { tre_tnfa_t *tnfa = (void *)preg->TRE_REGEX_T_FIELD; - return tre_match(tnfa, str, (unsigned)-1, STR_USER, nmatch, pmatch, eflags); + return tre_match(tnfa, str, (unsigned)-1, STR_USER, nmatch, pmatch, eflags, + preg->shortcut); } @@ -315,7 +327,7 @@ tre_match_approx(const tre_tnfa_t *tnfa, if (params.max_cost == 0 && !tnfa->have_approx && !(eflags & REG_APPROX_MATCHER)) return tre_match(tnfa, string, len, type, match->nmatch, match->pmatch, - eflags); + eflags, NULL); /* Back references are not supported by the approximate matcher. */ if (tnfa->have_backrefs) Modified: user/gabor/tre-integration/contrib/tre/lib/tre-compile.c ============================================================================== --- user/gabor/tre-integration/contrib/tre/lib/tre-compile.c Thu Jun 30 10:56:02 2011 (r223692) +++ user/gabor/tre-integration/contrib/tre/lib/tre-compile.c Thu Jun 30 14:10:49 2011 (r223693) @@ -20,6 +20,7 @@ #include #include +#include "fastmatch.h" #include "tre-internal.h" #include "tre-mem.h" #include "tre-stack.h" @@ -1858,17 +1859,30 @@ tre_compile(regex_t *preg, const tre_cha tre_ast_node_t *tree, *tmp_ast_l, *tmp_ast_r; tre_pos_and_tags_t *p; int *counts = NULL, *offs = NULL; - int i, add = 0; + int i, add = 0, ret; tre_tnfa_transition_t *transitions, *initial; tre_tnfa_t *tnfa = NULL; tre_submatch_data_t *submatch_data; tre_tag_direction_t *tag_directions = NULL; reg_errcode_t errcode; tre_mem_t mem; + fastmatch_t shortcut; /* Parse context. */ tre_parse_ctx_t parse_ctx; + /* Check if we can cheat with a fixed string algorithm. */ + ret = (cflags & REG_LITERAL) + ? tre_fastcomp_literal(&shortcut, regex, n, cflags) + : tre_fastcomp(&shortcut, regex, n, cflags); + if (!ret) + { + preg->shortcut = &shortcut; + return REG_OK; + } + else + preg->shortcut = NULL; + /* Allocate a stack used throughout the compilation process for various purposes. */ stack = tre_stack_new(512, 10240, 128); Modified: user/gabor/tre-integration/contrib/tre/lib/tre.h ============================================================================== --- user/gabor/tre-integration/contrib/tre/lib/tre.h Thu Jun 30 10:56:02 2011 (r223692) +++ user/gabor/tre-integration/contrib/tre/lib/tre.h Thu Jun 30 14:10:49 2011 (r223693) @@ -48,6 +48,7 @@ typedef int regoff_t; typedef struct { size_t re_nsub; /* Number of parenthesized subexpressions. */ void *value; /* For internal use only. */ + void *shortcut; /* For internal use only. */ const char *re_endp; } regex_t; Modified: user/gabor/tre-integration/include/regex.h ============================================================================== --- user/gabor/tre-integration/include/regex.h Thu Jun 30 10:56:02 2011 (r223692) +++ user/gabor/tre-integration/include/regex.h Thu Jun 30 14:10:49 2011 (r223693) @@ -40,6 +40,7 @@ typedef int regoff_t; typedef struct { size_t re_nsub; /* Number of parenthesized subexpressions. */ void *value; /* For internal use only. */ + void *shortcut; /* For internal use only. */ const char *re_endp; } regex_t; From owner-svn-src-user@FreeBSD.ORG Thu Jun 30 16:13:00 2011 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 B744E106564A; Thu, 30 Jun 2011 16:13:00 +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 A7D058FC08; Thu, 30 Jun 2011 16:13:00 +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 p5UGD0xb050753; Thu, 30 Jun 2011 16:13:00 GMT (envelope-from gabor@svn.freebsd.org) Received: (from gabor@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id p5UGD0d7050751; Thu, 30 Jun 2011 16:13:00 GMT (envelope-from gabor@svn.freebsd.org) Message-Id: <201106301613.p5UGD0d7050751@svn.freebsd.org> From: Gabor Kovesdan Date: Thu, 30 Jun 2011 16:13:00 +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: r223696 - 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: Thu, 30 Jun 2011 16:13:00 -0000 Author: gabor Date: Thu Jun 30 16:13:00 2011 New Revision: 223696 URL: http://svn.freebsd.org/changeset/base/223696 Log: - When shortcut is possible, there are no subexpressions Modified: user/gabor/tre-integration/contrib/tre/lib/tre-compile.c Modified: user/gabor/tre-integration/contrib/tre/lib/tre-compile.c ============================================================================== --- user/gabor/tre-integration/contrib/tre/lib/tre-compile.c Thu Jun 30 16:08:56 2011 (r223695) +++ user/gabor/tre-integration/contrib/tre/lib/tre-compile.c Thu Jun 30 16:13:00 2011 (r223696) @@ -1878,6 +1878,7 @@ tre_compile(regex_t *preg, const tre_cha if (!ret) { preg->shortcut = &shortcut; + preg->re_nsub = 0; return REG_OK; } else From owner-svn-src-user@FreeBSD.ORG Sat Jul 2 20:14:40 2011 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 D8E0B106564A; Sat, 2 Jul 2011 20:14:40 +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 C7CDB8FC18; Sat, 2 Jul 2011 20:14:40 +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 p62KEewK054193; Sat, 2 Jul 2011 20:14:40 GMT (envelope-from gabor@svn.freebsd.org) Received: (from gabor@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id p62KEefU054187; Sat, 2 Jul 2011 20:14:40 GMT (envelope-from gabor@svn.freebsd.org) Message-Id: <201107022014.p62KEefU054187@svn.freebsd.org> From: Gabor Kovesdan Date: Sat, 2 Jul 2011 20:14:40 +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: r223726 - 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: Sat, 02 Jul 2011 20:14:40 -0000 Author: gabor Date: Sat Jul 2 20:14:40 2011 New Revision: 223726 URL: http://svn.freebsd.org/changeset/base/223726 Log: - Fix some bugs - Refactor to support single-byte, multi-byte and wide character strings; at the moment still not complete - Be more consistent to TRE coding style Modified: user/gabor/tre-integration/contrib/tre/lib/fastmatch.c user/gabor/tre-integration/contrib/tre/lib/fastmatch.h user/gabor/tre-integration/contrib/tre/lib/regcomp.c user/gabor/tre-integration/contrib/tre/lib/regexec.c user/gabor/tre-integration/contrib/tre/lib/tre-compile.c Modified: user/gabor/tre-integration/contrib/tre/lib/fastmatch.c ============================================================================== --- user/gabor/tre-integration/contrib/tre/lib/fastmatch.c Sat Jul 2 18:43:35 2011 (r223725) +++ user/gabor/tre-integration/contrib/tre/lib/fastmatch.c Sat Jul 2 20:14:40 2011 (r223726) @@ -38,9 +38,10 @@ #include "fastmatch.h" #include "hashtable.h" #include "tre.h" +#include "tre-internal.h" #include "xmalloc.h" -static int fastcmp(const tre_char_t *, const tre_char_t *, size_t); +static int fastcmp(const tre_char_t *, const void *, size_t, tre_str_type_t); static void revstr(tre_char_t *, int); #ifdef TRE_WCHAR @@ -49,6 +50,30 @@ static void revstr(tre_char_t *, int); #define TRE_CHAR(n) n #endif +#define SKIP_CHARS(n) \ + do { \ + switch (type) \ + { \ + case STR_BYTE: \ + startptr = str_byte + n; \ + break; \ + case STR_MBS: \ + for (skip = j = 0; j < n; j++) \ + { \ + siz = mbrlen(str_byte, MB_CUR_MAX, NULL); \ + skip += siz; \ + } \ + startptr = str_byte + skip; \ + break; \ + case STR_WIDE: \ + startptr = str_wide + n; \ + break; \ + default: \ + /* XXX */ \ + break; \ + } \ + } while (0); \ + /* * Returns: -1 on failure, 0 on success */ @@ -57,14 +82,16 @@ tre_fastcomp_literal(fastmatch_t *fg, co { /* Initialize. */ - fg->len = n; + fg->len = (n == 0) ? tre_strlen(pat) : n; fg->bol = false; fg->eol = false; fg->reversed = false; fg->cflags = cflags; - fg->pattern = xmalloc((n + 1) * sizeof(tre_char_t)); - memcpy(&fg->pattern, pat, n * sizeof(tre_char_t)); - fg->pattern[n] = TRE_CHAR('\0'); + fg->pattern = xmalloc((fg->len + 1) * sizeof(tre_char_t)); + if (fg->pattern == NULL) + return -1; + memcpy(fg->pattern, pat, fg->len * sizeof(tre_char_t)); + fg->pattern[fg->len] = TRE_CHAR('\0'); /* Preprocess pattern. */ #ifdef TRE_WCHAR @@ -84,7 +111,7 @@ tre_fastcomp_literal(fastmatch_t *fg, co fg->qsBc[fg->pattern[i]] = fg->len - i; #endif - return 0; + return REG_OK; } /* @@ -99,7 +126,7 @@ tre_fastcomp(fastmatch_t *fg, const tre_ int lastHalfDot = 0; /* Initialize. */ - fg->len = n; + fg->len = (n == 0) ? tre_strlen(pat) : n; fg->bol = false; fg->eol = false; fg->reversed = false; @@ -107,7 +134,7 @@ tre_fastcomp(fastmatch_t *fg, const tre_ fg->cflags = cflags; /* Remove end-of-line character ('$'). */ - if (fg->len > 0 && pat[fg->len - 1] == TRE_CHAR('$')) + if ((fg->len > 0) && (pat[fg->len - 1] == TRE_CHAR('$'))) { fg->eol = true; fg->len--; @@ -121,9 +148,9 @@ tre_fastcomp(fastmatch_t *fg, const tre_ pat++; } - if (fg->len >= 14 && - memcmp(pat, TRE_CHAR("[[:<:]]"), 7 * sizeof(tre_char_t)) == 0 && - memcmp(pat + fg->len - 7, TRE_CHAR("[[:>:]]"), 7 * sizeof(tre_char_t)) == 0) + if ((fg->len >= 14) && + (memcmp(pat, TRE_CHAR("[[:<:]]"), 7 * sizeof(tre_char_t)) == 0) && + (memcmp(pat + fg->len - 7, TRE_CHAR("[[:>:]]"), 7 * sizeof(tre_char_t)) == 0)) { fg->len -= 14; pat += 7; @@ -167,7 +194,7 @@ tre_fastcomp(fastmatch_t *fg, const tre_ /* Free memory and let others know this is empty. */ free(fg->pattern); fg->pattern = NULL; - return (-1); + return -1; } } @@ -230,20 +257,43 @@ tre_fastcomp(fastmatch_t *fg, const tre_ if (fg->reversed) revstr(fg->pattern, fg->len); - return (0); + return REG_OK; } int -tre_fastexec(const fastmatch_t *fg, const tre_char_t *data, size_t len, - int nmatch, regmatch_t pmatch[]) +tre_fastexec(const fastmatch_t *fg, const void *data, size_t len, + tre_str_type_t type, int nmatch, regmatch_t pmatch[]) { unsigned int j; + size_t siz, skip; int cnt = 0; int ret = REG_NOMATCH; + const char *str_byte = data; + const void *startptr; +#ifdef TRE_WCHAR + const wchar_t *str_wide = data; +#endif + + if (len == (unsigned)-1) + { + switch (type) + { + case STR_BYTE: + case STR_MBS: + len = strlen(str_byte); + break; + case STR_WIDE: + len = wcslen(str_wide); + break; + default: + /* XXX */ + break; + } + } /* No point in going farther if we do not have enough data. */ if (len < fg->len) - return (ret); + return ret; /* Only try once at the beginning or ending of the line. */ if (fg->bol || fg->eol) { @@ -251,28 +301,29 @@ tre_fastexec(const fastmatch_t *fg, cons if (!((fg->bol && fg->eol) && (len != fg->len))) { /* Determine where in data to start search at. */ j = fg->eol ? len - fg->len : 0; - if (fastcmp(fg->pattern, data + j, - fg->len) == -1) { + SKIP_CHARS(j); + if (fastcmp(fg->pattern, startptr, fg->len, type) == -1) { if (!(fg->cflags & REG_NOSUB) || (nmatch < 1)) - return 0; + return REG_OK; pmatch[cnt].rm_so = j; pmatch[cnt].rm_eo = j + fg->len; - ret = 0; + return REG_OK; } } } else if (fg->reversed) { /* Quick Search algorithm. */ j = len; do { - if (fastcmp(fg->pattern, data + j - fg->len, - fg->len) == -1) { + SKIP_CHARS(j - fg->len); + if (fastcmp(fg->pattern, startptr, fg->len, type) == -1) { if (!(fg->cflags & REG_NOSUB) || (nmatch < 1)) - return (0); + return REG_OK; pmatch[cnt++].rm_so = j - fg->len; pmatch[cnt++].rm_eo = j; nmatch--; + ret = REG_OK; if (nmatch < 1) - return (0); + return ret; else { j -= 2 * fg->len; continue; @@ -297,14 +348,16 @@ tre_fastexec(const fastmatch_t *fg, cons /* Quick Search algorithm. */ j = 0; do { - if (fastcmp(fg->pattern, data + j, fg->len) == -1) { + SKIP_CHARS(j); + if (fastcmp(fg->pattern, startptr, fg->len, type) == -1) { if (!(fg->cflags & REG_NOSUB) || (nmatch < 1)) - return (0); + return REG_OK; pmatch[cnt++].rm_so = j; pmatch[cnt++].rm_eo = j + fg->len; nmatch--; + ret = REG_OK; if (nmatch < 1) - return (0); + return ret; else { j += fg->len; continue; @@ -327,7 +380,7 @@ tre_fastexec(const fastmatch_t *fg, cons #endif } while (j <= (len - fg->len)); } - return (ret); + return ret; } void @@ -345,15 +398,45 @@ tre_fastfree(fastmatch_t *fg) * -1 on success */ static inline int -fastcmp(const tre_char_t *pat, const tre_char_t *data, size_t len) +fastcmp(const tre_char_t *pat, const void *data, size_t len, + tre_str_type_t type) { + const char *str_byte = data; +#ifdef TRE_WCHAR + const wchar_t *str_wide = data; + wint_t wc; + size_t s; +#endif for (unsigned int i = 0; i < len; i++) { - if ((pat[i] == data[i]) || (pat[i] == TRE_CHAR('.'))) + if (pat[i] == TRE_CHAR('.')) continue; - return (i); + switch (type) + { + case STR_BYTE: + if (pat[i] == btowc(str_byte[i])) + continue; + break; + case STR_MBS: + s = mbrtowc(&wc, str_byte, MB_CUR_MAX, NULL); + if (s == (size_t)-1) + return i; + else + str_byte += s; + if (pat[i] == wc) + continue; + break; + case STR_WIDE: + if (pat[i] == str_wide[i]) + continue; + break; + default: + /* XXX */ + break; + } + return i; } - return (-1); + return -1; } static inline void Modified: user/gabor/tre-integration/contrib/tre/lib/fastmatch.h ============================================================================== --- user/gabor/tre-integration/contrib/tre/lib/fastmatch.h Sat Jul 2 18:43:35 2011 (r223725) +++ user/gabor/tre-integration/contrib/tre/lib/fastmatch.h Sat Jul 2 20:14:40 2011 (r223726) @@ -32,6 +32,7 @@ #include "hashtable.h" #include "tre.h" +#include "tre-internal.h" typedef struct { size_t len; @@ -54,8 +55,8 @@ int tre_fastcomp_literal(fastmatch_t *pr size_t, int cflags); int tre_fastcomp(fastmatch_t *preg, const tre_char_t *regex, size_t, int cflags); -int tre_fastexec(const fastmatch_t *fg, const tre_char_t *data, - size_t len, int nmatch, regmatch_t pmatch[]); +int tre_fastexec(const fastmatch_t *fg, const void *data, size_t len, + tre_str_type_t type, int nmatch, regmatch_t pmatch[]); void tre_fastfree(fastmatch_t *preg); #endif /* FASTMATCH_H */ Modified: user/gabor/tre-integration/contrib/tre/lib/regcomp.c ============================================================================== --- user/gabor/tre-integration/contrib/tre/lib/regcomp.c Sat Jul 2 18:43:35 2011 (r223725) +++ user/gabor/tre-integration/contrib/tre/lib/regcomp.c Sat Jul 2 20:14:40 2011 (r223726) @@ -110,14 +110,13 @@ tre_regncomp(regex_t *preg, const char * int tre_regcomp(regex_t *preg, const char *regex, int cflags) { - size_t len; + size_t len; - if (cflags & REG_PEND) - { - if (preg->re_endp >= regex) - len = preg->re_endp - regex; - else - len = 0; + if (cflags & REG_PEND) + { + len = (preg->re_endp >= regex) + ? preg->re_endp - regex + : 0; return tre_regncomp(preg, regex, len, cflags); } else Modified: user/gabor/tre-integration/contrib/tre/lib/regexec.c ============================================================================== --- user/gabor/tre-integration/contrib/tre/lib/regexec.c Sat Jul 2 18:43:35 2011 (r223725) +++ user/gabor/tre-integration/contrib/tre/lib/regexec.c Sat Jul 2 20:14:40 2011 (r223726) @@ -151,15 +151,14 @@ tre_have_approx(const regex_t *preg) static int tre_match(const tre_tnfa_t *tnfa, const void *string, size_t len, tre_str_type_t type, size_t nmatch, regmatch_t pmatch[], - int eflags, void *shortcut) + int eflags, fastmatch_t *shortcut) { reg_errcode_t status; int *tags = NULL, eo; /* Check if we can cheat with a fixed string */ if (shortcut != NULL) - return tre_fastexec((fastmatch_t *)shortcut, (const tre_char_t *)string, - len, nmatch, pmatch); + return tre_fastexec(shortcut, string, len, nmatch, pmatch); if (tnfa->num_tags > 0 && nmatch > 0) { Modified: user/gabor/tre-integration/contrib/tre/lib/tre-compile.c ============================================================================== --- user/gabor/tre-integration/contrib/tre/lib/tre-compile.c Sat Jul 2 18:43:35 2011 (r223725) +++ user/gabor/tre-integration/contrib/tre/lib/tre-compile.c Sat Jul 2 20:14:40 2011 (r223726) @@ -1866,23 +1866,29 @@ tre_compile(regex_t *preg, const tre_cha tre_tag_direction_t *tag_directions = NULL; reg_errcode_t errcode; tre_mem_t mem; - fastmatch_t shortcut; + fastmatch_t *shortcut; /* Parse context. */ tre_parse_ctx_t parse_ctx; /* Check if we can cheat with a fixed string algorithm. */ + shortcut = xmalloc(sizeof(fastmatch_t)); + if (!shortcut) + return REG_ESPACE; ret = (cflags & REG_LITERAL) - ? tre_fastcomp_literal(&shortcut, regex, n, cflags) - : tre_fastcomp(&shortcut, regex, n, cflags); + ? tre_fastcomp_literal(shortcut, regex, n, cflags) + : tre_fastcomp(shortcut, regex, n, cflags); if (!ret) { - preg->shortcut = &shortcut; + preg->shortcut = shortcut; preg->re_nsub = 0; return REG_OK; } else - preg->shortcut = NULL; + { + free(shortcut); + preg->shortcut = NULL; + } /* Allocate a stack used throughout the compilation process for various purposes. */