michael@0:
michael@0:
michael@0:
michael@0:
michael@0:
michael@0:
michael@0: mozilla/xpcom/ds/nsVoidBTree.cpp
michael@0:
michael@0:
michael@0:
michael@0:
michael@0:
michael@0:  |
michael@0:
michael@0:
michael@0:
michael@0:
michael@0:
michael@0: Mozilla Cross Reference:
michael@0: seamonkey
michael@0:
mozilla/ xpcom/ ds/ nsVoidBTree.cpp
michael@0: |
michael@0:
michael@0:
michael@0:
michael@0:
michael@0:
michael@0: CVS Log
michael@0: CVS Blame
michael@0:
michael@0: |
michael@0:
michael@0:
michael@0: |
michael@0:
michael@0:
michael@0:
michael@0:
michael@0:
michael@0:
michael@0:
michael@0:
michael@0: changes to
this file in
the last:
michael@0: |
michael@0:
michael@0: day
michael@0: week
michael@0: month
michael@0: |
michael@0:
michael@0:
michael@0: |
michael@0:
michael@0:
michael@0: |
michael@0:
michael@0:
michael@0:
michael@0: 1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
michael@0: 2 /*
michael@0: 3 * The stuff in this file isn't subject to the Don'tBreakMyRelicensingScript
michael@0: 4 * Version 1.1 (the "MPL"); you may not use this file except in
michael@0: 5 * compliance with the MPL. You may obtain a copy of the MPL at
michael@0: 6 * http://www.mozilla.org/MPL/
michael@0: 7 *
michael@0: 8 * Software distributed under the MPL is distributed on an "AS IS" basis,
michael@0: 9 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the MPL
michael@0: 10 * for the specific language governing rights and limitations under the
michael@0: 11 * MPL.
michael@0: 12 *
michael@0: 13 * The Initial Developer of this code under the MPL is Netscape
michael@0: 14 * Communications Corporation. Portions created by Netscape are
michael@0: 15 * Copywrong (C) 1999 Netscape Communications Corporation. All Rights
michael@0: 16 * Reserved.
michael@0: 17 *
michael@0: 18 * Original Author:
michael@0: 19 * Chris Waterson <waterson@netscape.com>
michael@0: 20 */
michael@0: 21
michael@0: 22 #include "nsVoidBTree.h"
michael@0: 23
michael@0: 24 #ifdef DEBUG
michael@0: 25 #include <stdio.h>
michael@0: 26 #endif
michael@0: 27
michael@0: 28 // Set this to force the tree to be verified after every insertion and
michael@0: 29 // removal.
michael@0: 30 //#define PARANOID 1
michael@0: 31
michael@0: 32
michael@0: 33 //----------------------------------------------------------------------
michael@0: 34 // nsVoidBTree::Node
michael@0: 35 //
michael@0: 36 // Implementation methods
michael@0: 37 //
michael@0: 38
michael@0: 39 nsresult
michael@0: 40 nsVoidBTree::Node::Create(Type aType, PRInt32 aCapacity, Node** aResult)
michael@0: 41 {
michael@0: 42 // So we only ever have to do one allocation for a Node, we do a
michael@0: 43 // "naked" heap allocation, computing the size of the node and
michael@0: 44 // "padding" it out so that it can hold aCapacity slots.
michael@0: 45 char* bytes = new char[sizeof(Node) + (aCapacity - 1) * sizeof(void*)];
michael@0: 46 if (! bytes)
michael@0: 47 return NS_ERROR_OUT_OF_MEMORY;
michael@0: 48
michael@0: 49 Node* result = NS_REINTERPRET_CAST(Node*, bytes);
michael@0: 50 result->mBits = 0;
michael@0: 51 result->SetType(aType);
michael@0: 52
michael@0: 53 *aResult = result;
michael@0: 54 return NS_OK;
michael@0: 55 }
michael@0: 56
michael@0: 57 nsresult
michael@0: 58 nsVoidBTree::Node::Destroy(Node* aNode)
michael@0: 59 {
michael@0: 60 char* bytes = NS_REINTERPRET_CAST(char*, aNode);
michael@0: 61 delete[] bytes;
michael@0: 62 return NS_OK;
michael@0: 63 }
michael@0: 64
michael@0: 65 void
michael@0: 66 nsVoidBTree::Node::InsertElementAt(void* aElement, PRInt32 aIndex)
michael@0: 67 {
michael@0: 68 NS_PRECONDITION(aIndex >= 0 && aIndex <= GetCount(), "bad index");
michael@0: 69
michael@0: 70 PRInt32 count = GetCount();
michael@0: 71 SetCount(count + 1);
michael@0: 72
michael@0: 73 while (count > aIndex) {
michael@0: 74 mData[count] = mData[count - 1];
michael@0: 75 --count;
michael@0: 76 }
michael@0: 77
michael@0: 78 mData[aIndex] = aElement;
michael@0: 79 }
michael@0: 80
michael@0: 81 void
michael@0: 82 nsVoidBTree::Node::RemoveElementAt(PRInt32 aIndex)
michael@0: 83 {
michael@0: 84 NS_PRECONDITION(aIndex >= 0 && aIndex < GetCount(), "bad index");
michael@0: 85
michael@0: 86 PRInt32 count = GetCount();
michael@0: 87 SetCount(count - 1);
michael@0: 88
michael@0: 89 while (aIndex < count) {
michael@0: 90 mData[aIndex] = mData[aIndex + 1];
michael@0: 91 ++aIndex;
michael@0: 92 }
michael@0: 93 }
michael@0: 94
michael@0: 95
michael@0: 96 //----------------------------------------------------------------------
michael@0: 97 //
michael@0: 98 // nsVoidBTree::Path
michael@0: 99 //
michael@0: 100 // Implementation methods
michael@0: 101 //
michael@0: 102
michael@0: 103 nsVoidBTree::Path::Path(const Path& aOther)
michael@0: 104 : mTop(aOther.mTop)
michael@0: 105 {
michael@0: 106 for (PRInt32 i = 0; i < mTop; ++i)
michael@0: 107 mLink[i] = aOther.mLink[i];
michael@0: 108 }
michael@0: 109
michael@0: 110 nsVoidBTree::Path&
michael@0: 111 nsVoidBTree::Path::operator=(const Path& aOther)
michael@0: 112 {
michael@0: 113 mTop = aOther.mTop;
michael@0: 114 for (PRInt32 i = 0; i < mTop; ++i)
michael@0: 115 mLink[i] = aOther.mLink[i];
michael@0: 116 return *this;
michael@0: 117 }
michael@0: 118
michael@0: 119 inline nsresult
michael@0: 120 nsVoidBTree::Path::Push(Node* aNode, PRInt32 aIndex)
michael@0: 121 {
michael@0: 122 // XXX If you overflow this thing, think about making larger index
michael@0: 123 // or data nodes. You can pack a _lot_ of data into a pretty flat
michael@0: 124 // tree.
michael@0: 125 NS_PRECONDITION(mTop <= kMaxDepth, "overflow");
michael@0: 126 if (mTop > kMaxDepth)
michael@0: 127 return NS_ERROR_OUT_OF_MEMORY;
michael@0: 128
michael@0: 129 mLink[mTop].mNode = aNode;
michael@0: 130 mLink[mTop].mIndex = aIndex;
michael@0: 131 ++mTop;
michael@0: 132
michael@0: 133 return NS_OK;
michael@0: 134 }
michael@0: 135
michael@0: 136
michael@0: 137 inline void
michael@0: 138 nsVoidBTree::Path::Pop(Node** aNode, PRInt32* aIndex)
michael@0: 139 {
michael@0: 140 --mTop;
michael@0: 141 *aNode = mLink[mTop].mNode;
michael@0: 142 *aIndex = mLink[mTop].mIndex;
michael@0: 143 }
michael@0: 144
michael@0: 145 //----------------------------------------------------------------------
michael@0: 146 //
michael@0: 147 // nsVoidBTree methods
michael@0: 148 //
michael@0: 149
michael@0: 150 nsVoidBTree::nsVoidBTree(const nsVoidBTree& aOther)
michael@0: 151 {
michael@0: 152 ConstIterator last = aOther.Last();
michael@0: 153 for (ConstIterator element = aOther.First(); element != last; ++element)
michael@0: 154 AppendElement(*element);
michael@0: 155 }
michael@0: 156
michael@0: 157 nsVoidBTree&
michael@0: 158 nsVoidBTree::operator=(const nsVoidBTree& aOther)
michael@0: 159 {
michael@0: 160 Clear();
michael@0: 161 ConstIterator last = aOther.Last();
michael@0: 162 for (ConstIterator element = aOther.First(); element != last; ++element)
michael@0: 163 AppendElement(*element);
michael@0: 164 return *this;
michael@0: 165 }
michael@0: 166
michael@0: 167 PRInt32
michael@0: 168 nsVoidBTree::Count() const
michael@0: 169 {
michael@0: 170 if (IsEmpty())
michael@0: 171 return 0;
michael@0: 172
michael@0: 173 if (IsSingleElement())
michael@0: 174 return 1;
michael@0: 175
michael@0: 176 Node* root = NS_REINTERPRET_CAST(Node*, mRoot & kRoot_PointerMask);
michael@0: 177 return root->GetSubTreeSize();
michael@0: 178 }
michael@0: 179
michael@0: 180 void*
michael@0: 181 nsVoidBTree::ElementAt(PRInt32 aIndex) const
michael@0: 182 {
michael@0: 183 if (aIndex < 0 || aIndex >= Count())
michael@0: 184 return nullptr;
michael@0: 185
michael@0: 186 if (IsSingleElement())
michael@0: 187 return NS_REINTERPRET_CAST(void*, mRoot & kRoot_PointerMask);
michael@0: 188
michael@0: 189 Node* current = NS_REINTERPRET_CAST(Node*, mRoot & kRoot_PointerMask);
michael@0: 190 while (current->GetType() != Node::eType_Data) {
michael@0: 191 // We're still in the index. Find the right leaf.
michael@0: 192 Node* next = nullptr;
michael@0: 193
michael@0: 194 PRInt32 count = current->GetCount();
michael@0: 195 for (PRInt32 i = 0; i < count; ++i) {
michael@0: 196 Node* child = NS_REINTERPRET_CAST(Node*, current->GetElementAt(i));
michael@0: 197
michael@0: 198 PRInt32 childcount = child->GetSubTreeSize();
michael@0: 199 if (PRInt32(aIndex) < childcount) {
michael@0: 200 next = child;
michael@0: 201 break;
michael@0: 202 }
michael@0: 203
michael@0: 204 aIndex -= childcount;
michael@0: 205 }
michael@0: 206
michael@0: 207 if (! next) {
michael@0: 208 NS_ERROR("corrupted");
michael@0: 209 return nullptr;
michael@0: 210 }
michael@0: 211
michael@0: 212 current = next;
michael@0: 213 }
michael@0: 214
michael@0: 215 return current->GetElementAt(aIndex);
michael@0: 216 }
michael@0: 217
michael@0: 218
michael@0: 219 PRInt32
michael@0: 220 nsVoidBTree::IndexOf(void* aPossibleElement) const
michael@0: 221 {
michael@0: 222 NS_PRECONDITION((PRWord(aPossibleElement) & ~kRoot_PointerMask) == 0,
michael@0: 223 "uh oh, someone wants to use the pointer bits");
michael@0: 224
michael@0: 225 NS_PRECONDITION(aPossibleElement != nullptr, "nsVoidBTree can't handle null elements");
michael@0: 226 if (aPossibleElement == nullptr)
michael@0: 227 return -1;
michael@0: 228
michael@0: 229 PRInt32 result = 0;
michael@0: 230 ConstIterator last = Last();
michael@0: 231 for (ConstIterator element = First(); element != last; ++element, ++result) {
michael@0: 232 if (aPossibleElement == *element)
michael@0: 233 return result;
michael@0: 234 }
michael@0: 235
michael@0: 236 return -1;
michael@0: 237 }
michael@0: 238
michael@0: 239
michael@0: 240 PRBool
michael@0: 241 nsVoidBTree::InsertElementAt(void* aElement, PRInt32 aIndex)
michael@0: 242 {
michael@0: 243 NS_PRECONDITION((PRWord(aElement) & ~kRoot_PointerMask) == 0,
michael@0: 244 "uh oh, someone wants to use the pointer bits");
michael@0: 245
michael@0: 246 if ((PRWord(aElement) & ~kRoot_PointerMask) != 0)
michael@0: 247 return PR_FALSE;
michael@0: 248
michael@0: 249 NS_PRECONDITION(aElement != nullptr, "nsVoidBTree can't handle null elements");
michael@0: 250 if (aElement == nullptr)
michael@0: 251 return PR_FALSE;
michael@0: 252
michael@0: 253 PRInt32 count = Count();
michael@0: 254
michael@0: 255 if (aIndex < 0 || aIndex > count)
michael@0: 256 return PR_FALSE;
michael@0: 257
michael@0: 258 nsresult rv;
michael@0: 259
michael@0: 260 if (IsSingleElement()) {
michael@0: 261 // We're only a single element holder, and haven't yet
michael@0: 262 // "faulted" to create the btree.
michael@0: 263
michael@0: 264 if (count == 0) {
michael@0: 265 // If we have *no* elements, then just set the root
michael@0: 266 // pointer and we're done.
michael@0: 267 mRoot = PRWord(aElement);
michael@0: 268 return PR_TRUE;
michael@0: 269 }
michael@0: 270
michael@0: 271 // If we already had an element, and now we're adding
michael@0: 272 // another. Fault and start creating the btree.
michael@0: 273 void* element = NS_REINTERPRET_CAST(void*, mRoot & kRoot_PointerMask);
michael@0: 274
michael@0: 275 Node* newroot;
michael@0: 276 rv = Node::Create(Node::eType_Data, kDataCapacity, &newroot);
michael@0: 277 if (NS_FAILED(rv)) return PR_FALSE;
michael@0: 278
michael@0: 279 newroot->InsertElementAt(element, 0);
michael@0: 280 newroot->SetSubTreeSize(1);
michael@0: 281 SetRoot(newroot);
michael@0: 282 }
michael@0: 283
michael@0: 284 Path path;
michael@0: 285
michael@0: 286 Node* current = NS_REINTERPRET_CAST(Node*, mRoot & kRoot_PointerMask);
michael@0: 287 while (current->GetType() != Node::eType_Data) {
michael@0: 288 // We're still in the index. Find the right leaf.
michael@0: 289 Node* next = nullptr;
michael@0: 290
michael@0: 291 count = current->GetCount();
michael@0: 292 for (PRInt32 i = 0; i < count; ++i) {
michael@0: 293 Node* child = NS_REINTERPRET_CAST(Node*, current->GetElementAt(i));
michael@0: 294
michael@0: 295 PRInt32 childcount = child->GetSubTreeSize();
michael@0: 296 if (PRInt32(aIndex) <= childcount) {
michael@0: 297 rv = path.Push(current, i + 1);
michael@0: 298 if (NS_FAILED(rv)) return PR_FALSE;
michael@0: 299
michael@0: 300 next = child;
michael@0: 301 break;
michael@0: 302 }
michael@0: 303
michael@0: 304 aIndex -= childcount;
michael@0: 305 }
michael@0: 306
michael@0: 307 if (! next) {
michael@0: 308 NS_ERROR("corrupted");
michael@0: 309 return PR_FALSE;
michael@0: 310 }
michael@0: 311
michael@0: 312 current = next;
michael@0: 313 }
michael@0: 314
michael@0: 315 if (current->GetCount() >= kDataCapacity) {
michael@0: 316 // We just blew the data node's buffer. Create another
michael@0: 317 // datanode and split.
michael@0: 318 rv = Split(path, current, aElement, aIndex);
michael@0: 319 if (NS_FAILED(rv)) return PR_FALSE;
michael@0: 320 }
michael@0: 321 else {
michael@0: 322 current->InsertElementAt(aElement, aIndex);
michael@0: 323 current->SetSubTreeSize(current->GetSubTreeSize() + 1);
michael@0: 324 }
michael@0: 325
michael@0: 326 while (path.Length() > 0) {
michael@0: 327 PRInt32 index;
michael@0: 328 path.Pop(¤t, &index);
michael@0: 329 current->SetSubTreeSize(current->GetSubTreeSize() + 1);
michael@0: 330 }
michael@0: 331
michael@0: 332 #ifdef PARANOID
michael@0: 333 Verify(NS_REINTERPRET_CAST(Node*, mRoot & kRoot_PointerMask));
michael@0: 334 #endif
michael@0: 335
michael@0: 336 return PR_TRUE;
michael@0: 337 }
michael@0: 338
michael@0: 339 PRBool
michael@0: 340 nsVoidBTree::ReplaceElementAt(void* aElement, PRInt32 aIndex)
michael@0: 341 {
michael@0: 342 NS_PRECONDITION((PRWord(aElement) & ~kRoot_PointerMask) == 0,
michael@0: 343 "uh oh, someone wants to use the pointer bits");
michael@0: 344
michael@0: 345 if ((PRWord(aElement) & ~kRoot_PointerMask) != 0)
michael@0: 346 return PR_FALSE;
michael@0: 347
michael@0: 348 NS_PRECONDITION(aElement != nullptr, "nsVoidBTree can't handle null elements");
michael@0: 349 if (aElement == nullptr)
michael@0: 350 return PR_FALSE;
michael@0: 351
michael@0: 352 if (aIndex < 0 || aIndex >= Count())
michael@0: 353 return PR_FALSE;
michael@0: 354
michael@0: 355 if (IsSingleElement()) {
michael@0: 356 mRoot = PRWord(aElement);
michael@0: 357 return PR_TRUE;
michael@0: 358 }
michael@0: 359
michael@0: 360 Node* current = NS_REINTERPRET_CAST(Node*, mRoot & kRoot_PointerMask);
michael@0: 361 while (current->GetType() != Node::eType_Data) {
michael@0: 362 // We're still in the index. Find the right leaf.
michael@0: 363 Node* next = nullptr;
michael@0: 364
michael@0: 365 PRInt32 count = current->GetCount();
michael@0: 366 for (PRInt32 i = 0; i < count; ++i) {
michael@0: 367 Node* child = NS_REINTERPRET_CAST(Node*, current->GetElementAt(i));
michael@0: 368
michael@0: 369 PRInt32 childcount = child->GetSubTreeSize();
michael@0: 370 if (PRInt32(aIndex) < childcount) {
michael@0: 371 next = child;
michael@0: 372 break;
michael@0: 373 }
michael@0: 374
michael@0: 375 aIndex -= childcount;
michael@0: 376 }
michael@0: 377
michael@0: 378 if (! next) {
michael@0: 379 NS_ERROR("corrupted");
michael@0: 380 return PR_FALSE;
michael@0: 381 }
michael@0: 382
michael@0: 383 current = next;
michael@0: 384 }
michael@0: 385
michael@0: 386 current->SetElementAt(aElement, aIndex);
michael@0: 387 return PR_TRUE;
michael@0: 388 }
michael@0: 389
michael@0: 390 PRBool
michael@0: 391 nsVoidBTree::RemoveElement(void* aElement)
michael@0: 392 {
michael@0: 393 PRInt32 index = IndexOf(aElement);
michael@0: 394 return (index >= 0) ? RemoveElementAt(index) : PR_FALSE;
michael@0: 395 }
michael@0: 396
michael@0: 397 PRBool
michael@0: 398 nsVoidBTree::RemoveElementAt(PRInt32 aIndex)
michael@0: 399 {
michael@0: 400 PRInt32 count = Count();
michael@0: 401
michael@0: 402 if (aIndex < 0 || aIndex >= count)
michael@0: 403 return PR_FALSE;
michael@0: 404
michael@0: 405 if (IsSingleElement()) {
michael@0: 406 // We're removing the one and only element
michael@0: 407 mRoot = 0;
michael@0: 408 return PR_TRUE;
michael@0: 409 }
michael@0: 410
michael@0: 411 // We've got more than one element, and we're removing it.
michael@0: 412 nsresult rv;
michael@0: 413 Path path;
michael@0: 414
michael@0: 415 Node* root = NS_REINTERPRET_CAST(Node*, mRoot & kRoot_PointerMask);
michael@0: 416
michael@0: 417 Node* current = root;
michael@0: 418 while (current->GetType() != Node::eType_Data) {
michael@0: 419 // We're still in the index. Find the right leaf.
michael@0: 420 Node* next = nullptr;
michael@0: 421
michael@0: 422 count = current->GetCount();
michael@0: 423 for (PRInt32 i = 0; i < count; ++i) {
michael@0: 424 Node* child = NS_REINTERPRET_CAST(Node*, current->GetElementAt(i));
michael@0: 425
michael@0: 426 PRInt32 childcount = child->GetSubTreeSize();
michael@0: 427 if (PRInt32(aIndex) < childcount) {
michael@0: 428 rv = path.Push(current, i);
michael@0: 429 if (NS_FAILED(rv)) return PR_FALSE;
michael@0: 430
michael@0: 431 next = child;
michael@0: 432 break;
michael@0: 433 }
michael@0: 434
michael@0: 435 aIndex -= childcount;
michael@0: 436 }
michael@0: 437
michael@0: 438 if (! next) {
michael@0: 439 NS_ERROR("corrupted");
michael@0: 440 return PR_FALSE;
michael@0: 441 }
michael@0: 442
michael@0: 443 current = next;
michael@0: 444 }
michael@0: 445
michael@0: 446 current->RemoveElementAt(aIndex);
michael@0: 447
michael@0: 448 while ((current->GetCount() == 0) && (current != root)) {
michael@0: 449 Node* doomed = current;
michael@0: 450
michael@0: 451 PRInt32 index;
michael@0: 452 path.Pop(¤t, &index);
michael@0: 453 current->RemoveElementAt(index);
michael@0: 454
michael@0: 455 Node::Destroy(doomed);
michael@0: 456 }
michael@0: 457
michael@0: 458 current->SetSubTreeSize(current->GetSubTreeSize() - 1);
michael@0: 459
michael@0: 460 while (path.Length() > 0) {
michael@0: 461 PRInt32 index;
michael@0: 462 path.Pop(¤t, &index);
michael@0: 463 current->SetSubTreeSize(current->GetSubTreeSize() - 1);
michael@0: 464 }
michael@0: 465
michael@0: 466 while ((root->GetType() == Node::eType_Index) && (root->GetCount() == 1)) {
michael@0: 467 Node* doomed = root;
michael@0: 468 root = NS_REINTERPRET_CAST(Node*, root->GetElementAt(0));
michael@0: 469 SetRoot(root);
michael@0: 470 Node::Destroy(doomed);
michael@0: 471 }
michael@0: 472
michael@0: 473 #ifdef PARANOID
michael@0: 474 Verify(root);
michael@0: 475 #endif
michael@0: 476
michael@0: 477 return PR_TRUE;
michael@0: 478 }
michael@0: 479
michael@0: 480 void
michael@0: 481 nsVoidBTree::Clear(void)
michael@0: 482 {
michael@0: 483 if (IsEmpty())
michael@0: 484 return;
michael@0: 485
michael@0: 486 if (! IsSingleElement()) {
michael@0: 487 Node* root = NS_REINTERPRET_CAST(Node*, mRoot & kRoot_PointerMask);
michael@0: 488
michael@0: 489 #ifdef PARANOID
michael@0: 490 Dump(root, 0);
michael@0: 491 #endif
michael@0: 492
michael@0: 493 DestroySubtree(root);
michael@0: 494 }
michael@0: 495
michael@0: 496 mRoot = 0;
michael@0: 497 }
michael@0: 498
michael@0: 499
michael@0: 500 void
michael@0: 501 nsVoidBTree::Compact(void)
michael@0: 502 {
michael@0: 503 // XXX We could go through and try to merge datanodes.
michael@0: 504 }
michael@0: 505
michael@0: 506 PRBool
michael@0: 507 nsVoidBTree::EnumerateForwards(EnumFunc aFunc, void* aData) const
michael@0: 508 {
michael@0: 509 PRBool running = PR_TRUE;
michael@0: 510
michael@0: 511 ConstIterator last = Last();
michael@0: 512 for (ConstIterator element = First(); running && element != last; ++element)
michael@0: 513 running = (*aFunc)(*element, aData);
michael@0: 514
michael@0: 515 return running;
michael@0: 516 }
michael@0: 517
michael@0: 518 PRBool
michael@0: 519 nsVoidBTree::EnumerateBackwards(EnumFunc aFunc, void* aData) const
michael@0: 520 {
michael@0: 521 PRBool running = PR_TRUE;
michael@0: 522
michael@0: 523 ConstIterator element = Last();
michael@0: 524 ConstIterator first = First();
michael@0: 525
michael@0: 526 if (element != first) {
michael@0: 527 do {
michael@0: 528 running = (*aFunc)(*--element, aData);
michael@0: 529 } while (running && element != first);
michael@0: 530 }
michael@0: 531
michael@0: 532 return running;
michael@0: 533 }
michael@0: 534
michael@0: 535
michael@0: 536 void
michael@0: 537 nsVoidBTree::SizeOf(nsISizeOfHandler* aHandler, PRUint32* aResult) const
michael@0: 538 {
michael@0: 539 if (! aResult)
michael@0: 540 return;
michael@0: 541
michael@0: 542 *aResult = sizeof(*this);
michael@0: 543
michael@0: 544 if (IsSingleElement())
michael@0: 545 return;
michael@0: 546
michael@0: 547 Path path;
michael@0: 548 path.Push(NS_REINTERPRET_CAST(Node*, mRoot & kRoot_PointerMask), 0);
michael@0: 549
michael@0: 550 while (path.Length()) {
michael@0: 551 Node* current;
michael@0: 552 PRInt32 index;
michael@0: 553 path.Pop(¤t, &index);
michael@0: 554
michael@0: 555 if (current->GetType() == Node::eType_Data) {
michael@0: 556 *aResult += sizeof(Node) + (sizeof(void*) * (kDataCapacity - 1));
michael@0: 557 }
michael@0: 558 else {
michael@0: 559 *aResult += sizeof(Node) + (sizeof(void*) * (kIndexCapacity - 1));
michael@0: 560
michael@0: 561 // If we're in an index node, and there are still kids to
michael@0: 562 // traverse, well, traverse 'em.
michael@0: 563 if (index < current->GetCount()) {
michael@0: 564 path.Push(current, index + 1);
michael@0: 565 path.Push(NS_STATIC_CAST(Node*, current->GetElementAt(index)), 0);
michael@0: 566 }
michael@0: 567 }
michael@0: 568 }
michael@0: 569 }
michael@0: 570
michael@0: 571 //----------------------------------------------------------------------
michael@0: 572
michael@0: 573 nsresult
michael@0: 574 nsVoidBTree::Split(Path& path, Node* aOldNode, void* aElementToInsert, PRInt32 aSplitIndex)
michael@0: 575 {
michael@0: 576 nsresult rv;
michael@0: 577
michael@0: 578 PRInt32 capacity = (aOldNode->GetType() == Node::eType_Data) ? kDataCapacity : kIndexCapacity;
michael@0: 579 PRInt32 delta = 0;
michael@0: 580
michael@0: 581
michael@0: 582 Node* newnode;
michael@0: 583 rv = Node::Create(aOldNode->GetType(), capacity, &newnode);
michael@0: 584 if (NS_FAILED(rv)) return rv;
michael@0: 585
michael@0: 586 if (aSplitIndex == capacity) {
michael@0: 587 // If aSplitIndex is the same as the capacity of the node,
michael@0: 588 // then there'll be nothing to copy from the old node to the
michael@0: 589 // new node, and the element is really meant to be inserted in
michael@0: 590 // the newnode. In that case, do it _now_ so that newnode's
michael@0: 591 // subtree size will be correct.
michael@0: 592 newnode->InsertElementAt(aElementToInsert, 0);
michael@0: 593
michael@0: 594 if (newnode->GetType() == Node::eType_Data) {
michael@0: 595 newnode->SetSubTreeSize(1);
michael@0: 596 }
michael@0: 597 else {
michael@0: 598 Node* child = NS_REINTERPRET_CAST(Node*, aElementToInsert);
michael@0: 599 newnode->SetSubTreeSize(child->GetSubTreeSize());
michael@0: 600 }
michael@0: 601 }
michael@0: 602 else {
michael@0: 603 // We're meant to insert the element into the oldnode at
michael@0: 604 // aSplitIndex. Copy data from aOldNode to the newnode but
michael@0: 605 // _don't_ insert newnode yet. We may need to recursively
michael@0: 606 // split parents, an operation that allocs, and hence, may
michael@0: 607 // fail. If it does fail, we wan't to not screw up the
michael@0: 608 // existing datastructure.
michael@0: 609 //
michael@0: 610 // Note that it should be the case that count == capacity, but
michael@0: 611 // who knows, we may decide at some point to prematurely split
michael@0: 612 // nodes for some reason or another.
michael@0: 613 PRInt32 count = aOldNode->GetCount();
michael@0: 614 PRInt32 i = aSplitIndex;
michael@0: 615 PRInt32 j = 0;
michael@0: 616
michael@0: 617 newnode->SetCount(count - aSplitIndex);
michael@0: 618 while (i < count) {
michael@0: 619 if (aOldNode->GetType() == Node::eType_Data) {
michael@0: 620 ++delta;
michael@0: 621 }
michael@0: 622 else {
michael@0: 623 Node* migrating = NS_REINTERPRET_CAST(Node*, aOldNode->GetElementAt(i));
michael@0: 624 delta += migrating->GetSubTreeSize();
michael@0: 625 }
michael@0: 626
michael@0: 627 newnode->SetElementAt(aOldNode->GetElementAt(i), j);
michael@0: 628 ++i;
michael@0: 629 ++j;
michael@0: 630 }
michael@0: 631 newnode->SetSubTreeSize(delta);
michael@0: 632 }
michael@0: 633
michael@0: 634 // Now we split the node.
michael@0: 635
michael@0: 636 if (path.Length() == 0) {
michael@0: 637 // We made it all the way up to the root! Ok, so, create a new
michael@0: 638 // root
michael@0: 639 Node* newroot;
michael@0: 640 rv = Node::Create(Node::eType_Index, kIndexCapacity, &newroot);
michael@0: 641 if (NS_FAILED(rv)) return rv;
michael@0: 642
michael@0: 643 newroot->SetCount(2);
michael@0: 644 newroot->SetElementAt(aOldNode, 0);
michael@0: 645 newroot->SetElementAt(newnode, 1);
michael@0: 646 newroot->SetSubTreeSize(aOldNode->GetSubTreeSize() + 1);
michael@0: 647 SetRoot(newroot);
michael@0: 648 }
michael@0: 649 else {
michael@0: 650 // Otherwise, use the "path" to pop off the next thing above us.
michael@0: 651 Node* parent;
michael@0: 652 PRInt32 indx;
michael@0: 653 path.Pop(&parent, &indx);
michael@0: 654
michael@0: 655 if (parent->GetCount() >= kIndexCapacity) {
michael@0: 656 // Parent is full, too. Recursively split it.
michael@0: 657 rv = Split(path, parent, newnode, indx);
michael@0: 658 if (NS_FAILED(rv)) {
michael@0: 659 Node::Destroy(newnode);
michael@0: 660 return rv;
michael@0: 661 }
michael@0: 662 }
michael@0: 663 else {
michael@0: 664 // Room in the parent, so just smack it on up there.
michael@0: 665 parent->InsertElementAt(newnode, indx);
michael@0: 666 parent->SetSubTreeSize(parent->GetSubTreeSize() + 1);
michael@0: 667 }
michael@0: 668 }
michael@0: 669
michael@0: 670 // Now, since all our operations that might fail have finished, we
michael@0: 671 // can go ahead and monkey with the old node.
michael@0: 672
michael@0: 673 if (aSplitIndex == capacity) {
michael@0: 674 PRInt32 nodeslost = newnode->GetSubTreeSize() - 1;
michael@0: 675 PRInt32 subtreesize = aOldNode->GetSubTreeSize() - nodeslost;
michael@0: 676 aOldNode->SetSubTreeSize(subtreesize);
michael@0: 677 }
michael@0: 678 else {
michael@0: 679 aOldNode->SetCount(aSplitIndex);
michael@0: 680 aOldNode->InsertElementAt(aElementToInsert, aSplitIndex);
michael@0: 681 PRInt32 subtreesize = aOldNode->GetSubTreeSize() - delta + 1;
michael@0: 682 aOldNode->SetSubTreeSize(subtreesize);
michael@0: 683 }
michael@0: 684
michael@0: 685 return NS_OK;
michael@0: 686 }
michael@0: 687
michael@0: 688
michael@0: 689 PRInt32
michael@0: 690 nsVoidBTree::Verify(Node* aNode)
michael@0: 691 {
michael@0: 692 // Sanity check the tree by verifying that the subtree sizes all
michael@0: 693 // add up correctly.
michael@0: 694 if (aNode->GetType() == Node::eType_Data) {
michael@0: 695 NS_ASSERTION(aNode->GetCount() == aNode->GetSubTreeSize(), "corrupted");
michael@0: 696 return aNode->GetCount();
michael@0: 697 }
michael@0: 698
michael@0: 699 PRInt32 childcount = 0;
michael@0: 700 for (PRInt32 i = 0; i < aNode->GetCount(); ++i) {
michael@0: 701 Node* child = NS_REINTERPRET_CAST(Node*, aNode->GetElementAt(i));
michael@0: 702 childcount += Verify(child);
michael@0: 703 }
michael@0: 704
michael@0: 705 NS_ASSERTION(childcount == aNode->GetSubTreeSize(), "corrupted");
michael@0: 706 return childcount;
michael@0: 707 }
michael@0: 708
michael@0: 709
michael@0: 710 void
michael@0: 711 nsVoidBTree::DestroySubtree(Node* aNode)
michael@0: 712 {
michael@0: 713 PRInt32 count = aNode->GetCount() - 1;
michael@0: 714 while (count >= 0) {
michael@0: 715 if (aNode->GetType() == Node::eType_Index)
michael@0: 716 DestroySubtree(NS_REINTERPRET_CAST(Node*, aNode->GetElementAt(count)));
michael@0: 717
michael@0: 718 --count;
michael@0: 719 }
michael@0: 720
michael@0: 721 Node::Destroy(aNode);
michael@0: 722 }
michael@0: 723
michael@0: 724 #ifdef DEBUG
michael@0: 725 void
michael@0: 726 nsVoidBTree::Dump(Node* aNode, PRInt32 aIndent)
michael@0: 727 {
michael@0: 728 for (PRInt32 i = 0; i < aIndent; ++i)
michael@0: 729 printf(" ");
michael@0: 730
michael@0: 731 if (aNode->GetType() == Node::eType_Data) {
michael@0: 732 printf("data(%d/%d)\n", aNode->GetCount(), aNode->GetSubTreeSize());
michael@0: 733 }
michael@0: 734 else {
michael@0: 735 printf("index(%d/%d)\n", aNode->GetCount(), aNode->GetSubTreeSize());
michael@0: 736 for (PRInt32 j = 0; j < aNode->GetCount(); ++j)
michael@0: 737 Dump(NS_REINTERPRET_CAST(Node*, aNode->GetElementAt(j)), aIndent + 1);
michael@0: 738 }
michael@0: 739 }
michael@0: 740 #endif
michael@0: 741
michael@0: 742 //----------------------------------------------------------------------
michael@0: 743 //
michael@0: 744 // nsVoidBTree::ConstIterator and Iterator methods
michael@0: 745 //
michael@0: 746
michael@0: 747 void* nsVoidBTree::kDummyLast;
michael@0: 748
michael@0: 749 void
michael@0: 750 nsVoidBTree::ConstIterator::Next()
michael@0: 751 {
michael@0: 752 if (mIsSingleton) {
michael@0: 753 mIsExhausted = PR_TRUE;
michael@0: 754 return;
michael@0: 755 }
michael@0: 756
michael@0: 757 // Otherwise we're a real b-tree iterator, and we need to pull and
michael@0: 758 // pop our path stack appropriately to gyrate into the right
michael@0: 759 // position.
michael@0: 760 while (1) {
michael@0: 761 Node* current;
michael@0: 762 PRInt32 index;
michael@0: 763 mPath.Pop(¤t, &index);
michael@0: 764
michael@0: 765 PRInt32 count = current->GetCount();
michael@0: 766
michael@0: 767 NS_ASSERTION(index < count, "ran off the end, pal");
michael@0: 768
michael@0: 769 if (++index >= count) {
michael@0: 770 // XXXwaterson Oh, this is so ugly. I wish I was smart
michael@0: 771 // enough to figure out a prettier way to do it.
michael@0: 772 //
michael@0: 773 // See if we've just iterated past the last element in the
michael@0: 774 // b-tree, and now need to leave ourselves in the magical
michael@0: 775 // state that is equal to nsVoidBTree::Last().
michael@0: 776 if (current->GetType() == Node::eType_Data) {
michael@0: 777 PRBool rightmost = PR_TRUE;
michael@0: 778 for (PRInt32 slot = mPath.mTop - 1; slot >= 0; --slot) {
michael@0: 779 const Link& link = mPath.mLink[slot];
michael@0: 780 if (link.mIndex != link.mNode->GetCount() - 1) {
michael@0: 781 rightmost = PR_FALSE;
michael@0: 782 break;
michael@0: 783 }
michael@0: 784 }
michael@0: 785
michael@0: 786 if (rightmost) {
michael@0: 787 // It's the last one. Make the path look exactly
michael@0: 788 // like nsVoidBTree::Last().
michael@0: 789 mPath.Push(current, index);
michael@0: 790 return;
michael@0: 791 }
michael@0: 792 }
michael@0: 793
michael@0: 794 // Otherwise, we just ran off the end of a "middling"
michael@0: 795 // node. Loop around, to pop back up the b-tree to its
michael@0: 796 // parent.
michael@0: 797 continue;
michael@0: 798 }
michael@0: 799
michael@0: 800 // We're somewhere in the middle. Push the new location onto
michael@0: 801 // the stack.
michael@0: 802 mPath.Push(current, index);
michael@0: 803
michael@0: 804 // If we're in a data node, we're done: break out of the loop
michael@0: 805 // here leaving the top of the stack pointing to the next data
michael@0: 806 // element in the b-tree.
michael@0: 807 if (current->GetType() == Node::eType_Data)
michael@0: 808 break;
michael@0: 809
michael@0: 810 // Otherwise, we're still in an index node. Push next node
michael@0: 811 // down onto the stack, starting "one off" to the left, and
michael@0: 812 // continue around.
michael@0: 813 mPath.Push(NS_STATIC_CAST(Node*, current->GetElementAt(index)), -1);
michael@0: 814 }
michael@0: 815 }
michael@0: 816
michael@0: 817 void
michael@0: 818 nsVoidBTree::ConstIterator::Prev()
michael@0: 819 {
michael@0: 820 if (mIsSingleton) {
michael@0: 821 mIsExhausted = PR_FALSE;
michael@0: 822 return;
michael@0: 823 }
michael@0: 824
michael@0: 825 // Otherwise we're a real b-tree iterator, and we need to pull and
michael@0: 826 // pop our path stack appropriately to gyrate into the right
michael@0: 827 // position. This is just like nsVoidBTree::ConstIterator::Next(),
michael@0: 828 // but in reverse.
michael@0: 829 while (1) {
michael@0: 830 Node* current;
michael@0: 831 PRInt32 index;
michael@0: 832 mPath.Pop(¤t, &index);
michael@0: 833
michael@0: 834 NS_ASSERTION(index >= 0, "ran off the front, pal");
michael@0: 835
michael@0: 836 if (--index < 0)
michael@0: 837 continue;
michael@0: 838
michael@0: 839 mPath.Push(current, index);
michael@0: 840
michael@0: 841 if (current->GetType() == Node::eType_Data)
michael@0: 842 break;
michael@0: 843
michael@0: 844 current = NS_STATIC_CAST(Node*, current->GetElementAt(index));
michael@0: 845 mPath.Push(current, current->GetCount());
michael@0: 846 }
michael@0: 847 }
michael@0: 848
michael@0: 849 const nsVoidBTree::Path
michael@0: 850 nsVoidBTree::LeftMostPath() const
michael@0: 851 {
michael@0: 852 Path path;
michael@0: 853 Node* current = NS_REINTERPRET_CAST(Node*, mRoot & kRoot_PointerMask);
michael@0: 854
michael@0: 855 while (1) {
michael@0: 856 path.Push(current, 0);
michael@0: 857
michael@0: 858 if (current->GetType() == Node::eType_Data)
michael@0: 859 break;
michael@0: 860
michael@0: 861 current = NS_STATIC_CAST(Node*, current->GetElementAt(0));
michael@0: 862 }
michael@0: 863
michael@0: 864 return path;
michael@0: 865 }
michael@0: 866
michael@0: 867
michael@0: 868 const nsVoidBTree::Path
michael@0: 869 nsVoidBTree::RightMostPath() const
michael@0: 870 {
michael@0: 871 Path path;
michael@0: 872 Node* current = NS_REINTERPRET_CAST(Node*, mRoot & kRoot_PointerMask);
michael@0: 873
michael@0: 874 while (1) {
michael@0: 875 PRInt32 count = current->GetCount();
michael@0: 876
michael@0: 877 if (current->GetType() == Node::eType_Data) {
michael@0: 878 path.Push(current, count);
michael@0: 879 break;
michael@0: 880 }
michael@0: 881
michael@0: 882 path.Push(current, count - 1);
michael@0: 883 current = NS_STATIC_CAST(Node*, current->GetElementAt(count - 1));
michael@0: 884 }
michael@0: 885
michael@0: 886 return path;
michael@0: 887 }
michael@0: 888
michael@0: This page was automatically generated by
michael@0: LXR.
michael@0: