map.cpp

00001 /*
00002  * Copyright (C) 2014 Pavel Kirienko <pavel.kirienko@gmail.com>
00003  */
00004 
00005 #if __GNUC__
00006 // We need auto_ptr for compatibility reasons
00007 # pragma GCC diagnostic ignored "-Wdeprecated-declarations"
00008 # pragma GCC diagnostic ignored "-Wzero-as-null-pointer-constant"
00009 #endif
00010 
00011 #include <string>
00012 #include <cstdio>
00013 #include <memory>
00014 #include <gtest/gtest.h>
00015 #include <uavcan/util/map.hpp>
00016 
00017 
00018 /*
00019  * TODO: This one test has been temporarily disabled because it is not compatible with newer versions of libstdc++
00020  * that ship with newer versions of GCC. The problem is that std::string has become too large to fit into a 64-byte
00021  * large memory block. This should be fixed in the future.
00022  */
00023 #if 0
00024 static std::string toString(long x)
00025 {
00026     char buf[80];
00027     std::snprintf(buf, sizeof(buf), "%li", x);
00028     return std::string(buf);
00029 }
00030 
00031 static bool oddValuePredicate(const std::string& key, const std::string& value)
00032 {
00033     EXPECT_FALSE(key.empty());
00034     EXPECT_FALSE(value.empty());
00035     const int num = atoi(value.c_str());
00036     return num & 1;
00037 }
00038 
00039 struct KeyFindPredicate
00040 {
00041     const std::string target;
00042     KeyFindPredicate(std::string target) : target(target) { }
00043     bool operator()(const std::string& key, const std::string&) const { return key == target; }
00044 };
00045 
00046 struct ValueFindPredicate
00047 {
00048     const std::string target;
00049     ValueFindPredicate(std::string target) : target(target) { }
00050     bool operator()(const std::string&, const std::string& value) const { return value == target; }
00051 };
00052 
00053 
00054 TEST(Map, Basic)
00055 {
00056     using uavcan::Map;
00057 
00058     static const int POOL_BLOCKS = 3;
00059     uavcan::PoolAllocator<uavcan::MemPoolBlockSize * POOL_BLOCKS, uavcan::MemPoolBlockSize> pool;
00060 
00061     typedef Map<std::string, std::string> MapType;
00062     std::auto_ptr<MapType> map(new MapType(pool));
00063 
00064     // Empty
00065     ASSERT_FALSE(map->access("hi"));
00066     map->remove("foo");
00067     ASSERT_EQ(0, pool.getNumUsedBlocks());
00068     ASSERT_FALSE(map->getByIndex(0));
00069     ASSERT_FALSE(map->getByIndex(1));
00070     ASSERT_FALSE(map->getByIndex(10000));
00071 
00072     // Insertion
00073     ASSERT_EQ("a", *map->insert("1", "a"));
00074     ASSERT_EQ("b", *map->insert("2", "b"));
00075     ASSERT_EQ(1, pool.getNumUsedBlocks());
00076     ASSERT_EQ(2, map->getSize());
00077 
00078     // Ordering
00079     ASSERT_TRUE(map->getByIndex(0)->match("1"));
00080     ASSERT_TRUE(map->getByIndex(1)->match("2"));
00081 
00082     // Insertion
00083     ASSERT_EQ("c", *map->insert("3", "c"));
00084     ASSERT_EQ(1, pool.getNumUsedBlocks());
00085 
00086     ASSERT_EQ("d", *map->insert("4", "d"));
00087     ASSERT_EQ(2, pool.getNumUsedBlocks());       // Assuming that at least 2 items fit one block
00088     ASSERT_EQ(4, map->getSize());
00089 
00090     // Making sure everything is here
00091     ASSERT_EQ("a", *map->access("1"));
00092     ASSERT_EQ("b", *map->access("2"));
00093     ASSERT_EQ("c", *map->access("3"));
00094     ASSERT_EQ("d", *map->access("4"));
00095     ASSERT_FALSE(map->access("hi"));
00096 
00097     // Modifying existing entries
00098     *map->access("1") = "A";
00099     *map->access("2") = "B";
00100     *map->access("3") = "C";
00101     *map->access("4") = "D";
00102     ASSERT_EQ("A", *map->access("1"));
00103     ASSERT_EQ("B", *map->access("2"));
00104     ASSERT_EQ("C", *map->access("3"));
00105     ASSERT_EQ("D", *map->access("4"));
00106 
00107     // Finding some keys
00108     ASSERT_EQ("1", *map->find(KeyFindPredicate("1")));
00109     ASSERT_EQ("2", *map->find(KeyFindPredicate("2")));
00110     ASSERT_EQ("3", *map->find(KeyFindPredicate("3")));
00111     ASSERT_EQ("4", *map->find(KeyFindPredicate("4")));
00112     ASSERT_FALSE(map->find(KeyFindPredicate("nonexistent_key")));
00113 
00114     // Finding some values
00115     ASSERT_EQ("1", *map->find(ValueFindPredicate("A")));
00116     ASSERT_EQ("2", *map->find(ValueFindPredicate("B")));
00117     ASSERT_EQ("3", *map->find(ValueFindPredicate("C")));
00118     ASSERT_EQ("4", *map->find(ValueFindPredicate("D")));
00119     ASSERT_FALSE(map->find(KeyFindPredicate("nonexistent_value")));
00120 
00121     // Removing one
00122     map->remove("1");                             // One of dynamics now migrates to the static storage
00123     map->remove("foo");                           // There's no such thing anyway
00124     ASSERT_EQ(2, pool.getNumUsedBlocks());
00125     ASSERT_EQ(3, map->getSize());
00126 
00127     ASSERT_FALSE(map->access("1"));
00128     ASSERT_EQ("B", *map->access("2"));
00129     ASSERT_EQ("C", *map->access("3"));
00130     ASSERT_EQ("D", *map->access("4"));
00131 
00132     // Removing another
00133     map->remove("2");
00134     ASSERT_EQ(2, map->getSize());
00135     ASSERT_EQ(2, pool.getNumUsedBlocks());
00136 
00137     ASSERT_FALSE(map->access("1"));
00138     ASSERT_FALSE(map->access("2"));
00139     ASSERT_EQ("C", *map->access("3"));
00140     ASSERT_EQ("D", *map->access("4"));
00141 
00142     // Adding some new
00143     unsigned max_key_integer = 0;
00144     for (int i = 0; i < 100; i++)
00145     {
00146         const std::string key   = toString(i);
00147         const std::string value = toString(i);
00148         std::string* res = map->insert(key, value);  // Will override some from the above
00149         if (res == UAVCAN_NULLPTR)
00150         {
00151             ASSERT_LT(2, i);
00152             break;
00153         }
00154         else
00155         {
00156             ASSERT_EQ(value, *res);
00157         }
00158         max_key_integer = unsigned(i);
00159     }
00160     std::cout << "Max key/value: " << max_key_integer << std::endl;
00161     ASSERT_LT(4, max_key_integer);
00162 
00163     // Making sure there is true OOM
00164     ASSERT_EQ(0, pool.getNumFreeBlocks());
00165     ASSERT_FALSE(map->insert("nonexistent", "value"));
00166     ASSERT_FALSE(map->access("nonexistent"));
00167     ASSERT_FALSE(map->access("value"));
00168 
00169     // Removing odd values - nearly half of them
00170     map->removeAllWhere(oddValuePredicate);
00171 
00172     // Making sure there's no odd values left
00173     for (unsigned kv_int = 0; kv_int <= max_key_integer; kv_int++)
00174     {
00175         const std::string* val = map->access(toString(kv_int));
00176         if (val)
00177         {
00178             ASSERT_FALSE(kv_int & 1);
00179         }
00180         else
00181         {
00182             ASSERT_TRUE(kv_int & 1);
00183         }
00184     }
00185 
00186     // Making sure the memory will be released
00187     map.reset();
00188     ASSERT_EQ(0, pool.getNumUsedBlocks());
00189 }
00190 #endif
00191 
00192 
00193 TEST(Map, PrimitiveKey)
00194 {
00195     using uavcan::Map;
00196 
00197     static const int POOL_BLOCKS = 3;
00198     uavcan::PoolAllocator<uavcan::MemPoolBlockSize * POOL_BLOCKS, uavcan::MemPoolBlockSize> pool;
00199 
00200     typedef Map<short, short> MapType;
00201     std::auto_ptr<MapType> map(new MapType(pool));
00202 
00203     // Empty
00204     ASSERT_FALSE(map->access(1));
00205     map->remove(8);
00206     ASSERT_EQ(0, pool.getNumUsedBlocks());
00207     ASSERT_EQ(0, map->getSize());
00208     ASSERT_FALSE(map->getByIndex(0));
00209 
00210     // Insertion
00211     ASSERT_EQ(1, *map->insert(1, 1));
00212     ASSERT_EQ(1, map->getSize());
00213     ASSERT_EQ(2, *map->insert(2, 2));
00214     ASSERT_EQ(2, map->getSize());
00215     ASSERT_EQ(3, *map->insert(3, 3));
00216     ASSERT_EQ(4, *map->insert(4, 4));
00217     ASSERT_EQ(4, map->getSize());
00218 
00219     // Ordering
00220     ASSERT_TRUE(map->getByIndex(0)->match(1));
00221     ASSERT_TRUE(map->getByIndex(1)->match(2));
00222     ASSERT_TRUE(map->getByIndex(2)->match(3));
00223     ASSERT_TRUE(map->getByIndex(3)->match(4));
00224     ASSERT_FALSE(map->getByIndex(5));
00225     ASSERT_FALSE(map->getByIndex(1000));
00226 }