[1/5] git commit: TS-1135: minor Trie and Queue fixes

[jp...@apache.org]

Updated Branches:
  refs/heads/master 2731f6bfa -> a6867032e


TS-1135: minor Trie and Queue fixes

  - Add empty() to Queue<>
  - Add Empty() to Trie<>
  - Clarify node allocation in Trie<> and add some additional const
    qualifiers.


Project: http://git-wip-us.apache.org/repos/asf/trafficserver/repo
Commit: http://git-wip-us.apache.org/repos/asf/trafficserver/commit/9c1958ab
Tree: http://git-wip-us.apache.org/repos/asf/trafficserver/tree/9c1958ab
Diff: http://git-wip-us.apache.org/repos/asf/trafficserver/diff/9c1958ab

Branch: refs/heads/master
Commit: 9c1958ab49e3cd6a8f4fec785a033a204ea222bb
Parents: 687fdbf
Author: James Peach <jp...@apache.org>
Authored: Wed Mar 7 22:32:11 2012 -0800
Committer: James Peach <jp...@apache.org>
Committed: Tue Mar 27 20:32:26 2012 -0700

----------------------------------------------------------------------
 lib/ts/List.h |    1 +
 lib/ts/Trie.h |   29 +++++++++++++++++++----------
 2 files changed, 20 insertions(+), 10 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/trafficserver/blob/9c1958ab/lib/ts/List.h
----------------------------------------------------------------------
diff --git a/lib/ts/List.h b/lib/ts/List.h
index e72358c..83331f5 100644
--- a/lib/ts/List.h
+++ b/lib/ts/List.h
@@ -219,6 +219,7 @@ template <class C, class L = typename C::Link_link> class Queue : public DLL<C,L
   void append(Queue<C,L> q);
   void append(DLL<C,L> q);
   void clear() { head = NULL; tail = NULL; }
+  bool empty() const { return head == NULL; }
 
   Queue() : tail(NULL) {}
 };

http://git-wip-us.apache.org/repos/asf/trafficserver/blob/9c1958ab/lib/ts/Trie.h
----------------------------------------------------------------------
diff --git a/lib/ts/Trie.h b/lib/ts/Trie.h
index 2f79e5a..64d80a2 100644
--- a/lib/ts/Trie.h
+++ b/lib/ts/Trie.h
@@ -1,6 +1,6 @@
 /** @file
 
-    A brief file description
+    Trie implementation for 8-bit string keys.
 
     @section license License
 
@@ -45,10 +45,12 @@ public:
   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);
+  T* Search(const char *key, int key_len = -1) const;
   void Clear();
   void Print();
 
+  bool Empty() const { return m_value_list.empty(); }
+
   virtual ~Trie() { Clear(); }
 
 private:
@@ -62,14 +64,21 @@ private:
     int rank;
 
     void Clear() {
+      value = NULL;
       occupied = false;
       rank = 0;
-      bzero(children, sizeof(Node *) * N_NODE_CHILDREN);
+      ink_zero(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; }
+    inline Node* AllocateChild(char index) {
+      Node * &child = children[static_cast<unsigned char>(index)];
+      ink_debug_assert(child == NULL);
+      child = static_cast<Node*>(ats_malloc(sizeof(Node)));
+      child->Clear();
+      return child;
+    }
 
   private:
     Node *children[N_NODE_CHILDREN];
@@ -114,16 +123,16 @@ Trie<T>::Insert(const char *key, T* value, int rank, int key_len /* = -1 */)
       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();
+        curr_node = curr_node->AllocateChild(key[i]);
         ++i;
       }
       break;
@@ -147,12 +156,12 @@ Trie<T>::Insert(const char *key, T* value, int rank, int key_len /* = -1 */)
 
 template<typename T>
 T*
-Trie<T>::Search(const char *key, int key_len /* = -1 */)
+Trie<T>::Search(const char *key, int key_len /* = -1 */) const
 {
   _CheckArgs(key, key_len);
 
-  Node *found_node = 0;
-  Node *curr_node = &m_root;
+  const Node *found_node = 0;
+  const Node *curr_node = &m_root;
   int i = 0;
 
   while (curr_node) {