home *** CD-ROM | disk | FTP | other *** search
/ Il CD di internet / CD.iso / SOURCE / CONTRIB / MBASE / MBASE51.TAR / mbase51 / tech / chapter.7 < prev    next >
Encoding:
Text File  |  1993-09-04  |  5.5 KB  |  123 lines
  1. Tech Chapter 7 - Multi-length fields                              MetalBase 5.1
  2. -------------------------------------------------------------------------------
  3.  
  4.  
  5. MetalBase 5.1 is the first release to support multi-length fields.  The primary
  6.    reason for delaying the introduction of such a useful ability is that it was
  7.    difficult to convince myself that there is no better way to work with field
  8.    data than in temporary files.  Hell, I may still be wrong; but it's in
  9.    now.
  10.  
  11.  
  12. /*
  13.  * THE GENERAL IDEA -----------------------------------------------------------
  14.  *
  15.  */
  16.  
  17. If you've read the chapter on relation format, you know that the inside of the
  18.    .REL files is very structured; there's a header followed by any number of
  19.    records, each exactly the same length.  So there's the first real problem--
  20.    if the fields in a relation don't take the same amount of space, then the
  21.    records won't be the same length.  Bad.
  22.  
  23. That's solved by moving the actual field data off to a separate file; MB uses
  24.    a .DAT extension for these.  The .DAT file is created by mb_create() if
  25.    the design contains multi-length fields, and isn't created otherwise.
  26.    Inside the .REL, each record has an eight-byte structure wherever a multi-
  27.    length field should be... there are two pieces of information stored in
  28.    that eight-byte block:
  29.  
  30.          dataptr  pos.....pointer to field data within .DAT file
  31.          char    *name....file name for data transfer
  32.  
  33. While it's stored, the only relevant information in the .REL for multi-length
  34.    fields is the 'pos' field.  The other one is used because the same 8-byte
  35.    structure is returned to the user, and has to contain everything needed to
  36.    keep track of multi-length fields.  The 'name' field is maintained as a
  37.    character pointer so we won't have a 32- or 64-byte array of wasted space
  38.    in the .REL files.. instead, MB will malloc() space for the names when it
  39.    needs 'em.
  40.  
  41. So before you can look up data, you pass a record (or part of it) to recInit(),
  42.    to assign temporary files to each multi-length field.  Those files are then
  43.    actually created, so later on you'll have to use a cleanup function,
  44.    recFree(), to delete them, or you'll have billions of temp files lying
  45.    around everywhere.
  46.  
  47. Then, when you retrieve a record, the data is copied into the temporary file
  48.    that was chosen for it.  If you instead add or update records, data is read
  49.    from those temporary files and stored in a convenient place in the .DAT
  50.    file.
  51.  
  52.  
  53. /*
  54.  * THREADED-HEAP FORMAT, FREE SPACE -------------------------------------------
  55.  *
  56.  */
  57.  
  58. The problem is finding that "convenient place".  In order to ensure the fastest
  59.    access to chunks of free space, MetalBase only maintains a single chain
  60.    through the heap--each free-space block has a header indicating its size,
  61.    and a pointer to the next free-space block.  Maintaining this thing is a
  62.    real bitch, let me tell you.  But it's quick, so it's probably worth it.
  63.  
  64. When searching for a place to put data, MetalBase uses a first-fit strategy to
  65.    keep speed up.  In trials, using best-fit doesn't really affect the amount
  66.    of fragmentation... it turns out that, by reducing the size of the left-over
  67.    free space chunk, the amount of small, unusable blocks increases.  Besides,
  68.    it's a bit more work--which means more chance for errors.
  69.  
  70. Adding data to the heap is easy--the data is placed in the first half of the
  71.    free-block, and a new link in the free-space chain is created at the end
  72.    of the data, to take the place of the one we wrote over.  If there's not
  73.    enough contiguous free space within the chain, the data is appended to the
  74.    end of the file.
  75.  
  76. The trouble comes about when we have to delete a chunk of data.  There are
  77.    four scenarios which have to be dealt with separately (' ' == a free block,
  78.    '=' == a used block, 'X' == the block we're deleting):
  79.  
  80.         [     ]  -- In this scenario, the first free block's size is simply
  81.         [XXXXX]     increased, to encompass the block we're deleting.  This is
  82.         [=====]     the easiest case.
  83.  
  84.         [=====]  -- In this scenario, a new link in the free-space chain is
  85.         [XXXXX]     created to encompass the datablock we're deleting.
  86.         [=====]
  87.  
  88.         [=====]  -- In this scenario, the trailing free block is expanded and
  89.         [XXXXX]     moved backwards, to encompass both the existing block and
  90.         [     ]     the block we're deleting.
  91.  
  92.         [     ]  -- In this scenario, the first free block's size is increased
  93.         [XXXXX]     to encompass the second free block, as well as the size of
  94.         [     ]     the block we're deleting.
  95.  
  96. As I said, it's a real bitch... there should be a simpler way.  But, it will
  97.    do.
  98.  
  99.  
  100. /*
  101.  * THREADED-HEAP FORMAT, USED SPACE -------------------------------------------
  102.  *
  103.  */
  104.  
  105. Segments within the .DAT file which contain data are in the following format:
  106.  
  107.      pos.....4 bytes:  overall size of this used-block.  This section is the
  108.                           location pointed to by the .REL file; it is not used
  109.                           during queries, but is used when returning the block
  110.                           to the free-space chain
  111.  
  112.      sig.....1 byte:   signature; '+' indicates data follows, '-' indicates
  113.                           an end-of-chain marker.
  114.  
  115.      size....4 bytes:  amount of data required to read entire upcoming page.
  116.  
  117.      page....(size):   actual data; see the chapter on data compression for
  118.                           format.  Each page will be at most 1k or so.
  119.  
  120. After each 'page', the stream continues with 'sig' until '-' is reached,
  121.    indicating the end of data.
  122.  
  123.