home *** CD-ROM | disk | FTP | other *** search
/ Media Share 9 / MEDIASHARE_09.ISO / cprog / ndx303.zip / NDX303.TXT < prev    next >
Text File  |  1993-02-13  |  9KB  |  204 lines
  1.                          NDX -- BTREE INDEXING ROUTINES
  2.                                   Version 3.03
  3.       Copyright (C) 1987-89, 92-93 by George H. Mealy, all rights reserved
  4.                                         
  5.                                         
  6. INTRODUCTION
  7.  
  8.  
  9. This package implements yet another variant of the balanced tree indexing method
  10. (Btree) described in section 6.2.4 of D. E. Knuth's "Sorting and Searching",
  11. volume 3 of "The Art of Programming."  Its features are:
  12.  
  13.  
  14.       1. Files with variable length records can be indexed.  Data file format
  15.           is arbitrary, since an index is stored as a separate file.
  16.           
  17.       2. Keys are variable length ASCIZ strings.  The package allows retrieval
  18.           on heads of index keys: when retrieving on the search key "FOO",
  19.           records with keys "FOO", "FOO1", "FOOP" and "FOOPU" may be retrieved
  20.           in that order.  That is, a search key may be matched by any key of
  21.           which it is a head.  Matching can be case sensitive or case-
  22.           insensitive.  Search behavior is specified when the index is opened.
  23.           
  24.       3. ISAM access to index entries is available; it may be first-in-first-
  25.           out or last-in-last-out, as specified when the index file is created.
  26.           
  27.       4. Index file records are cached.  A single cache is used when more than
  28.           one index file is open.
  29.           
  30.       5. The source file is supplied.  The package can be compiled using Turbo
  31.           C version 1.5+ or Microsoft C version 5.0+.
  32.           
  33. This package is copyrighted material.  You may use it for non commercial
  34. purposes and make exact and complete copies for others at cost.  Modified
  35. versions of the package may not be copied without express permission.  In any
  36. case, no warranty of any kind is made or implied by the author.
  37.  
  38. INDEX FILE FORMAT
  39.  
  40. The index file begins with a short header, padded with enough bytes to fill a
  41. 512 byte disk sector.  (See NDX.H for the format of the header and other data
  42. structures.)  Nodes in the tree are 1024 bytes in length on the disk.  Each
  43. starts with a value -- that of the node if it is currently in use, or that of
  44. the next node in the chain of free nodes on the disk.  The number of bytes
  45. occupied by keys in the node follows, and then the keys.
  46.  
  47. Each Key has three fields.  First is the file offset, if not zero, of a lower
  48. level node which has keys less than or equal to the current key, followed by the
  49. offset (or record number) in the data file which corresponds to the current key.
  50. Finally, the ASCIZ key itself is stored.  Only as many bytes as are necessary
  51. are stored.
  52.  
  53. Immediately following the last key in the node, a pointer to the next lower
  54. level may be stored; the field end_keys of NODE does not include the length of
  55. this pointer.  Starting at the root node, if all pointers to lower level nodes
  56. were replaced by the content of those nodes, the result would be all keys in the
  57. index in order.
  58.  
  59. The index structure Index is allocated and initialized when the index file is
  60. opened.  It contains:
  61.  
  62. 1.  A copy of the file header
  63.  
  64. 2.  A Key structure which holds the key resulting from index file operations.
  65.  
  66. 3.  A stack holding the path from the root of the index to the current key
  67. entry.
  68.  
  69. 4.  The index file name and handle.
  70.  
  71. 5.  The string comparison function to be used during key retrieval.
  72.  
  73. USAGE
  74.  
  75. The constructor
  76.  
  77.           Index::Index(char *indexname, unsigned mode, CFN compfn)
  78.           
  79. creates an empty index file.  The comparison function, if NULL, defaults to
  80. strcmp.  The mode is one of:
  81.  
  82.           NODUPS   No duplicate keys allowed
  83.           
  84.           FIFO           Duplicate keys are retrieved first-in-first-out.
  85.           
  86.           LIFO           Duplicate keys are retrieved last-in-last out.
  87.           
  88. The mode is stored in the index file header.  A NULL second argument defaults to
  89. NODUPS.  The third argument is the routine to be used for key matching -- if
  90. NULL, strcmp is used.
  91.  
  92.  
  93.  
  94.           Index::Index(char *indexname, CFN compfn)
  95.           
  96. is used to open an existing index file, while the destructor closes an index
  97. file.  Using the type cast (CFN), string comparison functions such as strcmp,
  98. strncmp, etc. may be used.
  99.  
  100.  
  101.           DWORD Index::insert(const char *key, DWORD value);
  102.           
  103. adds a key to the index, except when the mode is NODUPS and the key is already
  104. present.  In this case, the value specified in the call replaces the previous
  105. value.  If successful, insert returns the specified DWORD and otherwise it
  106. returns zero.
  107.  
  108. The value can be a long unsigned seek address used to reference the data file,
  109. or just a serial record number when the data file has fixed length records.  A
  110. valid value may not be zero.  The comparison function used for insertion is
  111. always strcmp.
  112.  
  113.  
  114.      Index::remove(const char *key, DWORD value);
  115.  
  116. deletes the key from the index.  If this leaves an empty node, the node is
  117. placed in the freelist.  The second argument is required due to the possibility
  118. of multiple occurrences of the same key.  Returns 0 for failure and 1 for
  119. success.
  120.  
  121.  
  122.      DWORD Index::find(const char *key);
  123.  
  124. attempts to find the specified key, according to the comparison function
  125. specified when the file was opened and the mode specified when the file was
  126. created.  The value part of the key found is returned on success; zero is re
  127. turned on failure.
  128.  
  129. In order to find all occurrences of a key when FIFO or LIFO operation is in
  130. effect, use Index::find with a NULL second argument after the first occurrence
  131. has been found.
  132.  
  133.  
  134.      DWORD Index::first(unsigned last);
  135.  
  136. positions the index file pointer to the first (last) key in the index.  The
  137. "file pointer" is, strictly speaking, the top stack entry and contains the seek
  138. address of the node and the offset of the key in that node.  The remainder of
  139. the stack records information required for traveling over the index tree
  140. starting from the file pointer, as if the index were flat rather than a tree.
  141. Zero is returned if the index is empty, else the value part of the key located
  142. is returned.
  143.  
  144.  
  145.      DWORD Index::next();
  146.      DWORD Index::prev();
  147.  
  148. These routines change the file pointer to the next or previous key and return
  149. the value part of that key, or zero if the current file pointer was at the end
  150. or beginning of the index.
  151.  
  152. Note that Index::find, Index::insert and Index::remove position the file
  153. pointer.  In the latter case, the file pointer is set to the key following the
  154. deleted key.  Note further that each successful key retrieval stores a copy of
  155. the current key structure in the index structure.  This key structure may be
  156. accessed  using
  157.  
  158.      const Key Index::key();
  159.  
  160. For examples of the use of the routines, see the test program.
  161.  
  162.  
  163. IMPROVEMENTS
  164.  
  165. Knuth suggests ways in which the Btree algorithms may be improved.  If you
  166. decide to experiment, be prepared for an interesting [sic] experience.  Be
  167. particularly wary of any changes you attempt to make in Index::remove --
  168. updating the index to properly reflect a deletion is an extremely tricky affair.
  169. Even xnext and xprev, which look deceptively simple, are easy to upset if you
  170. try to change the order in which things are done.
  171.  
  172.  
  173. CHANGES
  174.  
  175. My address is:
  176.  
  177.           George H. Mealy
  178.           38 Gilson Road
  179.           Scituate, MA 02066
  180.          USA
  181.  
  182.          (617) 545-1727
  183.  
  184. Version 2.02 corrected an egregious blunder in the Index::insert routine --
  185. thanks to John A. Matzen.  I also fixed a bug in Index::find, thanks to strong
  186. type checking and use of the typedef CFN.
  187.  
  188. The package has been recompiled using Borland C++ v3.1.  Version 3.01 corrects
  189. another bug in Index::insert.  NDX.H has been changed to make a few more items
  190. accessible to user programs.    The routine Index::key is supplied to allow safe
  191. access to the current key.
  192.  
  193. All previous versions contained a serious bug in Index::newnode.  Since the
  194. order in which nodes are first written out to the index file is unpredictable,
  195. it is vital that chsize() is called when the length of the file is extended!
  196. Version 3.02 includes this fix together with a few minor cosmetic changes.
  197.  
  198. Prior to version 3.03, the state of the index following a call to Index::remove
  199. was unpredictable.  The index file position is now defined to be at the key
  200. which immediately followed the removed key.  In addition, the index key count is
  201. stored in the index and can be verified by use of the routine Index::isvalid.
  202. Index::count may be used to retrieve the index key count.
  203.  
  204.