You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by jp...@apache.org on 2011/03/29 00:04:18 UTC
svn commit: r1086420 - in /trafficserver/traffic/trunk: ./ lib/ts/ proxy/
proxy/http/ proxy/http/remap/
Author: jplevyak
Date: Mon Mar 28 22:04:17 2011
New Revision: 1086420
URL: http://svn.apache.org/viewvc?rev=1086420&view=rev
Log:
TS-720: remove dependencies in STL, add new templated containers.
Added:
trafficserver/traffic/trunk/lib/ts/Map.h
trafficserver/traffic/trunk/lib/ts/Vec.cc
trafficserver/traffic/trunk/lib/ts/Vec.h
trafficserver/traffic/trunk/lib/ts/defalloc.h
trafficserver/traffic/trunk/lib/ts/test_Map.cc
trafficserver/traffic/trunk/lib/ts/test_Vec.cc
Modified:
trafficserver/traffic/trunk/LICENSE
trafficserver/traffic/trunk/lib/ts/List.h
trafficserver/traffic/trunk/lib/ts/Makefile.am
trafficserver/traffic/trunk/lib/ts/TestHttpHeader.cc
trafficserver/traffic/trunk/lib/ts/libts.h
trafficserver/traffic/trunk/proxy/ControlBase.cc
trafficserver/traffic/trunk/proxy/ControlBase.h
trafficserver/traffic/trunk/proxy/http/HttpConnectionCount.cc
trafficserver/traffic/trunk/proxy/http/HttpConnectionCount.h
trafficserver/traffic/trunk/proxy/http/remap/RemapProcessor.h
trafficserver/traffic/trunk/proxy/http/remap/UrlMappingPathIndex.h
trafficserver/traffic/trunk/proxy/logstats.cc
Modified: trafficserver/traffic/trunk/LICENSE
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/LICENSE?rev=1086420&r1=1086419&r2=1086420&view=diff
==============================================================================
--- trafficserver/traffic/trunk/LICENSE (original)
+++ trafficserver/traffic/trunk/LICENSE Mon Mar 28 22:04:17 2011
@@ -359,6 +359,33 @@ OF OR IN CONNECTION WITH THE USE OR PERF
~~~
+Copyright (c) 1994-2011 John Bradley Plevyak, 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.
+3. The name of the author may be used to endorse or promote products derived
+ from this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
+
+~~~
+
Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
Modified: trafficserver/traffic/trunk/lib/ts/List.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/lib/ts/List.h?rev=1086420&r1=1086419&r2=1086420&view=diff
==============================================================================
--- trafficserver/traffic/trunk/lib/ts/List.h (original)
+++ trafficserver/traffic/trunk/lib/ts/List.h Mon Mar 28 22:04:17 2011
@@ -61,6 +61,7 @@
#include "ink_queue.h"
#include "ink_resource.h"
#include "Compatability.h"
+#include "defalloc.h"
//
// Link cell for singly-linked list of objects of type C.
@@ -346,8 +347,123 @@ template<class C, class L = typename C::
};
#define SortableQue(_c, _l) SortableQueue<_c, _c::Link##_##_f>
+//
+// Adds counting to the Queue
+//
+
+template <class C, class L = typename C::Link_link> struct CountQueue : public Queue<C,L> {
+ int size;
+ inline CountQueue(void) : size(0) {}
+ inline void push(C *e);
+ inline C *pop();
+ inline void enqueue(C *e);
+ inline C *dequeue();
+ inline void remove(C *e);
+ inline void insert(C *e, C *after);
+ inline void append(CountQueue<C,L> &q);
+ inline void append_clear(CountQueue<C,L> &q);
+};
+#define CountQue(_c, _f) CountQueue<_c, _c::Link##_##_f>
+#define CountQueM(_c, _m, _mf, _f) CountQueue<_c, _c::Link##_##_mf##_##_f>
+
+template <class C, class L> inline void
+CountQueue<C,L>::push(C *e) {
+ Queue<C,L>::push(e);
+ size++;
+}
+
+template <class C, class L> inline C *
+CountQueue<C,L>::pop() {
+ C *ret = Queue<C,L>::pop();
+ if (ret)
+ size--;
+ return ret;
+}
+
+template <class C, class L> inline void
+CountQueue<C,L>::remove(C *e) {
+ Queue<C,L>::remove(e);
+ size--;
+}
+
+template <class C, class L> inline void
+CountQueue<C,L>::enqueue(C *e) {
+ Queue<C,L>::enqueue(e);
+ size++;
+}
+
+template <class C, class L> inline C *
+CountQueue<C,L>::dequeue() {
+ return pop();
+}
-// atomic lists
+template <class C, class L> inline void
+CountQueue<C,L>::insert(C *e, C *after) {
+ Queue<C,L>::insert(e, after);
+ size++;
+}
+
+template <class C, class L> inline void
+CountQueue<C,L>::append(CountQueue<C,L> &q) {
+ Queue<C,L>::append(q);
+ size += q.size;
+};
+
+template <class C, class L> inline void
+CountQueue<C,L>::append_clear(CountQueue<C,L> &q) {
+ append(q);
+ q.head = q.tail = 0;
+ q.size = 0;
+}
+
+//
+// List using cons cells
+//
+
+template <class C, class A = DefaultAlloc>
+struct ConsCell {
+ C car;
+ ConsCell *cdr;
+ ConsCell(C acar, ConsCell *acdr) : car(acar), cdr(acdr) {}
+ ConsCell(C acar) : car(acar), cdr(NULL) {}
+ ConsCell(ConsCell *acdr) : cdr(acdr) {}
+ static void *operator new(size_t size) { return A::alloc(size); }
+ static void operator delete(void *p, size_t size) { A::free(p); }
+};
+
+template <class C, class A = DefaultAlloc>
+struct List {
+ ConsCell<C,A> *head;
+ C first() { if (head) return head->car; else return 0; }
+ C car() { return first(); }
+ ConsCell<C,A> *rest() { if (head) return head->cdr; else return 0; }
+ ConsCell<C,A> *cdr() { return rest(); }
+ void push(C a) { head = new ConsCell<C,A>(a, head); }
+ void push() { head = new ConsCell<C,A>(head); }
+ C pop() { C a = car(); head = cdr(); return a; }
+ void clear() { head = NULL; }
+ void reverse();
+ List(C acar) : head(new ConsCell<C,A>(acar)) {}
+ List(C a, C b) : head(new ConsCell<C,A>(a, new ConsCell<C,A>(b))) {}
+ List(C a, C b, C c) : head(new ConsCell<C,A>(a, new ConsCell<C,A>(b, new ConsCell<C,A>(c)))) {}
+ List() : head(0) {}
+};
+#define forc_List(_c, _p, _l) if ((_l).head) for (_c *_p = (_l).head; _p; _p = _p->cdr)
+
+template <class C,class A> void
+List<C,A>::reverse() {
+ ConsCell<C,A> *n, *t;
+ for (ConsCell<C,A> *p = head; p; p = n) {
+ n = p->cdr;
+ p->cdr = t;
+ t = p;
+ }
+ head = t;
+}
+
+//
+// Atomic lists
+//
template<class C, class L = typename C::Link_link> struct AtomicSLL
{
Modified: trafficserver/traffic/trunk/lib/ts/Makefile.am
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/lib/ts/Makefile.am?rev=1086420&r1=1086419&r2=1086420&view=diff
==============================================================================
--- trafficserver/traffic/trunk/lib/ts/Makefile.am (original)
+++ trafficserver/traffic/trunk/lib/ts/Makefile.am Mon Mar 28 22:04:17 2011
@@ -17,7 +17,7 @@
# limitations under the License.
noinst_PROGRAMS = mkdfa CompileParseRules
-check_PROGRAMS = test_atomic test_freelist test_arena test_List
+check_PROGRAMS = test_atomic test_freelist test_arena test_List test_Map test_Vec
TESTS = $(check_PROGRAMS)
lib_LTLIBRARIES = libtsutil.la
@@ -39,6 +39,7 @@ libtsutil_la_SOURCES = \
DynArray.h \
HostLookup.cc \
HostLookup.h \
+ defalloc.h \
ink_aiocb.h \
ink_align.h \
ink_apidefs.h \
@@ -143,6 +144,9 @@ libtsutil_la_SOURCES = \
TextBuffer.h \
Tokenizer.cc \
Tokenizer.h \
+ Vec.h \
+ Vec.cc \
+ Map.h \
Version.cc
# Special hacks to generate the parser rules
@@ -166,6 +170,10 @@ test_arena_LDADD = libtsutil.la @LIBTHRE
test_arena_LDFLAGS = @EXTRA_CXX_LDFLAGS@
test_List_SOURCES = test_List.cc
+test_Map_SOURCES = test_Map.cc
+test_Map_LDADD = libtsutil.la
+test_Vec_SOURCES = test_Vec.cc
+test_Vec_LDADD = libtsutil.la
CompileParseRules_SOURCES = CompileParseRules.cc
Added: trafficserver/traffic/trunk/lib/ts/Map.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/lib/ts/Map.h?rev=1086420&view=auto
==============================================================================
--- trafficserver/traffic/trunk/lib/ts/Map.h (added)
+++ trafficserver/traffic/trunk/lib/ts/Map.h Mon Mar 28 22:04:17 2011
@@ -0,0 +1,937 @@
+/** @file
+
+ A set of Map templates.
+
+ @section license License
+
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+*/
+
+#ifndef _map_H_
+#define _map_H_
+
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include "List.h"
+#include "Vec.h"
+
+#define MAP_INTEGRAL_SIZE (1 << (2))
+#define MAP_INITIAL_SHIFT ((2)+1)
+#define MAP_INITIAL_SIZE (1 << MAP_INITIAL_SHIFT)
+
+typedef const char cchar;
+
+template<class A>
+static inline char *
+_dupstr(cchar *s, cchar *e = 0) {
+ int l = e ? e-s : strlen(s);
+ char *ss = (char*)A::alloc(l+1);
+ memcpy(ss, s, l);
+ ss[l] = 0;
+ return ss;
+}
+
+// Simple direct mapped Map (pointer hash table) and Environment
+
+template <class K, class C> class MapElem {
+ public:
+ K key;
+ C value;
+ bool operator==(MapElem &e) { return e.key == key; }
+ operator uintptr_t(void) { return (uintptr_t)(uintptr_t)key; }
+ MapElem(uintptr_t x) { assert(!x); key = 0; }
+ MapElem(K akey, C avalue) : key(akey), value(avalue) {}
+ MapElem(MapElem &e) : key(e.key), value(e.value) {}
+ MapElem() : key(0) {}
+};
+
+template <class K, class C, class A = DefaultAlloc> class Map : public Vec<MapElem<K,C>, A> {
+ public:
+ typedef MapElem<K,C> ME;
+ typedef Vec<ME,A> PType;
+ using PType::n;
+ using PType::i;
+ using PType::v;
+ ME *put(K akey, C avalue);
+ ME *put(K akey);
+ C get(K akey);
+ C *getp(K akey);
+ void get_keys(Vec<K> &keys);
+ void get_keys_set(Vec<K> &keys);
+ void get_values(Vec<C> &values);
+ void map_union(Map<K,C> &m);
+ int some_disjunction(Map<K,C> &m);
+};
+
+template <class C> class HashFns {
+ public:
+ static uintptr_t hash(C a);
+ static int equal(C a, C b);
+};
+
+template <class K, class C> class HashSetFns {
+ public:
+ static uintptr_t hash(C a);
+ static uintptr_t hash(K a);
+ static int equal(C a, C b);
+ static int equal(K a, C b);
+};
+
+template <class K, class AHashFns, class C, class A = DefaultAlloc> class HashMap : public Map<K,C,A> {
+ public:
+ using Map<K,C,A>::n;
+ using Map<K,C,A>::i;
+ using Map<K,C,A>::v;
+ using Map<K,C,A>::e;
+ MapElem<K,C> *get_internal(K akey);
+ C get(K akey);
+ MapElem<K,C> *put(K akey, C avalue);
+ void get_keys(Vec<K> &keys);
+ void get_values(Vec<C> &values);
+};
+
+#define form_Map(_c, _p, _v) if ((_v).n) for (_c *qq__##_p = (_c*)0, *_p = &(_v).v[0]; \
+ ((intptr_t)(qq__##_p) < (_v).n) && ((_p = &(_v).v[(intptr_t)qq__##_p]) || 1); \
+ qq__##_p = (_c*)(((intptr_t)qq__##_p) + 1)) \
+ if ((_p)->key)
+
+
+template <class K, class AHashFns, class C, class A = DefaultAlloc> class HashSet : public Vec<C,A> {
+ public:
+ typedef Vec<C,A> V;
+ using V::n;
+ using V::i;
+ using V::v;
+ using V::e;
+ C get(K akey);
+ C *put( C avalue);
+};
+
+class StringHashFns {
+ public:
+ static uintptr_t hash(cchar *s) {
+ uintptr_t h = 0;
+ // 31 changed to 27, to avoid prime2 in vec.cpp
+ while (*s) h = h * 27 + (unsigned char)*s++;
+ return h;
+ }
+ static int equal(cchar *a, cchar *b) { return !strcmp(a, b); }
+};
+
+class CaseStringHashFns {
+ public:
+ static uintptr_t hash(cchar *s) {
+ uintptr_t h = 0;
+ // 31 changed to 27, to avoid prime2 in vec.cpp
+ while (*s) h = h * 27 + (unsigned char)toupper(*s++);
+ return h;
+ }
+ static int equal(cchar *a, cchar *b) { return !strcasecmp(a, b); }
+};
+
+class PointerHashFns {
+ public:
+ static uintptr_t hash(void *s) { return (uintptr_t)(uintptr_t)s; }
+ static int equal(void *a, void *b) { return a == b; }
+};
+
+template <class C, class AHashFns, class A = DefaultAlloc> class ChainHash : public Map<uintptr_t, List<C,A>,A> {
+ public:
+ using Map<uintptr_t, List<C,A>,A>::n;
+ using Map<uintptr_t, List<C,A>,A>::v;
+ typedef ConsCell<C, A> ChainCons;
+ C put(C c);
+ C get(C c);
+ C put_bag(C c);
+ int get_bag(C c,Vec<C> &v);
+ int del(C avalue);
+ void get_elements(Vec<C> &elements);
+};
+
+template <class K, class AHashFns, class C, class A = DefaultAlloc> class ChainHashMap :
+ public Map<uintptr_t, List<MapElem<K,C>,A>,A> {
+ public:
+ using Map<uintptr_t, List<MapElem<K,C>,A>,A>::n;
+ using Map<uintptr_t, List<MapElem<K,C>,A>,A>::v;
+ MapElem<K,C> *put(K akey, C avalue);
+ C get(K akey);
+ int del(K akey);
+ MapElem<K,C> *put_bag(K akey, C c);
+ int get_bag(K akey, Vec<C> &v);
+ void get_keys(Vec<K> &keys);
+ void get_values(Vec<C> &values);
+};
+
+template<class F = StringHashFns, class A = DefaultAlloc>
+class StringChainHash : public ChainHash<cchar *, F, A> {
+ public:
+ cchar *canonicalize(cchar *s, cchar *e);
+ cchar *canonicalize(cchar *s) { return canonicalize(s, s + strlen(s)); }
+};
+
+template <class C, class AHashFns, int N, class A = DefaultAlloc> class NBlockHash {
+ public:
+ int n;
+ int i;
+ C *v;
+ C e[N];
+
+ C* end() { return last(); }
+ int length() { return N * n; }
+ C *first();
+ C *last();
+ C put(C c);
+ C get(C c);
+ C* assoc_put(C *c);
+ C* assoc_get(C *c);
+ int del(C c);
+ void clear();
+ void reset();
+ int count();
+ void size(int p2);
+ void copy(const NBlockHash<C,AHashFns,N,A> &hh);
+ void move(NBlockHash<C,AHashFns,N,A> &hh);
+ NBlockHash();
+ NBlockHash(NBlockHash<C,AHashFns,N,A> &hh) { v = e; copy(hh); }
+};
+
+/* use forv_Vec on BlockHashes */
+
+#define DEFAULT_BLOCK_HASH_SIZE 4
+template <class C, class ABlockHashFns> class BlockHash :
+ public NBlockHash<C, ABlockHashFns, DEFAULT_BLOCK_HASH_SIZE> {};
+typedef BlockHash<cchar *, StringHashFns> StringBlockHash;
+
+template <class K, class C, class A = DefaultAlloc> class Env {
+ public:
+ typedef ConsCell<C, A> EnvCons;
+ void put(K akey, C avalue);
+ C get(K akey);
+ void push();
+ void pop();
+ void clear() { store.clear(); scope.clear(); }
+
+ Env() {}
+ Map<K,List<C> *, A> store;
+ List<List<K>, A> scope;
+ List<C, A> *get_bucket(K akey);
+};
+
+/* IMPLEMENTATION */
+
+template <class K, class C, class A> inline C
+Map<K,C,A>::get(K akey) {
+ MapElem<K,C> e(akey, (C)0);
+ MapElem<K,C> *x = set_in(e);
+ if (x)
+ return x->value;
+ return (C)0;
+}
+
+template <class K, class C, class A> inline C *
+Map<K,C,A>::getp(K akey) {
+ MapElem<K,C> e(akey, (C)0);
+ MapElem<K,C> *x = set_in(e);
+ if (x)
+ return &x->value;
+ return 0;
+}
+
+template <class K, class C, class A> inline MapElem<K,C> *
+Map<K,C,A>::put(K akey, C avalue) {
+ MapElem<K,C> e(akey, avalue);
+ MapElem<K,C> *x = set_in(e);
+ if (x) {
+ x->value = avalue;
+ return x;
+ } else
+ return set_add(e);
+}
+
+template <class K, class C, class A> inline MapElem<K,C> *
+Map<K,C,A>::put(K akey) {
+ MapElem<K,C> e(akey, 0);
+ MapElem<K,C> *x = set_in(e);
+ if (x)
+ return x;
+ else
+ return set_add(e);
+}
+
+template <class K, class C, class A> inline void
+Map<K,C,A>::get_keys(Vec<K> &keys) {
+ for (int i = 0; i < n; i++)
+ if (v[i].key)
+ keys.add(v[i].key);
+}
+
+template <class K, class C, class A> inline void
+Map<K,C,A>::get_keys_set(Vec<K> &keys) {
+ for (int i = 0; i < n; i++)
+ if (v[i].key)
+ keys.set_add(v[i].key);
+}
+
+template <class K, class C, class A> inline void
+Map<K,C,A>::get_values(Vec<C> &values) {
+ for (int i = 0; i < n; i++)
+ if (v[i].key)
+ values.set_add(v[i].value);
+ values.set_to_vec();
+}
+
+template <class K, class C, class A> inline void
+Map<K,C,A>::map_union(Map<K,C> &m) {
+ for (int i = 0; i < m.n; i++)
+ if (m.v[i].key)
+ put(m.v[i].key, m.v[i].value);
+}
+
+template <class K, class C, class A> inline int
+Map<K,C,A>::some_disjunction(Map<K,C> &m) {
+ for (int i = 0; i < m.n; i++)
+ if (m.v[i].key && get(m.v[i].key) != m.v[i].value)
+ return 1;
+ for (int i = 0; i < n; i++)
+ if (v[i].key && m.get(v[i].key) != v[i].value)
+ return 1;
+ return 0;
+}
+
+template <class K, class C, class A> inline void
+map_set_add(Map<K,Vec<C,A>*,A> &m, K akey, C avalue) {
+ Vec<C,A> *v = m.get(akey);
+ if (!v)
+ m.put(akey, (v = new Vec<C,A>));
+ v->set_add(avalue);
+}
+
+template <class K, class C, class A> inline void
+map_set_add(Map<K,Vec<C,A>*,A> &m, K akey, Vec<C> *madd) {
+ Vec<C,A> *v = m.get(akey);
+ if (!v)
+ m.put(akey, (v = new Vec<C,A>));
+ v->set_union(*madd);
+}
+
+template <class K, class AHashFns, class C, class A> inline C
+HashSet<K, AHashFns, C, A>::get(K akey) {
+ if (!n)
+ return 0;
+ if (n <= MAP_INTEGRAL_SIZE) {
+ for (C *c = v; c < v + n; c++)
+ if (c)
+ if (AHashFns::equal(akey, *c))
+ return *c;
+ return 0;
+ }
+ uintptr_t h = AHashFns::hash(akey);
+ h = h % n;
+ for (int k = h, j = 0; j < i + 3;j++) {
+ if (!v[k])
+ return 0;
+ else if (AHashFns::equal(akey, v[k]))
+ return v[k];
+ k = (k + open_hash_primes[j]) % n;
+ }
+ return 0;
+}
+
+template <class K, class AHashFns, class C, class A> inline C *
+HashSet<K, AHashFns, C, A>::put(C avalue) {
+ if (n < MAP_INTEGRAL_SIZE) {
+ if (!v)
+ v = e;
+ for (int i = 0; i < n; i++)
+ if (AHashFns::equal(avalue, v[i]))
+ return &v[i];
+ v[n] = avalue;
+ n++;
+ return &v[n-1];
+ }
+ if (n > MAP_INTEGRAL_SIZE) {
+ uintptr_t h = AHashFns::hash(avalue);
+ h = h % n;
+ for (int k = h, j = 0; j < i + 3; j++) {
+ if (!v[k]) {
+ v[k] = avalue;
+ return &v[k];
+ }
+ k = (k + open_hash_primes[j]) % n;
+ }
+ } else
+ i = SET_INITIAL_INDEX-1; // will be incremented in set_expand
+ HashSet<K,AHashFns,C,A> vv(*this);
+ Vec<C,A>::set_expand();
+ for (int i = 0; i < vv.n; i++)
+ if (vv.v[i])
+ put(vv.v[i]);
+ return put(avalue);
+}
+
+template <class K, class AHashFns, class C, class A> inline MapElem<K,C> *
+HashMap<K,AHashFns,C,A>::get_internal(K akey) {
+ if (!n)
+ return 0;
+ if (n <= MAP_INTEGRAL_SIZE) {
+ for (MapElem<K,C> *c = v; c < v + n; c++)
+ if (c->key)
+ if (AHashFns::equal(akey, c->key))
+ return c;
+ return 0;
+ }
+ uintptr_t h = AHashFns::hash(akey);
+ h = h % n;
+ for (int k = h, j = 0; j < i + 3;j++) {
+ if (!v[k].key)
+ return 0;
+ else if (AHashFns::equal(akey, v[k].key))
+ return &v[k];
+ k = (k + open_hash_primes[j]) % n;
+ }
+ return 0;
+}
+
+template <class K, class AHashFns, class C, class A> inline C
+HashMap<K,AHashFns,C,A>::get(K akey) {
+ MapElem<K,C> *x = get_internal(akey);
+ if (!x)
+ return 0;
+ return x->value;
+}
+
+template <class K, class AHashFns, class C, class A> inline MapElem<K,C> *
+HashMap<K,AHashFns,C,A>::put(K akey, C avalue) {
+ MapElem<K,C> *x = get_internal(akey);
+ if (x) {
+ x->value = avalue;
+ return x;
+ } else {
+ if (n < MAP_INTEGRAL_SIZE) {
+ if (!v)
+ v = e;
+ v[n].key = akey;
+ v[n].value = avalue;
+ n++;
+ return &v[n-1];
+ }
+ if (n > MAP_INTEGRAL_SIZE) {
+ uintptr_t h = AHashFns::hash(akey);
+ h = h % n;
+ for (int k = h, j = 0; j < i + 3; j++) {
+ if (!v[k].key) {
+ v[k].key = akey;
+ v[k].value = avalue;
+ return &v[k];
+ }
+ k = (k + open_hash_primes[j]) % n;
+ }
+ } else
+ i = SET_INITIAL_INDEX-1; // will be incremented in set_expand
+ }
+ HashMap<K,AHashFns,C,A> vv(*this);
+ Map<K,C,A>::set_expand();
+ for (int i = 0; i < vv.n; i++)
+ if (vv.v[i].key)
+ put(vv.v[i].key, vv.v[i].value);
+ return put(akey, avalue);
+}
+
+template <class K, class AHashFns, class C, class A> inline void
+HashMap<K,AHashFns,C,A>::get_keys(Vec<K> &keys) { Map<K,C,A>::get_keys(keys); }
+
+template <class K, class AHashFns, class C, class A> inline void
+HashMap<K,AHashFns,C,A>::get_values(Vec<C> &values) { Map<K,C,A>::get_values(values); }
+
+template <class C, class AHashFns, class A> C
+ChainHash<C, AHashFns, A>::put(C c) {
+ uintptr_t h = AHashFns::hash(c);
+ List<C,A> *l;
+ MapElem<uintptr_t,List<C,A> > e(h, (C)0);
+ MapElem<uintptr_t,List<C,A> > *x = set_in(e);
+ if (x)
+ l = &x->value;
+ else {
+ l = &Map<uintptr_t, List<C,A>, A>::put(h, c)->value;
+ return l->head->car;
+ }
+ forc_List(ChainCons, x, *l)
+ if (AHashFns::equal(c, x->car))
+ return x->car;
+ l->push(c);
+ return (C)0;
+}
+
+template <class C, class AHashFns, class A> C
+ChainHash<C, AHashFns, A>::get(C c) {
+ uintptr_t h = AHashFns::hash(c);
+ List<C> empty;
+ MapElem<uintptr_t,List<C,A> > e(h, empty);
+ MapElem<uintptr_t,List<C,A> > *x = set_in(e);
+ if (!x)
+ return 0;
+ List<C> *l = &x->value;
+ forc_List(ChainCons, x, *l)
+ if (AHashFns::equal(c, x->car))
+ return x->car;
+ return 0;
+}
+
+template <class C, class AHashFns, class A> C
+ChainHash<C, AHashFns, A>::put_bag(C c) {
+ uintptr_t h = AHashFns::hash(c);
+ List<C, A> *l;
+ MapElem<uintptr_t,List<C,A> > e(h, (C)0);
+ MapElem<uintptr_t,List<C,A> > *x = set_in(e);
+ if (x)
+ l = &x->value;
+ else {
+ l = &Map<uintptr_t, List<C,A> >::put(h, c)->value;
+ return l->head->car;
+ }
+ l->push(c);
+ return (C)0;
+}
+
+template <class C, class AHashFns, class A> int
+ChainHash<C, AHashFns, A>::get_bag(C c, Vec<C> &v) {
+ uintptr_t h = AHashFns::hash(c);
+ List<C,A> empty;
+ MapElem<uintptr_t,List<C,A> > e(h, empty);
+ MapElem<uintptr_t,List<C,A> > *x = set_in(e);
+ if (!x)
+ return 0;
+ List<C,A> *l = &x->value;
+ forc_List(C, x, *l)
+ if (AHashFns::equal(c, x->car))
+ v.add(x->car);
+ return v.n;
+}
+
+template <class C, class AHashFns, class A> void
+ChainHash<C, AHashFns, A>::get_elements(Vec<C> &elements) {
+ for (int i = 0; i < n; i++) {
+ List<C, A> *l = &v[i].value;
+ forc_List(C, x, *l)
+ elements.add(x);
+ }
+}
+
+template <class C, class AHashFns, class A> int
+ChainHash<C, AHashFns, A>::del(C c) {
+ uintptr_t h = AHashFns::hash(c);
+ List<C> *l;
+ MapElem<uintptr_t,List<C,A> > e(h, (C)0);
+ MapElem<uintptr_t,List<C,A> > *x = set_in(e);
+ if (x)
+ l = &x->value;
+ else
+ return 0;
+ ConsCell<C> *last = 0;
+ forc_List(ConsCell<C>, x, *l) {
+ if (AHashFns::equal(c, x->car)) {
+ if (!last)
+ l->head = x->cdr;
+ else
+ last->cdr = x->cdr;
+ A::free(x);
+ return 1;
+ }
+ last = x;
+ }
+ return 0;
+}
+
+template <class K, class AHashFns, class C, class A> MapElem<K,C> *
+ChainHashMap<K, AHashFns, C, A>::put(K akey, C avalue) {
+ uintptr_t h = AHashFns::hash(akey);
+ List<MapElem<K,C>,A> empty;
+ List<MapElem<K,C>,A> *l;
+ MapElem<K, C> c(akey, avalue);
+ MapElem<uintptr_t,List<MapElem<K,C>,A> > e(h, empty);
+ MapElem<uintptr_t,List<MapElem<K,C>,A> > *x = set_in(e);
+ if (x)
+ l = &x->value;
+ else {
+ l = &Map<uintptr_t, List<MapElem<K,C>,A>,A>::put(h, c)->value;
+ return &l->head->car;
+ }
+ for (ConsCell<MapElem<K,C>,A> *p = l->head; p; p = p->cdr)
+ if (AHashFns::equal(akey, p->car.key)) {
+ p->car.value = avalue;
+ return &p->car;
+ }
+ l->push(c);
+ return 0;
+}
+
+template <class K, class AHashFns, class C, class A> C
+ChainHashMap<K, AHashFns, C, A>::get(K akey) {
+ uintptr_t h = AHashFns::hash(akey);
+ List<MapElem<K,C>, A> empty;
+ MapElem<uintptr_t,List<MapElem<K,C>,A> > e(h, empty);
+ MapElem<uintptr_t,List<MapElem<K,C>,A> > *x = set_in(e);
+ if (!x)
+ return 0;
+ List<MapElem<K,C>,A> *l = &x->value;
+ if (l->head)
+ for (ConsCell<MapElem<K,C>,A> *p = l->head; p; p = p->cdr)
+ if (AHashFns::equal(akey, p->car.key))
+ return p->car.value;
+ return 0;
+}
+
+template <class K, class AHashFns, class C, class A> MapElem<K,C> *
+ChainHashMap<K, AHashFns, C, A>::put_bag(K akey, C avalue) {
+ uintptr_t h = AHashFns::hash(akey);
+ List<MapElem<K,C>,A> empty;
+ List<MapElem<K,C>,A> *l;
+ MapElem<K, C> c(akey, avalue);
+ MapElem<uintptr_t,List<MapElem<K,C>,A> > e(h, empty);
+ MapElem<uintptr_t,List<MapElem<K,C>,A> > *x = set_in(e);
+ if (x)
+ l = &x->value;
+ else {
+ l = &Map<uintptr_t, List<MapElem<K,C>,A>,A>::put(h, c)->value;
+ return &l->head->car;
+ }
+ for (ConsCell<MapElem<K,C>,A> *p = l->head; p; p = p->cdr)
+ if (AHashFns::equal(akey, p->car.key) && AHashFns::equal_value(avalue, p->car.value))
+ return &p->car;
+ l->push(c);
+ return 0;
+}
+
+template <class K, class AHashFns, class C, class A> int
+ChainHashMap<K, AHashFns, C, A>::get_bag(K akey, Vec<C> &v) {
+ uintptr_t h = AHashFns::hash(akey);
+ List<MapElem<K,C>,A> empty;
+ MapElem<uintptr_t,List<MapElem<K,C>,A> > e(h, empty);
+ MapElem<uintptr_t,List<MapElem<K,C>,A> > *x = set_in(e);
+ if (!x)
+ return 0;
+ List<MapElem<K,C>,A> *l = &x->value;
+ for (ConsCell<MapElem<K,C>,A> *p = l->head; p; p = p->cdr)
+ if (AHashFns::equal(akey, p->car.key))
+ return v.add(x->car);
+ return v.n;
+}
+
+template <class K, class AHashFns, class C, class A> int
+ChainHashMap<K, AHashFns, C, A>::del(K akey) {
+ uintptr_t h = AHashFns::hash(akey);
+ List<MapElem<K,C>,A> empty;
+ List<MapElem<K,C>,A> *l;
+ MapElem<uintptr_t,List<MapElem<K,C>,A> > e(h, empty);
+ MapElem<uintptr_t,List<MapElem<K,C>,A> > *x = set_in(e);
+ if (x)
+ l = &x->value;
+ else
+ return 0;
+ ConsCell<MapElem<K,C>,A> *last = 0;
+ for (ConsCell<MapElem<K,C>,A> *p = l->head; p; p = p->cdr) {
+ if (AHashFns::equal(akey, p->car.key)) {
+ if (!last)
+ l->head = p->cdr;
+ else
+ last->cdr = p->cdr;
+ return 1;
+ }
+ last = p;
+ }
+ return 0;
+}
+
+template <class K, class AHashFns, class C, class A> void
+ChainHashMap<K, AHashFns, C, A>::get_keys(Vec<K> &keys) {
+ for (int i = 0; i < n; i++) {
+ List<MapElem<K,C> > *l = &v[i].value;
+ if (l->head)
+ for (ConsCell<MapElem<K,C>,A> *p = l->head; p; p = p->cdr)
+ keys.add(p->car.key);
+ }
+}
+
+template <class K, class AHashFns, class C, class A> void
+ChainHashMap<K, AHashFns, C, A>::get_values(Vec<C> &values) {
+ for (int i = 0; i < n; i++) {
+ List<MapElem<K,C>,A> *l = &v[i].value;
+ if (l->head)
+ for (ConsCell<MapElem<K,C>,A> *p = l->head; p; p = p->cdr)
+ values.add(p->car.value);
+ }
+}
+
+template <class F, class A> inline cchar *
+StringChainHash<F,A>::canonicalize(cchar *s, cchar *e) {
+ uintptr_t h = 0;
+ cchar *a = s;
+ // 31 changed to 27, to avoid prime2 in vec.cpp
+ if (e)
+ while (a != e) h = h * 27 + (unsigned char)*a++;
+ else
+ while (*a) h = h * 27 + (unsigned char)*a++;
+ MapElem<uintptr_t,List<cchar*, A> > me(h, (char*)0);
+ MapElem<uintptr_t,List<cchar*, A> > *x = set_in(me);
+ if (x) {
+ List<cchar*, A> *l = &x->value;
+ typedef ConsCell<cchar *, A> TT;
+ forc_List(TT, x, *l) {
+ a = s;
+ cchar *b = x->car;
+ while (1) {
+ if (!*b) {
+ if (a == e)
+ return x->car;
+ break;
+ }
+ if (a >= e || *a != *b)
+ break;
+ a++; b++;
+ }
+ }
+ }
+ s = _dupstr<A>(s, e);
+ cchar *ss = ChainHash<cchar *, F, A>::put(s);
+ if (ss)
+ return ss;
+ return s;
+}
+
+template <class K, class C, class A> inline C
+Env<K,C,A>::get(K akey) {
+ MapElem<K,List<C, A> *> e(akey, 0);
+ MapElem<K,List<C, A> *> *x = store.set_in(e);
+ if (x)
+ return x->value->first();
+ return (C)0;
+}
+
+template <class K, class C, class A> inline List<C, A> *
+Env<K,C,A>::get_bucket(K akey) {
+ List<C, A> *bucket = store.get(akey);
+ if (bucket)
+ return bucket;
+ bucket = new List<C>();
+ store.put(akey, bucket);
+ return bucket;
+}
+
+template <class K, class C, class A> inline void
+Env<K,C,A>::put(K akey, C avalue) {
+ scope.head->car.push(akey);
+ get_bucket(akey)->push(avalue);
+}
+
+template <class K, class C, class A> inline void
+Env<K,C,A>::push() {
+ scope.push();
+}
+
+template <class K, class C, class A> inline void
+Env<K,C,A>::pop() {
+ forc_List(EnvCons, e, scope.first())
+ get_bucket(e->car)->pop();
+}
+
+template <class C, class AHashFns, int N, class A> inline
+NBlockHash<C, AHashFns, N, A>::NBlockHash() : n(1), i(0) {
+ memset(&e[0], 0, sizeof(e));
+ v = e;
+}
+
+template <class C, class AHashFns, int N, class A> inline C*
+NBlockHash<C, AHashFns, N, A>::first() {
+ return &v[0];
+}
+
+template <class C, class AHashFns, int N, class A> inline C*
+NBlockHash<C, AHashFns, N, A>::last() {
+ return &v[n * N];
+}
+
+template <class C, class AHashFns, int N, class A> inline C
+NBlockHash<C, AHashFns, N, A>::put(C c) {
+ int a;
+ uintptr_t h = AHashFns::hash(c);
+ C *x = &v[(h % n) * N];
+ for (a = 0; a < N; a++) {
+ if (!x[a])
+ break;
+ if (AHashFns::equal(c, x[a]))
+ return x[a];
+ }
+ if (a < N) {
+ x[a] = c;
+ return (C)0;
+ }
+ C *vv = first(), *ve = last();
+ C *old_v = v;
+ i = i + 1;
+ size(i);
+ for (;vv < ve; vv++)
+ if (*vv)
+ put(*vv);
+ if (old_v != &e[0])
+ A::free(old_v);
+ return put(c);
+}
+
+template <class C, class AHashFns, int N, class A> inline void
+NBlockHash<C, AHashFns, N, A>::size(int p2) {
+ n = prime2[p2];
+ v = (C*)A::alloc(n * sizeof(C) * N);
+ memset(v, 0, n * sizeof(C) * N);
+}
+
+template <class C, class AHashFns, int N, class A> inline C
+NBlockHash<C, AHashFns, N, A>::get(C c) {
+ if (!n)
+ return (C)0;
+ uintptr_t h = AHashFns::hash(c);
+ C *x = &v[(h % n) * N];
+ for (int a = 0; a < N; a++) {
+ if (!x[a])
+ return (C)0;
+ if (AHashFns::equal(c, x[a]))
+ return x[a];
+ }
+ return (C)0;
+}
+
+template <class C, class AHashFns, int N, class A> inline C*
+NBlockHash<C, AHashFns, N, A>::assoc_get(C *c) {
+ if (!n)
+ return (C*)0;
+ uintptr_t h = AHashFns::hash(*c);
+ C *x = &v[(h % n) * N];
+ int a = 0;
+ if (c >= x && c < x + N)
+ a = c - x + 1;
+ for (; a < N; a++) {
+ if (!x[a])
+ return (C*)0;
+ if (AHashFns::equal(*c, x[a]))
+ return &x[a];
+ }
+ return (C*)0;
+}
+
+template <class C, class AHashFns, int N, class A> inline C*
+NBlockHash<C, AHashFns, N, A>::assoc_put(C *c) {
+ int a;
+ uintptr_t h = AHashFns::hash(*c);
+ C *x = &v[(h % n) * N];
+ for (a = 0; a < N; a++) {
+ if (!x[a])
+ break;
+ }
+ if (a < N) {
+ x[a] = *c;
+ return &x[a];
+ }
+ x[i % N] = *c;
+ i++;
+ return &x[i % N];
+}
+
+template <class C, class AHashFns, int N, class A> inline int
+NBlockHash<C, AHashFns, N, A>::del(C c) {
+ int a, b;
+ if (!n)
+ return 0;
+ uintptr_t h = AHashFns::hash(c);
+ C *x = &v[(h % n) * N];
+ for (a = 0; a < N; a++) {
+ if (!x[a])
+ return 0;
+ if (AHashFns::equal(c, x[a])) {
+ if (a < N - 1) {
+ for (b = a + 1; b < N; b++) {
+ if (!x[b])
+ break;
+ }
+ if (b != a + 1)
+ x[a] = x[b - 1];
+ x[b - 1] = (C)0;
+ return 1;
+ } else {
+ x[N - 1] = (C)0;
+ return 1;
+ }
+ }
+ }
+ return 0;
+}
+
+template <class C, class AHashFns, int N, class A> inline void
+NBlockHash<C, AHashFns, N, A>::clear() {
+ if (v && v != e) A::free(v);
+ v = e;
+ n = 1;
+}
+
+template <class C, class AHashFns, int N, class A> inline void
+NBlockHash<C, AHashFns, N, A>::reset() {
+ if (v)
+ memset(v, 0, n * N * sizeof(C));
+}
+
+template <class C, class AHashFns, int N, class A> inline int
+NBlockHash<C, AHashFns, N, A>::count() {
+ int nelements = 0;
+ C *l = last();
+ for (C *xx = first(); xx < l; xx++)
+ if (*xx)
+ nelements++;
+ return nelements;
+}
+
+template <class C, class AHashFns, int N, class A> inline void
+NBlockHash<C, AHashFns, N, A>::copy(const NBlockHash<C, AHashFns, N, A> &hh) {
+ clear();
+ n = hh.n;
+ i = hh.i;
+ if (hh.v == &hh.e[0]) {
+ memcpy(e, &hh.e[0], sizeof(e));
+ v = e;
+ } else {
+ if (hh.v) {
+ v = (C*)A::alloc(n * sizeof(C) * N);
+ memcpy(v, hh.v, n * sizeof(C) * N);
+ } else
+ v = 0;
+ }
+}
+
+template <class C, class AHashFns, int N, class A> inline void
+NBlockHash<C, AHashFns, N, A>::move(NBlockHash<C, AHashFns, N, A> &hh) {
+ clear();
+ n = hh.n;
+ i = hh.i;
+ v = hh.v;
+ if (hh.v == &hh.e[0]) {
+ memcpy(e, &hh.e[0], sizeof(e));
+ v = e;
+ }
+ hh.clear();
+}
+
+void test_map();
+
+#endif
Modified: trafficserver/traffic/trunk/lib/ts/TestHttpHeader.cc
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/lib/ts/TestHttpHeader.cc?rev=1086420&r1=1086419&r2=1086420&view=diff
==============================================================================
--- trafficserver/traffic/trunk/lib/ts/TestHttpHeader.cc (original)
+++ trafficserver/traffic/trunk/lib/ts/TestHttpHeader.cc Mon Mar 28 22:04:17 2011
@@ -30,7 +30,6 @@
****************************************************************************/
#include "HttpHeaderTokenizer.h"
#include "ink_assert.h"
-#include <fstream.h>
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
Added: trafficserver/traffic/trunk/lib/ts/Vec.cc
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/lib/ts/Vec.cc?rev=1086420&view=auto
==============================================================================
--- trafficserver/traffic/trunk/lib/ts/Vec.cc (added)
+++ trafficserver/traffic/trunk/lib/ts/Vec.cc Mon Mar 28 22:04:17 2011
@@ -0,0 +1,204 @@
+/* -*-Mode: c++;-*-
+ Various vector related code.
+
+ @section license License
+
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+*/
+
+/* UnionFind after Tarjan */
+
+#include <stdint.h>
+#include <assert.h>
+#include "Vec.h"
+
+uintptr_t prime2[] = {
+ 1, 3, 7, 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191,
+ 16381, 32749, 65521, 131071, 262139, 524287, 1048573, 2097143,
+ 4194301, 8388593, 16777213, 33554393, 67108859, 134217689,
+ 268435399, 536870909
+};
+
+// primes generated with map_mult.c
+uintptr_t open_hash_primes[256] = {
+0x02D4AF27, 0x1865DFC7, 0x47C62B43, 0x35B4889B, 0x210459A1, 0x3CC51CC7, 0x02ADD945, 0x0607C4D7,
+0x558E6035, 0x0554224F, 0x5A281657, 0x1C458C7F, 0x7F8BE723, 0x20B9BA99, 0x7218AA35, 0x64B10C2B,
+0x548E8983, 0x5951218F, 0x7AADC871, 0x695FA5B1, 0x40D40FCB, 0x20E03CC9, 0x55E9920F, 0x554CE08B,
+0x7E78B1D7, 0x7D965DF9, 0x36A520A1, 0x1B0C6C11, 0x33385667, 0x2B0A7B9B, 0x0F35AE23, 0x0BD608FB,
+0x2284ADA3, 0x6E6C0687, 0x129B3EED, 0x7E86289D, 0x1143C24B, 0x1B6C7711, 0x1D87BB41, 0x4C7E635D,
+0x67577999, 0x0A0113C5, 0x6CF085B5, 0x14A4D0FB, 0x4E93E3A7, 0x5C87672B, 0x67F3CA17, 0x5F944339,
+0x4C16DFD7, 0x5310C0E3, 0x2FAD1447, 0x4AFB3187, 0x08468B7F, 0x49E56C51, 0x6280012F, 0x097D1A85,
+0x34CC9403, 0x71028BD7, 0x6DEDC7E9, 0x64093291, 0x6D78BB0B, 0x7A03B465, 0x2E044A43, 0x1AE58515,
+0x23E495CD, 0x46102A83, 0x51B78A59, 0x051D8181, 0x5352CAC9, 0x57D1312B, 0x2726ED57, 0x2E6BC515,
+0x70736281, 0x5938B619, 0x0D4B6ACB, 0x44AB5E2B, 0x0029A485, 0x002CE54F, 0x075B0591, 0x3EACFDA9,
+0x0AC03411, 0x53B00F73, 0x2066992D, 0x76E72223, 0x55F62A8D, 0x3FF92EE1, 0x17EE0EB3, 0x5E470AF1,
+0x7193EB7F, 0x37A2CCD3, 0x7B44F7AF, 0x0FED8B3F, 0x4CC05805, 0x7352BF79, 0x3B61F755, 0x523CF9A3,
+0x1AAFD219, 0x76035415, 0x5BE84287, 0x6D598909, 0x456537E9, 0x407EA83F, 0x23F6FFD5, 0x60256F39,
+0x5D8EE59F, 0x35265CEB, 0x1D4AD4EF, 0x676E2E0F, 0x2D47932D, 0x776BB33B, 0x6DE1902B, 0x2C3F8741,
+0x5B2DE8EF, 0x686DDB3B, 0x1D7C61C7, 0x1B061633, 0x3229EA51, 0x7FCB0E63, 0x5F22F4C9, 0x517A7199,
+0x2A8D7973, 0x10DCD257, 0x41D59B27, 0x2C61CA67, 0x2020174F, 0x71653B01, 0x2FE464DD, 0x3E7ED6C7,
+0x164D2A71, 0x5D4F3141, 0x5F7BABA7, 0x50E1C011, 0x140F5D77, 0x34E80809, 0x04AAC6B3, 0x29C42BAB,
+0x08F9B6F7, 0x461E62FD, 0x45C2660B, 0x08BF25A7, 0x5494EA7B, 0x0225EBB7, 0x3C5A47CF, 0x2701C333,
+0x457ED05B, 0x48CDDE55, 0x14083099, 0x7C69BDAB, 0x7BF163C9, 0x41EE1DAB, 0x258B1307, 0x0FFAD43B,
+0x6601D767, 0x214DBEC7, 0x2852CCF5, 0x0009B471, 0x190AC89D, 0x5BDFB907, 0x15D4E331, 0x15D22375,
+0x13F388D5, 0x12ACEDA5, 0x3835EA5D, 0x2587CA35, 0x06756643, 0x487C6F55, 0x65C295EB, 0x1029F2E1,
+0x10CEF39D, 0x14C2E415, 0x444825BB, 0x24BE0A2F, 0x1D2B7C01, 0x64AE3235, 0x5D2896E5, 0x61BBBD87,
+0x4A49E86D, 0x12C277FF, 0x72C81289, 0x5CF42A3D, 0x332FF177, 0x0DAECD23, 0x6000ED1D, 0x203CDDE1,
+0x40C62CAD, 0x19B9A855, 0x782020C3, 0x6127D5BB, 0x719889A7, 0x40E4FCCF, 0x2A3C8FF9, 0x07411C7F,
+0x3113306B, 0x4D7CA03F, 0x76119841, 0x54CEFBDF, 0x11548AB9, 0x4B0748EB, 0x569966B1, 0x45BC721B,
+0x3D5A376B, 0x0D8923E9, 0x6D95514D, 0x0F39A367, 0x2FDAD92F, 0x721F972F, 0x42D0E21D, 0x5C5952DB,
+0x7394D007, 0x02692C55, 0x7F92772F, 0x025F8025, 0x34347113, 0x560EA689, 0x0DCC21DF, 0x09ECC7F5,
+0x091F3993, 0x0E0B52AB, 0x497CAA55, 0x0A040A49, 0x6D8F0CC5, 0x54F41609, 0x6E0CB8DF, 0x3DCB64C3,
+0x16C365CD, 0x6D6B9FB5, 0x02B9382B, 0x6A5BFAF1, 0x1669D75F, 0x13CFD4FD, 0x0FDF316F, 0x21F3C463,
+0x6FC58ABF, 0x04E45BE7, 0x1911225B, 0x28CD1355, 0x222084E9, 0x672AD54B, 0x476FC267, 0x6864E16D,
+0x20AEF4FB, 0x603C5FB9, 0x55090595, 0x1113B705, 0x24E38493, 0x5291AF97, 0x5F5446D9, 0x13A6F639,
+0x3D501313, 0x37E02017, 0x236B0ED3, 0x60F246BF, 0x01E02501, 0x2D2F66BD, 0x6BF23609, 0x16729BAF
+};
+
+// binary search over intervals
+static int
+i_find(Intervals *i, int x) {
+ assert(i->n);
+ int l = 0, h = i->n;
+ Lrecurse:
+ if (h <= l + 2) {
+ if (h <= l)
+ return -(l + 1);
+ if (x < i->v[l] || x > i->v[l + 1])
+ return -(l + 1);
+ return h;
+ }
+ int m = (((h - l) / 4) * 2) + l;
+ if (x > i->v[m + 1]) {
+ l = m;
+ goto Lrecurse;
+ }
+ if (x < i->v[m]) {
+ h = m;
+ goto Lrecurse;
+ }
+ return (l + 1);
+}
+
+int
+Intervals::in(int x) {
+ if (!n)
+ return 0;
+ if (i_find(this, x) > 0)
+ return 1;
+ return 0;
+}
+
+// insert into interval with merge
+void
+Intervals::insert(int x) {
+ if (!n) {
+ add(x);
+ add(x);
+ return;
+ }
+ int l = i_find(this, x);
+ if (l > 0)
+ return;
+ l = -l - 1;
+
+ if (x > v[l + 1]) {
+ if (x == v[l + 1] + 1) {
+ v[l + 1]++;
+ goto Lmerge;
+ }
+ l += 2;
+ if (l < n) {
+ if (x == v[l] - 1) {
+ v[l]--;
+ goto Lmerge;
+ }
+ }
+ goto Lmore;
+ } else {
+ assert(x < v[l]);
+ if (x == v[l] - 1) {
+ v[l]--;
+ goto Lmerge;
+ }
+ if (!l)
+ goto Lmore;
+ l -= 2;
+ if (x == v[l + 1] + 1) {
+ v[l + 1]++;
+ goto Lmerge;
+ }
+ }
+ Lmore:
+ fill(n + 2);
+ if (n - 2 - l > 0)
+ memmove(v + l + 2, v + l, sizeof(int) * (n - 2 - l));
+ v[l] = x;
+ v[l+1] = x;
+ return;
+ Lmerge:
+ if (l) {
+ if (v[l] - v[l-1] < 2) {
+ l -= 2;
+ goto Ldomerge;
+ }
+ }
+ if (l < n - 2) {
+ if (v[l + 2] - v[l + 1] < 2)
+ goto Ldomerge;
+ }
+ return;
+ Ldomerge:
+ memmove(v + l + 1, v + l + 3, sizeof(int) * (n - 3 - l));
+ n -= 2;
+ goto Lmerge;
+}
+
+void
+UnionFind::size(int s) {
+ int nn = n;
+ fill(s);
+ for (int i = nn; i < n; i++)
+ v[i] = -1;
+}
+
+int
+UnionFind::find(int n) {
+ int i, t;
+ for (i = n; v[i] >= 0; i = v[i]);
+ while (v[n] >= 0) {
+ t = n;
+ n = v[n];
+ v[t] = i;
+ }
+ return i;
+}
+
+void
+UnionFind::unify(int n, int m) {
+ n = find(n);
+ m = find(m);
+ if (n != m) {
+ if (v[m] < v[n]) {
+ v[m] += (v[n] - 1);
+ v[n] = m;
+ } else {
+ v[n] += (v[m] - 1);
+ v[m] = n;
+ }
+ }
+}
Added: trafficserver/traffic/trunk/lib/ts/Vec.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/lib/ts/Vec.h?rev=1086420&view=auto
==============================================================================
--- trafficserver/traffic/trunk/lib/ts/Vec.h (added)
+++ trafficserver/traffic/trunk/lib/ts/Vec.h Mon Mar 28 22:04:17 2011
@@ -0,0 +1,815 @@
+/** @file
+
+ Vector and Set templates with qsort.
+
+ @section license License
+
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+*/
+
+#ifndef _vec_H_
+#define _vec_H_
+
+#include <string.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <sys/types.h>
+#include "defalloc.h"
+
+// Simple Vector class, also supports open hashed sets
+
+#define VEC_INTEGRAL_SHIFT_DEFAULT 2 /* power of 2 (1 << VEC_INTEGRAL_SHIFT)*/
+#define VEC_INTEGRAL_SIZE (1 << (S))
+#define VEC_INITIAL_SHIFT ((S)+1)
+#define VEC_INITIAL_SIZE (1 << VEC_INITIAL_SHIFT)
+
+#define SET_LINEAR_SIZE 4 /* must be <= than VEC_INTEGRAL_SIZE */
+#define SET_INITIAL_INDEX 2
+
+template <class C, class A = DefaultAlloc, int S = VEC_INTEGRAL_SHIFT_DEFAULT> // S must be a power of 2
+class Vec {
+ public:
+ int n;
+ int i; // size index for sets, reserve for vectors
+ C *v;
+ C e[VEC_INTEGRAL_SIZE];
+
+ Vec();
+ Vec<C,A,S>(const Vec<C,A,S> &vv);
+ Vec<C,A,S>(const C c);
+ ~Vec();
+
+ C &operator[](int i) const { return v[i]; }
+
+ C get(int i);
+ void add(C a);
+ void push_back(C a) { add(a); } // std::vector name
+ int add_exclusive(C a);
+ C& add();
+ C pop();
+ void reset();
+ void clear();
+ void free();
+ void free_and_clear();
+ void delete_and_clear();
+ void set_clear();
+ C *set_add(C a);
+ void set_remove(C a); // expensive, use BlockHash for cheaper remove
+ C *set_add_internal(C a);
+ int set_union(Vec<C,A,S> &v);
+ int set_intersection(Vec<C,A,S> &v);
+ int some_intersection(Vec<C,A,S> &v);
+ int some_disjunction(Vec<C,A,S> &v);
+ int some_difference(Vec<C,A,S> &v);
+ void set_intersection(Vec<C,A,S> &v, Vec<C,A,S> &result);
+ void set_disjunction(Vec<C,A,S> &v, Vec<C,A,S> &result);
+ void set_difference(Vec<C,A,S> &v, Vec<C,A,S> &result);
+ int set_count();
+ int count();
+ C *in(C a);
+ C *set_in(C a);
+ C first_in_set();
+ C *set_in_internal(C a);
+ void set_expand();
+ int index(C a);
+ void set_to_vec();
+ void vec_to_set();
+ void move(Vec<C,A,S> &v);
+ void copy(const Vec<C,A,S> &v);
+ void fill(int n);
+ void append(const Vec<C> &v);
+ void prepend(const Vec<C> &v);
+ void remove_index(int index);
+ void remove(C a) { int i = index(a); if (i>=0) remove_index(i); }
+ C& insert(int index);
+ void insert(int index, Vec<C> &vv);
+ void insert(int index, C a);
+ void push(C a) { insert(0, a); }
+ void reverse();
+ void reserve(int n);
+ C* end() const { return v + n; }
+ C &first() const { return v[0]; }
+ C &last() const { return v[n-1]; }
+ Vec<C,A,S>& operator=(Vec<C,A,S> &v) { this->copy(v); return *this; }
+ int length () const { return n; }
+ // vector::size() intentionally not implemented because it should mean "bytes" not count of elements
+ int write(int fd);
+ int read(int fd);
+ void qsort(bool (*lt)(C,C));
+
+ // private:
+ void move_internal(Vec<C,A,S> &v);
+ void copy_internal(const Vec<C,A,S> &v);
+ void add_internal(C a);
+ C& add_internal();
+ void addx();
+};
+
+// c -- class, p -- pointer to elements of v, v -- vector
+#define forv_Vec(_c, _p, _v) if ((_v).n) for (_c *qq__##_p = (_c*)0, *_p = (_v).v[0]; \
+ ((intptr_t)(qq__##_p) < (_v).length()) && ((_p = (_v).v[(intptr_t)qq__##_p]) || 1); qq__##_p = (_c*)(((intptr_t)qq__##_p) + 1))
+#define for_Vec(_c, _p, _v) if ((_v).n) for (_c *qq__##_p = (_c*)0, _p = (_v).v[0]; \
+ ((intptr_t)(qq__##_p) < (_v).length()) && ((_p = (_v).v[(intptr_t)qq__##_p]) || 1); qq__##_p = (_c*)(((intptr_t)qq__##_p) + 1))
+#define forvp_Vec(_c, _p, _v) if ((_v).n) for (_c *qq__##_p = (_c*)0, *_p = &(_v).v[0]; \
+ ((intptr_t)(qq__##_p) < (_v).length()) && ((_p = &(_v).v[(intptr_t)qq__##_p]) || 1); qq__##_p = (_c*)(((intptr_t)qq__##_p) + 1))
+
+template <class C, class A = DefaultAlloc, int S = VEC_INTEGRAL_SHIFT_DEFAULT> class Accum { public:
+ Vec<C,A,S> asset;
+ Vec<C,A,S> asvec;
+ void add(C c) { if (asset.set_add(c)) asvec.add(c); }
+ void add(Vec<C,A,S> v) { for (int i = 0; i < v.n; i++) if (v.v[i]) add(v.v[i]); }
+ void clear() { asset.clear(); asvec.clear(); }
+};
+
+// Intervals store sets in interval format (e.g. [1..10][12..12]).
+// Inclusion test is by binary search on intervals.
+// Deletion is not supported
+class Intervals : public Vec<int> {
+ public:
+ void insert(int n);
+ int in(int n);
+};
+
+// UnionFind supports fast unify and finding of
+// 'representitive elements'.
+// Elements are numbered from 0 to N-1.
+class UnionFind : public Vec<int> {
+ public:
+ // set number of elements, initialized to singletons, may be called repeatedly to increase size
+ void size(int n);
+ // return representitive element
+ int find(int n);
+ // unify the sets containing the two elements
+ void unify(int n, int m);
+};
+
+extern uintptr_t prime2[];
+extern uintptr_t open_hash_primes[256];
+
+/* IMPLEMENTATION */
+
+template <class C, class A, int S> inline
+Vec<C,A,S>::Vec() : n(0), i(0), v(0) {
+ memset(&e[0], 0, sizeof(e));
+}
+
+template <class C, class A, int S> inline
+Vec<C,A,S>::Vec(const Vec<C,A,S> &vv) {
+ copy(vv);
+}
+
+template <class C, class A, int S> inline
+Vec<C,A,S>::Vec(C c) {
+ n = 1;
+ i = 0;
+ v = &e[0];
+ e[0] = c;
+}
+
+template <class C, class A, int S> inline C
+Vec<C,A,S>::get(int i) {
+ if (i < n && i >= 0)
+ return v[i];
+ else
+ return 0;
+}
+
+template <class C, class A, int S> inline void
+Vec<C,A,S>::add(C a) {
+ if (n & (VEC_INTEGRAL_SIZE-1))
+ v[n++] = a;
+ else if (!v)
+ (v = e)[n++] = a;
+ else
+ add_internal(a);
+}
+
+template <class C, class A, int S> inline C&
+Vec<C,A,S>::add() {
+ C *ret;
+ if (n & (VEC_INTEGRAL_SIZE-1))
+ ret = &v[n++];
+ else if (!v)
+ ret = &(v = e)[n++];
+ else
+ ret = &add_internal();
+ return *ret;
+}
+
+template <class C, class A, int S> inline C
+Vec<C,A,S>::pop() {
+ if (!n)
+ return 0;
+ n--;
+ C ret = v[n];
+ if (!n)
+ clear();
+ return ret;
+}
+
+template <class C, class A, int S> inline void
+Vec<C,A,S>::set_clear() {
+ memset(v, 0, n * sizeof(C));
+}
+
+template <class C, class A, int S> inline C *
+Vec<C,A,S>::set_add(C a) {
+ if (n < SET_LINEAR_SIZE) {
+ for (C *c = v; c < v + n; c++)
+ if (*c == a)
+ return 0;
+ add(a);
+ return &v[n-1];
+ }
+ if (n == SET_LINEAR_SIZE) {
+ Vec<C,A,S> vv(*this);
+ clear();
+ for (C *c = vv.v; c < vv.v + vv.n; c++)
+ set_add_internal(*c);
+ }
+ return set_add_internal(a);
+}
+
+template <class C, class A, int S> void
+Vec<C,A,S>::set_remove(C a) {
+ Vec<C,A,S> tmp;
+ tmp.move(*this);
+ for (C *c = tmp.v; c < tmp.v + tmp.n; c++)
+ if (*c != a)
+ set_add(a);
+}
+
+template <class C, class A, int S> inline int
+Vec<C,A,S>::count() {
+ int x = 0;
+ for (C *c = v; c < v + n; c++)
+ if (*c)
+ x++;
+ return x;
+}
+
+template <class C, class A, int S> inline C*
+Vec<C,A,S>::in(C a) {
+ for (C *c = v; c < v + n; c++)
+ if (*c == a)
+ return c;
+ return NULL;
+}
+
+template <class C, class A, int S> inline int
+Vec<C,A,S>::add_exclusive(C a) {
+ if (!in(a)) {
+ add(a);
+ return 1;
+ } else
+ return 0;
+}
+
+template <class C, class A, int S> inline C *
+Vec<C,A,S>::set_in(C a) {
+ if (n <= SET_LINEAR_SIZE)
+ return in(a);
+ return set_in_internal(a);
+}
+
+template <class C, class A, int S> inline C
+Vec<C,A,S>::first_in_set() {
+ for (C *c = v; c < v + n; c++)
+ if (*c)
+ return *c;
+ return 0;
+}
+
+template <class C, class A, int S> inline int
+Vec<C,A,S>::index(C a) {
+ for (C *c = v; c < v + n; c++)
+ if (*c == a)
+ return c - v;
+ return -1;
+}
+
+template <class C, class A, int S> inline void
+Vec<C,A,S>::move_internal(Vec<C,A,S> &vv) {
+ n = vv.n;
+ i = vv.i;
+ if (vv.v == &vv.e[0]) {
+ memcpy(e, &vv.e[0], sizeof(e));
+ v = e;
+ } else
+ v = vv.v;
+}
+
+template <class C, class A, int S> inline void
+Vec<C,A,S>::move(Vec<C,A,S> &vv) {
+ move_internal(vv);
+ vv.v = 0;
+ vv.clear();
+}
+
+template <class C, class A, int S> inline void
+Vec<C,A,S>::copy(const Vec<C,A,S> &vv) {
+ n = vv.n;
+ i = vv.i;
+ if (vv.v == &vv.e[0]) {
+ memcpy(e, &vv.e[0], sizeof(e));
+ v = e;
+ } else {
+ if (vv.v)
+ copy_internal(vv);
+ else
+ v = 0;
+ }
+}
+
+template <class C, class A, int S> inline void
+Vec<C,A,S>::fill(int nn) {
+ for (int i = n; i < nn; i++)
+ add() = 0;
+}
+
+template <class C, class A, int S> inline void
+Vec<C,A,S>::append(const Vec<C> &vv) {
+ for (C *c = vv.v; c < vv.v + vv.n; c++)
+ if (*c != 0)
+ add(*c);
+}
+
+template <class C, class A, int S> inline void
+Vec<C,A,S>::prepend(const Vec<C> &vv) {
+ if (vv.n) {
+ int oldn = n;
+ fill(n + vv.n);
+ if (oldn)
+ memmove(&v[vv.n], &v[0], oldn * sizeof(v[0]));
+ memcpy(&v[0], vv.v, vv.n * sizeof(v[0]));
+ }
+}
+
+template <class C, class A, int S> void
+Vec<C,A,S>::add_internal(C a) {
+ addx();
+ v[n++] = a;
+}
+
+template <class C, class A, int S> C&
+Vec<C,A,S>::add_internal() {
+ addx();
+ return v[n++];
+}
+
+template <class C, class A, int S> C *
+Vec<C,A,S>::set_add_internal(C c) {
+ int j, k;
+ if (n) {
+ uintptr_t h = (uintptr_t)c;
+ h = h % n;
+ for (k = h, j = 0; j < i + 3; j++) {
+ if (!v[k]) {
+ v[k] = c;
+ return &v[k];
+ } else if (v[k] == c)
+ return 0;
+ k = (k + open_hash_primes[j]) % n;
+ }
+ }
+ Vec<C,A,S> vv;
+ vv.move_internal(*this);
+ set_expand();
+ if (vv.v)
+ set_union(vv);
+ return set_add(c);
+}
+
+template <class C, class A, int S> C *
+Vec<C,A,S>::set_in_internal(C c) {
+ int j, k;
+ if (n) {
+ uintptr_t h = (uintptr_t)c;
+ h = h % n;
+ for (k = h, j = 0; j < i + 3; j++) {
+ if (!v[k])
+ return 0;
+ else if (v[k] == c)
+ return &v[k];
+ k = (k + open_hash_primes[j]) % n;
+ }
+ }
+ return 0;
+}
+
+template <class C, class A, int S> int
+Vec<C,A,S>::set_union(Vec<C,A,S> &vv) {
+ int changed = 0;
+ for (int i = 0; i < vv.n; i++)
+ if (vv.v[i])
+ changed = set_add(vv.v[i]) || changed;
+ return changed;
+}
+
+template <class C, class A, int S> int
+Vec<C,A,S>::set_intersection(Vec<C,A,S> &vv) {
+ Vec<C,A,S> tv;
+ tv.move(*this);
+ int changed = 0;
+ for (int i = 0; i < tv.n; i++)
+ if (tv.v[i]) {
+ if (vv.set_in(tv.v[i]))
+ set_add(tv.v[i]);
+ else
+ changed = 1;
+ }
+ return changed;
+}
+
+template <class C, class A, int S> int
+Vec<C,A,S>::some_intersection(Vec<C,A,S> &vv) {
+ for (int i = 0; i < n; i++)
+ if (v[i])
+ if (vv.set_in(v[i]))
+ return 1;
+ return 0;
+}
+
+template <class C, class A, int S> int
+Vec<C,A,S>::some_disjunction(Vec<C,A,S> &vv) {
+ for (int i = 0; i < n; i++)
+ if (v[i])
+ if (!vv.set_in(v[i]))
+ return 1;
+ for (int i = 0; i < vv.n; i++)
+ if (vv.v[i])
+ if (!set_in(vv.v[i]))
+ return 1;
+ return 0;
+}
+
+template <class C, class A, int S> void
+Vec<C,A,S>::set_intersection(Vec<C,A,S> &vv, Vec<C,A,S> &result) {
+ for (int i = 0; i < n; i++)
+ if (v[i])
+ if (vv.set_in(v[i]))
+ result.set_add(v[i]);
+}
+
+template <class C, class A, int S> void
+Vec<C,A,S>::set_disjunction(Vec<C,A,S> &vv, Vec<C,A,S> &result) {
+ for (int i = 0; i < n; i++)
+ if (v[i])
+ if (!vv.set_in(v[i]))
+ result.set_add(v[i]);
+ for (int i = 0; i < vv.n; i++)
+ if (vv.v[i])
+ if (!set_in(vv.v[i]))
+ result.set_add(vv.v[i]);
+}
+
+template <class C, class A, int S> void
+Vec<C,A,S>::set_difference(Vec<C,A,S> &vv, Vec<C,A,S> &result) {
+ for (int i = 0; i < n; i++)
+ if (v[i])
+ if (!vv.set_in(v[i]))
+ result.set_add(v[i]);
+}
+
+template <class C, class A, int S> int
+Vec<C,A,S>::some_difference(Vec<C,A,S> &vv) {
+ for (int i = 0; i < n; i++)
+ if (v[i])
+ if (!vv.set_in(v[i]))
+ return 1;
+ return 0;
+}
+
+template <class C, class A, int S> int
+Vec<C,A,S>::set_count() {
+ int x = 0;
+ for (int i = 0; i < n; i++)
+ if (v[i])
+ x++;
+ return x;
+}
+
+template <class C, class A, int S> void
+Vec<C,A,S>::set_to_vec() {
+ C *x = &v[0], *y = x;
+ for (; y < v + n; y++) {
+ if (*y) {
+ if (x != y)
+ *x = *y;
+ x++;
+ }
+ }
+ if (i) {
+ i = prime2[i]; // convert set allocation to reserve
+ if (i - n > 0)
+ memset(&v[n], 0, (i - n) * (sizeof(C)));
+ } else {
+ i = 0;
+ if (v == &e[0] && VEC_INTEGRAL_SIZE - n > 0)
+ memset(&v[n], 0, (VEC_INTEGRAL_SIZE - n) * (sizeof(C)));
+ }
+}
+
+template <class C, class A, int S> void
+Vec<C,A,S>::vec_to_set() {
+ Vec<C,A,S> vv;
+ vv.move(*this);
+ for (C *c = vv.v; c < vv.v + vv.n; c++)
+ set_add(*c);
+}
+
+template <class C, class A, int S> void
+Vec<C,A,S>::remove_index(int index) {
+ if (n > 1)
+ memmove(&v[index], &v[index+1], (n - 1 - index) * sizeof(v[0]));
+ n--;
+ if (n <= 0)
+ v = e;
+}
+
+template <class C, class A, int S> void
+Vec<C,A,S>::insert(int index, C a) {
+ add();
+ memmove(&v[index+1], &v[index], (n - index - 1) * sizeof(C));
+ v[index] = a;
+}
+
+template <class C, class A, int S> void
+Vec<C,A,S>::insert(int index, Vec<C> &vv) {
+ fill(n + vv.n);
+ memmove(&v[index+vv.n], &v[index], (n - index - 1) * sizeof(C));
+ for (int x = 0; x < vv.n; x++)
+ v[index + x] = vv[x];
+}
+
+template <class C, class A, int S> C &
+Vec<C,A,S>::insert(int index) {
+ add();
+ memmove(&v[index+1], &v[index], (n - index - 1) * sizeof(C));
+ memset(&v[index], 0, sizeof(C));
+ return v[index];
+}
+
+template <class C, class A, int S> void
+Vec<C,A,S>::reverse() {
+ for (int i = 0; i < n/2; i++) {
+ C *s = &v[i], *e = &v[n - 1 - i];
+ C t;
+ memcpy(&t, s, sizeof(t));
+ memcpy(s, e, sizeof(t));
+ memcpy(e, &t, sizeof(t));
+ }
+}
+
+template <class C, class A, int S> void
+Vec<C,A,S>::copy_internal(const Vec<C,A,S> &vv) {
+ int l = n, nl = (1 + VEC_INITIAL_SHIFT);
+ l = l >> VEC_INITIAL_SHIFT;
+ while (l) { l = l >> 1; nl++; }
+ nl = 1 << nl;
+ v = (C*)A::alloc(nl * sizeof(C));
+ memcpy(v, vv.v, n * sizeof(C));
+ memset(v + n, 0, (nl - n) * sizeof(C));
+ if (i > n) // reset reserve
+ i = 0;
+}
+
+template <class C, class A, int S> void
+Vec<C,A,S>::set_expand() {
+ if (!n)
+ i = SET_INITIAL_INDEX;
+ else
+ i = i + 1;
+ n = prime2[i];
+ v = (C*)A::alloc(n * sizeof(C));
+ memset(v, 0, n * sizeof(C));
+}
+
+template <class C, class A, int S> inline void
+Vec<C,A,S>::reserve(int x) {
+ if (x <= n)
+ return;
+ int xx = 1 << VEC_INITIAL_SHIFT;
+ while (xx < x) xx *= 2;
+ i = xx;
+ void *vv = (void*)v;
+ v = (C*)A::alloc(i * sizeof(C));
+ if (vv && n)
+ memcpy(v, vv, n * sizeof(C));
+ memset(&v[n], 0, (i-n) * sizeof(C));
+ if (vv && vv != e)
+ A::free(vv);
+}
+
+template <class C, class A, int S> inline void
+Vec<C,A,S>::addx() {
+ if (!v) {
+ v = e;
+ return;
+ }
+ if (v == e) {
+ v = (C*)A::alloc(VEC_INITIAL_SIZE * sizeof(C));
+ memcpy(v, &e[0], n * sizeof(C));
+ assert(n < VEC_INITIAL_SIZE);
+ memset(&v[n], 0, (VEC_INITIAL_SIZE - n) * sizeof(C));
+ } else {
+ if ((n & (n-1)) == 0) {
+ int nl = n * 2;
+ if (nl <= i)
+ return;
+ else
+ i = 0;
+ void *vv = (void*)v;
+ v = (C*)A::alloc(nl * sizeof(C));
+ memcpy(v, vv, n * sizeof(C));
+ memset(&v[n], 0, n * sizeof(C));
+ A::free(vv);
+ }
+ }
+}
+
+template <class C, class A, int S> inline void
+Vec<C,A,S>::free() {
+ if (v && v != e) A::free(v);
+}
+
+template <class C, class A, int S> inline void
+Vec<C,A,S>::reset() {
+ v = NULL;
+ n = 0;
+ i = 0;
+}
+
+template <class C, class A, int S> inline void
+Vec<C,A,S>::clear() {
+ if (v && v != e) A::free(v);
+ reset();
+}
+
+template <class C, class A, int S> inline void
+Vec<C,A,S>::free_and_clear() {
+ for (int x = 0; x < n; x++)
+ if (v[x])
+ A::free(v[x]);
+ clear();
+}
+
+template <class C, class A, int S> inline void
+Vec<C,A,S>::delete_and_clear() {
+ for (int x = 0; x < n; x++)
+ if (v[x])
+ delete v[x];
+ clear();
+}
+
+template <class C, class A, int S>
+inline Vec<C,A,S>::~Vec() {
+ if (v && v != e) A::free(v);
+}
+
+template <class C, class A, int S>
+inline int marshal_size(Vec<C,A,S> &v) {
+ int l = sizeof(int) * 2;
+ for (int x = 0; x < v.n; x++)
+ l += ::marshal_size(v.v[x]);
+ return l;
+}
+
+template <class C, class A, int S>
+inline int marshal(Vec<C,A,S> &v, char *buf) {
+ char *x = buf;
+ *(int*)x = v.n; x += sizeof(int);
+ *(int*)x = v.i; x += sizeof(int);
+ for (int i = 0; i < v.n; i++)
+ x += ::marshal(v.v[i], x);
+ return x - buf;
+}
+
+template <class C, class A, int S>
+inline int unmarshal(Vec<C,A,S> &v, char *buf) {
+ char *x = buf;
+ v.n = *(int*)x; x += sizeof(int);
+ v.i = *(int*)x; x += sizeof(int);
+ if (v.n) {
+ v.v = (C*)A::alloc(sizeof(C) * v.n);
+ memset(v.v, 0, sizeof(C) * v.n);
+ } else
+ v.v = v.e;
+ for (int i = 0; i < v.n; i++)
+ x += ::unmarshal(v.v[i], x);
+ return x - buf;
+}
+
+template <class C, class A, int S>
+inline int Vec<C,A,S>::write(int fd) {
+ int r = 0, t = 0;
+ if ((r = ::write(fd, this, sizeof(*this))) < 0) return r; t += r;
+ if ((r = ::write(fd, v, n * sizeof(C))) < 0) return r; t += r;
+ return t;
+}
+
+template <class C, class A, int S>
+inline int Vec<C,A,S>::read(int fd) {
+ int r = 0, t = 0;
+ if ((r = ::read(fd, this, sizeof(*this))) < 0) return r; t += r;
+ v = (C*)A::alloc(sizeof(C) * n);
+ memset(v, 0, sizeof(C) * n);
+ if ((r = ::read(fd, v, n * sizeof(C))) < 0) return r; t += r;
+ return t;
+}
+
+template <class C>
+inline void qsort_Vec(C *left, C *right, bool (*lt)(C,C)) {
+ Lagain:
+ if (right - left < 5) {
+ for (C *y = right - 1; y > left; y--) {
+ for (C *x = left; x < y; x++) {
+ if (lt(x[1],x[0])) {
+ C t = x[0];
+ x[0] = x[1];
+ x[1] = t;
+ }
+ }
+ }
+ } else {
+ C *i = left + 1, *j = right - 1;
+ C x = *left;
+ for (;;) {
+ while (lt(x,*j)) j--;
+ while (i < j && lt(*i,x)) i++;
+ if (i >= j) break;
+ C t = *i;
+ *i = *j;
+ *j = t;
+ i++; j--;
+ }
+ if (j == right - 1) {
+ *left = *(right - 1);
+ *(right - 1) = x;
+ right--;
+ goto Lagain;
+ }
+ if (left < j) qsort_Vec<C>(left, j + 1, lt);
+ if (j + 2 < right) qsort_Vec<C>(j + 1, right, lt);
+ }
+}
+
+template <class C>
+inline void qsort_VecRef(C *left, C *right, bool (*lt)(C&,C&)) {
+ Lagain:
+ if (right - left < 5) {
+ for (C *y = right - 1; y > left; y--) {
+ for (C *x = left; x < y; x++) {
+ if (lt(x[1],x[0])) {
+ C t = x[0];
+ x[0] = x[1];
+ x[1] = t;
+ }
+ }
+ }
+ } else {
+ C *i = left + 1, *j = right - 1;
+ C x = *left;
+ for (;;) {
+ while (lt(x,*j)) j--;
+ while (i < j && lt(*i,x)) i++;
+ if (i >= j) break;
+ C t = *i;
+ *i = *j;
+ *j = t;
+ i++; j--;
+ }
+ if (j == right - 1) {
+ *left = *(right - 1);
+ *(right - 1) = x;
+ right--;
+ goto Lagain;
+ }
+ if (left < j) qsort_VecRef<C>(left, j + 1, lt);
+ if (j + 2 < right) qsort_VecRef<C>(j + 1, right, lt);
+ }
+}
+
+template <class C, class A, int S>
+inline void Vec<C,A,S>::qsort(bool (*lt)(C,C)) {
+ if (n)
+ qsort_Vec<C>(&v[0], end(), lt);
+}
+
+void test_vec();
+
+#endif
Added: trafficserver/traffic/trunk/lib/ts/defalloc.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/lib/ts/defalloc.h?rev=1086420&view=auto
==============================================================================
--- trafficserver/traffic/trunk/lib/ts/defalloc.h (added)
+++ trafficserver/traffic/trunk/lib/ts/defalloc.h Mon Mar 28 22:04:17 2011
@@ -0,0 +1,32 @@
+/** @file
+
+ Default allocator: malloc/free
+
+ @section license License
+
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+ */
+#ifndef _defalloc_H_
+#define _defalloc_H_
+
+class DefaultAlloc { public:
+ static void *alloc(int s) { return ::malloc(s); }
+ static void free(void *p) { ::free(p); }
+};
+
+#endif
+
Modified: trafficserver/traffic/trunk/lib/ts/libts.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/lib/ts/libts.h?rev=1086420&r1=1086419&r2=1086420&view=diff
==============================================================================
--- trafficserver/traffic/trunk/lib/ts/libts.h (original)
+++ trafficserver/traffic/trunk/lib/ts/libts.h Mon Mar 28 22:04:17 2011
@@ -37,6 +37,8 @@
#if !defined (_inktomiplus_h_)
#define _inktomiplus_h_
+#define std *** _FIXME_REMOVE_DEPENDENCY_ON_THE_STL_ ***
+
#include "ink_config.h"
#include "ink_platform.h"
#include "ink_port.h"
@@ -89,6 +91,7 @@
#include "List.h"
#include "INK_MD5.h"
#include "MMH.h"
+#include "Map.h"
#include "MimeTable.h"
#include "ParseRules.h"
#include "Ptr.h"
@@ -103,5 +106,6 @@
#include "Regression.h"
#include "HostLookup.h"
#include "InkErrno.h"
+#include "Vec.h"
#endif /*_inktomiplus_h_*/
Added: trafficserver/traffic/trunk/lib/ts/test_Map.cc
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/lib/ts/test_Map.cc?rev=1086420&view=auto
==============================================================================
--- trafficserver/traffic/trunk/lib/ts/test_Map.cc (added)
+++ trafficserver/traffic/trunk/lib/ts/test_Map.cc Mon Mar 28 22:04:17 2011
@@ -0,0 +1,112 @@
+/** @file
+
+ Test code for the Map templates.
+
+ @section license License
+
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+*/
+#include <stdint.h>
+#include "Map.h"
+
+typedef const char cchar;
+
+int main(int argc, char **argv) {
+ typedef Map<cchar *, cchar *> SSMap;
+ typedef MapElem<cchar *, cchar *> SSMapElem;
+#define form_SSMap(_p, _v) form_Map(SSMapElem, _p, _v)
+ SSMap ssm;
+ ssm.put("a", "A");
+ ssm.put("b", "B");
+ ssm.put("c", "C");
+ ssm.put("d", "D");
+ form_SSMap(x, ssm) ;
+
+ StringChainHash<> h;
+ cchar *hi = "hi", *ho = "ho", *hum = "hum", *hhi = "hhi";
+ hhi++;
+ h.put(hi);
+ h.put(ho);
+ assert(h.put(hum) == hum);
+ assert(h.put(hhi) == hi);
+ assert(h.get(hhi) == hi && h.get(hi) == hi && h.get(ho) == ho);
+ assert(h.get("he") == 0 && h.get("hee") == 0);
+ h.del(ho);
+ assert(h.get(ho) == 0);
+
+ StringBlockHash hh;
+ hh.put(hi);
+ hh.put(ho);
+ assert(hh.put(hum) == 0);
+ assert(hh.put(hhi) == hi);
+ assert(hh.get(hhi) == hi && hh.get(hi) == hi && hh.get(ho) == ho);
+ assert(hh.get("he") == 0 && hh.get("hee") == 0);
+ hh.del(hi);
+ assert(hh.get(hhi) == 0);
+ assert(hh.get(hi) == 0);
+
+ HashMap<cchar *, StringHashFns, int> sh;
+ sh.put(hi, 1);
+ sh.put(ho, 2);
+ sh.put(hum, 3);
+ sh.put(hhi, 4);
+ assert(sh.get(hi) == 4);
+ assert(sh.get(ho) == 2);
+ assert(sh.get(hum) == 3);
+ sh.put("aa", 5);
+ sh.put("ab", 6);
+ sh.put("ac", 7);
+ sh.put("ad", 8);
+ sh.put("ae", 9);
+ sh.put("af", 10);
+ assert(sh.get(hi) == 4);
+ assert(sh.get(ho) == 2);
+ assert(sh.get(hum) == 3);
+ assert(sh.get("af") == 10);
+ assert(sh.get("ac") == 7);
+
+ ChainHashMap<cchar *, StringHashFns, int> ssh;
+ ssh.put(hi, 1);
+ ssh.put(ho, 2);
+ ssh.put(hum, 3);
+ ssh.put(hhi, 4);
+ assert(ssh.get(hi) == 4);
+ assert(ssh.get(ho) == 2);
+ assert(ssh.get(hum) == 3);
+ ssh.put("aa", 5);
+ ssh.put("ab", 6);
+ ssh.put("ac", 7);
+ ssh.put("ad", 8);
+ ssh.put("ae", 9);
+ ssh.put("af", 10);
+ assert(ssh.get(hi) == 4);
+ assert(ssh.get(ho) == 2);
+ assert(ssh.get(hum) == 3);
+ assert(ssh.get("af") == 10);
+ assert(ssh.get("ac") == 7);
+ ssh.del(ho);
+ assert(ssh.get(ho) == 0);
+
+ Vec<int> ints;
+ ssh.get_values(ints);
+ assert(ints.n == 8);
+ Vec<cchar *> chars;
+ ssh.get_keys(chars);
+ assert(chars.n == 8);
+ printf("test_Map PASSED\n");
+}
+
Added: trafficserver/traffic/trunk/lib/ts/test_Vec.cc
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/lib/ts/test_Vec.cc?rev=1086420&view=auto
==============================================================================
--- trafficserver/traffic/trunk/lib/ts/test_Vec.cc (added)
+++ trafficserver/traffic/trunk/lib/ts/test_Vec.cc Mon Mar 28 22:04:17 2011
@@ -0,0 +1,97 @@
+/* -*-Mode: c++;-*-
+ Various vector related code.
+
+ @section license License
+
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+*/
+
+/* UnionFind after Tarjan */
+
+#include <stdint.h>
+#include <stdio.h>
+#include <assert.h>
+#include "Vec.h"
+
+int main(int argc, char **argv) {
+ Vec<void *> v, vv, vvv;
+ int tt = 99 * 50, t = 0;
+
+ for (int i = 0; i < 100; i++)
+ v.add((void*)(intptr_t)i);
+ for (int i = 0; i < 100; i++)
+ t += (int)(intptr_t)v.v[i];
+ assert(t == tt);
+
+ t = 0;
+ for (int i = 1; i < 100; i++)
+ vv.set_add((void*)(intptr_t)i);
+ for (int i = 1; i < 100; i++)
+ vvv.set_add((void*)(intptr_t)i);
+ for (int i = 1; i < 100; i++)
+ vvv.set_add((void*)(intptr_t)(i * 1000));
+ vv.set_union(vvv);
+ for (int i = 0; i < vv.n; i++)
+ if (vv.v[i])
+ t += (int)(intptr_t)vv.v[i];
+ assert(t == tt + 1000 * tt);
+
+ v.clear();
+ v.reserve(1000);
+ t = 0;
+ for (int i = 0; i < 1000; i++)
+ v.add((void*)(intptr_t)i);
+ for (int i = 0; i < 1000; i++)
+ t += (int)(intptr_t)v.v[i];
+ assert(t == 999 * 500);
+ printf("%d %d\n", v.n, v.i);
+
+ Intervals in;
+ in.insert(1);
+ assert(in.n == 2);
+ in.insert(2);
+ assert(in.n == 2);
+ in.insert(6);
+ assert(in.n == 4);
+ in.insert(7);
+ assert(in.n == 4);
+ in.insert(9);
+ assert(in.n == 6);
+ in.insert(4);
+ assert(in.n == 8);
+ in.insert(5);
+ assert(in.n == 6);
+ in.insert(3);
+ assert(in.n == 4);
+ in.insert(8);
+ assert(in.n == 2);
+
+ UnionFind uf;
+ uf.size(4);
+ uf.unify(0,1);
+ uf.unify(2,3);
+ assert(uf.find(2) == uf.find(3));
+ assert(uf.find(0) == uf.find(1));
+ assert(uf.find(0) != uf.find(3));
+ assert(uf.find(1) != uf.find(3));
+ assert(uf.find(1) != uf.find(2));
+ assert(uf.find(0) != uf.find(2));
+ uf.unify(1,2);
+ assert(uf.find(0) == uf.find(3));
+ assert(uf.find(1) == uf.find(3));
+ printf("test_Vec PASSED\n");
+}
Modified: trafficserver/traffic/trunk/proxy/ControlBase.cc
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/proxy/ControlBase.cc?rev=1086420&r1=1086419&r2=1086420&view=diff
==============================================================================
--- trafficserver/traffic/trunk/proxy/ControlBase.cc (original)
+++ trafficserver/traffic/trunk/proxy/ControlBase.cc Mon Mar 28 22:04:17 2011
@@ -43,6 +43,7 @@
#include "HTTP.h"
#include "ControlMatcher.h"
#include "HdrUtils.h"
+#include "Vec.h"
#include "tsconfig/TsBuffer.h"
@@ -472,21 +473,14 @@ ControlBase::~ControlBase() {
void
ControlBase::clear() {
- // Free all of the modifiers.
- for ( Array::iterator spot = _mods.begin(), limit = _mods.end()
- ; spot != limit
- ; ++spot
- )
- delete *spot;
- // Erase the pointers.
- _mods.clear();
+ _mods.delete_and_clear();
}
// static const modifier_el default_el = { MOD_INVALID, NULL };
void
ControlBase::Print() {
- int n = _mods.size();
+ int n = _mods.length();
if (0 >= n) return;
@@ -520,10 +514,8 @@ ControlBase::CheckModifiers(HttpRequestD
if (!request_data->tag && findModOfType(Modifier::MOD_TAG))
return false;
- for (int i = 0, n = _mods.size() ; i < n; ++i) {
- Modifier* cur_mod = _mods[i];
+ forv_Vec(Modifier, cur_mod, _mods)
if (cur_mod && ! cur_mod->check(request_data)) return false;
- }
return true;
}
@@ -544,10 +536,8 @@ static const char *errorFormats[] = {
ControlBase::Modifier*
ControlBase::findModOfType(Modifier::Type t) const {
- for (int i = 0, n = _mods.size(); i < n; ++i) {
- Modifier* m = _mods[i];
- if (m && t == m->type()) return m;
- }
+ forv_Vec(Modifier, m, _mods)
+ if (m && t == m->type()) return m;
return 0;
}
Modified: trafficserver/traffic/trunk/proxy/ControlBase.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/proxy/ControlBase.h?rev=1086420&r1=1086419&r2=1086420&view=diff
==============================================================================
--- trafficserver/traffic/trunk/proxy/ControlBase.h (original)
+++ trafficserver/traffic/trunk/proxy/ControlBase.h Mon Mar 28 22:04:17 2011
@@ -34,7 +34,7 @@
#define _CONTROL_BASE_H_
#include "libts.h"
-#include <vector>
+
class HttpRequestData;
class Tokenizer;
struct matcher_line;
@@ -86,7 +86,7 @@ protected:
/// @internal Ugly but it's the only place external access is needed.
char const* getSchemeModText() const;
private:
- typedef std::vector<Modifier*> Array;
+ typedef Vec<Modifier*> Array;
Array _mods;
const char *ProcessSrcIp(char *val, void **opaque_ptr);
const char *ProcessTimeOfDay(char *val, void **opaque_ptr);
Modified: trafficserver/traffic/trunk/proxy/http/HttpConnectionCount.cc
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/proxy/http/HttpConnectionCount.cc?rev=1086420&r1=1086419&r2=1086420&view=diff
==============================================================================
--- trafficserver/traffic/trunk/proxy/http/HttpConnectionCount.cc (original)
+++ trafficserver/traffic/trunk/proxy/http/HttpConnectionCount.cc Mon Mar 28 22:04:17 2011
@@ -24,5 +24,5 @@
#include "HttpConnectionCount.h"
-ConnectionCount *ConnectionCount::_connectionCount = NULL;
+ConnectionCount ConnectionCount::_connectionCount;
ink_mutex ConnectionCount::_mutex;
Modified: trafficserver/traffic/trunk/proxy/http/HttpConnectionCount.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/proxy/http/HttpConnectionCount.h?rev=1086420&r1=1086419&r2=1086420&view=diff
==============================================================================
--- trafficserver/traffic/trunk/proxy/http/HttpConnectionCount.h (original)
+++ trafficserver/traffic/trunk/proxy/http/HttpConnectionCount.h Mon Mar 28 22:04:17 2011
@@ -22,28 +22,11 @@
*/
//
-#include "ink_defs.h"
+#include "libts.h"
+#include "Map.h"
#ifndef _HTTP_CONNECTION_COUNT_H_
-#if (__GNUC__ >= 3)
-#define _BACKWARD_BACKWARD_WARNING_H // needed for gcc 4.3
-#include <ext/hash_map>
-#undef _BACKWARD_BACKWARD_WARNING_H
-#else
-#include <hash_map>
-#endif
-// XXX - had to include map to get around "max" begin defined as a macro
-// in the traffic server code, really odd
-#include <map>
-#include <ink_mutex.h>
-
-#if (__GNUC__ >= 3)
-using namespace __gnu_cxx;
-#endif
-using namespace std;
-
-
/**
* Singleton class to keep track of the number of connections per host
*/
@@ -54,15 +37,8 @@ public:
* Static method to get the instance of the class
* @return Returns a pointer to the instance of the class
*/
- static ConnectionCount *getInstance()
- {
- ink_mutex_acquire(&_mutex);
- if (_connectionCount == NULL) {
- _connectionCount = new ConnectionCount;
- }
- ink_mutex_release(&_mutex);
-
- return _connectionCount;
+ static ConnectionCount *getInstance() {
+ return &_connectionCount;
}
/**
@@ -70,17 +46,11 @@ public:
* @param ip IP address of the host
* @return Number of connections
*/
- int getCount(const unsigned int ip)
- {
+ int getCount(const unsigned int ip) {
ink_mutex_acquire(&_mutex);
- hash_map<unsigned int, int>::const_iterator it = _hostCount.find(ip);
+ int count = _hostCount.get(ip);
ink_mutex_release(&_mutex);
-
- if (it != _hostCount.end()) {
- return it->second;
- } else {
- return 0;
- }
+ return count;
}
/**
@@ -90,26 +60,18 @@ public:
*/
void incrementCount(const unsigned int ip, const int delta = 1) {
ink_mutex_acquire(&_mutex);
- hash_map<unsigned int, int>::iterator it = _hostCount.find(ip);
- if (it != _hostCount.end()) {
- it->second += delta;
- } else {
- _hostCount[ip] = delta;
- }
+ int count = _hostCount.get(ip);
+ _hostCount.put(ip, count + delta);
ink_mutex_release(&_mutex);
}
private:
// Hide the constructor and copy constructor
- ConnectionCount() {
- }
- ConnectionCount(const ConnectionCount & x)
- {
- NOWARN_UNUSED(x);
- }
+ ConnectionCount() { }
+ ConnectionCount(const ConnectionCount & x) { NOWARN_UNUSED(x); }
- static ConnectionCount *_connectionCount;
- hash_map<unsigned int, int>_hostCount;
+ static ConnectionCount _connectionCount;
+ Map<unsigned int, int> _hostCount;
static ink_mutex _mutex;
};
Modified: trafficserver/traffic/trunk/proxy/http/remap/RemapProcessor.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/proxy/http/remap/RemapProcessor.h?rev=1086420&r1=1086419&r2=1086420&view=diff
==============================================================================
--- trafficserver/traffic/trunk/proxy/http/remap/RemapProcessor.h (original)
+++ trafficserver/traffic/trunk/proxy/http/remap/RemapProcessor.h Mon Mar 28 22:04:17 2011
@@ -31,6 +31,7 @@
#include "RemapPlugins.h"
#include "RemapPluginInfo.h"
#include "ReverseProxy.h"
+#undef std // FIXME: remove dependency on the STL
#include <map>
#define EVENT_REMAP_START (REMAP_EVENT_EVENTS_START+0)
Modified: trafficserver/traffic/trunk/proxy/http/remap/UrlMappingPathIndex.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/proxy/http/remap/UrlMappingPathIndex.h?rev=1086420&r1=1086419&r2=1086420&view=diff
==============================================================================
--- trafficserver/traffic/trunk/proxy/http/remap/UrlMappingPathIndex.h (original)
+++ trafficserver/traffic/trunk/proxy/http/remap/UrlMappingPathIndex.h Mon Mar 28 22:04:17 2011
@@ -23,6 +23,8 @@
#ifndef _URL_MAPPING_PATH_INDEX_H
#define _URL_MAPPING_PATH_INDEX_H
+#include "libts.h"
+#undef std // FIXME: remove dependancy on the STL
#include <map>
#include "URL.h"
Modified: trafficserver/traffic/trunk/proxy/logstats.cc
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/proxy/logstats.cc?rev=1086420&r1=1086419&r2=1086420&view=diff
==============================================================================
--- trafficserver/traffic/trunk/proxy/logstats.cc (original)
+++ trafficserver/traffic/trunk/proxy/logstats.cc Mon Mar 28 22:04:17 2011
@@ -21,6 +21,8 @@
limitations under the License.
*/
+#include "libts.h"
+#undef std // FIXME: remove dependency on the STL
#include "ink_config.h"
#include "ink_file.h"
#include "ink_unused.h"