This patch is generated from the trie branch of HEAD in squid3
Tue Aug 17 18:59:06 2004 GMT
See http://devel.squid-cache.org/

Index: squid3/bootstrap.sh
diff -u squid3/bootstrap.sh:1.1 squid3/bootstrap.sh:1.1.4.1
--- squid3/bootstrap.sh:1.1	Sun Oct 13 17:20:06 2002
+++ squid3/bootstrap.sh	Mon Oct 14 19:09:40 2002
@@ -65,3 +65,5 @@
 bootstrap autoconf$acver
 
 echo "Autotool bootstrapping complete."
+echo "bootstrapping sub projects."
+cd lib/libTrie && $SHELL ./bootstrap.sh
Index: squid3/configure.in
diff -u squid3/configure.in:1.1 squid3/configure.in:1.1.4.1
--- squid3/configure.in:1.1	Sun Oct 13 17:20:06 2002
+++ squid3/configure.in	Mon Oct 14 19:09:40 2002
@@ -2366,4 +2366,7 @@
 	helpers/external_acl/wbinfo_group/Makefile \
 	helpers/external_acl/winbind_group/Makefile \
 ])
+
+AC_CONFIG_SUBDIRS(lib/libTrie)
+
 AC_OUTPUT
Index: squid3/lib/Makefile.am
diff -u squid3/lib/Makefile.am:1.1 squid3/lib/Makefile.am:1.1.4.1
--- squid3/lib/Makefile.am:1.1	Sun Oct 13 17:18:18 2002
+++ squid3/lib/Makefile.am	Mon Oct 14 19:09:41 2002
@@ -3,6 +3,8 @@
 #  $Id: squid3-trie-HEAD,v 1.2 2004/09/29 00:22:52 hno Exp $
 #
 
+SUBDIRS = libTrie
+
 if ENABLE_XPROF_STATS
 XPROF_STATS_SOURCE = Profiler.c
 else
@@ -56,6 +58,8 @@
 	uudecode.c \
 	$(XPROF_STATS_SOURCE)
 libmiscutil_a_LIBADD = \
+        libTrie/src/Trie.o \
+	libTrie/src/TrieNode.o \
 	@LIBOBJS@
 # $(top_srcdir)/include/version.h should be a dependency
 libregex_a_SOURCES = \
Index: squid3/src/HttpHdrCc.cc
diff -u squid3/src/HttpHdrCc.cc:1.1 squid3/src/HttpHdrCc.cc:1.1.4.1
--- squid3/src/HttpHdrCc.cc:1.1	Sun Oct 13 17:18:19 2002
+++ squid3/src/HttpHdrCc.cc	Mon Oct 14 19:09:41 2002
@@ -36,6 +36,7 @@
 #include "squid.h"
 #include "Store.h"
 #include "HttpHeader.h"
+#include "Trie.h"
 
 /* this table is used for parsing cache control header */
 static const HttpHeaderFieldAttrs CcAttrs[CC_ENUM_END] =
@@ -62,6 +63,8 @@
 }
 
 
+static Trie *ccTrie = NULL;
+
 /* local prototypes */
 static int httpHdrCcParseInit(HttpHdrCc * cc, const String * str);
 
@@ -71,7 +74,13 @@
 void
 httpHdrCcInitModule(void)
 {
+    int i;
     CcFieldsInfo = httpHeaderBuildFieldsInfo(CcAttrs, CC_ENUM_END);
+    assert (ccTrie == NULL);
+    ccTrie = new Trie;
+    for (i = 0; i < CC_ENUM_END; ++i)
+	if (!ccTrie->add(strBuf(CcFieldsInfo[i].name), strLen(CcFieldsInfo[i].name), (void *) (i + 1)))
+	    fatal("Could not build CC search trie\n"); 
 }
 
 void
@@ -79,6 +88,8 @@
 {
     httpHeaderDestroyFieldsInfo(CcFieldsInfo, CC_ENUM_END);
     CcFieldsInfo = NULL;
+    delete ccTrie;
+    ccTrie = NULL;
 }
 
 /* implementation */
@@ -121,7 +132,7 @@
 	    ilen = p++ - item;
 	/* find type */
 	type = (http_hdr_cc_type ) httpHeaderIdByName(item, ilen,
-	    CcFieldsInfo, CC_ENUM_END);
+	    ccTrie);
 	if (type < 0) {
 	    debug(65, 2) ("hdr cc: unknown cache-directive: near '%s' in '%s'\n", item, strBuf(*str));
 	    type = CC_OTHER;
Index: squid3/src/HttpHeader.cc
diff -u squid3/src/HttpHeader.cc:1.1 squid3/src/HttpHeader.cc:1.1.4.1
--- squid3/src/HttpHeader.cc:1.1	Sun Oct 13 17:18:19 2002
+++ squid3/src/HttpHeader.cc	Mon Oct 14 19:09:41 2002
@@ -36,6 +36,7 @@
 #include "squid.h"
 #include "Store.h"
 #include "HttpHeader.h"
+#include "Trie.h"
 
 /*
  * On naming conventions:
@@ -234,6 +235,8 @@
 
 static int HeaderEntryParsedCount = 0;
 
+static Trie *headerTrie = NULL;
+
 /*
  * local routines
  */
@@ -262,6 +265,12 @@
     assert(countof(HeadersAttrs) == HDR_ENUM_END);
     if (!Headers)
 	Headers = httpHeaderBuildFieldsInfo(HeadersAttrs, HDR_ENUM_END);
+    /* Add to Trie */
+    assert (!headerTrie);
+    headerTrie = new Trie;
+    for (i = 0; i < HDR_ENUM_END; ++i)
+	if (!headerTrie->add(strBuf(Headers[i].name), strLen(Headers[i].name), (void *) (i + 1)))
+	    fatal("Could not build Header search trie\n");
     /* create masks */
     httpHeaderMaskInit(&ListHeadersMask, 0);
     httpHeaderCalcMask(&ListHeadersMask, (const int *) ListHeadersArr, countof(ListHeadersArr));
@@ -294,6 +303,8 @@
 {
     httpHeaderDestroyFieldsInfo(Headers, HDR_ENUM_END);
     Headers = NULL;
+    delete headerTrie;
+    headerTrie = NULL;
     httpHdrCcCleanModule();
 }
 
@@ -530,7 +541,7 @@
     while ((e = httpHeaderGetEntry(hdr, &pos))) {
 	if (!strCaseCmp(e->name, name)) {
 	    httpHeaderDelAt(hdr, pos);
-	    count++;
+	    ++count;
 	} else
 	    CBIT_SET(hdr->mask, e->id);
     }
@@ -1061,7 +1072,7 @@
     e = (HttpHeaderEntry *)memAllocate(MEM_HTTP_HDR_ENTRY);
     debug(55, 9) ("creating entry %p: near '%s'\n", e, getStringPrefix(field_start, field_end));
     /* is it a "known" field? */
-    id = httpHeaderIdByName(field_start, name_len, Headers, HDR_ENUM_END);
+    id = httpHeaderIdByName(field_start, name_len, headerTrie);
     if (id < 0)
 	id = HDR_OTHER;
     assert_eid(id);
@@ -1212,6 +1223,15 @@
 }
 
 http_hdr_type
+httpHeaderIdByName(const char *name, int name_len, Trie *aTrie)
+{
+    void *t;
+    int ourLen = name_len > -1 ? name_len: strlen (name) - 1;
+    t = aTrie->find( name, ourLen);
+    return (http_hdr_type)(((int) t) - 1);
+}
+
+http_hdr_type
 httpHeaderIdByName(const char *name, int name_len, const HttpHeaderFieldInfo * info, int end)
 {
     int i;
@@ -1230,7 +1250,8 @@
 {
     if (!Headers)
 	Headers = httpHeaderBuildFieldsInfo(HeadersAttrs, HDR_ENUM_END);
-    return httpHeaderIdByName(name, name_len, Headers, HDR_ENUM_END);
+    assert (headerTrie);
+    return httpHeaderIdByName(name, name_len, headerTrie);
 }
 
 const char *
Index: squid3/src/Makefile.am
diff -u squid3/src/Makefile.am:1.2 squid3/src/Makefile.am:1.2.4.1
--- squid3/src/Makefile.am:1.2	Mon Oct 14 02:09:09 2002
+++ squid3/src/Makefile.am	Mon Oct 14 19:09:41 2002
@@ -73,7 +73,8 @@
 
 SUBDIRS		= fs repl auth
 
-INCLUDES        = -I. -I$(srcdir) -I$(top_builddir)/include -I$(top_srcdir)/include
+INCLUDES        = -I. -I$(srcdir) -I$(top_builddir)/include \
+	-I$(top_srcdir)/include -I$(top_srcdir)/lib/libTrie/include
 
 EXTRA_PROGRAMS = \
 	unlinkd \
@@ -236,7 +237,7 @@
 	auth_modules.cc \
 	store_modules.cc \
 	cf_parser.h \
-	globals.c \
+	globals.cc \
 	string_arrays.c
 
 squid_LDADD = \
@@ -265,12 +266,12 @@
 recv_announce_SOURCES = recv-announce.cc
 
 nodist_pinger_SOURCES = \
-	globals.c
+	globals.cc
 
 BUILT_SOURCES = \
 	cf_gen_defines.h \
 	cf_parser.h \
-	globals.c \
+	globals.cc \
 	string_arrays.c \
 	repl_modules.cc \
 	auth_modules.cc \
@@ -320,7 +321,7 @@
 
 snmp_core.o snmp_agent.o: ../snmplib/libsnmp.a $(top_srcdir)/include/cache_snmp.h
 
-globals.c: globals.h mk-globals-c.pl
+globals.cc: globals.h mk-globals-c.pl
 	$(PERL) $(srcdir)/mk-globals-c.pl < $(srcdir)/globals.h > $@
 
 string_arrays.c: enums.h mk-string-arrays.pl
@@ -401,7 +402,7 @@
 	fi
 
 DISTCLEANFILES = cf_gen_defines.h cf.data cf_parser.h squid.conf.default \
-	globals.c string_arrays.c repl_modules.cc auth_modules.cc store_modules.cc
+	globals.cc string_arrays.c repl_modules.cc auth_modules.cc store_modules.cc
 
 ##install-pinger:
 ##	@f=$(PINGER_EXE); \
Index: squid3/src/protos.h
diff -u squid3/src/protos.h:1.2 squid3/src/protos.h:1.2.4.1
--- squid3/src/protos.h:1.2	Mon Oct 14 02:09:09 2002
+++ squid3/src/protos.h	Mon Oct 14 19:09:41 2002
@@ -407,7 +407,8 @@
 /* Http Header Tools */
 SQUIDCEXTERN HttpHeaderFieldInfo *httpHeaderBuildFieldsInfo(const HttpHeaderFieldAttrs * attrs, int count);
 SQUIDCEXTERN void httpHeaderDestroyFieldsInfo(HttpHeaderFieldInfo * info, int count);
-SQUIDCEXTERN http_hdr_type httpHeaderIdByName(const char *name, int name_len, const HttpHeaderFieldInfo * attrs, int end);
+class Trie;
+extern http_hdr_type httpHeaderIdByName(const char *name, int name_len, Trie *searchIn);
 SQUIDCEXTERN http_hdr_type httpHeaderIdByNameDef(const char *name, int name_len);
 SQUIDCEXTERN const char *httpHeaderNameById(int id);
 SQUIDCEXTERN void httpHeaderMaskInit(HttpHeaderMask * mask, int value);