1 /* Utility - some helper classes 2 * 3 * Copyright 2001-2004, Axel Dörfler, axeld@pinc-software.de. 4 * This file may be used under the terms of the MIT License. 5 */ 6 #ifndef UTILITY_H 7 #define UTILITY_H 8 9 10 #include <SupportDefs.h> 11 12 13 // Simple array, used for the duplicate handling in the B+Tree, 14 // and for the log entries. 15 16 struct sorted_array { 17 public: 18 off_t count; 19 off_t values[0]; 20 21 inline int32 Find(off_t value) const; 22 void Insert(off_t value); 23 bool Remove(off_t value); 24 25 private: 26 bool FindInternal(off_t value,int32 &index) const; 27 }; 28 29 30 inline int32 31 sorted_array::Find(off_t value) const 32 { 33 int32 i; 34 return FindInternal(value,i) ? i : -1; 35 } 36 37 38 // The BlockArray reserves a multiple of "blockSize" and 39 // maintain array size for new entries. 40 // This is used for the in-memory log entries before they 41 // are written to disk. 42 43 class BlockArray { 44 public: 45 BlockArray(int32 blockSize); 46 ~BlockArray(); 47 48 int32 Find(off_t value); 49 status_t Insert(off_t value); 50 status_t Remove(off_t value); 51 52 void MakeEmpty(); 53 54 int32 CountItems() const { return fArray != NULL ? fArray->count : 0; } 55 int32 BlocksUsed() const { return fArray != NULL ? ((fArray->count + 1) * sizeof(off_t) + fBlockSize - 1) / fBlockSize : 0; } 56 sorted_array *Array() const { return fArray; } 57 int32 Size() const { return fSize; } 58 59 private: 60 sorted_array *fArray; 61 int32 fBlockSize; 62 int32 fSize; 63 int32 fMaxBlocks; 64 }; 65 66 67 // Doubly linked list 68 69 template<class Node> struct node { 70 Node *next, *prev; 71 72 void 73 Remove() 74 { 75 prev->next = next; 76 next->prev = prev; 77 } 78 79 Node * 80 Next() 81 { 82 if (next && next->next != NULL) 83 return next; 84 85 return NULL; 86 } 87 }; 88 89 template<class Node> struct list { 90 Node *head, *tail, *last; 91 92 list() 93 { 94 head = (Node *)&tail; 95 tail = NULL; 96 last = (Node *)&head; 97 } 98 99 void 100 Add(Node *entry) 101 { 102 entry->next = (Node *)&tail; 103 entry->prev = last; 104 last->next = entry; 105 last = entry; 106 } 107 }; 108 109 #endif /* UTILITY_H */ 110