1/* 2 * Copyright 2011, Jérôme Duval, korli@users.berlios.de. 3 * Copyright 2001-2010, Axel Dörfler, axeld@pinc-software.de. 4 * This file may be used under the terms of the MIT License. 5 */ 6 7 8//! B+Tree implementation 9 10 11#include "BPlusTree.h" 12 13#include "CachedBlock.h" 14 15#include <stdlib.h> 16#include <string.h> 17#include <util/AutoLock.h> 18 19 20//#define TRACE_BTRFS 21#ifdef TRACE_BTRFS 22# define TRACE(x...) dprintf("\33[34mbtrfs:\33[0m " x) 23#else 24# define TRACE(x...) ; 25#endif 26# define ERROR(x...) dprintf("\33[34mbtrfs:\33[0m " x) 27 28 29BPlusTree::BPlusTree(Volume* volume, struct btrfs_stream *stream) 30 : 31 fStream(stream), 32 fRootBlock(0), 33 fVolume(volume) 34{ 35 mutex_init(&fIteratorLock, "btrfs b+tree iterator"); 36} 37 38 39BPlusTree::BPlusTree(Volume* volume, fsblock_t rootBlock) 40 : 41 fStream(NULL), 42 fRootBlock(rootBlock), 43 fVolume(volume) 44{ 45 mutex_init(&fIteratorLock, "btrfs b+tree iterator"); 46} 47 48 49BPlusTree::~BPlusTree() 50{ 51 // if there are any TreeIterators left, we need to stop them 52 // (can happen when the tree's inode gets deleted while 53 // traversing the tree - a TreeIterator doesn't lock the inode) 54 mutex_lock(&fIteratorLock); 55 56 SinglyLinkedList<TreeIterator>::Iterator iterator 57 = fIterators.GetIterator(); 58 while (iterator.HasNext()) 59 iterator.Next()->Stop(); 60 mutex_destroy(&fIteratorLock); 61} 62 63 64int32 65BPlusTree::_CompareKeys(struct btrfs_key &key1, struct btrfs_key &key2) 66{ 67 if (key1.ObjectID() > key2.ObjectID()) 68 return 1; 69 if (key1.ObjectID() < key2.ObjectID()) 70 return -1; 71 if (key1.Type() > key2.Type()) 72 return 1; 73 if (key1.Type() < key2.Type()) 74 return -1; 75 if (key1.Offset() > key2.Offset()) 76 return 1; 77 if (key1.Offset() < key2.Offset()) 78 return -1; 79 return 0; 80} 81 82 83/*! Searches the key in the tree, and stores the allocated found item in 84 _value, if successful. 85 Returns B_OK when the key could be found, B_ENTRY_NOT_FOUND if not. 86 It can also return other errors to indicate that something went wrong. 87*/ 88status_t 89BPlusTree::_Find(struct btrfs_key &key, void** _value, size_t* _size, 90 bplustree_traversing type) 91{ 92 TRACE("Find() objectid %lld type %d offset %lld \n", key.ObjectID(), 93 key.Type(), key.Offset()); 94 btrfs_stream *stream = fStream; 95 CachedBlock cached(fVolume); 96 fsblock_t physical; 97 if (stream == NULL) { 98 if (fVolume->FindBlock(fRootBlock, physical) != B_OK) { 99 ERROR("Find() unmapped block %lld\n", fRootBlock); 100 return B_ERROR; 101 } 102 stream = (btrfs_stream *)cached.SetTo(physical); 103 } 104 105 while (stream->header.Level() != 0) { 106 TRACE("Find() level %d\n", stream->header.Level()); 107 uint32 i = 1; 108 for (; i < stream->header.ItemCount(); i++) { 109 int32 comp = _CompareKeys(stream->index[i].key, key); 110 TRACE("Find() found index %ld at %lld comp %ld\n", i, 111 stream->index[i].BlockNum(), comp); 112 if (comp < 0) 113 continue; 114 if (comp > 0 || type == BPLUSTREE_BACKWARD) 115 break; 116 } 117 TRACE("Find() getting index %ld at %lld\n", i - 1, 118 stream->index[i - 1].BlockNum()); 119 120 if (fVolume->FindBlock(stream->index[i - 1].BlockNum(), physical) 121 != B_OK) { 122 ERROR("Find() unmapped block %lld\n", 123 stream->index[i - 1].BlockNum()); 124 return B_ERROR; 125 } 126 stream = (btrfs_stream *)cached.SetTo(physical); 127 } 128 129 uint32 i; 130#ifdef TRACE_BTRFS 131 TRACE("Find() dump count %ld\n", stream->header.ItemCount()); 132 for (i = 0; i < stream->header.ItemCount(); i++) { 133 int32 comp = _CompareKeys(key, stream->entries[i].key); 134 TRACE("Find() dump %ld %ld offset %lld comp %ld\n", 135 stream->entries[i].Offset(), 136 stream->entries[i].Size(), stream->entries[i].key.Offset(), comp); 137 } 138#endif 139 140 for (i = 0; i < stream->header.ItemCount(); i++) { 141 int32 comp = _CompareKeys(key, stream->entries[i].key); 142 TRACE("Find() found %ld %ld oid %lld type %d offset %lld comp %ld\n", 143 stream->entries[i].Offset(), stream->entries[i].Size(), 144 stream->entries[i].key.ObjectID(), stream->entries[i].key.Type(), 145 stream->entries[i].key.Offset(), comp); 146 if (comp == 0) 147 break; 148 if (comp < 0 && i > 0) { 149 if (type == BPLUSTREE_EXACT) 150 return B_ENTRY_NOT_FOUND; 151 if (type == BPLUSTREE_BACKWARD) 152 i--; 153 break; 154 } 155 } 156 157 if (i == stream->header.ItemCount()) { 158 if (type == BPLUSTREE_BACKWARD) 159 i--; 160 else 161 return B_ENTRY_NOT_FOUND; 162 } 163 164 if (i < stream->header.ItemCount() 165 && stream->entries[i].key.Type() == key.Type()) { 166 TRACE("Find() found %ld %ld\n", stream->entries[i].Offset(), 167 stream->entries[i].Size()); 168 if (_value != NULL) { 169 *_value = malloc(stream->entries[i].Size()); 170 memcpy(*_value, ((uint8 *)&stream->entries[0] 171 + stream->entries[i].Offset()), 172 stream->entries[i].Size()); 173 key.SetOffset(stream->entries[i].key.Offset()); 174 if (_size != NULL) 175 *_size = stream->entries[i].Size(); 176 } 177 return B_OK; 178 } 179 180 181 TRACE("Find() not found %lld %lld\n", key.Offset(), key.ObjectID()); 182 183 return B_ENTRY_NOT_FOUND; 184} 185 186 187status_t 188BPlusTree::FindNext(struct btrfs_key &key, void** _value, size_t* _size) 189{ 190 return _Find(key, _value, _size, BPLUSTREE_FORWARD); 191} 192 193 194status_t 195BPlusTree::FindPrevious(struct btrfs_key &key, void** _value, size_t* _size) 196{ 197 return _Find(key, _value, _size, BPLUSTREE_BACKWARD); 198} 199 200 201status_t 202BPlusTree::FindExact(struct btrfs_key &key, void** _value, size_t* _size) 203{ 204 return _Find(key, _value, _size, BPLUSTREE_EXACT); 205} 206 207 208void 209BPlusTree::_AddIterator(TreeIterator* iterator) 210{ 211 MutexLocker _(fIteratorLock); 212 fIterators.Add(iterator); 213} 214 215 216void 217BPlusTree::_RemoveIterator(TreeIterator* iterator) 218{ 219 MutexLocker _(fIteratorLock); 220 fIterators.Remove(iterator); 221} 222 223 224// #pragma mark - 225 226 227TreeIterator::TreeIterator(BPlusTree* tree, struct btrfs_key &key) 228 : 229 fTree(tree), 230 fCurrentKey(key) 231{ 232 Rewind(); 233 tree->_AddIterator(this); 234} 235 236 237TreeIterator::~TreeIterator() 238{ 239 if (fTree) 240 fTree->_RemoveIterator(this); 241} 242 243 244/*! Iterates through the tree in the specified direction. 245*/ 246status_t 247TreeIterator::Traverse(bplustree_traversing direction, struct btrfs_key &key, 248 void** value, size_t* size) 249{ 250 if (fTree == NULL) 251 return B_INTERRUPTED; 252 253 fCurrentKey.SetOffset(fCurrentKey.Offset() + direction); 254 status_t status = fTree->_Find(fCurrentKey, value, size, 255 direction); 256 if (status != B_OK) { 257 TRACE("TreeIterator::Traverse() Find failed\n"); 258 return B_ENTRY_NOT_FOUND; 259 } 260 261 return B_OK; 262} 263 264 265/*! just sets the current key in the iterator. 266*/ 267status_t 268TreeIterator::Find(struct btrfs_key &key) 269{ 270 if (fTree == NULL) 271 return B_INTERRUPTED; 272 fCurrentKey = key; 273 return B_OK; 274} 275 276 277void 278TreeIterator::Stop() 279{ 280 fTree = NULL; 281} 282 283