The SwappyItems Key-Values Store
Classes | Public Member Functions | Public Attributes | Private Types | Private Member Functions | Private Attributes | List of all members
SwappyQueue< TKEY, TVALUE, EACHFILE, OLDIES, RAMSIZE, BLOOMBITS, MASKLENGTH > Class Template Reference

#include <SwappyQueue.hpp>

Classes

struct  Item
 

Public Member Functions

 SwappyQueue (void)
 
 ~SwappyQueue (void)
 
bool get (TKEY key, Item &result)
 
bool top (TKEY &resultkey, Item &result)
 
bool set (TKEY key, Item &item)
 
void del (TKEY key)
 

Public Attributes

bool empty
 

Private Types

typedef SwappyItems< TKEY, Item, EACHFILE, OLDIES, RAMSIZE, BLOOMBITS, MASKLENGTH > Heap
 

Private Member Functions

void insert (TKEY key, Item &item)
 

Private Attributes

Heap * _data
 
TKEY _headKey
 

Detailed Description

template<class TKEY, class TVALUE, int EACHFILE = 16384, int OLDIES = 8, int RAMSIZE = 3, int BLOOMBITS = 4, int MASKLENGTH = (2* 4*16384)>
class SwappyQueue< TKEY, TVALUE, EACHFILE, OLDIES, RAMSIZE, BLOOMBITS, MASKLENGTH >

Examples
SwappyQueueTest_main.cpp.

Member Typedef Documentation

◆ Heap

template<class TKEY , class TVALUE , int EACHFILE = 16384, int OLDIES = 8, int RAMSIZE = 3, int BLOOMBITS = 4, int MASKLENGTH = (2* 4*16384)>
typedef SwappyItems<TKEY, Item, EACHFILE, OLDIES, RAMSIZE, BLOOMBITS, MASKLENGTH> SwappyQueue< TKEY, TVALUE, EACHFILE, OLDIES, RAMSIZE, BLOOMBITS, MASKLENGTH >::Heap
private

Constructor & Destructor Documentation

◆ SwappyQueue()

template<class TKEY , class TVALUE , int EACHFILE = 16384, int OLDIES = 8, int RAMSIZE = 3, int BLOOMBITS = 4, int MASKLENGTH = (2* 4*16384)>
SwappyQueue< TKEY, TVALUE, EACHFILE, OLDIES, RAMSIZE, BLOOMBITS, MASKLENGTH >::SwappyQueue ( void  )
inline
63  {
64  empty = true;
65  _data = new Heap(42);
66  }
SwappyQueue::_data
Heap * _data
Definition: SwappyQueue.hpp:58
SwappyQueue::empty
bool empty
Definition: SwappyQueue.hpp:46
SwappyQueue::Heap
SwappyItems< TKEY, Item, EACHFILE, OLDIES, RAMSIZE, BLOOMBITS, MASKLENGTH > Heap
Definition: SwappyQueue.hpp:56

◆ ~SwappyQueue()

template<class TKEY , class TVALUE , int EACHFILE = 16384, int OLDIES = 8, int RAMSIZE = 3, int BLOOMBITS = 4, int MASKLENGTH = (2* 4*16384)>
SwappyQueue< TKEY, TVALUE, EACHFILE, OLDIES, RAMSIZE, BLOOMBITS, MASKLENGTH >::~SwappyQueue ( void  )
inline
68  {
69  delete(_data);
70  }

Member Function Documentation

◆ del()

template<class TKEY , class TVALUE , int EACHFILE = 16384, int OLDIES = 8, int RAMSIZE = 3, int BLOOMBITS = 4, int MASKLENGTH = (2* 4*16384)>
void SwappyQueue< TKEY, TVALUE, EACHFILE, OLDIES, RAMSIZE, BLOOMBITS, MASKLENGTH >::del ( TKEY  key)
inline

delete an item

Parameters
keythe unique key
Returns
void
Examples
SwappyQueueTest_main.cpp.
137  {
138  typename Heap::statistic_s s = _data->getStatistic();
139  if (s.size == 0) return;
140 
141  if (s.size == 1) {
142  if (key == _headKey) {
143  _data->del(_headKey);
144  empty = true;
145  }
146  return;
147  }
148 
149  if (s.size > 1) {
150  typename Heap::Data * dummy1Pair;
151  typename Heap::Data * dummy2Pair = _data->get(key);
152 
153  if (dummy2Pair == nullptr) return;
154 
155  // = remember the datas from old element
156  Item item = dummy2Pair->first;
157  std::vector<TKEY> siblings(dummy2Pair->second);
158 
159  _data->del(key);
160 
161  std::vector<TKEY> newsiblings;
162  std::vector<TKEY> winners;
163  TKEY champion;
164 
165  if (key != _headKey) {
166  dummy1Pair = _data->get(item.parent);
167  // remove key from siblings of parent
168  for (auto n : dummy1Pair->second) {
169  if (n != key) newsiblings.push_back(n);
170  }
171  _data->set(item.parent, dummy1Pair->first, newsiblings);
172  }
173 
174  // build pairs (1. phase)
175  for (uint64_t i=0; i < siblings.size(); i+=2) {
176  if ((i+1) >= siblings.size()) {
177  // a single element ...
178  winners.push_back(siblings[i]);
179  } else {
180  dummy1Pair = _data->get(siblings[i]);
181  dummy2Pair = _data->get(siblings[i+1]);
182  if (dummy1Pair->first.prio < dummy2Pair->first.prio) {
183  winners.push_back(siblings[i]);
184  dummy2Pair->first.parent = siblings[i];
185  dummy1Pair->second.push_back(siblings[i+1]);
186  //_data->set(...); // hey, we use pointers. the data in _ramList should be accessable and changed!
187  } else {
188  winners.push_back(siblings[i+1]);
189  dummy1Pair->first.parent = siblings[i+1];
190  dummy2Pair->second.push_back(siblings[i]);
191  //_data->set(...); // hey, we use pointers. the data in _ramList should be accessable and changed!
192  }
193  }
194  }
195 
196  // build a single tree (2. phase)
197  if (winners.size() > 0) {
198  champion = winners[0];
199  dummy1Pair = _data->get(champion);
200 
201  for (uint64_t i=1; i < winners.size(); ++i) {
202  dummy2Pair = _data->get(winners[i]);
203  if (dummy2Pair->first.prio < dummy1Pair->first.prio) {
204  // we found a new head/champion
205  dummy2Pair->second.push_back(champion);
206  dummy1Pair->first.parent = winners[i];
207  champion = winners[i];
208  dummy1Pair = dummy2Pair;
209  } else {
210  dummy1Pair->second.push_back(winners[i]);
211  dummy2Pair->first.parent = champion;
212  }
213  }
214 
215  // may set a new head
216  if (key == _headKey) {
217  _headKey = champion; // the winner of all winners
218  dummy1Pair = _data->get(_headKey);
219  dummy1Pair->first.parent = _headKey; // no parent = link to its self!
220  } else {
221  dummy1Pair = _data->get(champion);
222  dummy1Pair->first.parent = item.parent;
223  dummy2Pair = _data->get(item.parent);
224  dummy2Pair->second.push_back(champion);
225  }
226  }
227 
228  }
229  }
SwappyItems::Data
std::pair< TVALUE, std::vector< TKEY > > Data
Definition: SwappyItems.hpp:52
SwappyItems::get
Data * get(const TKEY &key)
Definition: SwappyItems.hpp:188
SwappyItems::del
bool del(const TKEY &key)
Definition: SwappyItems.hpp:211
SwappyItems::getStatistic
struct statistic_s getStatistic(void)
Definition: SwappyItems.hpp:288
SwappyItems::set
bool set(TKEY key, TVALUE value)
Definition: SwappyItems.hpp:123
SwappyQueue::_headKey
TKEY _headKey
Definition: SwappyQueue.hpp:59

◆ get()

template<class TKEY , class TVALUE , int EACHFILE = 16384, int OLDIES = 8, int RAMSIZE = 3, int BLOOMBITS = 4, int MASKLENGTH = (2* 4*16384)>
bool SwappyQueue< TKEY, TVALUE, EACHFILE, OLDIES, RAMSIZE, BLOOMBITS, MASKLENGTH >::get ( TKEY  key,
Item &  result 
)
inline

get an item

Parameters
keythe unique key
resulthas the reference to the item
Returns
false, if it does not exist
80  {
81  typename Heap::Data * p;
82  p = _data->get(key);
83  if (p == nullptr) return false;
84  result = p->first;
85  return true;
86  }

◆ insert()

template<class TKEY , class TVALUE , int EACHFILE = 16384, int OLDIES = 8, int RAMSIZE = 3, int BLOOMBITS = 4, int MASKLENGTH = (2* 4*16384)>
void SwappyQueue< TKEY, TVALUE, EACHFILE, OLDIES, RAMSIZE, BLOOMBITS, MASKLENGTH >::insert ( TKEY  key,
Item &  item 
)
inlineprivate
Todo:
force a 2 pahse, if head siblings are to many (e.g. EACHFILE/2)
235  {
236  typename Heap::statistic_s s = _data->getStatistic();
237  if (s.size == 0) {
238  _headKey = key;
239  item.parent = key;
240  _data->set(key, item, std::vector<TKEY>(0));
241  empty = false;
242  } else {
243  typename Heap::Data * headpair = _data->get(_headKey);
244 
245  if (item.prio < headpair->first.prio) {
246  item.parent = key;
247  std::vector<TKEY> siblings;
248  siblings.push_back(_headKey);
249  _data->set(key, item, siblings);
250 
251  headpair->first.parent = key;
252  _data->set(_headKey, headpair->first);
253 
254  _headKey = key;
255  } else {
256  item.parent = _headKey;
257  _data->set(key, item, std::vector<TKEY>(0));
258 
259  headpair->second.push_back(key);
260  _data->set(_headKey, headpair->first, headpair->second);
261  }
262  }
263  }

◆ set()

template<class TKEY , class TVALUE , int EACHFILE = 16384, int OLDIES = 8, int RAMSIZE = 3, int BLOOMBITS = 4, int MASKLENGTH = (2* 4*16384)>
bool SwappyQueue< TKEY, TVALUE, EACHFILE, OLDIES, RAMSIZE, BLOOMBITS, MASKLENGTH >::set ( TKEY  key,
Item &  item 
)
inline

insert or update an item

Parameters
keythe unique key
itemhas the data
Returns
true, if it is new and not just an update
Examples
SwappyQueueTest_main.cpp.
113  {
114  typename Heap::Data * p = _data->get(key);
115 
116  if (p == nullptr) {
117  insert(key, item);
118  return true;
119  } else {
120  if (p->first.prio == item.prio) {
121  _data->set(key, item);
122  } else {
123  del(key);
124  insert(key, item);
125  }
126  return false;
127  }
128  }
SwappyQueue::insert
void insert(TKEY key, Item &item)
Definition: SwappyQueue.hpp:235
SwappyQueue::del
void del(TKEY key)
Definition: SwappyQueue.hpp:137

◆ top()

template<class TKEY , class TVALUE , int EACHFILE = 16384, int OLDIES = 8, int RAMSIZE = 3, int BLOOMBITS = 4, int MASKLENGTH = (2* 4*16384)>
bool SwappyQueue< TKEY, TVALUE, EACHFILE, OLDIES, RAMSIZE, BLOOMBITS, MASKLENGTH >::top ( TKEY &  resultkey,
Item &  result 
)
inline

get the item with minimal prio

Parameters
resultkeyreference to the unique key of the head
resulthas the reference to the item
Returns
false, if it does not exist
Examples
SwappyQueueTest_main.cpp.
96  {
97  if (empty) {
98  return false;
99  } else {
100  resultkey = _headKey;
101  return get(_headKey, result);
102  }
103  }
SwappyQueue::get
bool get(TKEY key, Item &result)
Definition: SwappyQueue.hpp:80

Member Data Documentation

◆ _data

template<class TKEY , class TVALUE , int EACHFILE = 16384, int OLDIES = 8, int RAMSIZE = 3, int BLOOMBITS = 4, int MASKLENGTH = (2* 4*16384)>
Heap* SwappyQueue< TKEY, TVALUE, EACHFILE, OLDIES, RAMSIZE, BLOOMBITS, MASKLENGTH >::_data
private

◆ _headKey

template<class TKEY , class TVALUE , int EACHFILE = 16384, int OLDIES = 8, int RAMSIZE = 3, int BLOOMBITS = 4, int MASKLENGTH = (2* 4*16384)>
TKEY SwappyQueue< TKEY, TVALUE, EACHFILE, OLDIES, RAMSIZE, BLOOMBITS, MASKLENGTH >::_headKey
private

◆ empty

template<class TKEY , class TVALUE , int EACHFILE = 16384, int OLDIES = 8, int RAMSIZE = 3, int BLOOMBITS = 4, int MASKLENGTH = (2* 4*16384)>
bool SwappyQueue< TKEY, TVALUE, EACHFILE, OLDIES, RAMSIZE, BLOOMBITS, MASKLENGTH >::empty
The documentation for this class was generated from the following file:
Generated by doxygen 1.9.1