multiset.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/multiset.hpp>
00016 
00017 
00018 static std::string toString(long x)
00019 {
00020     char buf[80];
00021     std::snprintf(buf, sizeof(buf), "%li", x);
00022     return std::string(buf);
00023 }
00024 
00025 static bool oddValuePredicate(const std::string& value)
00026 {
00027     EXPECT_FALSE(value.empty());
00028     const int num = atoi(value.c_str());
00029     return num & 1;
00030 }
00031 
00032 struct FindPredicate
00033 {
00034     const std::string target;
00035     FindPredicate(const std::string& target) : target(target) { }
00036     bool operator()(const std::string& value) const { return value == target; }
00037 };
00038 
00039 struct NoncopyableWithCounter : uavcan::Noncopyable
00040 {
00041     static int num_objects;
00042     long long value;
00043 
00044     NoncopyableWithCounter() : value(0) { num_objects++; }
00045     NoncopyableWithCounter(long long x) : value(x) { num_objects++; }
00046     ~NoncopyableWithCounter() { num_objects--; }
00047 
00048     static bool isNegative(const NoncopyableWithCounter& val)
00049     {
00050         return val.value < 0;
00051     }
00052 
00053     bool operator==(const NoncopyableWithCounter& ref) const { return ref.value == value; }
00054 };
00055 
00056 int NoncopyableWithCounter::num_objects = 0;
00057 
00058 template <typename T>
00059 struct SummationOperator : uavcan::Noncopyable
00060 {
00061     T accumulator;
00062     SummationOperator() : accumulator() { }
00063     void operator()(const T& x) { accumulator += x; }
00064 };
00065 
00066 struct ClearingOperator
00067 {
00068     template <typename T>
00069     void operator()(T& x) const { x = T(); }
00070 };
00071 
00072 
00073 TEST(Multiset, Basic)
00074 {
00075     using uavcan::Multiset;
00076 
00077     static const int POOL_BLOCKS = 4;
00078     uavcan::PoolAllocator<uavcan::MemPoolBlockSize * POOL_BLOCKS, uavcan::MemPoolBlockSize> pool;
00079 
00080     typedef Multiset<std::string> MultisetType;
00081     std::auto_ptr<MultisetType> mset(new MultisetType(pool));
00082 
00083     typedef SummationOperator<std::string> StringConcatenationOperator;
00084 
00085     // Empty
00086     mset->removeFirst("foo");
00087     ASSERT_EQ(0, pool.getNumUsedBlocks());
00088     ASSERT_FALSE(mset->getByIndex(0));
00089     ASSERT_FALSE(mset->getByIndex(1));
00090     ASSERT_FALSE(mset->getByIndex(10000));
00091 
00092     // Static addion
00093     ASSERT_EQ("1", *mset->emplace("1"));
00094     ASSERT_EQ("2", *mset->emplace("2"));
00095     ASSERT_LE(1, pool.getNumUsedBlocks());      // One or more
00096     ASSERT_EQ(2, mset->getSize());
00097 
00098     {
00099         StringConcatenationOperator op;
00100         mset->forEach<StringConcatenationOperator&>(op);
00101         ASSERT_EQ(2, op.accumulator.size());
00102     }
00103 
00104     // Dynamic addition
00105     ASSERT_EQ("3", *mset->emplace("3"));
00106     ASSERT_LE(1, pool.getNumUsedBlocks());      // One or more
00107 
00108     ASSERT_EQ("4", *mset->emplace("4"));
00109     ASSERT_LE(1, pool.getNumUsedBlocks());      // One or more
00110     ASSERT_EQ(4, mset->getSize());
00111 
00112     ASSERT_FALSE(mset->getByIndex(100));
00113     ASSERT_FALSE(mset->getByIndex(4));
00114 
00115     // Finding some items
00116     ASSERT_EQ("1", *mset->find(FindPredicate("1")));
00117     ASSERT_EQ("2", *mset->find(FindPredicate("2")));
00118     ASSERT_EQ("3", *mset->find(FindPredicate("3")));
00119     ASSERT_EQ("4", *mset->find(FindPredicate("4")));
00120     ASSERT_FALSE(mset->find(FindPredicate("nonexistent")));
00121 
00122     {
00123         StringConcatenationOperator op;
00124         mset->forEach<StringConcatenationOperator&>(op);
00125         std::cout << "Accumulator: " << op.accumulator << std::endl;
00126         ASSERT_EQ(4, op.accumulator.size());
00127     }
00128 
00129     // Removing some
00130     mset->removeFirst("1");
00131     mset->removeFirst("foo");                           // There's no such thing anyway
00132     mset->removeFirst("2");
00133 
00134     // Adding some new items
00135     unsigned max_value_integer = 0;
00136     for (int i = 0; i < 100; i++)
00137     {
00138         const std::string value = toString(i);
00139         std::string* res = mset->emplace(value);  // Will NOT override above
00140         if (res == UAVCAN_NULLPTR)
00141         {
00142             ASSERT_LT(1, i);
00143             break;
00144         }
00145         else
00146         {
00147             ASSERT_EQ(value, *res);
00148         }
00149         max_value_integer = unsigned(i);
00150     }
00151     std::cout << "Max value: " << max_value_integer << std::endl;
00152 
00153     // Making sure there is true OOM
00154     ASSERT_EQ(0, pool.getNumFreeBlocks());
00155     ASSERT_FALSE(mset->emplace("nonexistent"));
00156 
00157     // Removing odd values - nearly half of them
00158     mset->removeAllWhere(oddValuePredicate);
00159 
00160     // Making sure there's no odd values left
00161     for (unsigned kv_int = 0; kv_int <= max_value_integer; kv_int++)
00162     {
00163         const std::string* val = mset->find(FindPredicate(toString(kv_int)));
00164         if (val)
00165         {
00166             ASSERT_FALSE(kv_int & 1);
00167         }
00168         else
00169         {
00170             ASSERT_TRUE(kv_int & 1);
00171         }
00172     }
00173 
00174     // Clearing all strings
00175     {
00176         StringConcatenationOperator op;
00177         mset->forEach<StringConcatenationOperator&>(op);
00178         std::cout << "Accumulator before clearing: " << op.accumulator << std::endl;
00179     }
00180     mset->forEach(ClearingOperator());
00181     {
00182         StringConcatenationOperator op;
00183         mset->forEach<StringConcatenationOperator&>(op);
00184         std::cout << "Accumulator after clearing: " << op.accumulator << std::endl;
00185         ASSERT_TRUE(op.accumulator.empty());
00186     }
00187 
00188     // Making sure the memory will be released
00189     mset.reset();
00190     ASSERT_EQ(0, pool.getNumUsedBlocks());
00191 }
00192 
00193 
00194 TEST(Multiset, PrimitiveKey)
00195 {
00196     using uavcan::Multiset;
00197 
00198     static const int POOL_BLOCKS = 3;
00199     uavcan::PoolAllocator<uavcan::MemPoolBlockSize * POOL_BLOCKS, uavcan::MemPoolBlockSize> pool;
00200 
00201     typedef Multiset<int> MultisetType;
00202     std::auto_ptr<MultisetType> mset(new MultisetType(pool));
00203 
00204     // Empty
00205     mset->removeFirst(8);
00206     ASSERT_EQ(0, pool.getNumUsedBlocks());
00207     ASSERT_EQ(0, mset->getSize());
00208     ASSERT_FALSE(mset->getByIndex(0));
00209 
00210     // Insertion
00211     ASSERT_EQ(1, *mset->emplace(1));
00212     ASSERT_EQ(1, mset->getSize());
00213     ASSERT_EQ(2, *mset->emplace(2));
00214     ASSERT_EQ(2, mset->getSize());
00215     ASSERT_EQ(3, *mset->emplace(3));
00216     ASSERT_EQ(4, *mset->emplace(4));
00217     ASSERT_EQ(4, mset->getSize());
00218 
00219     // Summation and clearing
00220     {
00221         SummationOperator<int> summation_operator;
00222         mset->forEach<SummationOperator<int>&>(summation_operator);
00223         ASSERT_EQ(1 + 2 + 3 + 4, summation_operator.accumulator);
00224     }
00225     mset->forEach(ClearingOperator());
00226     {
00227         SummationOperator<int> summation_operator;
00228         mset->forEach<SummationOperator<int>&>(summation_operator);
00229         ASSERT_EQ(0, summation_operator.accumulator);
00230     }
00231 }
00232 
00233 
00234 TEST(Multiset, NoncopyableWithCounter)
00235 {
00236     using uavcan::Multiset;
00237 
00238     static const int POOL_BLOCKS = 3;
00239     uavcan::PoolAllocator<uavcan::MemPoolBlockSize * POOL_BLOCKS, uavcan::MemPoolBlockSize> pool;
00240 
00241     typedef Multiset<NoncopyableWithCounter> MultisetType;
00242     std::auto_ptr<MultisetType> mset(new MultisetType(pool));
00243 
00244     ASSERT_EQ(0, NoncopyableWithCounter::num_objects);
00245     ASSERT_EQ(0,    mset->emplace()->value);
00246     ASSERT_EQ(1, NoncopyableWithCounter::num_objects);
00247     ASSERT_EQ(123,  mset->emplace(123)->value);
00248     ASSERT_EQ(2, NoncopyableWithCounter::num_objects);
00249     ASSERT_EQ(-456, mset->emplace(-456)->value);
00250     ASSERT_EQ(3, NoncopyableWithCounter::num_objects);
00251     ASSERT_EQ(456,  mset->emplace(456)->value);
00252     ASSERT_EQ(4, NoncopyableWithCounter::num_objects);
00253     ASSERT_EQ(-789, mset->emplace(-789)->value);
00254     ASSERT_EQ(5, NoncopyableWithCounter::num_objects);
00255 
00256     mset->removeFirst(NoncopyableWithCounter(0));
00257     ASSERT_EQ(4, NoncopyableWithCounter::num_objects);
00258 
00259     mset->removeFirstWhere(&NoncopyableWithCounter::isNegative);
00260     ASSERT_EQ(3, NoncopyableWithCounter::num_objects);
00261 
00262     mset->removeAllWhere(&NoncopyableWithCounter::isNegative);
00263     ASSERT_EQ(2, NoncopyableWithCounter::num_objects);          // Only 1 and 2 are left
00264 
00265     mset.reset();
00266 
00267     ASSERT_EQ(0, pool.getNumUsedBlocks());
00268     ASSERT_EQ(0, NoncopyableWithCounter::num_objects);          // All destroyed
00269 }