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 2012/03/28 05:33:12 UTC
[3/5] git commit: TS-1135: move Trie.h to libts
TS-1135: move Trie.h to libts
Project: http://git-wip-us.apache.org/repos/asf/trafficserver/repo
Commit: http://git-wip-us.apache.org/repos/asf/trafficserver/commit/687fdbfe
Tree: http://git-wip-us.apache.org/repos/asf/trafficserver/tree/687fdbfe
Diff: http://git-wip-us.apache.org/repos/asf/trafficserver/diff/687fdbfe
Branch: refs/heads/master
Commit: 687fdbfee6d47c6d4d81f9458d69d23311f6f35d
Parents: 2731f6b
Author: James Peach <jp...@apache.org>
Authored: Wed Mar 7 21:52:25 2012 -0800
Committer: James Peach <jp...@apache.org>
Committed: Tue Mar 27 20:32:26 2012 -0700
----------------------------------------------------------------------
lib/ts/Trie.h | 242 ++++++++++++++++++++++++++++++++++++
proxy/http/remap/Makefile.am | 1 -
proxy/http/remap/Trie.h | 243 -------------------------------------
3 files changed, 242 insertions(+), 244 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/687fdbfe/lib/ts/Trie.h
----------------------------------------------------------------------
diff --git a/lib/ts/Trie.h b/lib/ts/Trie.h
new file mode 100644
index 0000000..2f79e5a
--- /dev/null
+++ b/lib/ts/Trie.h
@@ -0,0 +1,242 @@
+/** @file
+
+ A brief file description
+
+ @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 _TRIE_H
+#define _TRIE_H
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "List.h"
+
+// Note that you should provide the class to use here, but we'll store
+// pointers to such objects internally.
+template<typename T>
+class Trie
+{
+public:
+ Trie()
+ {
+ m_root.Clear();
+ }
+
+ // will return false for duplicates; key should be NULL-terminated
+ // if key_len is defaulted to -1
+ bool Insert(const char *key, T *value, int rank, int key_len = -1);
+
+ // will return false if not found; else value_ptr will point to found value
+ T* Search(const char *key, int key_len = -1);
+ void Clear();
+ void Print();
+
+ virtual ~Trie() { Clear(); }
+
+private:
+ static const int N_NODE_CHILDREN = 256;
+
+ class Node
+ {
+ public:
+ T* value;
+ bool occupied;
+ int rank;
+
+ void Clear() {
+ occupied = false;
+ rank = 0;
+ bzero(children, sizeof(Node *) * N_NODE_CHILDREN);
+ }
+
+ void Print(const char *debug_tag) const;
+ inline Node* GetChild(char index) const { return children[static_cast<unsigned char>(index)]; }
+ inline void SetChild(char index, Node *child) { children[static_cast<unsigned char>(index)] = child; }
+
+ private:
+ Node *children[N_NODE_CHILDREN];
+ };
+
+ Node m_root;
+ Queue<T> m_value_list;
+
+ void _CheckArgs(const char *key, int &key_len) const;
+ void _Clear(Node *node);
+
+ // make copy-constructor and assignment operator private
+ // till we properly implement them
+ Trie(const Trie<T> &rhs) { };
+ Trie &operator =(const Trie<T> &rhs) { return *this; }
+};
+
+template<typename T>
+void
+Trie<T>::_CheckArgs(const char *key, int &key_len) const
+{
+ if (!key) {
+ key_len = 0;
+ }
+ else if (key_len == -1) {
+ key_len = strlen(key);
+ }
+}
+
+template<typename T>
+bool
+Trie<T>::Insert(const char *key, T* value, int rank, int key_len /* = -1 */)
+{
+ _CheckArgs(key, key_len);
+
+ Node *next_node;
+ Node *curr_node = &m_root;
+ int i = 0;
+
+ while (true) {
+ if (is_debug_tag_set("Trie::Insert")) {
+ Debug("Trie::Insert", "Visiting Node...");
+ curr_node->Print("Trie::Insert");
+ }
+ if (i == key_len) {
+ break;
+ }
+ next_node = curr_node->GetChild(key[i]);
+ if (!next_node) {
+ while (i < key_len) {
+ Debug("Trie::Insert", "Creating child node for char %c (%d)", key[i], key[i]);
+ curr_node->SetChild(key[i], static_cast<Node*>(ats_malloc(sizeof(Node))));
+ curr_node = curr_node->GetChild(key[i]);
+ curr_node->Clear();
+ ++i;
+ }
+ break;
+ }
+ curr_node = next_node;
+ ++i;
+ }
+
+ if (curr_node->occupied) {
+ Error("Cannot insert duplicate!");
+ return false;
+ }
+
+ curr_node->occupied = true;
+ curr_node->value = value;
+ curr_node->rank = rank;
+ m_value_list.enqueue(curr_node->value);
+ Debug("Trie::Insert", "inserted new element!");
+ return true;
+}
+
+template<typename T>
+T*
+Trie<T>::Search(const char *key, int key_len /* = -1 */)
+{
+ _CheckArgs(key, key_len);
+
+ Node *found_node = 0;
+ Node *curr_node = &m_root;
+ int i = 0;
+
+ while (curr_node) {
+ if (is_debug_tag_set("Trie::Search")) {
+ Debug("Trie::Search", "Visiting node...");
+ curr_node->Print("Trie::Search");
+ }
+ if (curr_node->occupied) {
+ if (!found_node) {
+ found_node = curr_node;
+ }
+ else {
+ if (curr_node->rank < found_node->rank) {
+ found_node = curr_node;
+ }
+ }
+ }
+ if (i == key_len) {
+ break;
+ }
+ curr_node = curr_node->GetChild(key[i]);
+ ++i;
+ }
+
+ if (found_node) {
+ Debug("Trie::Search", "Returning element with rank %d", found_node->rank);
+ return found_node->value;
+ }
+
+ return NULL;
+}
+
+
+template<typename T>
+void
+Trie<T>::_Clear(Node *node)
+{
+ Node *child;
+
+ for (int i = 0; i < N_NODE_CHILDREN; ++i) {
+ child = node->GetChild(i);
+ if (child) {
+ _Clear(child);
+ ats_free(child);
+ }
+ }
+}
+
+template<typename T>
+void
+Trie<T>::Clear()
+{
+ forl_LL(T, iter, m_value_list)
+ delete iter;
+ m_value_list.clear();
+
+ _Clear(&m_root);
+ m_root.Clear();
+}
+
+template<typename T>
+void
+Trie<T>::Print() {
+ // The class we contain must provide a ::Print() method.
+ forl_LL(T, iter, m_value_list)
+ iter->Print();
+}
+
+template<typename T>
+void
+Trie<T>::Node::Print(const char *debug_tag) const
+{
+ if (occupied) {
+ Debug(debug_tag, "Node is occupied");
+ Debug(debug_tag, "Node has rank %d", rank);
+ } else {
+ Debug(debug_tag, "Node is not occupied");
+ }
+
+ for (int i = 0; i < N_NODE_CHILDREN; ++i) {
+ if (GetChild(i)) {
+ Debug(debug_tag, "Node has child for char %c", static_cast<char>(i));
+ }
+ }
+}
+
+#endif // _TRIE_H
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/687fdbfe/proxy/http/remap/Makefile.am
----------------------------------------------------------------------
diff --git a/proxy/http/remap/Makefile.am b/proxy/http/remap/Makefile.am
index a5c186c..448ae54 100644
--- a/proxy/http/remap/Makefile.am
+++ b/proxy/http/remap/Makefile.am
@@ -47,6 +47,5 @@ libhttp_remap_a_SOURCES = \
UrlMapping.h \
UrlRewrite.cc \
UrlRewrite.h \
- Trie.h \
UrlMappingPathIndex.h \
UrlMappingPathIndex.cc
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/687fdbfe/proxy/http/remap/Trie.h
----------------------------------------------------------------------
diff --git a/proxy/http/remap/Trie.h b/proxy/http/remap/Trie.h
deleted file mode 100644
index 59e9fb5..0000000
--- a/proxy/http/remap/Trie.h
+++ /dev/null
@@ -1,243 +0,0 @@
-/** @file
-
- A brief file description
-
- @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 _TRIE_H
-#define _TRIE_H
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "List.h"
-
-// Note that you should provide the class to use here, but we'll store
-// pointers to such objects internally.
-template<typename T>
-class Trie
-{
-public:
- Trie()
- {
- m_root.Clear();
- }
-
- // will return false for duplicates; key should be NULL-terminated
- // if key_len is defaulted to -1
- bool Insert(const char *key, T *value, int rank, int key_len = -1);
-
- // will return false if not found; else value_ptr will point to found value
- T* Search(const char *key, int key_len = -1);
- void Clear();
- void Print();
-
- virtual ~Trie() { Clear(); }
-
-private:
- static const int N_NODE_CHILDREN = 256;
-
- class Node
- {
- public:
- T* value;
- bool occupied;
- int rank;
-
- void Clear() {
- occupied = false;
- rank = 0;
- bzero(children, sizeof(Node *) * N_NODE_CHILDREN);
- }
-
- void Print(const char *debug_tag) const;
- inline Node* GetChild(char index) const { return children[static_cast<unsigned char>(index)]; }
- inline void SetChild(char index, Node *child) { children[static_cast<unsigned char>(index)] = child; }
-
- private:
- Node *children[N_NODE_CHILDREN];
- };
-
- Node m_root;
- Queue<T> m_value_list;
-
- void _CheckArgs(const char *key, int &key_len) const;
- void _Clear(Node *node);
-
- // make copy-constructor and assignment operator private
- // till we properly implement them
- Trie(const Trie<T> &rhs) { };
- Trie &operator =(const Trie<T> &rhs) { return *this; }
-};
-
-template<typename T>
-void
-Trie<T>::_CheckArgs(const char *key, int &key_len) const
-{
- if (!key) {
- key_len = 0;
- }
- else if (key_len == -1) {
- key_len = strlen(key);
- }
-}
-
-template<typename T>
-bool
-Trie<T>::Insert(const char *key, T* value, int rank, int key_len /* = -1 */)
-{
- _CheckArgs(key, key_len);
-
- bool retval = false;
- Node *next_node;
- Node *curr_node = &m_root;
- int i = 0;
-
- while (true) {
- if (is_debug_tag_set("Trie::Insert")) {
- Debug("Trie::Insert", "Visiting Node...");
- curr_node->Print("Trie::Insert");
- }
- if (i == key_len) {
- break;
- }
- next_node = curr_node->GetChild(key[i]);
- if (!next_node) {
- while (i < key_len) {
- Debug("Trie::Insert", "Creating child node for char %c (%d)", key[i], key[i]);
- curr_node->SetChild(key[i], static_cast<Node*>(ats_malloc(sizeof(Node))));
- curr_node = curr_node->GetChild(key[i]);
- curr_node->Clear();
- ++i;
- }
- break;
- }
- curr_node = next_node;
- ++i;
- }
-
- if (curr_node->occupied) {
- Error("Cannot insert duplicate!");
- } else {
- curr_node->occupied = true;
- curr_node->value = value;
- curr_node->rank = rank;
- m_value_list.enqueue(curr_node->value);
- retval = true;
- Debug("Trie::Insert", "inserted new element!");
- }
- return retval;
-}
-
-template<typename T>
-T*
-Trie<T>::Search(const char *key, int key_len /* = -1 */)
-{
- _CheckArgs(key, key_len);
-
- Node *found_node = 0;
- Node *curr_node = &m_root;
- int i = 0;
-
- while (curr_node) {
- if (is_debug_tag_set("Trie::Search")) {
- Debug("Trie::Search", "Visiting node...");
- curr_node->Print("Trie::Search");
- }
- if (curr_node->occupied) {
- if (!found_node) {
- found_node = curr_node;
- }
- else {
- if (curr_node->rank < found_node->rank) {
- found_node = curr_node;
- }
- }
- }
- if (i == key_len) {
- break;
- }
- curr_node = curr_node->GetChild(key[i]);
- ++i;
- }
-
- if (found_node) {
- Debug("Trie::Search", "Returning element with rank %d", found_node->rank);
- return found_node->value;
- }
-
- return NULL;
-}
-
-
-template<typename T>
-void
-Trie<T>::_Clear(Node *node)
-{
- Node *child;
-
- for (int i = 0; i < N_NODE_CHILDREN; ++i) {
- child = node->GetChild(i);
- if (child) {
- _Clear(child);
- ats_free(child);
- }
- }
-}
-
-template<typename T>
-void
-Trie<T>::Clear()
-{
- forl_LL(T, iter, m_value_list)
- delete iter;
- m_value_list.clear();
-
- _Clear(&m_root);
- m_root.Clear();
-}
-
-template<typename T>
-void
-Trie<T>::Print() {
- // The class we contain must provide a ::Print() method.
- forl_LL(T, iter, m_value_list)
- iter->Print();
-}
-
-template<typename T>
-void
-Trie<T>::Node::Print(const char *debug_tag) const
-{
- if (occupied) {
- Debug(debug_tag, "Node is occupied");
- Debug(debug_tag, "Node has rank %d", rank);
- } else {
- Debug(debug_tag, "Node is not occupied");
- }
-
- for (int i = 0; i < N_NODE_CHILDREN; ++i) {
- if (GetChild(i)) {
- Debug(debug_tag, "Node has child for char %c", static_cast<char>(i));
- }
- }
-}
-
-#endif // _TRIE_H