home *** CD-ROM | disk | FTP | other *** search
/ Media Share 9 / MEDIASHARE_09.ISO / cprog / ndx303.zip / NDX.CPP < prev    next >
C/C++ Source or Header  |  1993-02-13  |  14KB  |  538 lines
  1. //  NDX.CPP  . . .  BTree Index Handling Routines
  2.  
  3. //  Copyright (C) 1987-89, 1992-93 by George H. Mealy
  4.  
  5. #pragma OPTION   -w-pia
  6.  
  7. #include    <stdlib.h>
  8. #include    <stdarg.h>
  9. #include    <io.h>
  10. #include    <fcntl.h>
  11. #include    <ctype.h>
  12. #include    <sys\stat.h>
  13. #include    "ndx.h"
  14.  
  15. #define MAJOR       3
  16. #define MINOR       3
  17.  
  18. #define HDRSIZE     512
  19. #define POP(a)              a->pop(a)
  20. #define PUSH(a, b)          b->push(a)
  21.  
  22. CACHE       Index::cache[NCACHE];       // The node cache
  23. unsigned    Index::cache_users;         // User count
  24.  
  25. unsigned Index::hdrsize = FIELDOFFSET(Index, stacktop);
  26.  
  27. void fatal(char *format, ...);
  28.  
  29. char notice[] = "B-tree indexing routines copyright (C) 1987-89, 92-93 by "
  30.                     "George H. Mealy.";
  31. Index   *ndx;               /* Current index block */
  32. char    searcharg[maxkey];
  33. int     searchn;
  34.  
  35. Index::Index(char *name, int md, CFN compfn)    // Create new Index
  36. {
  37.     ndx = this;
  38.     handle = fopen(name, "w+b");
  39.     strcpy(filename, name);
  40.     if (!handle) fatal("Cannot open %s\n\a", name);
  41.     initcache();
  42.     stacktop = 0;
  43.     n = 0;
  44.     root = eof = HDRSIZE;
  45.     freelist = 0L;
  46.     major = MAJOR;
  47.     minor = MINOR;
  48.     mode = md;
  49.     newnode();
  50.     write(0L, &root, hdrsize);           // Write virgin file header
  51.     write((DWORD)hdrsize, cache[0].node->keys, HDRSIZE - hdrsize);
  52.         // This is guaranteed to be cleared, since getnode did it!
  53.     if (compfn) cmpfn = compfn;
  54. }
  55.  
  56. Index::Index(char *name, CFN compfn)    // Open existing index file
  57. {
  58.     ndx = this;
  59.     stacktop = 0;
  60.     handle = fopen(name, "r+b");
  61.     if(! handle) fatal("Index file %s unavailable\n\a", name);
  62.     initcache();
  63.     strcpy(filename, name);
  64.     read(0L, &root, hdrsize);            // Read the index file header
  65.     if (compfn) cmpfn = compfn;
  66. }
  67.  
  68. Index::~Index()
  69. {
  70.     ndx = this;
  71.     cache_users--;
  72.     for (int i=0; i < NCACHE; i++)
  73.         if (cache[i].handle == handle) {
  74.             if (cache[i].dirty) write(cache[i].node->offset,
  75.                                       cache[i].node, nodesize);
  76.             if (!cache_users) delete cache[i].node;
  77.             else {
  78.                 cache[i].node->offset =  cache[i].dirty = 0;
  79.                 cache[i].handle = NULL;
  80.             }
  81.         }
  82.     write(0L, &root, hdrsize);
  83.     fclose(handle);
  84. }
  85.  
  86. //  Cache handling routines
  87.  
  88. Index::initcache()
  89. {
  90.     int i;
  91.     
  92.     if (! cache_users++) {
  93.         for (i=0; i<NCACHE; i++) {
  94.             if (! (cache[i].node = new Node)) return 0;
  95.             memset(cache[i].node, 0, nodesize);
  96.             }
  97.     }
  98.     return 1;
  99. }
  100.  
  101. Node *Index::newnode()
  102. {
  103.     Node *slot = getnode(0L);   // New slot in the cache
  104.     DWORD n;
  105.     
  106.     cache[0].dirty++;           // Mark it dirty
  107.     if (freelist) {  /* If we can use an old node
  108.                   -- that is, if the node freelist has an entry */
  109.         read(n = freelist, slot, nodesize);
  110.         freelist = slot->offset;
  111.         slot->offset = n;
  112.     }
  113.     else {                      // extend the file
  114.         slot->offset = eof;
  115.         eof += nodesize;
  116.         chsize(fileno(handle), eof);
  117.     }
  118.     memset(&slot->endkeys, 0, maxendkeys + sizeof(WORD));    // Zero the keys
  119.     return slot;
  120. }
  121.  
  122. Node * Index::getnode(DWORD offset)
  123. {
  124.     CACHE *c = cache, temp;
  125.     
  126.     for (int i=0; i < NCACHE; i++, c++)     /* It may be in the cache */
  127.         if (c->node->offset == offset && (c->handle == handle
  128.             || !offset)) break;
  129.     if (i == NCACHE) {                  /* No luck */
  130.         /* Try to find an empty slot */
  131.         for (c=cache, i=0; i < NCACHE && c->node->offset ; c++, i++) ;
  132.         /* None ... empty the last one */
  133.         if (i == NCACHE) {  
  134.             c--; i--;
  135.             write(c->node->offset, c->node, nodesize);
  136.         }
  137.         c->dirty = 0;
  138.         if (! offset) memset(c->node, 0, nodesize);
  139.             else read(offset, c->node, nodesize);
  140.     }
  141.     temp = *c;                  /* Promote it to the top */
  142.     temp.handle = handle;
  143.     memmove(cache + 1, cache, i*sizeof(CACHE));
  144.     *cache = temp;
  145.     return temp.node;
  146. }
  147.  
  148. void Index::read(DWORD start, void *buffer, unsigned n)
  149. {
  150.     if (fseek(handle, start, SEEK_SET) ||
  151.         n != fread(buffer, 1, n, handle))
  152.         fatal("Read failure on file %s\n", filename);
  153. }
  154.  
  155. void Index::write(DWORD start, void *buffer, unsigned n)
  156. {
  157.     if (fseek(handle, start, SEEK_SET) ||
  158.         n != fwrite(buffer, 1, n, handle))
  159.         fatal("Write failure on file %s\n", filename);
  160. }
  161.  
  162. Index::isvalid()
  163. {
  164.     if (!first() && !n) return 1;
  165.     for (unsigned i = 1 ; next(); i++);
  166.     return i == n;
  167. }
  168.  
  169. Key::Key(const char *k, DWORD off)
  170. {
  171.     if (strlen(k) >= maxkey) fatal("Key \"%s\" too long");
  172.     strcpy(data, k);
  173.     offset = off;
  174.     lson = 0L;
  175. }
  176.  
  177. DWORD Index::insert(const char * key, DWORD offset)
  178. {
  179.     Key k(key, offset);
  180.     long result;
  181.     
  182.     ndx = this;
  183.     do {
  184.         stacktop = 0;
  185.         result = k.insert(root);
  186.         } while (result < 0);
  187.     ckey = k;
  188.     if (result) n++;
  189.     return result? k.offset: result;
  190. }
  191.  
  192. DWORD Key::insert(DWORD root)
  193. {
  194.     Node * node;
  195.     Key *k, *ik;
  196.     void *end;
  197.     int compare = -1, n;
  198.     
  199.     if (! root) return 0;
  200.     node = ndx->getnode(root);
  201.     k = (Key *)node->keys;
  202.     end = (char *)k + node->endkeys;
  203.     while (k < end &&
  204.       (compare = strcmp(k->data, data)) < 0)
  205.         k = k->next();
  206.     if (! compare) {      /* Found it */
  207.         ik = k;
  208.         if (ndx->mode == NODUPS)
  209.             {offset = k->offset; return 0; }
  210.         for (; k < end; k = k->next()) {
  211.                 if ((compare = strcmp((char *)k->data, data)) != 0) break;
  212.                 if (k->offset == offset) return k->offset;
  213.             }
  214.         if (ndx->mode == LIFO) k = ik;
  215.         }
  216.     if (k->lson) {           /* Recurse */
  217.         PUSH(node, k);
  218.         return insert(k->lson);
  219.         }
  220.     if (node->endkeys + length() > maxendkeys) /* Node full, so split */
  221.         return node->split()? -1: 0;
  222.     node->shiftup(k, length());
  223.     PUSH(node, k->next());
  224.     k->keycpy(this);
  225.     ndx->cache[0].dirty = 1;
  226.     return k->offset;
  227. }
  228.  
  229. DWORD Index::remove(const char *key, DWORD offset)
  230. {
  231.     unsigned ttop, i;
  232.     Node *node;
  233.     Key *kp, *tkey;
  234.  
  235.     // If key==NULL assume ckey is to be removed!
  236.     if (key && !findkeyrec(key, offset)) return 0;
  237.  
  238.     ndx = this;
  239.     ttop = stacktop;
  240.     node = POP(kp);
  241.     if (! kp->lson) {                       // Key is simply deleted
  242.         node->shiftdn(kp, kp->length(), 0);
  243.         // If at end of node, up to next key
  244.         while (kp == (Key *)(node->keys + node->endkeys)) {
  245.             if (!stacktop)
  246.                 {*ckey.data = 0; return ckey.offset = ckey.lson = 0L;}
  247.             node = POP(kp);
  248.             }
  249.         }
  250.     else {
  251.         stacktop++;                 // Retain node on stack
  252.         do  {                       // Find lower rightmost key to pull up
  253.             node = getnode(kp->lson);
  254.             kp = (Key *)(node->keys + node->endkeys);
  255.             PUSH(node, kp);
  256.             } while (kp->lson);
  257.         node = POP(kp);
  258.         kp = kp->prev(node);        // This is the key to go up
  259.                                     // need only the offset and key
  260.         tkey = (Key *)malloc(i = kp->length());
  261.         memcpy(tkey, kp, i);
  262.         node->shiftdn(kp, i, 1);    // Leave the lson part untouched
  263.         stacktop = ttop;
  264.         node = POP(kp);
  265.          /* Preserve the original lson */
  266.         tkey->lson = kp->lson;
  267.          /* Substitute tkey for key being deleted */
  268.         node->endkeys++;           // Avoid deletion of node!
  269.         node->shiftdn(kp, kp->length(), 0);
  270.         node->endkeys--;
  271.         node->shiftup(kp, i);
  272.         memcpy(kp, tkey, i);
  273.         free(tkey);
  274.         }
  275.     ++stacktop;                     // Retain node on stack
  276.     while (kp->lson) {              // Get lowest left son, if any
  277.         PUSH(node, kp);
  278.         node = getnode(kp->lson);
  279.         kp = (Key *)node->keys;
  280.         }
  281.     ckey = *kp;                     // The new current key
  282.     n--;
  283.     return ckey.offset;
  284. }
  285.  
  286. DWORD Index::findkeyrec(const char *key, DWORD offset)
  287. {
  288.     DWORD rcd;
  289.  
  290.     rcd = find(key);
  291.     while (rcd && rcd != offset) rcd = next();
  292.     return rcd;
  293. }
  294.  
  295. DWORD Index::find(const char *key)
  296. {
  297.     ndx = this;
  298.     if (key) {
  299.         strcpy(searcharg, key);
  300.         searchn = strlen(key);
  301.         stacktop = 0;
  302.         return _find(key, root);  /* Inner routine */
  303.     }
  304.     if (! next() ||
  305.         (ndx->cmpfn)(searcharg, ckey.data, searchn)) return NULL;
  306.     return ckey.offset;
  307. }
  308.  
  309. DWORD Index::_find(const char * key, DWORD root)
  310. {
  311.     Node *node = getnode(root);
  312.     Key * k = (Key *)node->keys;
  313.     DWORD rcd;
  314.     int  compare, n = strlen(key);
  315.     
  316.     for (; k < (Key *)(node->keys + node->endkeys); k = k->next()) {
  317.         /* Find right place in this level */
  318.         if (! (compare = (* ndx->cmpfn)(key, k->data, n))) {
  319.             if (k->lson) {    /* Lower level keys -- recurse */
  320.                 PUSH(node, k);
  321.                 rcd = _find(key, k->lson);
  322.                 if (rcd) return rcd;
  323.                 node = POP(k);
  324.             }
  325.                 /* We have the key */
  326.             PUSH(node, k);                  // Save it on the stack
  327.             ckey.keycpy(k);                 // and copy to current key
  328.             return ckey.offset;
  329.         }
  330.         if (compare < 0) break;
  331.     }
  332.  
  333.     /* Ran into larger key or at end of this level */
  334.     PUSH(node, k);      /* Update stack */
  335.     rcd = 0;
  336.     if (k->lson) /* More keys on right -- recurse */
  337.         rcd =  _find(key, k->lson);
  338.     if (! rcd) POP(k);
  339.     return rcd;
  340. }
  341.  
  342. DWORD Index::first(unsigned last)
  343. {
  344.     Node *node = getnode(root);
  345.     DWORD lson;
  346.     Key *kp;
  347.     
  348.     ndx = this;
  349.     if (! node->endkeys && ! ((Key *)(node->keys))->lson) return 0;
  350.     stacktop = 0;
  351.     /* Find lowermost leftmost key (or last) in the index, setting the stack */
  352.     while ((kp = (Key *)(node->keys + (last? node->endkeys: 0)))->lson) {
  353.         PUSH(node, kp);
  354.         node = getnode(kp->lson);
  355.     }
  356.     if (last) kp = kp->prev(node);
  357.     PUSH(node, kp);
  358.     ckey.keycpy(kp);
  359.     return ckey.offset;
  360. }
  361.  
  362. DWORD Index::next()
  363. {
  364.     Node *node;
  365.     Key *kp;
  366.     
  367.     ndx = this;
  368.         
  369.     /*  The state at return is that left by find():
  370.           The top of the stack is the node in which a key was last found
  371.           and the offset is that of the key.  */
  372.         
  373.     node = POP(kp);             //
  374.     kp = kp->next();
  375.  
  376.     while (kp->lson) {          // While left son, descend to lowest one
  377.         PUSH(node, kp);
  378.         node = getnode(kp->lson);
  379.         kp = (Key *)node->keys;
  380.         continue;
  381.     }
  382.     // While at end of current node, back up a level
  383.     while (kp == (Key *)(node->keys + node->endkeys)) {
  384.         if (stacktop == 0) return 0;
  385.         node = POP(kp);
  386.     }
  387.     PUSH(node, kp);
  388.     ckey.keycpy(kp);
  389.     return ckey.offset;
  390. }
  391.  
  392. DWORD Index::prev()
  393. {
  394.     Node *node;
  395.     Key *kp;
  396.  
  397.     ndx = this;
  398.     node = POP(kp);
  399.     while (kp->lson) {
  400.         PUSH(node, kp);
  401.         node = getnode(kp->lson);
  402.         kp = (Key *)(node->keys + node->endkeys);
  403.         }
  404.     kp = kp->prev(node);
  405.     while (! kp) {
  406.         if (stacktop) {
  407.             node = POP(kp);
  408.             kp = kp->prev(node);
  409.         }
  410.         else return 0;
  411.         }
  412.     PUSH(node, kp);
  413.     ckey.keycpy(kp);
  414.     return kp->offset;
  415. }
  416.  
  417. void Key::push(Node *node)
  418. {
  419.     Frame *stk = (Frame *)&ndx->stack[ndx->stacktop++];
  420.  
  421.     if (ndx->stacktop > stackdepth) fatal("Index stack overflow");
  422.     stk->node = node->offset;
  423.     stk->offset = (char *)this - (char *)node->keys;
  424. }
  425.  
  426. Node * Key::pop(Key *&k)
  427. {
  428.     Frame *stk = (Frame *)&ndx->stack[--ndx->stacktop];
  429.     Node *node = ndx->getnode(stk->node);
  430.     k = (Key *)(node->keys + stk->offset);
  431.     return node;
  432. }
  433.  
  434. int Node::  split()
  435. {
  436.     Node *parent, *added;
  437.     Key *kp, *kpop, *old, *pivot;
  438.     unsigned n, np;
  439.  
  440.     /* Find entry to be moved up a level */
  441.     kp = (Key *)(keys + endkeys/2);
  442.     pivot = kp->prev(this);
  443.     np = pivot->length();
  444.     old = pivot->next();
  445.     n = (char *)old - keys;    /* The entry goes to new node, for */
  446.     if (ndx->stacktop) {               /*   the moment */
  447.         /* If parent full, split it, then we will be back hopefully */
  448.         parent = kpop->pop(kpop);
  449.         if (pivot->length() + parent->endkeys >= maxendkeys)
  450.             return parent->split();
  451.         }
  452.  
  453.     /* Copy first keys and pivot to new node */
  454.  
  455.     added = ndx->newnode();
  456.     memcpy(added->keys, keys, n);
  457.     added->endkeys = n - np;
  458.     ((Key *)(added->keys + n))->lson = 0;
  459.  
  460.     /* Then move the remaining keys of the original node down */
  461.  
  462.     endkeys -= n;
  463.     memmove(keys , old, endkeys + sizeof(DWORD));
  464.     ndx->cache[1].dirty = 1;
  465.  
  466.     /* If it was the root, create a new one */
  467.  
  468.     if (offset == ndx->root) {
  469.         parent = ndx->newnode();
  470.         kpop = (Key *)parent->keys ;
  471.         kpop->lson = offset;
  472.         ndx->root = parent->offset;
  473.         }
  474.  
  475.     /* Put the pivot in the next higher level */
  476.  
  477.     pivot = (Key *)((char *)added->keys + added->endkeys);
  478.     parent->shiftup(kpop, pivot->length());
  479.     kpop->keycpy(pivot);
  480.     kpop->lson = added->offset;   /* Pivot may have a lson! */
  481.     return ndx->cache[0].dirty = 1;
  482. }
  483.  
  484. void Node::shiftup(Key *kp, unsigned n)
  485. {
  486.     int m = keys + endkeys - (char *)kp + sizeof(DWORD);
  487.  
  488.     memmove((char *)kp + n, kp, m);
  489.     endkeys += n;
  490.     ndx->cache[0].dirty = 1;
  491. }
  492.  
  493. void Node::shiftdn(Key *kp, unsigned n, unsigned leave)
  494. {
  495.     int m = keys + endkeys - (char *)kp + sizeof(DWORD);
  496.     DWORD link;
  497.  
  498.     if (! leave) memmove(kp, (char *)kp + n, m);
  499.     endkeys -= n;
  500.     ndx->cache[0].dirty = 1;
  501.     if (endkeys || kp->lson || ! ndx->stacktop) return;
  502.     link = offset;                      // Hook node into the freelist
  503.     offset = ndx->freelist;
  504.     ndx->freelist = link;
  505.     ndx->write(link, this, nodesize);   // Have to do this here!
  506.     ndx->cache[0].dirty = 0;
  507.     POP(kp);                            // Back up to poppa
  508.     kp->lson = 0;                       // No son now
  509.     ndx->cache[0].dirty = 1;
  510.     ndx->stacktop++;                    // REALLY do this???
  511. }
  512.  
  513.  
  514. Key * Key::prev(Node *node)
  515. {
  516.     Key *pk = (Key *)node->keys, *k = pk;
  517.  
  518.     if (pk == this) return NULL;
  519.     while (k < this) {
  520.         pk = k;
  521.         k = k->next();
  522.     }
  523.     return pk;
  524. }
  525.  
  526. void fatal(char *format, ...)
  527. {
  528.     va_list argptr;
  529.  
  530.     fprintf(stderr, "FATAL ERROR: ");
  531.     va_start(argptr, format);
  532.     vprintf(format, argptr);
  533.     va_end(argptr);
  534.     fputs("\n", stderr);
  535.     exit(-1);
  536. }
  537.  
  538.