src/libswift/tests/freemap.cpp

   1 /*
   2  *  freemap.cpp
   3  *  serp++
   4  *
   5  *  Created by Victor Grishchenko on 3/22/09.
   6  *  Copyright 2009-2012 TECHNISCHE UNIVERSITEIT DELFT. All rights reserved.
   7  *
   8  */
   9 #include <time.h>
  10 #include <gtest/gtest.h>
  11 #include <set>
  12 #include "binmap.h"
  13
  14 using namespace swift;
  15
  16 #ifdef _MSC_VER
  17         #define RANDOM  rand
  18 #else
  19         #define RANDOM  random
  20 #endif
  21
  22 uint8_t rand_norm (uint8_t lim) {
  23     long rnd = RANDOM() & ((1<<lim)-1);
  24     uint8_t bits = 0;
  25     while (rnd) {
  26         bits += rnd&1;
  27         rnd >>= 1;
  28     }
  29     return bits;
  30 }
  31
  32 TEST(FreemapTest,Freemap) {
  33     binmap_t space;
  34     const bin_t top(30,0);
  35     space.reset(top);
  36     typedef std::pair<int,bin_t> timebin_t;
  37     typedef std::set<timebin_t> ts_t;
  38     ts_t to_free;
  39     for (int t=0; t<1000000; t++) {
  40
  41         if ((t % 1000) == 0)
  42                 printf(".");
  43
  44         if (t<500000 || t>504000) {
  45             uint8_t lr = rand_norm(28);
  46             bin_t alloc = space.find_empty();
  47             while (alloc.layer()>lr)
  48                 alloc = alloc.left();
  49             ASSERT_NE(0ULL,~alloc.toUInt());
  50             EXPECT_TRUE(space.is_empty(alloc));
  51             space.set(alloc);
  52             long dealloc_time = 1<<rand_norm(22);
  53 #ifdef SHOWPUTPUT
  54             printf("alloc 2**%i starting at %lli for %li ticks\n",
  55                 (int)lr,alloc.toUInt(),dealloc_time);
  56 #endif
  57             dealloc_time += t;
  58             to_free.insert(timebin_t(dealloc_time,alloc));
  59         }
  60         // now, the red-black tree
  61         while (to_free.begin()->first<=t) {
  62             bin_t freebin = to_free.begin()->second;
  63             to_free.erase(to_free.begin());
  64             space.reset(freebin);
  65 #ifdef SHOWOUTPUT
  66             printf("freed at %lli\n",
  67                 freebin.toUInt());
  68 #endif
  69        }
  70         // log: space taken, gaps, binmap cells, tree cells
  71         int cells = space.cells_number();
  72
  73 #ifdef SHOWOUTPUT
  74         printf("time %i cells used %i blocks %i\n",
  75                 t,cells,(int)to_free.size());
  76 #endif
  77         //space.dump("space");
  78     }
  79     for(ts_t::iterator i=to_free.begin(); i!=to_free.end(); i++)
  80         space.reset(i->second);
  81     EXPECT_TRUE(space.is_empty(top));
  82 }
  83
  84 int main (int argc, char** argv) {
  85         testing::InitGoogleTest(&argc, argv);
  86         return RUN_ALL_TESTS();
  87 }