1 #ifndef UTILITY_H 2 #define UTILITY_H 3 /* Utility - some helper classes 4 ** 5 ** Initial version by Axel Dörfler, axeld@pinc-software.de 6 ** This file may be used under the terms of the OpenBeOS License. 7 */ 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 20 #if __MWERKS__ 21 off_t values[1]; 22 #else 23 off_t values[0]; 24 #endif 25 26 inline int32 Find(off_t value) const; 27 void Insert(off_t value); 28 bool Remove(off_t value); 29 30 private: 31 bool FindInternal(off_t value,int32 &index) const; 32 }; 33 34 35 inline int32 36 sorted_array::Find(off_t value) const 37 { 38 int32 i; 39 return FindInternal(value,i) ? i : -1; 40 } 41 42 43 // The BlockArray reserves a multiple of "blockSize" and 44 // maintain array size for new entries. 45 // This is used for the in-memory log entries before they 46 // are written to disk. 47 48 class BlockArray { 49 public: 50 BlockArray(int32 blockSize); 51 ~BlockArray(); 52 53 int32 Find(off_t value); 54 status_t Insert(off_t value); 55 status_t Remove(off_t value); 56 57 void MakeEmpty(); 58 59 int32 CountItems() const { return fArray != NULL ? fArray->count : 0; } 60 int32 BlocksUsed() const { return fArray != NULL ? ((fArray->count + 1) * sizeof(off_t) + fBlockSize - 1) / fBlockSize : 0; } 61 sorted_array *Array() const { return fArray; } 62 int32 Size() const { return fSize; } 63 64 private: 65 sorted_array *fArray; 66 int32 fBlockSize; 67 int32 fSize; 68 int32 fMaxBlocks; 69 }; 70 71 72 // Doubly linked list 73 74 template<class Node> struct node { 75 Node *next,*prev; 76 77 void 78 Remove() 79 { 80 prev->next = next; 81 next->prev = prev; 82 } 83 84 Node * 85 Next() 86 { 87 if (next && next->next != NULL) 88 return next; 89 90 return NULL; 91 } 92 }; 93 94 template<class Node> struct list { 95 Node *head,*tail,*last; 96 97 list() 98 { 99 head = (Node *)&tail; 100 tail = NULL; 101 last = (Node *)&head; 102 } 103 104 void 105 Add(Node *entry) 106 { 107 entry->next = (Node *)&tail; 108 entry->prev = last; 109 last->next = entry; 110 last = entry; 111 } 112 }; 113 114 115 // Some atomic operations that are somehow missing in BeOS: 116 // 117 // _atomic_test_and_set(value, newValue, testAgainst) 118 // sets "value" to "newValue", if "value" is equal to "testAgainst" 119 // _atomic_set(value, newValue) 120 // sets "value" to "newValue" 121 122 #if _NO_INLINE_ASM 123 // Note that these atomic versions *don't* work as expected! 124 // They are only used for single processor user space tests 125 // (and don't even work correctly there) 126 inline int32 127 _atomic_test_and_set(volatile int32 *value, int32 newValue, int32 testAgainst) 128 { 129 int32 oldValue = *value; 130 if (oldValue == testAgainst) 131 *value = newValue; 132 133 return oldValue; 134 } 135 136 inline void 137 _atomic_set(volatile int32 *value, int32 newValue) 138 { 139 *value = newValue; 140 } 141 #elif __INTEL__ 142 inline int32 143 _atomic_test_and_set(volatile int32 *value, int32 newValue, int32 testAgainst) 144 { 145 int32 oldValue; 146 asm volatile("lock; cmpxchg %%ecx, (%%edx)" 147 : "=a" (oldValue) : "a" (testAgainst), "c" (newValue), "d" (value)); 148 return oldValue; 149 } 150 151 inline void 152 _atomic_set(volatile int32 *value, int32 newValue) 153 { 154 asm volatile("lock; xchg %%eax, (%%edx)" 155 : : "a" (newValue), "d" (value)); 156 } 157 #elif __POWERPC__ && __MWERKS__ /* GCC has different assembler syntax */ 158 inline asm int32 159 _atomic_set(volatile int32 *value, int32) 160 { 161 loop: 162 dcbf r0, r3; 163 lwarx r0, 0, r3; 164 stwcx. r4, 0, r3; 165 bc 5, 2, loop 166 mr r3,r5; 167 isync; 168 blr; 169 } 170 171 inline asm int32 172 _atomic_test_and_set(volatile int32 *value, int32 newValue, int32 testAgainst) 173 { 174 loop: 175 dcbf r0, r3; 176 lwarx r0, 0, r3; 177 cmpw r5, r0; 178 bne no_dice; 179 stwcx. r4, 0, r3; 180 bc 5, 2, loop 181 182 mr r3,r0; 183 isync; 184 blr; 185 186 no_dice: 187 stwcx. r0, 0, r3; 188 mr r3,r0; 189 isync; 190 blr; 191 } 192 193 #else 194 # error The macros _atomic_set(), and _atomic_test_and_set() are not defined for the target processor 195 #endif 196 197 198 extern "C" size_t strlcpy(char *dest, char const *source, size_t length); 199 200 201 #endif /* UTILITY_H */ 202