home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 2 BBS / 02-BBS.zip / msq31004.zip / mxbt.c < prev    next >
C/C++ Source or Header  |  1995-07-20  |  7KB  |  256 lines
  1. /* mxbt - btree functions that operate on an index file compatible
  2.    with that used by Mix Database Toolchest (or something like that). */
  3.    
  4. /* Written by Paul Edwards and released to the public domain */
  5.  
  6. /* The btree index file is comprised of three different record types,
  7.    stored as a fixed length (e.g. 512 bytes), even though the record
  8.    types may not require that full length.
  9.  
  10.    1. A control record.  This is the first record in the file, and
  11.    contains important information such as the fixed length that all
  12.    the other records are.
  13.    
  14.    2. Leaf nodes.  These are identified by having "-1" in the first
  15.    field (a "long").  Every search key will be found in one of these
  16.    records.  The leaf nodes appear after the control record.
  17.    
  18.    3. Index nodes.  These are identified by not having "-1" in the
  19.    first field.  Some, but not all, of the keys will be found in
  20.    one of these fields.  The index nodes appear after the last leaf
  21.    node.
  22.    
  23.    Note that if you wish to update records in this index file, you
  24.    should update the leaf nodes before the index nodes.
  25.  
  26.    The objective of all this is to find a matching key, which will
  27.    then have a corresponding "long" value.  This long value can
  28.    then be used as an offset into an appropriate data file.
  29.  
  30.    The basic structure of the index records goes like this.  Each
  31.    index record has several keys stored in it.  If your key is
  32.    lower than the first key, then the recType field doubles up as
  33.    the *record number* of the left branch.  Multiply that by the
  34.    record size and you have your offset.  Otherwise, go through
  35.    the index entries until you find the an entry with a key greater
  36.    than yours, or you reach the end.  The previous entry to that
  37.    one will have the left node for you to follow, in the "lower"
  38.    variable.  Again, this is a record number.  The idea is that
  39.    you keep following the appropriate left branch until you hit
  40.    a leaf node, then you do a sequential search.  Crikey, if 
  41.    you're a real loser you could even do a binary search of the
  42.    leaf node.
  43.       
  44. */
  45.  
  46. /* The algorithm we employ is:
  47.  
  48.    1. fetch the control record
  49.    
  50.    2. Search the index nodes for our key until we reach a leaf
  51.       node.
  52.       
  53.    3. Search the leaf node for our key. */
  54.  
  55. #include <stdio.h>
  56.  
  57. #include "mxbt.h"
  58.  
  59. static void mxbtInit(MXBT *mxbt);
  60. static void mxbtOpen(MXBT *mxbt, char *indexFile);
  61. static void mxbtClose(MXBT *mxbt);
  62. static void mxbtFetchControl(MXBT *mxbt);
  63. static void mxbtSetKey(MXBT *mxbt, void *searchKey);
  64. static void mxbtSetCompare(MXBT *mxbt, 
  65.             int (*compare)(void *testKey, void *searchKey, int len));
  66. static void mxbtReadRec(MXBT *mxbt);
  67. static void mxbtFindLeaf(MXBT *mxbt);
  68. static void mxbtSearchLeaf(MXBT *mxbt);
  69.  
  70. long mxbtOneSearch(MXBT *mxbt, 
  71.                    char *indexFile, 
  72.                    void *searchKey,
  73.                    int (*compare)(void *testKey, void *searchKey, int len))
  74. {
  75.     mxbt->error = 0;
  76.     mxbtInit(mxbt);
  77.     if (!mxbt->error)
  78.     {
  79.         mxbtOpen(mxbt, indexFile);
  80.         if (!mxbt->error)
  81.         {
  82.             mxbtFetchControl(mxbt);
  83.             if (!mxbt->error)
  84.             {
  85.                 mxbtSetKey(mxbt, searchKey);
  86.                 mxbtSetCompare(mxbt, compare);
  87.                 mxbtFindLeaf(mxbt);
  88.                 if (!mxbt->error)
  89.                 {
  90.                     mxbtSearchLeaf(mxbt);
  91.                 }
  92.             }
  93.             mxbtClose(mxbt);
  94.         }
  95.     }
  96.     if (mxbt->error)
  97.     {
  98.         return (-1L);
  99.     }     
  100.     else
  101.     {
  102.         return (mxbt->value);
  103.     }
  104. }
  105.  
  106. static void mxbtInit(MXBT *mxbt)
  107. {
  108.     mxbt->buf = mxbt->myunion.intbuf;
  109.     mxbt->index = (struct mxbt_indexrec *)mxbt->buf;
  110.     mxbt->leaf = (struct mxbt_leafrec *)mxbt->buf;
  111.     return;
  112. }
  113.  
  114. static void mxbtOpen(MXBT *mxbt, char *indexFile)
  115. {
  116.     mxbt->fp = fopen(indexFile, "rb");
  117.     if (mxbt->fp == NULL)
  118.     {
  119.         mxbt->error = 1;
  120.     }
  121.     return;
  122. }
  123.  
  124. static void mxbtClose(MXBT *mxbt)
  125. {
  126.     if (fclose(mxbt->fp) != 0)
  127.     {
  128.         mxbt->error = 1;
  129.     }
  130.     return;
  131. }
  132.  
  133. static void mxbtFetchControl(MXBT *mxbt)
  134. {
  135.     if (fread(&mxbt->recSize, sizeof(unsigned short), 1, mxbt->fp) != 1)
  136.     {
  137.         mxbt->error = 1;
  138.     }
  139.     else if (fread(&mxbt->control, sizeof mxbt->control, 1, mxbt->fp) != 1)
  140.     {
  141.         mxbt->error = 1;
  142.     }
  143.     return;
  144. }
  145.  
  146. static void mxbtSetKey(MXBT *mxbt, void *searchKey)
  147. {
  148.     mxbt->searchK = searchKey;
  149.     return;
  150. }
  151.  
  152. static void mxbtSetCompare(MXBT *mxbt, 
  153.             int (*compare)(void *testKey, void *searchKey, int len))
  154. {
  155.     mxbt->compareF = compare;
  156.     return;
  157. }
  158.  
  159. static void mxbtReadRec(MXBT *mxbt)
  160. {
  161.     size_t x;
  162.     int y;
  163.     
  164.     y = fseek(mxbt->fp, mxbt->recordNum * mxbt->recSize, SEEK_SET);
  165.     if (y != 0)
  166.     {
  167.         mxbt->error = 1;
  168.     }
  169.     else
  170.     {
  171.         x = fread(mxbt->buf, mxbt->recSize, 1, mxbt->fp);
  172.         if (x != 1)
  173.         {
  174.             mxbt->error = 1;
  175.         }
  176.     }
  177.     return;
  178. }
  179.  
  180. static void mxbtFindLeaf(MXBT *mxbt)
  181. {
  182.     int cnt;
  183.     int x;
  184.     
  185.     mxbt->recordNum = mxbt->control.indexStart;
  186.     mxbtReadRec(mxbt);
  187.     while (!mxbt->error && (mxbt->index->recType != -1))
  188.     {
  189.         cnt = mxbt->index->keyCount;
  190.         if (cnt < 0)
  191.         {
  192.             mxbt->error = 1;
  193.         }
  194.         else
  195.         {
  196.             for (x = 0; x < cnt; x++)
  197.             {
  198.                 if (mxbt->compareF((char *)mxbt->index 
  199.                                    + mxbt->index->keys[x].offset,
  200.                                    mxbt->searchK,
  201.                                    mxbt->index->keys[x].len) > 0)
  202.                 {
  203.                     break;
  204.                 }
  205.             }
  206.             if (x == 0)
  207.             {
  208.                 mxbt->recordNum = mxbt->index->recType;
  209.             }
  210.             else
  211.             {
  212.                 mxbt->recordNum = mxbt->index->keys[x-1].lower;
  213.             }
  214.             mxbtReadRec(mxbt);
  215.         }
  216.     }
  217.     return;
  218. }
  219.  
  220. static void mxbtSearchLeaf(MXBT *mxbt)
  221. {
  222.     int cnt;
  223.     int x;
  224.     int ret;
  225.     
  226.     cnt = mxbt->leaf->keyCount;
  227.     if (cnt == 0)
  228.     {
  229.         mxbt->error = 1;
  230.     }
  231.     else
  232.     {
  233.         for (x = 0; x < cnt; x++)
  234.         {
  235.             ret = mxbt->compareF((char *)mxbt->leaf 
  236.                                  + mxbt->leaf->keys[x].offset,
  237.                                  mxbt->searchK,
  238.                                  mxbt->leaf->keys[x].len);
  239.             if (ret > 0)
  240.             {
  241.                 mxbt->error = 1;
  242.                 break;
  243.             }
  244.             else if (ret == 0)
  245.             {
  246.                 mxbt->value = mxbt->leaf->keys[x].value;
  247.                 break;
  248.             }
  249.         }
  250.     }
  251.     if (cnt == x && ret == -1)    /* seems to fix problem with unknown system */
  252.         mxbt->error = 1;
  253.     return;
  254. }
  255.  
  256.