home *** CD-ROM | disk | FTP | other *** search
/ Super Net 1 / SUPERNET_1.iso / PC / OTROS / UNIX / GOPHER / BTREE / BTREE.H next >
Encoding:
C/C++ Source or Header  |  1991-10-06  |  6.7 KB  |  200 lines

  1. /*
  2. BTree.h
  3. Copyright 1990, NeXT, Inc.
  4. Responsibility: Jack Greenfield
  5.  
  6. DEFINED AS: A common class
  7. HEADER FILES: BTree.h
  8. */
  9.  
  10. #import    "BTreeCursor.h"
  11. #import    "BTreeErrors.h"
  12.  
  13. typedef int 
  14. NXBTreeComparator(const void *data1, unsigned short length1, 
  15.     const void *data2, unsigned short length2);
  16.  
  17. extern int 
  18. NXBTreeCompareStrings(const void *data1, unsigned short length1, 
  19.     const void *data2, unsigned short length2);
  20.  
  21. extern int 
  22. NXBTreeCompareMonocaseStrings(const void *data1, unsigned short length1, 
  23.     const void *data2, unsigned short length2);
  24.  
  25. extern int 
  26. NXBTreeCompareBytes(const void *data1, unsigned short length1, 
  27.     const void *data2, unsigned short length2);
  28.  
  29. extern int 
  30. NXBTreeCompareShorts(const void *data1, unsigned short length1, 
  31.     const void *data2, unsigned short length2);
  32.  
  33. extern int 
  34. NXBTreeCompareLongs(const void *data1, unsigned short length1, 
  35.     const void *data2, unsigned short length2);
  36.  
  37. extern int 
  38. NXBTreeCompareUnsignedBytes(const void *data1, unsigned short length1, 
  39.     const void *data2, unsigned short length2);
  40.  
  41. extern int 
  42. NXBTreeCompareUnsignedShorts(const void *data1, unsigned short length1, 
  43.     const void *data2, unsigned short length2);
  44.  
  45. extern int 
  46. NXBTreeCompareUnsignedLongs(const void *data1, unsigned short length1, 
  47.     const void *data2, unsigned short length2);
  48.  
  49. @interface BTree : Object
  50. /*
  51. 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.
  52.  
  53. This class is used by the BTreeFile class to implement BTrees in files.  Other types of backing stores are also possible.  The BTreeCursor class defines objects that perform operations on BTrees.  The BTree class reports errors with NX_RAISE().
  54.  
  55. For a description of the B* tree algorithm and its properties, see \fIAlgorithms\fR by Sedgewick, or \fIThe Art of Computer Programming, Vol.  3/Sorting and Searching\fR, by Knuth.  Both sources provide additional references to the literature.
  56. */
  57. {
  58.     unsigned short        pageSize;    /* The size of 
  59.                         a backing store page */
  60.     void            *backingStore;    /* A handle to 
  61.                         the backing store */
  62.     NXBTreeComparator    *comparator;    /* The key comparator */
  63.     unsigned long        btreeDepth;    /* The number of levels 
  64.                         in the tree */
  65.     unsigned long        _syncVersion;
  66.     unsigned long        _codeVersion;
  67. }
  68.  
  69. /*
  70. METHOD TYPES
  71. Creating and freeing instances
  72. Ordering the keys
  73. Saving and undoing changes
  74. Archiving
  75. */
  76.  
  77. + new;
  78. /*
  79. TYPE: Creating and freeing instances; Returns a new BTree object 
  80.  
  81. Returns a new BTree object for an empty BTree residing in virtual memory.  To create a BTree in a file, use the BTreeFile class.
  82.  
  83. CF: + new (BTreeCursor), - createBTreeNamed: (BTreeFile)
  84. */
  85.  
  86. + _newWith: (void *) private;
  87.  
  88. - free;
  89. /*
  90. TYPE: Creating and freeing instances; Frees the BTree object 
  91.  
  92. Saves changes, frees the storage occupied by the BTree object, and reclaims any storage used to cache the BTree in the backing store.
  93. */
  94.  
  95. - (unsigned) _count;
  96.  
  97. - (void) setComparator: (NXBTreeComparator *) comparator;
  98. /*
  99. TYPE: Ordering the keys; Sets the key comparator 
  100.  
  101. Sets the comparator used to order keys in the BTree.  The type used to declare \fIcomparator\fR is defined as follows.
  102.  
  103. .nf
  104. typedef int 
  105. NXBTreeComparator(const void *data1, unsigned short length1, 
  106. .in +5
  107. const void *data2, unsigned short length2);
  108. .in -5
  109. .fi
  110.  
  111. If this method is never called, \fBNXBTreeCompareStrings()\fR is used as the default comparator.  \fBNXBTreeCompareStrings()\fR performs case sensitive comparsions between strings, with or without null termination.
  112.  
  113. This class supplies the following comparators.
  114.  
  115. .nf
  116. \fBNXBTreeCompareStrings()\fR
  117. \fBNXBTreeCompareMonocaseStrings()\fR
  118. \fBNXBTreeCompareBytes()\fR
  119. \fBNXBTreeCompareUnsignedBytes()\fR
  120. \fBNXBTreeCompareShorts()\fR
  121. \fBNXBTreeCompareUnsignedShorts()\fR
  122. \fBNXBTreeCompareLongs()\fR
  123. \fBNXBTreeCompareUnsignedLongs()\fR
  124. .fi
  125.  
  126. 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.
  127.  
  128. CF: - comparator
  129. */
  130.  
  131. - (NXBTreeComparator *) comparator;
  132. /*
  133. TYPE: Ordering the keys; Returns the key comparator 
  134.  
  135. Returns the comparator used to order keys in the BTree.  The default comparator is \fBNXBTreeCompareStrings()\fR.
  136.  
  137. CF: - setComparator:
  138. */
  139.  
  140. - cursor;
  141. /*
  142. 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.
  143.  
  144. CF: + new (BTreeCursor)
  145. */ 
  146.  
  147. - (unsigned) count;
  148. /*
  149. Returns the number of \fIkey/record\fR pairs in the BTree.  This method is much faster than enumerating and counting the \fIkey/record\fR pairs.
  150. */
  151.  
  152. - (void) empty;
  153. /*
  154. Empties the BTree.  All storage allocated to the BTree is freed, but the BTree object is not freed; the BTree is \fInot\fR removed from the backing store.  This method is much faster than enumerating and explicitly removing all of the records with BTreeCursor's \fBremove\fR method.
  155.  
  156. CF: - free, - removeBTreeNamed: (BTreeFile), - remove (BTreeCursor)
  157. */
  158.  
  159. - (void) save;
  160. /*
  161. TYPE: Saving and undoing changes; Saves changes
  162.  
  163. Saves all changes made since the last call to \fBsave\fR.  The first call to \fBsave\fR saves all changes made since the BTree was opened.
  164.  
  165. CF: - undo, - save (BTreeFile)
  166. */
  167.  
  168. - (void) undo;
  169. /*
  170. TYPE: Saving and undoing changes; Undoes changes
  171.  
  172. Undoes all changes made since the last call to \fBsave\fR.  If \fBsave\fR has not been called since the BTree was opened, then \fBundo\fR undoes all changes made since the BTree was opened, if possible.
  173.  
  174. \fBundo\fR is used internally by the BTree and BTreeCursor classes to recover from errors encountered during operations that modify the BTree structure.
  175.  
  176. CF: - save, - undo (BTreeFile)
  177. */
  178.  
  179. - read: (NXTypedStream *) stream;
  180. /*
  181. TYPE: Archiving; Reads a BTree description from a typed stream 
  182.  
  183. Empties the receiver if necessary, and then instantiates in the receiver a copy of the BTree described by \fIstream\fR.  The \fBread:\fR and \fBwrite:\fR methods should not be used as substitutes for a persistent BTree backing store like BTreeFile.
  184.  
  185. CF: - write:
  186. */
  187.  
  188. - write: (NXTypedStream *) stream;
  189. /*
  190. TYPE: Archiving; Writes a BTree description to a typed stream 
  191.  
  192. Writes a description of the BTree managed by the receiver to \fIstream\fR.  The \fBread:\fR method can use the description to instantiate a copy of the BTree.  The \fBread:\fR and \fBwrite:\fR methods should not be used as substitutes for a persistent BTree backing store like BTreeFile.
  193.  
  194. CF: - read:
  195. */
  196.  
  197.  
  198. @end
  199.  
  200.