This is BTree.rtf in view mode; [Download] [Up]
paperh22175 margl-907 margr0 margt0 margb0 {fonttblf0fswiss Helvetica;f1froman Times;f2fmodern Courier;f3ftech Symbol;f4froman Palantino;}fi0 ri0 ql sb0 f1 fs24 Release 2.0 Copyright f3 'e3f1 1990 by NeXT Computer, Inc. All Rights Reserved.
pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 f1 fs28 fs16
fs28
fs16
fs28 fs16 fs28
fs16
fs28 fs16 fs28
fs16
fs28 pard s19 li1108 fi0 ri1007 ql b fs36 fs16
fs36 BTree
fs16
fs36 pard s20 li2116 fi0 ri1007 ql tx7156 b0 fs28 fs16 fs28 INHERITS FROM Object
fs16
fs28 s6 fs16 fs28 DECLARED IN BTree.h
fs16
fs28 s22 fs16
fs28 CLASS DESCRIPTION
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 fs16 fs28 The BTree class implements key based associative memories using the well-known B* tree algorithm. By default, each BTree object manages a single B* tree that resides in virtual memory.
fs16
fs28 fs16 fs28 This class is used by the BTreeFile class to implement B* trees in files. Other types of backing stores are also possible. The BTreeCursor class defines objects that perform operations on B* trees. The BTree class reports errors with NX_RAISE().
fs16
fs28 fs16 fs28 For a description of the B* tree algorithm and its properties, see i Algorithmsi0 by Sedgewick, or i The Art of Computer Programming, Vol. 3/Sorting and Searchingi0 , by Knuth. Both sources provide additional references to the literature.
fs16
fs28 pard s22 li2116 fi0 ri1007 ql tx7156 fs16
fs28 INSTANCE VARIABLES
fs16
fs28 pard s23 li7156 fi-4536 ri1007 ql tx7156 tx10180 tx10684 fs16 fs28 i Inherited from Objecti0 Class isa;
fs16
fs28 i Declared in BTreei0 unsigned short pageSize;
pard s12 li7660 fi-503 ri1007 ql tx10180 tx10684 void *backingStore;
NXBTreeComparator *comparator;
unsigned long btreeDepth;
pard s23 li7156 fi-4536 ri1007 ql tx7156 tx10180 tx10684 fs16
fs28 pageSize The size of a backing store page
fs16
fs28 backingStore A handle to the backing store
fs16
fs28 comparator The key comparator
fs16
fs28 btreeDepth The number of levels in the tree
pard s22 li2116 fi0 ri1007 ql tx7156 fs16
fs28 METHOD TYPES
fs16
fs28 pard s23 li7156 fi-4536 ri1007 ql tx7156 tx10180 tx10684 fs16 fs28 Creating and freeing instances f3 - f1 free
pard s12 li7660 fi-503 ri1007 ql tx10180 tx10684 + new
pard s23 li7156 fi-4536 ri1007 ql tx7156 tx10180 tx10684 fs16
fs28 Ordering the keys f3 - f1 comparator
pard s12 li7660 fi-503 ri1007 ql tx10180 tx10684 f3 - f1 setComparator:
pard s23 li7156 fi-4536 ri1007 ql tx7156 tx10180 tx10684 fs16
fs28 Saving and undoing changes f3 - f1 save
pard s12 li7660 fi-503 ri1007 ql tx10180 tx10684 f3 - f1 undo
pard s23 li7156 fi-4536 ri1007 ql tx7156 tx10180 tx10684 fs16
fs28 Archiving f3 - f1 read:
pard s12 li7660 fi-503 ri1007 ql tx10180 tx10684 f3 - f1 write:
pard s23 li7156 fi-4536 ri1007 ql tx7156 tx10180 tx10684 fs16
fs28 Miscellaneous f3 - f1 count
pard s12 li7660 fi-503 ri1007 ql tx10180 tx10684 f3 - f1 cursor
f3 - f1 empty
pard s22 li2116 fi0 ri1007 ql tx7156 fs16
fs28 CLASS METHODS
fs16
fs28 s10 b fs28 fs16
fs28 new
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 + b new
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 b0 fs16 fs28 Returns a new BTree object for an empty B* tree residing in virtual memory. To create a B* tree in a file, use the BTreeFile class.
fs16
fs28 fs16 fs28 See also: + b new b0 (BTreeCursor), f3 - b f1 createBTreeNamed: b0 (BTreeFile)
fs16
fs28 pard s22 li2116 fi0 ri1007 ql tx7156 fs16
fs28 INSTANCE METHODS
fs16
fs28 s10 b fs28 fs16
fs28 comparator
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (NXBTreeComparator *)b comparator
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 b0 fs16 fs28 Returns the comparator used to order keys in the B* tree. The default comparator is b NXBTreeCompareStrings()b0 .
fs16
fs28 fs16 fs28 See also: f3 - b f1 setComparator:
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 fs28 fs16
fs28 count
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (unsigned long)b count
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 b0 fs16 fs28 Returns the number of i key/recordi0 pairs in the B* tree. This method is much faster than enumerating and counting the i key/recordi0 pairs.
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 cursor
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - b f1 cursor
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 b0 fs16 fs28 Returns a new BTreeCursor object for the receiver. This method may be called more than once to obtain multiple cursors. See the BTreeCursor class for more information on BTreeCursor objects.
fs16
fs28 fs16 fs28 See also: + b new b0 (BTreeCursor)
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 empty
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (void)b empty
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 b0 fs16 fs28 Empties the B* tree. All storage allocated to the B* tree is freed, but the BTree object is not freed; the B* tree is i noti0 removed from the backing store. This method is much faster than enumerating and explicitly removing all of the records with BTreeCursor's b removeb0 method.
fs16
fs28 fs16 fs28 See also: f3 - b f1 freeb0 , f3 - b f1 removeBTreeNamed: b0 (BTreeFile), f3 - b f1 remove b0 (BTreeCursor)
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 free
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - b f1 free
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 b0 fs16 fs28 Saves changes, frees the storage occupied by the BTree object, and reclaims any storage used to cache the B* tree in the backing store.
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 read:
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - b f1 read:b0 (NXTypedStream *)i stream
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 i0 fs16 fs28 Empties the receiver if necessary, and then instantiates in the receiver a copy of the B* tree described by i streami0 . The b read:b0 and b write:b0 methods should not be used as substitutes for a persistent B* tree backing store like BTreeFile.
fs16
fs28 fs16 fs28 See also: f3 - b f1 write:
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 fs28 fs16
fs28 save
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (void)b save
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 b0 fs16 fs28 Saves all changes made since the receipt of the last b saveb0 message, if the B* tree resides in virtual memory. This method does nothing for other types of B* trees. If b saveb0 has not been sent since the B* tree was opened, this method saves all changes made since the B* tree was opened.
fs16
fs28 fs16 fs28 The b undob0 method is used internally by the BTree class when errors are detected during an operation that modifies the B* tree. Since b saveb0 is never used internally, however, this may have the effect of discarding the entire B* tree. This method enables the user to determine the scope of the undo operation performed during error recovery.
fs16
fs28 fs16 fs28 See also: f3 - b f1 undob0 , f3 - b f1 save b0 (BTreeFile)
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 setComparator:
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (void)b setComparator:b0 (NXBTreeComparator *)i comparator
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 i0 fs16 fs28 Sets the comparator used to order keys in the B* tree. The type used to declare i comparatori0 is defined as follows.
fs16
fs28 pard s13 li3124 fi0 ri1007 ql f2 fs24 typedef int
fi0 NXBTreeComparator(const void *data1, unsigned short length1,
fi0 const void *data2, unsigned short length2);
pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 f1 fs28 fs16
fs28 If this method is never called, b NXBTreeCompareStrings()b0 is used as the default comparator. b NXBTreeCompareStrings()b0 performs case sensitive comparsions between strings, with or without null termination.
fs16
fs28 fs16 fs28 This class supplies the following comparators.
fs16
fs28 pard s7 li3124 fi0 ri1007 ql tx5140 tx7156 tx9172 tx11188 NXBTreeCompareStrings()
fi0 NXBTreeCompareMonocaseStrings()
fi0 NXBTreeCompareBytes()
fi0 NXBTreeCompareUnsignedBytes()
fi0 NXBTreeCompareShorts()
fi0 NXBTreeCompareUnsignedShorts()
fi0 NXBTreeCompareLongs()
fi0 NXBTreeCompareUnsignedLongs()
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 fs16 fs28 Each of the supplied comparators compares two arrays, each containing zero or more elements of the base type. If the two arrays are identical in the length of the shorter, then the longer is considered the greater of the two.
fs16
fs28 fs16 fs28 See also: f3 - b f1 comparator
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 fs28 fs16
fs28 undo
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (void)b undo
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 b0 fs16 fs28 Undoes all changes made since the receipt of the last b saveb0 message, if the B* tree resides in virtual memory. This method does nothing for other types of B* trees. If b saveb0 has not been sent since the B* tree was opened, this method undoes all changes made since the B* tree was opened.
fs16
fs28 fs16 fs28 See also: f3 - b f1 saveb0 , f3 - b f1 undo b0 (BTreeFile)
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 write:
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - b f1 write:b0 (NXTypedStream *)i stream
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 i0 fs16 fs28 Writes a description of the B* tree managed by the receiver to i streami0 . The b read:b0 method can use the description to instantiate a copy of the B* tree. The b read:b0 and b write:b0 methods should not be used as substitutes for a persistent B* tree backing store like BTreeFile.
fs16
fs28 fs16 fs28 See also: f3 - b f1 read:
fs16
fs28 }These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.