initInStore:Copyright ©1995 by NeXT Computer, Inc. All Rights Reserved.
| IXBTree |
| Inherits From: | Object | |
| Conforms To: | IXBlockAndStoreAccess IXNameAndFileAccess IXComparatorSetting IXComparisonSetting | |
| Declared In: | btree/IXBTree.h |
| Class Description |
| An IXBTree provides ordered associative storage and retrieval of untyped data. It identifies and orders data items, called values, by key using a comparator function or key format description. A companion class, IXBTreeCursor, is used to actually manipulate the contents of the IXBTree.
An IXBTree can be used with a memory-based IXStore, or with an IXStoreFile. File-based IXBTrees can be used to build persistent dictionaries and databases. As examples, the IXStoreDirectory class makes use of an IXBTree to provide names for other store clients, and the IXRecordManager uses multiple IXBTrees to provide a data management facility that uses Objective C objects as records.
Setting Up an IXBTree An IXBTree can either be initialized as a new client of an IXStore or opened from existing data in an IXStore. In either case, since IXBTree is a store client (as described in the IXBlockAndStoreAccess protocol specification) the IXBTree must use an IXStore to hold its contents. The protocol methods initInStore: and initWithName:inFile: can be used to initialize a new IXBTree in an IXStore. To open an IXBTree from previously created data, use the protocol methods initFromBlock:inStore: or initFromName:inFile:forWriting. After the IXBTree has been initialized, it must have its comparator function or key format description set with the setComparator:context: or setComparisonFormat: messages. A comparator function takes as arguments two pieces of arbitrary data and their lengths, and returns an integer indicating their ordering relative to one another. A key format description is a character string in the Objective C standard type encoding that describes the contents of the keys; the legal type codes are listed in the IXComparisonSetting protocol specification. IXBTrees compare keys as strings by default. See the IXCompareBytes() and IXFormatComparator() function descriptions for examples and for more information on key comparison.
Getting Data into and out of an IXBTree As stated above, IXBTree simply provides the capacity for associative storage. An IXBTreeCursor is needed to take advantage of that capacity. An IXBTreeCursor is like a pointer into the IXBTree: it can move to specific positions within the key space and perform operations on the values stored at those locations, independent of other cursors. The IXCursorPositioning protocol specification describes basic cursoring techniques, and the IXBTreeCursor class specification describes additional methods unique to IXBTreeCursor. Multiple IXBTreeCursors may independently access a single IXBTree. The actions of one cursor don't affect any of the other cursors in the IXBTree, except to the extent that they modify the contents of the IXBTree. It is both safe and meaningful to remove a record that another IXBTreeCursor has just located, as long as the code using the other IXBTreeCursor anticipates this possibility, as described below. IXBTree has a mutex lock which may be used to prevent collisions between cursors operating from different threads. In the case of one cursor removing a value that another cursor has just located, the second cursor will have received an indication from a key-locating method (for example, setKey:andLength:) that it has found a key. When it tries to access the value associated with that key, however, the key may no longer exist. The cursor will detect the deletion and slide forward to the next available key if asked to read the value (see the IXCursorPositioning protocol specification), or will raise an exception if asked to remove or write the value. If your code allows multiple cursors to be concurrently active on a single IXBTree, it must anticipate this behavior by handling the exceptions that may be raised, and by comparing the key against the expected value after invoking getKey:andLength:. Alternatively, your code may group key location and value manipulation operations by locking the IXBTree's mutex with IXLockBTreeMutex() and IXUnLockBTreeMutex() around the pair, or by some alternative mechanism, like a condition, applied at a higher point in the application.
Working with an IXBTree's Store Since IXBTree is a store client, as defined in the IXBlockAndStoreAccess protocol specification, the transaction model of IXStore applies to changes made to the contents of an IXBTree. In particular, the IXBTree's store must be sent commitTransaction messages to make changes to the IXBTree take effect (and be flushed to disk for a file-based store). If an IXBTree is used on a strictly read-only basis, transaction management can be ignored. |
| Instance Variables |
| struct mutex mutexLock; |
| mutexLock | Used to manage concurrent access in multithreaded applications. |
| Adopted Protocols |
| IXBlockAndStoreAccess | initInStore: |
| initFromBlock:inStore: freeFromStore + freeFromBlock:inStore: getBlock:andStore: |
| IXNameAndFileAccess | initWithName:inFile: |
| initFromName:inFile:forWriting: freeFromStore + freeFromName:andFile: getName:andFile: |
| IXComparatorSetting | setComparator:andContext: |
| getComparator:andContext: |
| IXComparisonSetting | setComparisonFormat: |
| comparisonFormat |
| Method Types |
| Accessing IXBTree information | count |
| keyLimit |
| Affecting IXBTree contents | empty |
| compact |
| Optimizing performance | optimizeForTime |
| optimizeForSpace |
| Instance Methods |
| compact |
| compact |
| Compacts the contents of the IXBTree so that it consumes as little space as possible (the average amount of reduction is about 25%). This method may move significant amounts of data, so it can take some time to complete. Key insertion will become slower for a while after this method is invoked, because data has to be moved around again to make room. Key search may become substantially faster however, since less data is paged from disk when searching. Compaction is useful when occasional updates to an IXBTree are followed by lots of reading. Returns self.
Note: This method does nothing in NEXTSTEP Release 3, but should be fully implemented in a later update of the Indexing Kit. Your code may invoke this method freely in anticipation of its being implemented. See also: |
| count |
| (unsigned int)count |
| Returns the number of key/value pairs stored in the IXBTree. |
| empty |
| empty |
| Removes all key/value pairs from the IXBTree, and reduces its storage allocation to the smallest possible size (128 bytes). Returns self. |
| keyLimit |
| (unsigned int)keyLimit |
| Returns the maximum allowable length of keys kept in the IXBTree. An IXBTreeCursor positions itself with a key and the length of the key. That length should never be greater than the key limit. If it is, the IX_TooLargeError exception is raised. |
| optimizeForSpace |
| optimizeForSpace |
| Causes the IXBTree to move its contents around when inserting keys, so that the total amount of storage allocated is kept as small as possible. This will result in slower insertion times, but faster seek times. Your code should send this message when the IXBTree will be used mostly for reading.
Once optimization is enabled, it can't be disabled; however, the type of optimization may be switched at any time between space (fast seek times) and time (fast insertions). Also, an IXBTree doesn't record its optimization type in its IXStore, so optimization must be re-enabled whenever an IXBTree is reconstituted. See also: |
| optimizeForTime |
| optimizeForTime |
| Causes the IXBTree to avoid moving its contents around when inserting keys, so that insertions happen as fast as possible. This can result in more unused storage space and slower seek times. Your code should send an IXBTree this message when it will be making a lot of insertions.
Once optimization is enabled, it can't be disabled; however, the type of optimization may be switched at any time between space (fast seek times) and time (fast insertions). Also, an IXBTree doesn't record its optimization type in its IXStore, so optimization must be re-enabled whenever an IXBTree is reconstituted. See also: |