BAM
Abstract Machine for Bottom-Up Evaluation with the Push Method
list.h
Go to the documentation of this file.
1 // ============================================================================
2 // Project: Deductive Database
3 // Filename: list.h
4 // Purpose: List of objects/tuples - relation with binding pattern f..f
5 // Last Change: 04.08.2017
6 // Language: C++
7 // EMail: brass@informatik.uni-halle.de
8 // WWW: http://www.informatik.uni-halle.de/~brass/
9 // Address: Feldschloesschen 15, D-06120 Halle (Saale), GERMANY
10 // Copyright: (c) 2015-2017 by Stefan Brass
11 // License: See file "LICENSE" for copying conditions.
12 // Note: There is no warranty at all - this code may contain bugs.
13 // ============================================================================
14 
15 
22 //=============================================================================
23 // Include File Frame:
24 //=============================================================================
25 
26 #ifndef LIST_INCLUDED
27 #define LIST_INCLUDED
28 
29 //=============================================================================
30 // Used Types and Macros:
31 //=============================================================================
32 
33 #ifndef VER_INCLUDED
34 #include "../base/ver.h"
35 #endif
36 
37 #ifndef STR_INCLUDED
38 #include "../base/str.h"
39 #endif
40 
41 #ifndef ERR_INCLUDED
42 #include "../base/err.h"
43 #endif
44 
45 #ifndef CHECK_INCLUDED
46 #include "../base/check.h"
47 #endif
48 
49 #ifndef PAGE_INCLUDED
50 #include "../mem/page.h"
51 #endif
52 
53 #ifndef MPOOL_INCLUDED
54 #include "../mem/mpool.h"
55 #endif
56 
57 #ifndef REL_INCLUDED
58 #include "../rel/rel.h"
59 #endif
60 
61 
62 //=============================================================================
63 // Private Constants:
64 //=============================================================================
65 
66 //-----------------------------------------------------------------------------
67 // LIST_MAGIC: Magic number (identifies objects of this class).
68 //-----------------------------------------------------------------------------
69 
70 static const long LIST_MAGIC = 0x4C53540AL; // 'LST\n'
71 
72 //-----------------------------------------------------------------------------
73 // Null Pointers:
74 //-----------------------------------------------------------------------------
75 
76 #define LIST_LEAF_NULL (static_cast<T*>(PAGE_NULL))
77 #define LIST_MID_NULL (static_cast<T**>(PAGE_NULL))
78 #define LIST_TOP_NULL (static_cast<T***>(PAGE_NULL))
79 
80 //-----------------------------------------------------------------------------
81 // Forward declaration of the corresponding cursor class (for friend decl.):
82 //-----------------------------------------------------------------------------
83 
84 template<class T> class cur_list_c;
85 
86 //=============================================================================
87 // Class Template for Sequences/Lists (with Insertion only at the End):
88 //=============================================================================
89 
90 template<class T> class list_c: public rel_c {
91  public:
92 
93 //-----------------------------------------------------------------------------
94 // Constructor, Destructor:
95 //-----------------------------------------------------------------------------
96 
97  // Constructor:
98  list_c(str_t list_name) : rel_c(list_name, 0, T::NUM_COLS,
99  "Tree of Tuple Arrays") {
100 
101  // Check parameter:
102  CHECK(list_name != STR_NULL,
103  "list_c::constructor: list_name is NULL");
104 
105  // Initialize attributes:
106  Height = 0;
107  LeafNode = LIST_LEAF_NULL;
108  MidNode = LIST_MID_NULL;
109  TopNode = LIST_TOP_NULL;
110  LeafPtr = LIST_LEAF_NULL;
111  MidPtr = LIST_MID_NULL;
112  TopPtr = LIST_TOP_NULL;
113  LeafFree = 0;
114  MidFree = 0;
115  TopFree = 0;
116  UnusedPage1 = PAGE_NULL;
117  UnusedPage2 = PAGE_NULL;
118 
119  // Set Magic number:
120  CHECK_CODE(Magic = LIST_MAGIC);
121  }
122 
123  // Destructor:
124  ~list_c()
125  {
126  // Check this object:
127  CHECK_VALID("list_c::destructor");
128 
129  // Make this object invalid:
130  CHECK_CODE(Magic = 0);
131  }
132 
133 //-----------------------------------------------------------------------------
134 // Copy-constructor and assignment operator are not supported for this class:
135 //-----------------------------------------------------------------------------
136 
137  private:
138 
139  list_c(const list_c& obj); // Not implemented
140  list_c& operator=(const list_c& obj); // Not implemented
141 
142 //=============================================================================
143 // Auxiliary Methods for Memory Page Management:
144 //=============================================================================
145 
146  private:
147 
148  // This handles the following problem:
149  // When a memory page allocation fails,
150  // we want to restore the state before the operation.
151  // However, insert might have to allocate three memory pages,
152  // and if the last allocation fails, there are two unused memory pages.
153  // This is not a real memory leak, because the pages are stored
154  // in the memory pool, and the memory pool will free them
155  // when it is destroyed.
156  //
157  // It is also unlikely that a memory page allocation fails,
158  // and later it works again (in which case every insert might
159  // allocate two unused pages in the worst case).
160  //
161  // However, to be very correct, we remember the unused pages
162  // in this object, and use them in the next memory allocation,
163  // before we allocate new pages from the memory pool.
164  // In this way, there can never be more than two unused pages
165  // in this object.
166 
167 //-----------------------------------------------------------------------------
168 // alloc_page: Get a memory page.
169 //-----------------------------------------------------------------------------
170 
171  inline page_t alloc_page() {
172  if(UnusedPage1 == PAGE_NULL)
173  return MemPool.alloc_page();
174  page_t page = UnusedPage1;
175  UnusedPage1 = UnusedPage2;
176  UnusedPage2 = PAGE_NULL;
177  return page;
178  }
179 
180 //-----------------------------------------------------------------------------
181 // free_page: De-allocate a memory page.
182 //-----------------------------------------------------------------------------
183 
184  inline void free_page(page_t page) {
185  CHECK(page != PAGE_NULL, "list_c::free_page: page is NULL");
186  if(UnusedPage1 == PAGE_NULL)
187  UnusedPage1 = page;
188  else {
189  CHECK(UnusedPage2 == PAGE_NULL,
190  "list_c::free_page: too many pages");
191  UnusedPage2 = page;
192  }
193  }
194 
195 //=============================================================================
196 // (Object) Methods:
197 //=============================================================================
198 
199  public:
200 
201 //-----------------------------------------------------------------------------
202 // insert: Append new element to the list (at the end).
203 //-----------------------------------------------------------------------------
204 
205  inline bool insert(T elem) {
206  page_t page;
207 
208  // Ensure that object is valid:
209  CHECK_VALID("list_c::insert");
210 
211  // Most common case: Add elem to current leaf node:
212  if(LeafFree > 0) {
213  LeafFree--;
214  *LeafPtr++ = elem;
215  NumRows++;
216  return true;
217  }
218 
219  // Allocate first leaf:
220  if(LeafNode == LIST_LEAF_NULL) {
221  CHECK(Height == 0,
222  "list_c::insert: null leaf, height != 0");
223  CHECK(NumRows == 0,
224  "list_c::insert: null leaf, num_rows != 0");
225  page = alloc_page();
226  if(page == PAGE_NULL) {
227  MemErr = true;
228  return false;
229  }
230  LeafNode = reinterpret_cast<T*>(page);
231  LeafFree = PAGE_SIZE(T) - 1;
232  CHECK(LeafFree >= 0, "list_c::insert: T too large");
233  LeafPtr = LeafNode;
234  *LeafPtr++ = elem;
235  Height = 1;
236  NumRows = 1;
237  return true;
238  }
239 
240  // There is a leaf node, but it is full:
241  CHECK(LeafNode != LIST_LEAF_NULL,
242  "list_c::insert: LeafNode is NULL");
243  CHECK(LeafFree == 0,
244  "list_c::insert: LeafFree not 0");
245 
246  // Remember old leaf node in case there is no mid node:
247  T* old_leaf_node = LeafNode;
248 
249  // Allocate new leaf node:
250  page = alloc_page();
251  if(page == PAGE_NULL) {
252  MemErr = true;
253  return false;
254  }
255  LeafNode = reinterpret_cast<T*>(page);
256  LeafFree = PAGE_SIZE(T) - 1;
257  CHECK(LeafFree >= 0,
258  "list_c::insert: T too large (2)");
259  LeafPtr = LeafNode;
260  *LeafPtr++ = elem;
261 
262  // Now we must enter the new leaf node to the mid branch level
263  // In case there was no mid branch level before, both nodes,
264  // the old leaf node and the new leaf node must be entered
265  // to the first mid level branch node.
266 
267  // Construct first mid level branch node:
268  if(MidNode == LIST_MID_NULL) {
269  page = alloc_page();
270  if(page == PAGE_NULL) {
271  // Restore state before failed insert:
272  free_page(LeafNode);
273  LeafNode = old_leaf_node;
274  LeafFree = 0;
275  MemErr = true;
276  return false;
277  }
278  MidNode = reinterpret_cast<T**>(page);
279  MidFree = PAGE_SIZE(T*) - 2;
280  CHECK(MidFree >= 0,
281  "list_c::insert: T* too large");
282  MidPtr = MidNode;
283  *MidPtr++ = old_leaf_node;
284  *MidPtr++ = LeafNode;
285  Height = 2;
286  NumRows++;
287  return true;
288  }
289 
290  // There is a mid level branch node and it is not yet full:
291  else if(MidFree > 0) {
292  MidFree--;
293  *MidPtr++ = LeafNode;
294  NumRows++;
295  return true;
296  }
297 
298  // There is a mid level branch node, but it is full:
299  CHECK(MidNode != LIST_MID_NULL,
300  "list_c::insert: MidNode is NULL");
301  CHECK(MidFree == 0,
302  "list_c::insert: MidFree not 0");
303 
304  // Construct additional (not first) mid level branch node:
305  page = alloc_page();
306  if(page == PAGE_NULL) {
307  // Restore state before failed insert:
308  free_page(LeafNode);
309  LeafNode = old_leaf_node;
310  LeafFree = 0;
311  MemErr = true;
312  return false;
313  }
314  T** old_mid_node = MidNode;
315  MidNode = reinterpret_cast<T**>(page);
316  MidFree = PAGE_SIZE(T*) - 1;
317  CHECK(MidFree >= 0,
318  "list_c::insert: T* too large (2)");
319  MidPtr = MidNode;
320  *MidPtr++ = LeafNode;
321 
322  // Now we must enter the new mid node to top level
323  // (because it is not the first / only one).
324  // Simple case: There is already a top node.
325  if(TopNode != LIST_TOP_NULL) {
326  // If it has no space, we would need another level,
327  // which is not implemented:
328  if(TopFree <= 0) {
329  free_page(LeafNode);
330  LeafNode = old_leaf_node;
331  LeafFree = 0;
332  free_page(MidNode);
333  MidNode = old_mid_node;
334  MidFree = 0;
335  err_c::list_capacity_limit(Name, NumRows);
336  return false;
337  }
338  TopFree--;
339  *TopPtr++ = MidNode;
340  NumRows++;
341  return true;
342  }
343 
344  // Finally handle the case that there is no top level node yet.
345  // Construct one (there will always be only one):
346  CHECK(TopNode == LIST_TOP_NULL,
347  "list_c::insert: TopNode is not null");
348  page = alloc_page();
349  if(page == PAGE_NULL) {
350  // Restore state before failed insert:
351  free_page(LeafNode);
352  LeafNode = old_leaf_node;
353  LeafFree = 0;
354  free_page(MidNode);
355  MidNode = old_mid_node;
356  MidFree = 0;
357  MemErr = true;
358  return false;
359  }
360  TopNode = reinterpret_cast<T***>(page);
361  TopFree = PAGE_SIZE(T**) - 2;
362  CHECK(TopFree >= 0,
363  "list_c::insert: T** too large");
364  TopPtr = TopNode;
365  *TopPtr++ = old_mid_node;
366  *TopPtr++ = MidNode;
367  Height = 3;
368  NumRows++;
369  return true;
370  }
371 
372 
373 //=============================================================================
374 // Debugging Support:
375 //=============================================================================
376 
377 //-----------------------------------------------------------------------------
378 // check: Check the integrity of this object, return error message or NULL.
379 //-----------------------------------------------------------------------------
380 
381 #if VER_DEBUG
382  // Integrity check:
383  public:
384  str_t check() const {
385 
386  // Check magic number:
387  if(Magic != LIST_MAGIC)
388  return "wrong magic number";
389 
390  // Check superclass:
391  str_t msg = rel_c::check();
392  if(msg)
393  return msg;
394 
395  // Check number of free places in nodes:
396  if(LeafFree < 0)
397  CHECK_ERR("LeafFree is negative");
398  if(MidFree < 0)
399  CHECK_ERR("MidFree is negative");
400  if(TopFree < 0)
401  CHECK_ERR("TopFree is negative");
402  if(LeafFree >= PAGE_SIZE(T))
403  CHECK_ERR("LeafFree too large");
404  if(MidFree >= PAGE_SIZE(T*))
405  CHECK_ERR("MidFree too large");
406  if(TopFree >= PAGE_SIZE(T**))
407  CHECK_ERR("TopFree too large");
408 
409  // If a node is null, the number of free places must be 0:
410  if(LeafNode == LIST_LEAF_NULL && LeafFree != 0)
411  CHECK_ERR("LeafNode is null, but LeafFree != 0");
412  if(MidNode == LIST_MID_NULL && MidFree != 0)
413  CHECK_ERR("MidNode is null, but MidFree != 0");
414  if(TopNode == LIST_TOP_NULL && TopFree != 0)
415  CHECK_ERR("TopNode is null, but TopFree != 0");
416 
417  // Node and pointer can only be together null:
418  if(LeafNode == LIST_LEAF_NULL && LeafPtr != LIST_LEAF_NULL)
419  CHECK_ERR("LeafNode is null, but LeafPtr is not");
420  if(LeafNode != LIST_LEAF_NULL && LeafPtr == LIST_LEAF_NULL)
421  CHECK_ERR("LeafNode is not null, but LeafPtr is null");
422  if(MidNode == LIST_MID_NULL && MidPtr != LIST_MID_NULL)
423  CHECK_ERR("MidNode is null, but MidPtr is not");
424  if(MidNode != LIST_MID_NULL && MidPtr == LIST_MID_NULL)
425  CHECK_ERR("MidNode is not null, but MidPtr is null");
426  if(TopNode == LIST_TOP_NULL && TopPtr != LIST_TOP_NULL)
427  CHECK_ERR("TopNode is null, but TopPtr is not");
428  if(TopNode != LIST_TOP_NULL && TopPtr == LIST_TOP_NULL)
429  CHECK_ERR("TopNode is not null, but TopPtr is null");
430 
431  // Check that pointers correspond to free places:
432  if(LeafNode != LIST_LEAF_NULL &&
433  LeafFree != PAGE_SIZE(T) - (LeafPtr-LeafNode))
434  CHECK_ERR("LeafFree and LeafPtr are inconsistent");
435  if(MidNode != LIST_MID_NULL &&
436  MidFree != PAGE_SIZE(T*) - (MidPtr-MidNode))
437  CHECK_ERR("MidFree and MidPtr are inconsistent");
438  if(TopNode != LIST_TOP_NULL &&
439  TopFree != PAGE_SIZE(T**) - (TopPtr-TopNode))
440  CHECK_ERR("TopFree and TopPtr are inconsistent");
441 
442  // Check by height:
443  switch(Height) {
444  case 0:
445  if(NumRows != 0)
446  CHECK_ERR("Height 0 - NumRows != 0");
447  if(LeafNode != LIST_LEAF_NULL)
448  CHECK_ERR("Height 0 - Leaf not null");
449  if(MidNode != LIST_MID_NULL)
450  CHECK_ERR("Height 0 - Mid not null");
451  if(TopNode != LIST_TOP_NULL)
452  CHECK_ERR("Height 0 - Top not null");
453  if(LeafFree != 0)
454  CHECK_ERR("Height 0 - LeafFree != 0");
455  if(MidFree != 0)
456  CHECK_ERR("Height 0 - MidFree != 0");
457  if(TopFree != 0)
458  CHECK_ERR("Height 0 - TopFree != 0");
459  break;
460  case 1:
461  if(NumRows > PAGE_SIZE(T))
462  CHECK_ERR(
463  "Height 1 - NumRows too large");
464  if(LeafNode == LIST_LEAF_NULL)
465  CHECK_ERR("Height 1 - Leaf is null");
466  if(MidNode != LIST_MID_NULL)
467  CHECK_ERR("Height 1 - Mid not null");
468  if(TopNode != LIST_TOP_NULL)
469  CHECK_ERR("Height 1 - Top not null");
470  if(MidFree != 0)
471  CHECK_ERR("Height 1 - MidFree != 0");
472  if(TopFree != 0)
473  CHECK_ERR("Height 1 - TopFree != 0");
474  break;
475  case 2:
476  if(NumRows > PAGE_SIZE(T) * PAGE_SIZE(T*))
477  CHECK_ERR(
478  "Height 2 - NumRows too large");
479  if(LeafNode == LIST_LEAF_NULL)
480  CHECK_ERR("Height 2 - Leaf is null");
481  if(MidNode == LIST_MID_NULL)
482  CHECK_ERR("Height 2 - Mid is null");
483  if(TopNode != LIST_TOP_NULL)
484  CHECK_ERR("Height 2 - Top not null");
485  if(TopFree != 0)
486  CHECK_ERR("Height 2 - TopFree != 0");
487  break;
488  case 3:
489  if(NumRows > PAGE_SIZE(T) * PAGE_SIZE(T*)
490  * PAGE_SIZE(T**))
491  CHECK_ERR(
492  "Height 3 - NumRows too large");
493  if(LeafNode == LIST_LEAF_NULL)
494  CHECK_ERR("Height 3 - Leaf is null");
495  if(MidNode == LIST_MID_NULL)
496  CHECK_ERR("Height 3 - Mid is null");
497  if(TopNode == LIST_TOP_NULL)
498  CHECK_ERR("Height 3 - Top is null");
499  break;
500  default:
501  CHECK_ERR("Invalid height");
502  }
503 
504  // Ok:
505  return STR_NULL;
506  }
507 
508  // Magic number (identifies objects of this class for debugging).
509  private:
510  long Magic; // Must be "LIST_MAGIC".
511 #endif
512 
513 //-----------------------------------------------------------------------------
514 // dump: Show data structure.
515 //-----------------------------------------------------------------------------
516 
517 #if VER_DUMP
518 
519  public:
520 
521 void dump(str_t headline = STR_NULL) const
522 {
523  // Headline:
524  if(headline == STR_NULL)
525  headline = "Relation/Sequence";
526  err_c::dump_begin(headline);
527 
528  // Basic information:
529  err_c::dump_str("Name: '");
530  err_c::dump_str(Name);
531  err_c::dump_str("'");
532  err_c::dump_nl();
533  err_c::dump_str("NumRows: ");
534  err_c::dump_int(NumRows);
535  err_c::dump_nl();
536  err_c::dump_str("Height: ");
537  err_c::dump_int(Height);
538  err_c::dump_nl();
539  err_c::dump_str("NumPages: ");
540  err_c::dump_int(MemPool.num_alloc_pages());
541  err_c::dump_nl();
542 
543  err_c::dump_str("Page Size: ");
544  err_c::dump_int(VER_PAGESIZE);
545  err_c::dump_str(" Bytes");
546  err_c::dump_nl();
547  err_c::dump_str("PAGE_SIZE(T): ");
548  err_c::dump_int(PAGE_SIZE(T));
549  err_c::dump_nl();
550  err_c::dump_str("PAGE_SIZE(T*): ");
551  err_c::dump_int(PAGE_SIZE(T*));
552  err_c::dump_nl();
553 
554  err_c::dump_str("LeafFree: ");
555  err_c::dump_int(LeafFree);
556  err_c::dump_nl();
557  err_c::dump_str("MidFree: ");
558  err_c::dump_int(MidFree);
559  err_c::dump_nl();
560  err_c::dump_str("TopFree: ");
561  err_c::dump_int(TopFree);
562  err_c::dump_nl();
563 
564  err_c::dump_str("LeafNode: ");
565  err_c::dump_ptr(LeafNode);
566  err_c::dump_nl();
567  err_c::dump_str("LeafPtr: ");
568  err_c::dump_ptr(LeafPtr);
569  err_c::dump_str(" [index ");
570  err_c::dump_int(static_cast<int>(LeafPtr - LeafNode));
571  err_c::dump_str("]");
572  err_c::dump_nl();
573 
574  err_c::dump_str("MidNode: ");
575  err_c::dump_ptr(MidNode);
576  err_c::dump_nl();
577  err_c::dump_str("MidPtr: ");
578  err_c::dump_ptr(MidPtr);
579  err_c::dump_str(" [index ");
580  err_c::dump_int(static_cast<int>(MidPtr - MidNode));
581  err_c::dump_str("]");
582  err_c::dump_nl();
583 
584  err_c::dump_str("TopNode: ");
585  err_c::dump_ptr(TopNode);
586  err_c::dump_nl();
587  err_c::dump_str("TopPtr: ");
588  err_c::dump_ptr(TopPtr);
589  err_c::dump_str(" [index ");
590  err_c::dump_int(static_cast<int>(TopPtr - TopNode));
591  err_c::dump_str("]");
592  err_c::dump_nl();
593  err_c::dump_nl();
594 
595  // Done:
596  err_c::dump_end();
597 }
598 
599 #endif
600 
601 
602 //=============================================================================
603 // Private Object Members:
604 //=============================================================================
605 
606  private:
607 
608  // Height: Height of the radix tree implementing the flexible array.
609  int Height; // Can only be 0 (empty tree), 1 (only leaf), 2, 3.
610 
611  // LeafNode: Current/Rightmost Leaf Node
612  T *LeafNode; // If Height == 1, this is the root.
613 
614  // MidNode: Current/Rightmost branch node one level above leaf nodes.
615  T **MidNode; // If Height == 2, this is the root.
616 
617  // TopNode: Branch node two levels above leaf nodes.
618  T ***TopNode; // Root for Height == 3. Otherwise unused.
619 
620  // LeafPtr: Next free entry in current leaf node.
621  T *LeafPtr;
622 
623  // MidPtr: Next free entry in current branch node one above leaf nodes.
624  T **MidPtr;
625 
626  // TopPtr: Next free entry in TopNode (two levels above leaf nodes).
627  T ***TopPtr;
628 
629  // LeafFree: Free entries in current leaf node.
630  int LeafFree;
631 
632  // MidFree: Free entries in current mid level node.
633  int MidFree;
634 
635  // TopFree: Free entries in top level node.
636  int TopFree;
637 
638  // Unused pages left over from a failed insert operation:
639  page_t UnusedPage1;
640  page_t UnusedPage2;
641 
642 //-----------------------------------------------------------------------------
643 // This class works together with the corresponding cursor class:
644 //-----------------------------------------------------------------------------
645 
646  friend class cur_list_c<T>;
647 
648 //=============================================================================
649 // End of Class Template:
650 //=============================================================================
651 
652 };
653 
654 
655 //=============================================================================
656 // End of Include File:
657 //=============================================================================
658 
659 #endif
660 
CHECK_CODE
#define CHECK_CODE(CODE)
Definition: check.h:167
err_c::dump_ptr
static void dump_ptr(const void *p)
Definition: err.cpp:791
CHECK_ERR
#define CHECK_ERR(MSG)
Definition: check.h:182
err_c::dump_str
static void dump_str(str_t str)
Definition: err.cpp:705
VER_PAGESIZE
#define VER_PAGESIZE
Definition: ver.h:186
rel_c
Definition: rel.h:72
CHECK_VALID
#define CHECK_VALID(EX)
Definition: check.h:85
err_c::dump_begin
static void dump_begin(str_t headline)
Definition: err.cpp:685
str_t
const char * str_t
Definition: str.h:41
list_c
Definition: list.h:90
err_c::list_capacity_limit
static void list_capacity_limit(str_t name, int curr_length)
Definition: err.cpp:204
STR_NULL
#define STR_NULL
Definition: str.h:52
cur_list_c
Definition: cur_list.h:68
err_c::dump_end
static void dump_end()
Definition: err.cpp:811
err_c::dump_int
static void dump_int(int n)
Definition: err.cpp:739
err_c::dump_nl
static void dump_nl()
Definition: err.cpp:717
CHECK
#define CHECK(EX, MSG)
Definition: check.h:69
Generated by   doxygen 1.8.10