home *** CD-ROM | disk | FTP | other *** search
/ Boston 2 / boston-2.iso / DOS / PROGRAM / C / BPLUS / BPLUS.DOC < prev    next >
Text File  |  1993-12-01  |  25KB  |  640 lines
  1. \033(s10H
  2.  
  3.  
  4.  
  5.  
  6.  
  7.                                THE B-PLUS PROGRAM
  8.                          A B-TREE INDEXING FILE MODULE
  9.                                FOR C PROGRAMMERS
  10.                                        by
  11.                              Hunter and Associates
  12.  
  13.  
  14.  
  15.               B-PLUS is a versatile, carefully designed module for C
  16.          programmers who need a fast, efficient program for indexing
  17.          data files.  B-PLUS allows data records to be retrieved based
  18.          on a key value without regard to their position in the data
  19.          file.  The data records can also be accessed in sequential
  20.          order in either a forward and reverse direction.
  21.  
  22.               The B-PLUS Program Module is based on the famous and
  23.          widely used b-tree algorithm and has a number of useful
  24.          extensions which are not found in many programs of this type.
  25.          Some of its features are the following:
  26.  
  27.               - Variable length keys are allowed
  28.  
  29.               - File size limited only by DOS or by disk space
  30.  
  31.               - All functions are non-recursive so very little stack
  32.                 space is required
  33.  
  34.               - The most recently used key values are stored in a
  35.                 cache buffer in main memory for fast access
  36.  
  37.               - Duplicate keys are allowed
  38.  
  39.               The B-PLUS program has been tested using the Microsoft C
  40.          Compilers, Versions 4.0, 4.5 (OS2 Beta release), 5.0 and the
  41.          Borland Turbo C Compiler Version 1.0.  The compiled object
  42.          file is less than 9.4K bytes in length for these compilers.
  43.          See the instructions at the end of this user's guide for a
  44.          special note regarding Microsoft C Version 5.0 and Quick C.
  45.  
  46.               Version 1.1 has several new features that were not in
  47.          Version 1.0.  The next_key and prev_key routines can now be
  48.          called immediately after adding or deleting an index key.  It
  49.          is no longer necessary to "reset" the index file with a
  50.          find_key or locate_key function call after adding or deleting
  51.          keys.  Several minor bugs that were discovered in Version 1.0
  52.          have been corrected in Version 1.1.
  53.  
  54.  
  55.          LICENSE AND REGISTRATION
  56.  
  57.               B-PLUS is distributed as a "share ware" program.  Please
  58.          help us get it known by giving unmodified copies of the
  59.  
  60.  
  61.          HUNTER AND ASSOCIATES            B-PLUS FILE INDEXING PROGRAM
  62.          -------------------------------------------------------------
  63.  
  64.  
  65.          program and documentation to other programmers who may find
  66.          B-PLUS useful.
  67.  
  68.               B-PLUS is copyright (C) 1987 by Hunter and Associates.
  69.          It is not public domain or free software.  Non-registered
  70.          users are granted a limited license to use B-PLUS on a trial
  71.          basis for determining whether or not it is suitable for their
  72.          needs.  Registration permits the use of B-PLUS on one CPU and
  73.          allows the use of the compiled B-PLUS modules in programs for
  74.          general sale and/or distribution.
  75.  
  76.               The registration fee is $25 or $35.  Users who pay the
  77.          $35 fee will be sent a disk containing a fully commented
  78.          listing of the latest source code, the user documentation,
  79.          and a number of useful sample programs.  Users who pay the
  80.          $25 fee are not sent a new disk but are included in the
  81.          mailing list for announcements about both current and future
  82.          products.  Your prompt registration of your copy of the B-
  83.          PLUS program is appreciated.
  84.  
  85.               A trial disk with supporting documentation is available
  86.          directly from Hunter and Associates for $10.
  87.  
  88.               Register your usage of B-PLUS by sending the registra-
  89.          tion fee to:
  90.  
  91.                         Hunter and Associates
  92.                         7050 NW Zinfandel Lane
  93.                         Corvallis, OR  97330
  94.                         Telephone: (503) 745-7186
  95.  
  96.          Your comments regarding the B-PLUS program or any suggestions
  97.          you have for extensions or for other programs that would be
  98.          useful to you are welcomed.
  99.  
  100.               Hunter and Associates makes no warranties whatsoever
  101.          regarding the B-PLUS computer programs or the supporting
  102.          documentation.
  103.  
  104.  
  105.          USING B-PLUS IN YOUR PROGRAMS
  106.  
  107.               The B-PLUS File Indexing Module contains twelve
  108.          functions that handle the retrieval of data records by key
  109.          value.  The keys that are used to locate records are null
  110.          terminated strings.  The data structures and constants that
  111.          are used are defined in the header file bplus.h.
  112.  
  113.               If the data record field that you want to use as a key
  114.          contains numeric data, you can use one of the library
  115.  
  116.                                    Page 2
  117.  
  118.  
  119.          HUNTER AND ASSOCIATES            B-PLUS FILE INDEXING PROGRAM
  120.          -------------------------------------------------------------
  121.  
  122.  
  123.          conversion routines (fcvt, evct, sprintf) to convert the data
  124.          to string format.
  125.  
  126.               The connection between a key and its reference is
  127.          formalized as a structure of type ENTRY.  This structure
  128.          contains three elements:
  129.  
  130.          typedef struct
  131.            {
  132.              RECPOS   idxptr;         /* long pointer to next index
  133.                                          level                      */
  134.              RECPOS   recptr;         /* long pointer to the file
  135.                                          position of data record    */
  136.              char     key[MAXKEY];    /* with this key value        */
  137.            } ENTRY;
  138.  
  139.               The application program uses only the recptr and key[]
  140.          fields.  The idxptr is used and maintained by the B-PLUS
  141.          modules.
  142.  
  143.               A variable of type IX_DESC is declared for each open
  144.          index file.  See the header file bplus.h if you are
  145.          interested in the elements of this structure.  ENTRY and
  146.          IX_DESC are the only two data types that are normally used by
  147.          application programs.
  148.  
  149.               Here is a sample program stub which calls the open_index
  150.          and find_index subroutines.
  151.  
  152.  
  153.          Example:
  154.  
  155.            #include "bplus.h"
  156.            main()
  157.              {
  158.                 ENTRY    e;
  159.                 IX_DESC  names;
  160.  
  161.                 /* open index file called NAMES.IDX */
  162.  
  163.                 open_index("NAMES.IDX", &names, 0);
  164.  
  165.                 /* find an index record for John Smith */
  166.  
  167.                 strcpy(e.key, "SMITH JOHN");
  168.                 if(find_key(&e, &names))
  169.                   printf("Data record address is %ld", e.recptr);
  170.                 else
  171.                   printf("Cannot find record for that key");
  172.               }
  173.  
  174.                                    Page 3
  175.  
  176.  
  177.          HUNTER AND ASSOCIATES            B-PLUS FILE INDEXING PROGRAM
  178.          -------------------------------------------------------------
  179.  
  180.  
  181.          Each of the twelve subroutines is now described.
  182.  
  183.          int cdecl open_index(name, pix, dup);
  184.  
  185.               char *name;         File path name
  186.               IX_DESC *pix;       Pointer to index file variable
  187.               int dup;            0 - no duplicate keys allowed
  188.                                   1 - allow duplicate keys
  189.  
  190.               Description:  The open_index function is used to open
  191.               and initialize an existing index file specified by name
  192.               and prepares the file for subsequent reading or writing.
  193.               The file structure variable pix is defined in the
  194.               application program.  Duplicate keys are allowed or not
  195.               allowed depending on whether dup has the value of 0 or
  196.               1.  The open_index function returns the value IX_OK (1)
  197.               if the file is opened successfully.  If the file cannot
  198.               be opened, an error message is displayed and the program
  199.               is aborted.
  200.  
  201.  
  202.  
  203.          int cdecl make_index(name, pix, dup);
  204.  
  205.               char *name;         File path name
  206.               IX_DESC *pix;       Pointer to index file variable
  207.               int dup;            0 - no duplicate keys allowed
  208.                                   1 - allow duplicate keys
  209.  
  210.               Description:  The make_index function is used to create
  211.               and initialize a new index file specified by name and to
  212.               prepare the file for subsequent reading or writing.  If
  213.               a file of this name already exists, its contents are
  214.               destroyed when the new file is created.  The file
  215.               structure variable pix is defined in the application
  216.               program.  Duplicate keys are allowed or not allowed
  217.               depending on whether dup has the value of 0 or 1.  The
  218.               make_index function returns the value IX_OK (1) if the
  219.               file is created successfully.  If the file cannot be
  220.               created, an error message is displayed and the program
  221.               is aborted.
  222.  
  223.  
  224.  
  225.          int cdecl close_index(pix);
  226.  
  227.               IX_DESC *pix;       Pointer to index file variable
  228.  
  229.               Description:  The close_index file function clears the
  230.               internal cache buffer and closes the specified index
  231.  
  232.                                    Page 4
  233.  
  234.  
  235.          HUNTER AND ASSOCIATES            B-PLUS FILE INDEXING PROGRAM
  236.          -------------------------------------------------------------
  237.  
  238.  
  239.               file.  It is very important that each index file be
  240.               closed.  Otherwise data that is stored in the internal
  241.  
  242.               cache buffer may be lost and the index file may not be
  243.               properly updated.  The close_index function returns the
  244.               value IX_OK (1) if the file is successfully closed.
  245.  
  246.  
  247.  
  248.          int cdecl find_key(pe, pix);
  249.  
  250.               ENTRY *pe;          Pointer to variable of type ENTRY
  251.               IX_DESC *pix;       Pointer to index file variable
  252.  
  253.               Description:  The find_key function searches the index
  254.               file for the key value contained in pe.key.  If an exact
  255.               match is found, the value IX_OK (1) is returned and the
  256.               location of the data record with this key value is
  257.               stored in pe.recptr.  If an exact match is not found,
  258.               the value IX_FAIL (0) is returned and pe.recptr is
  259.               undefined.  If the index file contains duplicate keys,
  260.               the first key is always found.
  261.  
  262.  
  263.  
  264.          int cdecl locate_key(pe, pix);
  265.  
  266.               ENTRY *pe;          Pointer to variable of type ENTRY
  267.               IX_DESC *pix;       Pointer to index file variable
  268.  
  269.               Description:  The locate key function searches the index
  270.               file for the first key value which is equal to or
  271.               greater than that stored in pe.key.  The location of the
  272.               data record which is equal to or greater than pe.key is
  273.               stored in pe.recptr.  This function can be used to
  274.               locate an entry in the index file when only part of the
  275.               key value is known.  If the index file contains
  276.               duplicate keys, locate_key will locate the first key.
  277.               The following values are returned by locate_key:
  278.  
  279.                    IX_OK  -  the value (1) is returned if an exact
  280.                              match is found
  281.  
  282.                    IX_FAIL - the value (0) is returned if an exact
  283.                              match is not found
  284.  
  285.                    EOIX  -   the value (-2) is returned for end of
  286.                              index if the search key is greater than
  287.                              all keys in the index file and pe.recptr
  288.                              is undefined.
  289.  
  290.                                    Page 5
  291.  
  292.  
  293.          HUNTER AND ASSOCIATES            B-PLUS FILE INDEXING PROGRAM
  294.          -------------------------------------------------------------
  295.  
  296.  
  297.  
  298.  
  299.          int cdecl add_key(pe, pix);
  300.  
  301.               ENTRY *pe;          Pointer to variable of type ENTRY
  302.               IX_DESC *pix;       Pointer to index file variable
  303.  
  304.               Description:  The add_key function adds new entries to
  305.               the index file.  The calling program stores the key
  306.               value in pe.key and the data record address in
  307.               pe.recptr.  Add_key first looks to see if an entry with
  308.               this key already exists in the index file.  If no entry
  309.               with this key exists, the new entry is added.  If an
  310.               entry with this key already exists, the new entry is
  311.               added only if duplicate keys are allowed (as defined by
  312.               the open_index function).  If the entry is successfully
  313.               added, IX_OK (1) is returned; otherwise IX_FAIL (0) is
  314.               returned.
  315.  
  316.  
  317.  
  318.          int cdecl delete_key(pe, pix);
  319.  
  320.               ENTRY *pe;          Pointer to variable of type ENTRY
  321.               IX_DESC *pix;       Pointer to index file variable
  322.  
  323.               Description:  The delete_key function deletes entries
  324.               in the index file.  The key to be deleted is stored in
  325.               pe.key.  If duplicate records are allowed, the
  326.               corresponding data record address must also be stored in
  327.               pe.recptr.  In this case, delete key needs the record
  328.               number to distinguish entries.  If there are not
  329.               duplicate entries, this field is ignored.  If the entry
  330.               is successfully deleted, IX_OK (1) is returned;
  331.               otherwise IX_FAIL (0) is returned.  The space that was
  332.               occupied by the entry is marked as free for reused by
  333.               B_PLUS.
  334.  
  335.  
  336.  
  337.          int cdecl first_key(pix);
  338.  
  339.               IX_DESC *pix;       Pointer to index file variable
  340.  
  341.               Description:  The first_key function positions the index
  342.               file pointer to the beginning of the index file.  The
  343.               function next_key can then be used to list the file in
  344.               key order.  The first_key function returns the value
  345.               IX_OK (1).
  346.  
  347.  
  348.                                    Page 6
  349.  
  350.  
  351.          HUNTER AND ASSOCIATES            B-PLUS FILE INDEXING PROGRAM
  352.          -------------------------------------------------------------
  353.  
  354.  
  355.          int cdecl last_key(pix);
  356.  
  357.               IX_DESC *pix;       Pointer to index file variable
  358.  
  359.               Description:  The last_key function positions the index
  360.               file pointer at the end of the index file.  The function
  361.               previous_key can then be used to list the file in
  362.               reverse key order.  The last_key function returns the
  363.               value IX_OK (1).
  364.  
  365.  
  366.  
  367.          int cdecl next_key(pe, pix);
  368.  
  369.               ENTRY *pe;          Pointer to variable of type ENTRY
  370.               IX_DESC *pix;       Pointer to index file variable
  371.  
  372.               Description:  The next_key function returns the next
  373.               entry in the index file.  After deleting or adding keys,
  374.               next_key returns the key immediately following the
  375.               addition or deletion.  Next_key can be used to locate
  376.               the desired data record when duplicate keys are allowed.
  377.               Next_key is used to process files sequential.  Next_key
  378.               returns the value IX_OK (1) if the next key is present
  379.               and the value EOIX (-2) when the file pointer is at the
  380.               end of the index file.  The following program processes
  381.               an indexed file sequentially:
  382.  
  383.               #include "bplus.h"
  384.               main()
  385.                 {
  386.                   ENTRY e;
  387.                   IX_DESC names;
  388.  
  389.                   /* open the index file */
  390.                   open_index("names.idx", &names);
  391.  
  392.                   /* now process the file sequentially */
  393.                   first_key(&names);
  394.                   ret = next_key(&e, &names);
  395.                   while (ret == IX_OK)
  396.                     {
  397.                       /* the data record location is e.recptr */
  398.                       /* the program would retrieve and process it */
  399.                       ret = next_key(&e, &names);
  400.                     }
  401.  
  402.                   /* remember to always close open files */
  403.                   close_index(&names);
  404.                 }
  405.  
  406.                                    Page 7
  407.  
  408.  
  409.          HUNTER AND ASSOCIATES            B-PLUS FILE INDEXING PROGRAM
  410.          -------------------------------------------------------------
  411.  
  412.  
  413.          int cdecl prev_key(pe, pix);
  414.  
  415.               ENTRY *pe;          Pointer to variable of type ENTRY
  416.               IX_DESC *pix;       Pointer to index file variable
  417.  
  418.               Description:  The prev_key function returns the previous
  419.               entry in the index file.  After deleting or adding keys,
  420.               prev_key returns the key immediately preceeding the
  421.               addition or deletion.  Prev_key can be used to process
  422.               files sequentially in reverse order. Prev_key returns
  423.               the value IX_OK (1) if there is a previous key and the
  424.               value EOIX (-2) when the file pointer is at the
  425.               beginning of the index file.
  426.  
  427.  
  428.  
  429.          int cdecl find_exact(pe, pix);
  430.  
  431.               ENTRY *pe;          Pointer to variable of type ENTRY
  432.               IX_DESC *pix;       Pointer to index file variable
  433.  
  434.               Description:  The find_exact function searches the index
  435.               file for the key value contained in pe.key and the data
  436.               record position stored in pe.recptr.  If an exact match
  437.               is found for both of these values, the value IX_OK (1)
  438.               is returned, and the internal index file pointer is set
  439.               to that position in the index file.  If an exact match
  440.               is not found, the value IX_FAIL (0) is returned.
  441.  
  442.  
  443.  
  444.          TAILORING OR CHANGING B-PLUS
  445.  
  446.               Most applications can use the B-PLUS program as it is
  447.          distributed by Hunter and Associates without any changes.  It
  448.          allows multiple, large data files to be indexed in a fast,
  449.          efficient manner.  However, a description of the values that
  450.          can be changed to tailor B-PLUS are given in this section.
  451.  
  452.               An index tree becomes full when no more entries can be
  453.          added to the tree.  This is the case when adding another
  454.          entry to the tree would cause the tree to grow larger than
  455.          its maximum allowed height.  This height depends on the size
  456.          of the index blocks and the average size of the keys used by
  457.          the data files.  The minimum capacity of a b-tree index is
  458.          given by the following formula:
  459.  
  460.               C = (B / E + 1) * (B / (2 * E)  + 1) ** (H - 1)
  461.  
  462.          where C is the number of entries in the index file, B is the
  463.  
  464.                                    Page 8
  465.  
  466.  
  467.          HUNTER AND ASSOCIATES            B-PLUS FILE INDEXING PROGRAM
  468.          -------------------------------------------------------------
  469.  
  470.  
  471.          block size in bytes, E is the average size of an ENTRY in
  472.          bytes, and H is the maximum tree height.
  473.  
  474.               The maximum key size is defined by MAXKEY and is set at
  475.          100.  The block size is 1024 bytes as defined by IXB_SIZE.
  476.          Ten bytes are used by pointers so 1014 bytes are used by
  477.          entries.  The size of an ENTRY is 9 + the key length.
  478.  
  479.               Thus, if the average key length is 11, an average ENTRY
  480.          is 20 bytes long and the minimum number of entries that can
  481.          be contained in a tree of height 4 is:
  482.  
  483.               C = (1014 / 20 + 1) * (1014 / 40 + 1) ** 3
  484.                 = 945,072
  485.  
  486.          If the average ENTRY is 40 bytes long, the minimum number of
  487.          entries that can be contained in a tree of height 4 is
  488.          67,384.  The corresponding values for a tree of height 3 are
  489.          35,896 and 4927, respectively.
  490.  
  491.               The maximum tree height is determined by MAX_LEVELS and
  492.          is set to eight.  Very little memory space is used by
  493.          allowing the maximum tree height to be this large.  B-PLUS
  494.          increases the height of the tree dynamically as required by
  495.          number of records in the data file.
  496.  
  497.               If your application does not use long keys and your
  498.          files are not huge, IXB_SIZE can be changed to 512 bytes with
  499.          only a slight degradation in performance.
  500.  
  501.               The root of an open index file is always memory resident
  502.          as defined by the variable of type IX_DESC.  A dynamic pool
  503.          of cache buffers is used for other index blocks of the tree.
  504.          The number of blocks in the pool is defined by NUM_BUFS with
  505.          a default value of 8.  Each memory block is sizeof(IXB_SIZE)
  506.          + 8 bytes in length so approximately 8K of memory is used for
  507.          cache storage of index blocks.  If the number of index files
  508.          that are open simultaneously is larger than 4, you may want
  509.          to increase NUM_BUFS.  If the usage of memory is critical,
  510.          the number of buffers can be decreased.  However, NUM_BUFS
  511.          must be at least 2.  In general, the speed of file access can
  512.          be expected to improve if the number of buffers is increased
  513.          since more of the index file is memory resident.
  514.  
  515.               Because some indices are always memory resident, and
  516.          because the DOS Operating System requires it, it is very
  517.          important that all open index files be closed before an
  518.          application program terminates.
  519.  
  520.               As stated earlier, the B-PLUS program has been tested
  521.  
  522.                                    Page 9
  523.  
  524.  
  525.          HUNTER AND ASSOCIATES            B-PLUS FILE INDEXING PROGRAM
  526.          -------------------------------------------------------------
  527.  
  528.  
  529.          using Microsoft's Optimizing C Compilers, Versions 4, 4.5 and
  530.          5.0, and Borland's Turbo C, Version 1.0.  However, standard K
  531.          & R programming guidelines are followed so B-PLUS should be
  532.          able to be used with other C Compilers with little
  533.          modification.  Since B-PLUS is non-recursive, the usage of
  534.          stack space does not change dynamically.  It is recommend
  535.          that the B-PLUS program be complied without stack checking.
  536.          For Microsoft C, the /Ox option can be used to maximize speed
  537.          and minimize code size.  For Turbo C, B-PLUS can be complied
  538.          with maximum optimization to minimize the object size and
  539.          improve performance.
  540.  
  541.  
  542.          ACKNOWLEDGMENTS AND REFERENCES
  543.  
  544.               The following reference materials were used and helpful
  545.          in writing the B-PLUS program:
  546.  
  547.               Wirth, Niklaus:
  548.                      Algorithms + Data Structures = Programs
  549.                      Prentice Hall (1976)
  550.  
  551.               Hunt, William James:
  552.                      The C Toolbox
  553.                      (Serious C Programming for the IBM PC)
  554.                      Addison-Wesley (1985)
  555.  
  556.  
  557.               Wirth's book is a standard reference source for binary
  558.          trees and data structures.  Hunt's C Toolbox contains useful
  559.          C programming concepts with carefully constructed programming
  560.          examples.
  561.  
  562.  
  563.          USING THE BPLUS ROUTINES
  564.  
  565.               The BPLUS.C routines must be compiled and the object
  566.          file (BPLUS.OBJ) loaded with programs that use the B_PLUS
  567.          toolkit.  Several sample C programs have been included which
  568.          illustrate how to use the BPLUS Toolkit.  These programs
  569.          should be compiled and run to make sure your copy of the
  570.          program is correct.
  571.  
  572.  
  573.          A SPECIAL NOTE REGARDING MICROSOFT C COMPILERS
  574.  
  575.               The Microsoft C library routines are different for
  576.          Version 4.0 and for Version 5.0 and Quick C.  In particular,
  577.          the memcpy routine in Version 5.0 does not check that
  578.          overlapping bytes are copied correctly.  Consequently, the
  579.  
  580.                                   Page 10
  581.  
  582.  
  583.          HUNTER AND ASSOCIATES            B-PLUS FILE INDEXING PROGRAM
  584.          -------------------------------------------------------------
  585.  
  586.  
  587.          memmove routine must be used for Version 5.0 and for Quick C.
  588.          A macro is included in BLUS.C which makes this substitution.
  589.          This macro MUST be used (remove the comment delimiters) for
  590.          these versions of the Microsoft compilers.
  591.  
  592.  
  593.  
  594.  
  595.  
  596.  
  597.  
  598.  
  599.  
  600.  
  601.  
  602.  
  603.  
  604.  
  605.  
  606.  
  607.  
  608.  
  609.  
  610.  
  611.  
  612.  
  613.  
  614.  
  615.  
  616.  
  617.  
  618.  
  619.  
  620.  
  621.  
  622.  
  623.  
  624.  
  625.  
  626.  
  627.  
  628.  
  629.  
  630.  
  631.  
  632.  
  633.  
  634.  
  635.  
  636.  
  637.  
  638.                                   Page 11
  639. \032
  640.