From d8e7d6bcb94a3ed9cb8a60440dde1792efa6acc2 Mon Sep 17 00:00:00 2001
From: "Daniel R. Carvalho" <odanrc@yahoo.com.br>
Date: Tue, 10 Mar 2020 09:58:07 +0100
Subject: [PATCH] base: Add static assert to trie

Trie is based on the condition that they key is an integral. As so,
add a static_assert to guarantee that. Also, added some general info
about tries to the class.

Change-Id: Idc18f6a685db8047cd44b791f427666d3dd2d187
Signed-off-by: Daniel R. Carvalho <odanrc@yahoo.com.br>
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/26784
Reviewed-by: Gabe Black <gabeblack@google.com>
Maintainer: Bobby R. Bruce <bbruce@ucdavis.edu>
Tested-by: kokoro <noreply+kokoro@google.com>
---
 src/base/trie.hh | 13 ++++++++++++-
 1 file changed, 12 insertions(+), 1 deletion(-)

diff --git a/src/base/trie.hh b/src/base/trie.hh
index a75e9e735..71a14c55c 100644
--- a/src/base/trie.hh
+++ b/src/base/trie.hh
@@ -31,16 +31,27 @@
 
 #include <cassert>
 #include <iostream>
+#include <type_traits>
 
 #include "base/cprintf.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.
+ */
 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;
-- 
2.30.2