This is BTreeCursor.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 BTreeCursor
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 BTreeCursor class defines objects that perform operations on B* trees.
fs16
fs28 fs16 fs28 A B* tree is logically an ordered set of i key/recordi0 pairs, and a position in a B* tree is defined by a specific key. Each BTreeCursor records a position in a B* tree; the key defining its position is stored in a per instance key buffer. This means that two or more BTreeCursors may be opened on a B* tree without difficulty.
fs16
fs28 fs16 fs28 The lengths of the keys stored in a B* tree are limited by the page size of the backing store. The maximum key length is returned by the b maxKeyLengthb0 method. For efficiency, however, keys should be kept as small as possible. In principle, the lengths of the records stored in a B* tree are limited only by the resolution of a long unsigned integer. In practice, record lengths are limited by the amount of available disk space. Records smaller than the virtual memory page size are copied; records lar ger than the page size are memory mapped.
fs16
fs28 fs16 fs28 For efficiency in working with large records, the BTreeCursor exports several methods for reading and writing ranges of bytes within records. These methods read and write only the pages affected by the byte range operations.
fs16
fs28 fs16 fs28 The BTreeCursor class reports errors with NX_RAISE().
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 BTreeCursori0 void *keyBuffer;
pard s12 li7660 fi-503 ri1007 ql tx10180 tx10684 unsigned short bufferLength;
unsigned short maxKeyLength;
unsigned short keyLength;
id btree;
unsigned long positionHint;
pard s23 li7156 fi-4536 ri1007 ql tx7156 tx10180 tx10684 fs16
fs28 keyBuffer The key buffer
fs16
fs28 bufferLength The current length of the key buffer
fs16
fs28 maxKeyLength The maximum key length for this B* tree
fs16
fs28 keyLength The length of the key in the key buffer
fs16
fs28 btree The BTree object addressed by this cursor
fs16
fs28 positionHint A hint for accelerating key alignment
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 Setting the cursor position f3 - f1 setEnd
pard s12 li7660 fi-503 ri1007 ql tx10180 tx10684 f3 - f1 setFirst
f3 - f1 setKey:length:
f3 - f1 setNext
f3 - f1 setPrevious
pard s23 li7156 fi-4536 ri1007 ql tx7156 tx10180 tx10684 fs16
fs28 Reading and writing keys and records
fi0 f3 - f1 getKey:length:valid:
pard s12 li7660 fi-503 ri1007 ql tx10180 tx10684 f3 - f1 insert:length:
f3 - f1 read:length:valid:
f3 - f1 remove
f3 - f1 replace:length:
pard s23 li7156 fi-4536 ri1007 ql tx7156 tx10180 tx10684 fs16
fs28 Reading and writing byte ranges f3 - f1 append:length:
pard s12 li7660 fi-503 ri1007 ql tx10180 tx10684 f3 - f1 insert:length:at:
f3 - f1 read:length:at:
f3 - f1 remove:at:
f3 - f1 replace:length:at:
pard s23 li7156 fi-4536 ri1007 ql tx7156 tx10180 tx10684 fs16
fs28 Using hints f3 - f1 hint
pard s12 li7660 fi-503 ri1007 ql tx10180 tx10684 f3 - f1 setKey:length:hint:
pard s23 li7156 fi-4536 ri1007 ql tx7156 tx10180 tx10684 fs16
fs28 Miscellaneous f3 - f1 btree
pard s12 li7660 fi-503 ri1007 ql tx10180 tx10684 f3 - f1 maxKeyLength
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 BTreeCursor object for a new B* tree residing in virtual memory. To obtain a BTreeCursor for any other type of B* tree, use the b cursorb0 method of the BTree class.
fs16
fs28 fs16 fs28 See also: + b new b0 (BTree), f3 - b f1 cursor b0 (BTree)
fs16
fs28 pard s22 li2116 fi0 ri1007 ql tx7156 fs16
fs28 INSTANCE METHODS
fs16
fs28 s10 b fs28 fs16
fs28 append:length:
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (void)b append:b0 (void *)i data b i0 length:b0 (unsigned long)i dataLength
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 i0 fs16 fs28 Appends the range of bytes defined by i datai0 and i dataLengthi0 to the record at the cursor position. If there is no i key/recordi0 pair at the cursor position, this method raises an exception.
fs16
fs28 fs16 fs28 See also: f3 - b f1 insert:length:at:
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 fs28 fs16
fs28 btree
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - b f1 btree
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 b0 fs16 fs28 Returns a pointer to the BTree addressed by this 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 Frees the storage occupied by the BTreeCursor object.
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 getKey:length:valid:
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (BOOL)b getKey:b0 (void **)i data
fi0 b i0 length:b0 (unsigned short *)i dataLength
fi0 b i0 valid:b0 (BOOL *)i validFlag
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 i0 fs16 fs28 Aligns the cursor with the i key/recordi0 pair at the current cursor position. If there is no i key/recordi0 pair at the current cursor position, this method aligns the cursor with the i key/recordi0 pair immediately following the current cursor position, and repositions the cursor to match the alignment.
fs16
fs28 fs16 fs28 This method then returns the key defining the cursor position in i *datai0 and i *dataLengthi0 , and returns boolean false in i *validFlagi0 when the cursor is beyond the last i key/recordi0 pair in the B* tree. The return value is boolean true if the cursor postiion did not change.
fs16
fs28 fs16 fs28 The pointer returned in i *datai0 points to the per instance key buffer; it is not guaranteed to remain valid beyond subsequent messages, since the buffer may be moved by b realloc(3)b0 .
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 hint
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (unsigned long)b hint
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 b0 fs16 fs28 Returns a hint describing the cursor position. The hint may be used with the b setKey:length:hint:b0 method to accelerate the key alignment operations performed by b getKey:length:valid:b0 and b read:length:valid:b0 .
fs16
fs28 fs16 fs28 See also: f3 - b f1 setKey:length:hint
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 fs28 fs16
fs28 insert:length:
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (BOOL)b insert:b0 (void *)i data b i0 length:b0 (unsigned long)i dataLength
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 i0 fs16 fs28 If there is no i key/recordi0 pair at the cursor position, this method inserts a new i key/recordi0 pair into the B* tree at the cursor position. The record is defined by i datai0 and i dataLengthi0 ; i dataLengthi0 may be zero. This method returns boolean true if the insertion was performed.
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 insert:length:at:
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (void)b insert:b0 (void *)i data
fi0 b i0 length:b0 (unsigned long)i dataLength
fi0 b i0 at:b0 (unsigned long)i byteOffset
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 i0 fs16 fs28 Inserts the range of bytes defined by i datai0 and i dataLengthi0 at i byteOffseti0 in the record at the cursor position. The portion of the record above i byteOffseti0 is logically shifted to the right. If there is no i key/recordi0 pair at the cursor position, this method raises an exception.
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 maxKeyLength
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (unsigned short)b maxKeyLength
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 b0 fs16 fs28 Returns the maximum key length for the B* tree addressed by the cursor. This is computed as the page size of the backing store less per page overhead. For maximum efficiency, keys should be kept as small as possible.
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 read:length:at:
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (void)b read:b0 (void **)i data
fi0 b i0 length:b0 (unsigned long)i dataLength
fi0 b i0 at:b0 (unsigned long)i byteOffset
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 i0 fs16 fs28 Reads the range of bytes defined by i byteOffseti0 and i dataLengthi0 from the record at the cursor position into i *datai0 . If there is no i key/recordi0 pair at the cursor position, this method raises an exception.
fs16
fs28 fs16 fs28 If both i datai0 and i *datai0 are nonf3 - f1 zero, then i **datai0 must be a the starting address of a valid region of memory at least i dataLengthi0 bytes long. i dataLengthi0 bytes of the record beginning at i byteOffseti0 are then read or mapped into i **datai0 .
fs16
fs28 fs16 fs28 If i datai0 is nonf3 - f1 zero and i *datai0 is zero, then a buffer at least i dataLengthi0 bytes long is allocated with b malloc(3)b0 . i dataLengthi0 bytes of the record beginning at i byteOffseti0 are then read or mapped into the buffer. The address of the buffer is returned in i *datai0 . The sender is responsible for freeing the buffer with b free(3)b0 .
fs16
fs28 fs16 fs28 If i datai0 is zero, this method raises an exception.
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 read:length:valid:
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (BOOL)b read:b0 (void **)i data
fi0 b i0 length:b0 (unsigned long *)i dataLength
fi0 b i0 valid:b0 (BOOL *)i validFlag
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 i0 fs16 fs28 Aligns the cursor with the i key/recordi0 pair at the current cursor position. If there is no i key/recordi0 pair at the current cursor position, this method aligns the cursor with the i key/recordi0 pair immediately following the current cursor position, and repositions the cursor to match the alignment.
fs16
fs28 fs16 fs28 This method then reads the record at the cursor position into i *datai0 and i *dataLengthi0 , and returns boolean false in i *validFlagi0 when the cursor is beyond the last i key/recordi0 pair in the B* tree. The return value is boolean true if the cursor postiion did not change.
fs16
fs28 fs16 fs28 If both i datai0 and i *datai0 are nonf3 - f1 zero, then i **datai0 must be a valid memory location, and i *dataLengthi0 must describe the number of bytes of storage available at i **datai0 . Up to i *dataLengthi0 bytes of the record are then read or mapped into i **datai0 .
fs16
fs28 fs16 fs28 If i datai0 is nonf3 - f1 zero and i *datai0 is zero, then a buffer large enough to hold the record is allocated with b malloc(3)b0 . The entire record is then read or mapped into the buffer, and the record length is returned in i *dataLengthi0 . The address of the buffer is returned in i *datai0 . The sender is responsible for freeing the buffer with b free(3)b0 .
fs16
fs28 fs16 fs28 If i datai0 is zero, then the record length is returned in i *dataLengthi0 .
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 remove
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (void)b remove
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 b0 fs16 fs28 Removes the i key/recordi0 pair at the cursor position. If there is no i key/recordi0 pair at the cursor position, this method raises an exception.
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 remove:at:
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (void)b remove:b0 (unsigned long)i dataLength b i0 at:b0 (unsigned long)i byteOffset
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 i0 fs16 fs28 Removes the range of bytes defined by i byteOffseti0 and i dataLengthi0 from the record at the cursor position. The portion of the record above i byteOffseti0 is logically shifted to the left. If there is no i key/recordi0 pair at the cursor position, this method raises an exception.
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 replace:length:
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (void)b replace:b0 (void *)i data b i0 length:b0 (unsigned long)i dataLength
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 i0 fs16 fs28 Replaces the record at the cursor position using i datai0 and i dataLengthi0 . If there is no i key/recordi0 pair at the cursor position, this method raises an exception.
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 replace:length:at:
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (void)b replace:b0 (void *)i datai0
fi0 b length:b0 (unsigned long)i dataLength
fi0 b i0 at:b0 (unsigned long)i byteOffset
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 i0 fs16 fs28 Replaces the range of bytes defined by i byteOffseti0 and i dataLengthi0 in the record at the cursor position with i datai0 . If the range overruns the end of the record, the excess is silently appended. If there is no i key/recordi0 pair at the cursor position, this method raises an exception.
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 setEnd
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (void)b setEnd
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 b0 fs16 fs28 Positions the cursor at the end of the B* tree, i beyondi0 the last i key/recordi0 pair. A subsequent b setPreviousb0 message will position the cursor i ati0 the last i key/recordi0 pair in the B* tree.
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 setFirst
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (BOOL)b setFirst
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 b0 fs16 fs28 If there is at least one i key/recordi0 pair in the B* tree, this method returns true and positions the cursor at the first i key/recordi0 pair.
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 setKey:length:
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (void)b setKey:b0 (void *)i data b i0 length:b0 (unsigned short)i dataLength
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 i0 fs16 fs28 Sets the cursor position to the key defined by i datai0 and i dataLengthi0 . The key is blind data; key ordering is determined by a user supplied key comparator. See the BTree class for more information on the key comparator.
fs16
fs28 fs16 fs28 See also: f3 - b f1 setKey:length:hint
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 fs28 fs16
fs28 setKey:length:hint:
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (void)b setKey:b0 (void *)i data
fi0 b i0 length:b0 (unsigned short)i dataLength
fi0 b i0 hint:b0 (unsigned long)i aHint
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 i0 fs16 fs28 Similar to b setKey:length:b0 , but accepts a hint returned by b hintb0 . For relatively static B* trees, the use of hints will significantly reduce the average running time of the key alignment operation performed by b getKey:length:valid:b0 and b read:length:valid:b0 . Hints become less effective as B* trees are modified. The use of hints may actually increase the average running time of the key alignment operation for highly dynamic B* trees.
fs16
fs28 fs16 fs28 Hints are especially valuable for improving the performance of secondary key resolution for relatively static B* trees. Retrieve the hint for each primary i key/recordi0 pair after every b getKey:length:valid:b0 , b read:length:valid:b0 or b insert:length:b0 message sent to the primary B* tree. If the hint has changed, store the new hint in the secondary record. At retrieval time, use this method instead of b setKey:length:b0 .
fs16
fs28 fs16 fs28 See also: f3 - b f1 setKey:length:
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 fs28 fs16
fs28 setNext
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (BOOL)b setNext
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 b0 fs16 fs28 Positions the cursor at the i key/recordi0 pair immediately following the current cursor position, and returns boolean false when the cursor moves beyond the last i key/recordi0 pair in the B* tree.
fs16
fs28 pard s10 li2116 fi0 ri1007 ql tx7156 b fs28 fs16
fs28 setPrevious
pard s4 li3628 fi-1007 ri1007 ql b0 fs28 f3 - f1 (BOOL)b setPrevious
fs16
fs28 pard s2 li2620 fi0 ri1007 ql tx3124 tx3628 tx4132 b0 fs16 fs28 Positions the cursor at the i key/recordi0 pair immediately preceding the current cursor position, and returns boolean false when the cursor is already at the first i key/recordi0 pair in the B* tree.
fs16
fs28 }These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.