base: Tag API methods to debug.hh

[gem5.git] / src / base / trie.hh

diff --git a/src/base/trie.hh b/src/base/trie.hh
index e6b2881ab14fe9fd24038a72c63b704b5614d0cf..9722c24389410a0fe12e5b8be637953cf237c35e 100644 (file)
--- a/src/base/trie.hh
+++ b/src/base/trie.hh
@@ -24,24 +24,36 @@
  * 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.
- *
- * Authors: Gabe Black
  */
 
 #ifndef __BASE_TRIE_HH__
 #define __BASE_TRIE_HH__
 
 #include <cassert>
+#include <iostream>
+#include <type_traits>
 
 #include "base/cprintf.hh"
-#include "base/misc.hh"
+#include "base/logging.hh"
 #include "base/types.hh"
 
-// Key has to be an integral type.
+/**
+ * A trie is a tree-based data structure used for data retrieval. It uses
+ * bits masked from the msb of the key to to determine a value's location,
+ * so its lookups have their worst case time dictated by the key's size.
+ *
+ * @tparam Key Type of the key of the tree nodes. Must be an integral type.
+ * @tparam Value Type of the values associated to the keys.
+ *
+ * @ingroup api_base_utils
+ */
 template <class Key, class Value>
 class Trie
 {
   protected:
+    static_assert(std::is_integral<Key>::value,
+        "Key has to be an integral type");
+
     struct Node
     {
         Key key;
@@ -82,20 +94,21 @@ class Trie
         }
 
         void
-        dump(int level)
+        dump(std::ostream &os, int level)
         {
             for (int i = 1; i < level; i++) {
-                cprintf("|");
+                ccprintf(os, "|");
             }
             if (level == 0)
-                cprintf("Root ");
+                ccprintf(os, "Root ");
             else
-                cprintf("+ ");
-            cprintf("(%p, %p, %#X, %#X, %p)\n", parent, this, key, mask, value);
+                ccprintf(os, "+ ");
+            ccprintf(os, "(%p, %p, %#X, %#X, %p)\n",
+                     parent, this, key, mask, value);
             if (kids[0])
-                kids[0]->dump(level + 1);
+                kids[0]->dump(os, level + 1);
             if (kids[1])
-                kids[1]->dump(level + 1);
+                kids[1]->dump(os, level + 1);
         }
     };
 
@@ -103,11 +116,20 @@ class Trie
     Node head;
 
   public:
+    /**
+     * @ingroup api_base_utils
+     */
     typedef Node *Handle;
 
+    /**
+     * @ingroup api_base_utils
+     */
     Trie() : head(0, 0, NULL)
     {}
 
+    /**
+     * @ingroup api_base_utils
+     */
     static const unsigned MaxBits = sizeof(Key) * 8;
 
   private:
@@ -181,10 +203,16 @@ class Trie
      * @param width How many bits of the key (from msb) should be used.
      * @param val A pointer to the value to store in the trie.
      * @return A Handle corresponding to this value.
+     *
+     * @ingroup api_base_utils
      */
     Handle
     insert(Key key, unsigned width, Value *val)
     {
+        // We use NULL value pointers to mark internal nodes of the trie, so
+        // we don't allow inserting them as real values.
+        assert(val);
+
         // Build a mask which masks off all the bits we don't care about.
         Key new_mask = ~(Key)0;
         if (width < MaxBits)
@@ -263,6 +291,8 @@ class Trie
      * Method which looks up the Value corresponding to a particular key.
      * @param key The key to look up.
      * @return The first Value matching this key, or NULL if none was found.
+     *
+     * @ingroup api_base_utils
      */
     Value *
     lookup(Key key)
@@ -278,6 +308,8 @@ class Trie
      * Method to delete a value from the trie.
      * @param node A Handle to remove.
      * @return The Value pointer from the removed entry.
+     *
+     * @ingroup api_base_utils
      */
     Value *
     remove(Handle handle)
@@ -322,6 +354,8 @@ class Trie
      * Method to lookup a value from the trie and then delete it.
      * @param key The key to look up and then remove.
      * @return The Value pointer from the removed entry, if any.
+     *
+     * @ingroup api_base_utils
      */
     Value *
     remove(Key key)
@@ -335,6 +369,8 @@ class Trie
     /**
      * A method which removes all key/value pairs from the trie. This is more
      * efficient than trying to remove elements individually.
+     *
+     * @ingroup api_base_utils
      */
     void
     clear()
@@ -347,13 +383,13 @@ class Trie
      * @param title An identifying title to put in the dump header.
      */
     void
-    dump(const char *title)
+    dump(const char *title, std::ostream &os=std::cout)
     {
-        cprintf("**************************************************\n");
-        cprintf("*** Start of Trie: %s\n", title);
-        cprintf("*** (parent, me, key, mask, value pointer)\n");
-        cprintf("**************************************************\n");
-        head.dump(0);
+        ccprintf(os, "**************************************************\n");
+        ccprintf(os, "*** Start of Trie: %s\n", title);
+        ccprintf(os, "*** (parent, me, key, mask, value pointer)\n");
+        ccprintf(os, "**************************************************\n");
+        head.dump(os, 0);
     }
 };