home *** CD-ROM | disk | FTP | other *** search
/ World of Shareware - Software Farm 2 / wosw_2.zip / wosw_2 / DATABASE / DPG.ZIP / FILES.C < prev    next >
C/C++ Source or Header  |  1992-04-21  |  22KB  |  881 lines
  1. #include    <stdio.h>
  2. #include    <stdlib.h>
  3. #include    <fcntl.h>
  4. #include    <io.h>
  5. #include    <string.h>
  6. #include    <assert.h>
  7. #include    "video.h"
  8. #include    "files.h"
  9.  
  10. #define    MAXKEY        32        /* Maximum depth a tree can achieve */
  11. #define    NODESIZE        512    /* Physical size of each node */
  12.  
  13.                                     /* Macros to access values from nodes in memory */
  14.  
  15. #define    nentries            (*(short *)(node + NODESIZE - sizeof (short)))
  16. #define    nodeptr(i)        ((long *)node)[i]
  17. #define    recptr(i)        ((long *)node)[i + m]
  18. #define    entry(i)            (node + (m*2 - 1)*sizeof (long) + (i)*length)
  19.  
  20. #define    nentries2        (*(short *)(node2 + NODESIZE - sizeof (short)))
  21. #define    nodeptr2(i)        ((long *)node2)[i]
  22. #define    recptr2(i)        ((long *)node2)[i + m]
  23. #define    entry2(i)        (node2 + (m*2 - 1)*sizeof (long) + (i)*length)
  24.  
  25. #define    nentries3        (*(short *)(node3 + NODESIZE - sizeof (short)))
  26. #define    nodeptr3(i)        ((long *)node3)[i]
  27. #define    recptr3(i)        ((long *)node3)[i + m]
  28. #define    entry3(i)        (node3 + (m*2 - 1)*sizeof (long) + (i)*length)
  29.  
  30.                                     /* Storage for nodes in memory */
  31. static char node[NODESIZE];
  32. static char node2[NODESIZE];
  33. static char node3[NODESIZE];
  34. static m;                        /* Maximum branching factor */
  35. static length;                    /* Length of keys */
  36. static indexfile;                /* Handle for index file */
  37. static miscoff;                /* Offset of data in miscfile */
  38. static long newnodeptr;        /* Pointer to newly created node */
  39.  
  40. int miscfile;
  41.  
  42.         /* Read data from file with error checking */
  43.  
  44. void Read (int file,long p,void *buf,int bytes)
  45. {
  46.     lseek (file,p,SEEK_SET);
  47.     if (read (file,buf,bytes) != bytes)
  48.     {
  49.         printf ("Read Error\n");
  50.         exit (1);
  51.     }
  52. }
  53.  
  54.         /* Write data to file with error checking */
  55.  
  56. void Write (int file,long p,void *buf,int bytes)
  57. {
  58.     lseek (file,p,SEEK_SET);
  59.     if (write (file,buf,bytes) != bytes)
  60.     {
  61.         printf ("Write Error\n");
  62.         exit (1);
  63.     }
  64. }
  65.  
  66.         /* Calculate the maximum branching factor given the key length for the
  67.             current index file */
  68.  
  69. static void calcm (void)
  70. {
  71.     m = (NODESIZE + length + sizeof (long) - sizeof (short)) /
  72.             (length + 2*sizeof (long));
  73. }
  74.  
  75.         /* Allocate a new node */
  76.  
  77. static long allocnode (void)
  78. {
  79.     long p;
  80.     long next;
  81.  
  82.                         /* Pointer to first node on free list */
  83.  
  84.     Read (miscfile,miscoff + 3*sizeof (long),&p,sizeof p);
  85.  
  86.     if (p < 0)        /* If no nodes on free list, add one to end of file */
  87.         return filelength (indexfile);
  88.  
  89.                         /* Return first node on free list and update list pointer */
  90.  
  91.     Read (indexfile,p,&next,sizeof next);
  92.     Write (miscfile,miscoff + 3*sizeof (long),&next,sizeof next);
  93.     return p;
  94. }
  95.  
  96.         /* Add a node to free list */
  97.  
  98. static void freenode (long t)
  99. {
  100.     long p;
  101.  
  102.     Read (miscfile,miscoff + 3*sizeof (long),&p,sizeof p);
  103.     Write (indexfile,t,&p,sizeof p);
  104.     Write (miscfile,miscoff + 3*sizeof (long),&t,sizeof t);
  105. }
  106.  
  107.         /* Delete a record from linked list of records, and add it to list of
  108.             free data records */
  109.  
  110. void delete (int file,long ptr,void *rec,long _miscoff)
  111. {
  112.     long listptr[3];
  113.     long next;
  114.     long prev;
  115.  
  116.     miscoff = _miscoff;
  117.  
  118.     next = ((long *)rec)[0];        /* Pointer to next record */
  119.     prev = ((long *)rec)[1];        /* Pointer to previous record */
  120.  
  121.             /* Remove record from linked list */
  122.  
  123.     if (next >= 0)
  124.         Write (file,next + sizeof (long),&prev,sizeof prev);
  125.     if (prev >= 0)
  126.         Write (file,prev,&next,sizeof next);
  127.     Read (miscfile,miscoff,listptr,sizeof listptr);
  128.     if (listptr[1] == ptr)
  129.         listptr[1] = next;
  130.     if (listptr[2] == ptr)
  131.         listptr[2] = prev;
  132.  
  133.             /* Add record to free list */
  134.  
  135.     Write (file,ptr,&listptr[0],sizeof listptr[0]);
  136.     listptr[0] = ptr;
  137.  
  138.     Write (miscfile,miscoff,listptr,sizeof listptr);
  139. }
  140.  
  141.         /* Delete a data record from an indexed file */
  142.  
  143. void deleteindex (int file,long ptr,void *rec,long _miscoff,
  144.         char *key,int _length,int _indexfile)
  145. {
  146.     long t,t2;
  147.     int n;
  148.     int lo,hi;
  149.     int i,j,k;
  150.     int c;
  151.     int iv[MAXKEY];
  152.     long chain[MAXKEY];
  153.  
  154.     indexfile = _indexfile;
  155.     miscoff = _miscoff;
  156.     length = _length;
  157.     calcm ();
  158.  
  159.             /* Delete record from linked list */
  160.  
  161.     delete (file,ptr,rec,miscoff);
  162.  
  163.     t = 0;
  164.     n = -1;
  165.     for (;;)
  166.     {
  167.         Read (indexfile,t,node,NODESIZE);
  168.         lo = 0;
  169.         hi = nentries - 1;
  170.         while (lo <= hi)
  171.         {
  172.             i = (lo + hi) / 2;
  173.             c = memicmp (entry (i),key,length);
  174.             if (c == 0)
  175.                 break;
  176.             if (c < 0)
  177.                 lo = i + 1;
  178.             else
  179.                 hi = i - 1;
  180.         }
  181.         if (c == 0)
  182.             break;
  183.         n++;
  184.         assert (n < MAXKEY);
  185.         iv[n] = lo;
  186.         chain[n] = t;
  187.         t = nodeptr (lo);
  188.         assert (t >= 0);
  189.     }
  190.     if (nodeptr (0) >= 0)
  191.     {
  192.         t2 = t;
  193.         lo++;
  194.         n++;
  195.         assert (n < MAXKEY);
  196.         iv[n] = lo;
  197.         chain[n] = t;
  198.         t = nodeptr (lo);
  199.         assert (t >= 0);
  200.         Read (indexfile,t,node,NODESIZE);
  201.         do
  202.         {
  203.             n++;
  204.             assert (n < MAXKEY);
  205.             iv[n] = 0;
  206.             chain[n] = t;
  207.             t = nodeptr (0);
  208.             assert (t >= 0);
  209.             Read (indexfile,t,node,NODESIZE);
  210.         }
  211.         while (nodeptr (0) >= 0);
  212.         Write (indexfile,t2 + (m+lo)*sizeof (long),&recptr (lo),sizeof (long));
  213.         Write (indexfile,t2 + m*2*sizeof (long) + lo*length,entry (lo),length);
  214.     }
  215.     memmove (&nodeptr (lo),&nodeptr (lo + 1),(nentries - lo)*sizeof (long));
  216.     memmove (&recptr (lo),&recptr (lo + 1),(nentries - lo - 1)*sizeof (long));
  217.     memmove (entry (lo),entry (lo + 1),(nentries - lo - 1)*length);
  218.     nentries--;
  219.     Write (indexfile,t,node,NODESIZE);
  220.  
  221.             /* While current node has too few entries */
  222.  
  223.     while (nentries < (m - 1) / 2 && n > 0)
  224.     {
  225.                 /* Read father node */
  226.  
  227.         Read (indexfile,chain[n - 1],node3,NODESIZE);
  228.  
  229.                 /* Index for father key */
  230.  
  231.         i = iv[n - 1] - 1;
  232.  
  233.                 /* If current node is leftmost, merge with right brother */
  234.  
  235.         if (i < 0)
  236.         {
  237.                     /* Read brother node */
  238.  
  239.             t2 = nodeptr3 (1);
  240.             Read (indexfile,t2,node2,NODESIZE);
  241.  
  242.                     /* If merged node would have few enough entries */
  243.  
  244.             if (nentries + nentries2 < m - 1)
  245.             {
  246.                         /* Move over brother node keys */
  247.  
  248.                 memmove (&nodeptr2 (nentries + 1),&nodeptr2 (0),(nentries2 + 1)*sizeof (long));
  249.                 memmove (&recptr2 (nentries + 1),&recptr2 (0),nentries2*sizeof (long));
  250.                 memmove (entry2 (nentries + 1),entry2 (0),nentries2*length);
  251.                 nentries2 += nentries + 1;
  252.  
  253.                         /* Copy current node keys into brother node */
  254.  
  255.                 memcpy (&nodeptr2 (0),&nodeptr (0),(nentries + 1)*sizeof (long));
  256.                 memcpy (&recptr2 (0),&recptr (0),nentries*sizeof (long));
  257.                 memcpy (entry2 (0),entry (0),nentries*length);
  258.  
  259.                         /* Put father key into brother node */
  260.  
  261.                 recptr2 (nentries) = recptr3 (0);
  262.                 memcpy (entry2 (nentries),entry3 (0),length);
  263.  
  264.                         /* Delete father key from father node */
  265.  
  266.                 memmove (&nodeptr3 (0),&nodeptr3 (1),nentries3*sizeof (long));
  267.                 memmove (&recptr3 (0),&recptr3 (1),(nentries3 - 1)*sizeof (long));
  268.                 memmove (entry3 (0),entry3 (1),(nentries3 - 1)*length);
  269.                 nentries3--;
  270.  
  271.                         /* Free current node */
  272.  
  273.                 freenode (t);
  274.  
  275.                         /* If father node is root node and empty, delete it */
  276.  
  277.                 if (n == 1 && nentries3 == 0)
  278.                 {
  279.                             /* Free prior location of brother node */
  280.  
  281.                     freenode (t2);
  282.  
  283.                             /* Write brother node into root node's location */
  284.  
  285.                     Write (indexfile,0,node2,NODESIZE);
  286.                 }
  287.                 else    /* Write back nodes */
  288.                 {
  289.                             /* Write back brother node */
  290.  
  291.                     Write (indexfile,t2,node2,NODESIZE);
  292.  
  293.                             /* Write back father node */
  294.  
  295.                     Write (indexfile,chain[n - 1],node3,NODESIZE);
  296.                 }
  297.  
  298.                         /* Finish */
  299.  
  300.                 break;
  301.             }
  302.             else    /* Redistribute keys between two nodes */
  303.             {
  304.                         /* Middle key to be used as replacement for father key */
  305.  
  306.                 j = (nentries2 + nentries) / 2 - nentries - 1;
  307.  
  308.                         /* Copy in father key */
  309.  
  310.                 recptr (nentries) = recptr3 (0);
  311.                 memcpy (entry (nentries),entry3 (0),length);
  312.  
  313.                         /* Copy keys from brother node to current node */
  314.  
  315.                 memcpy (&nodeptr (nentries + 1),&nodeptr2 (0),(j + 1)*sizeof (long));
  316.                 memcpy (&recptr (nentries + 1),&recptr2 (0),j*sizeof (long));
  317.                 memcpy (entry (nentries + 1),entry2 (0),j*length);
  318.  
  319.                         /* Copy middle key into father node */
  320.  
  321.                 recptr3 (0) = recptr2 (j);
  322.                 memcpy (entry3 (0),entry2 (j),length);
  323.                 nentries += j + 1;
  324.  
  325.                         /* Move down entries in brother node */
  326.  
  327.                 memmove (&nodeptr2 (0),&nodeptr2 (j + 1),(nentries2 - j)*sizeof (long));
  328.                 memmove (&recptr2 (0),&recptr2 (j + 1),(nentries2 - j - 1)*sizeof (long));
  329.                 memmove (entry2 (0),entry2 (j + 1),(nentries2 - j - 1)*length);
  330.                 nentries2 -= j + 1;
  331.  
  332.                         /* Write back current node */
  333.  
  334.                 Write (indexfile,t,node,NODESIZE);
  335.  
  336.                         /* Write back brother node */
  337.  
  338.                 Write (indexfile,t2,node2,NODESIZE);
  339.  
  340.                         /* Write back father node */
  341.  
  342.                 Write (indexfile,chain[n - 1],node3,NODESIZE);
  343.  
  344.                         /* Step up to father node and continue */
  345.  
  346.                 memcpy (node,node3,NODESIZE);
  347.                 n--;
  348.                 t = chain[n];
  349.             }
  350.         }
  351.         else    /* Merge with left brother */
  352.         {
  353.                     /* Read brother node */
  354.  
  355.             t2 = nodeptr3 (i);
  356.             Read (indexfile,t2,node2,NODESIZE);
  357.  
  358.                     /* If merged node would have few enough entries */
  359.  
  360.             if (nentries + nentries2 < m - 1)
  361.             {
  362.                         /* Put father key into brother node */
  363.  
  364.                 recptr2 (nentries2) = recptr3 (i);
  365.                 memcpy (entry2 (nentries2),entry3 (i),length);
  366.                 nentries2++;
  367.  
  368.                         /* Merge current node keys into brother node */
  369.  
  370.                 memcpy (&nodeptr2 (nentries2),&nodeptr (0),(nentries + 1)*sizeof (long));
  371.                 memcpy (&recptr2 (nentries2),&recptr (0),nentries*sizeof (long));
  372.                 memcpy (entry2 (nentries2),entry (0),nentries*length);
  373.                 nentries2 += nentries;
  374.  
  375.                         /* Delete father key from father node */
  376.  
  377.                 memmove (&nodeptr3 (i + 1),&nodeptr3 (i + 2),(nentries3 - i)*sizeof (long));
  378.                 memmove (&recptr3 (i),&recptr3 (i + 1),(nentries3 - i - 1)*sizeof (long));
  379.                 memmove (entry3 (i),entry3 (i + 1),(nentries3 - i - 1)*length);
  380.                 nentries3--;
  381.  
  382.                         /* Free current node */
  383.  
  384.                 freenode (t);
  385.  
  386.                         /* Write back brother node */
  387.  
  388.                 Write (indexfile,t2,node2,NODESIZE);
  389.  
  390.                         /* Write back father node */
  391.  
  392.                 Write (indexfile,chain[n - 1],node3,NODESIZE);
  393.  
  394.                         /* Finish */
  395.  
  396.                 break;
  397.             }
  398.             else    /* Redistribute keys between two nodes */
  399.             {
  400.                         /* Middle key to be used as replacement for father key */
  401.  
  402.                 j = (nentries2 + nentries) / 2;
  403.  
  404.                         /* Number of keys to transfer from brother to current node */
  405.  
  406.                 k = nentries2 - j;
  407.  
  408.                         /* Move over keys in current node to make room */
  409.  
  410.                 memmove (&nodeptr (k + 1),&nodeptr (0),(nentries + 1)*sizeof (long));
  411.                 memmove (&recptr (k + 1),&recptr (0),nentries*sizeof (long));
  412.                 memmove (entry (k + 1),entry (0),nentries*length);
  413.                 nentries += k + 1;
  414.  
  415.                         /* Copy in father key */
  416.  
  417.                 recptr (k) = recptr3 (i);
  418.                 memcpy (entry (k),entry3 (i),length);
  419.  
  420.                         /* Copy keys from brother node to current node */
  421.  
  422.                 memcpy (&nodeptr (0),&nodeptr2 (j + 1),(k + 1)*sizeof (long));
  423.                 memcpy (&recptr (0),&recptr2 (j + 1),k*sizeof (long));
  424.                 memcpy (entry (0),entry2 (j + 1),k*length);
  425.                 nentries2 -= k + 1;
  426.  
  427.                         /* Copy middle key into father node */
  428.  
  429.                 recptr3 (i) = recptr2 (j);
  430.                 memcpy (entry3 (i),entry2 (j),length);
  431.  
  432.                         /* Write back current node */
  433.  
  434.                 Write (indexfile,t,node,NODESIZE);
  435.  
  436.                         /* Write back brother node */
  437.  
  438.                 Write (indexfile,t2,node2,NODESIZE);
  439.  
  440.                         /* Write back father node */
  441.  
  442.                 Write (indexfile,chain[n - 1],node3,NODESIZE);
  443.  
  444.                         /* Step up to father node and continue */
  445.  
  446.                 memcpy (node,node3,NODESIZE);
  447.                 n--;
  448.                 t = chain[n];
  449.             }
  450.         }
  451.     }
  452. }
  453.  
  454.         /* Allocate a new data record, and add to linked list */
  455.  
  456. void create (int file,long *ptr,void *rec,int size,long _miscoff)
  457. {
  458.     long listptr[3];
  459.     long p;
  460.  
  461.     miscoff = _miscoff;
  462.  
  463.     Read (miscfile,miscoff,listptr,sizeof listptr);
  464.  
  465.     if (listptr[0] < 0)                /* If free list is empty */
  466.         p = filelength (file);        /* get new record from end of file */
  467.     else                                    /* get first record from free list */
  468.     {
  469.         p = listptr[0];
  470.         Read (file,p,listptr,sizeof (long));
  471.     }
  472.  
  473.     if (listptr[2] < 0)        /* If linked list is empty, initialize it */
  474.     {
  475.         listptr[1] = p;
  476.         listptr[2] = p;
  477.     }
  478.     else                            /* add record to linked list */
  479.     {
  480.         ((long *)rec)[1] = listptr[2];
  481.         Write (file,listptr[2],&p,sizeof (long));
  482.         listptr[2] = p;
  483.     }
  484.  
  485.     Write (file,p,rec,size);
  486.     Write (miscfile,miscoff,listptr,sizeof listptr);
  487.     *ptr = p;
  488. }
  489.  
  490.         /* Recursively insert key in B-tree and return error if any */
  491.  
  492. static insert (long t,long *rptr,char *rkey,long ptr,char *key)
  493. {
  494.     long newptr;
  495.     char newkey[MAXKEY];
  496.     int lo,hi;
  497.     int i,j;
  498.     int c;
  499.     long n1;
  500.  
  501.     if (t < 0)        /* Run out of tree so have to back up */
  502.     {
  503.         *rptr = ptr;
  504.         memcpy (rkey,key,length);
  505.         return 0;
  506.     }
  507.  
  508.     Read (indexfile,t,node,NODESIZE);
  509.  
  510.             /* Find where to insert new key in current node */
  511.  
  512.     lo = 0;
  513.     hi = nentries - 1;
  514.     while (lo <= hi)
  515.     {
  516.         i = (lo + hi) / 2;
  517.         c = memicmp (entry (i),key,length);
  518.         if (c == 0)        /* Key already exists, so return error */
  519.             return 1;
  520.         if (c < 0)
  521.             lo = i + 1;
  522.         else
  523.             hi = i - 1;
  524.     }
  525.  
  526.             /* Recursively insert key below current node */
  527.  
  528.     if (insert (nodeptr (i),&newptr,newkey,ptr,key))
  529.         return 1;
  530.  
  531.             /* If insertion has propagated up from node below */
  532.  
  533.     if (newptr >= 0)
  534.     {
  535.         Read (indexfile,t,node,NODESIZE);
  536.  
  537.                 /* Again find key in current node */
  538.  
  539.         lo = 0;
  540.         hi = nentries - 1;
  541.         while (lo <= hi)
  542.         {
  543.             i = (lo + hi) / 2;
  544.             c = memicmp (entry (i),newkey,length);
  545.             assert (c != 0);
  546.             if (c < 0)
  547.                 lo = i + 1;
  548.             else
  549.                 hi = i - 1;
  550.         }
  551.         if (nentries == m - 1)        /* If node is too full, split it */
  552.         {
  553.             n1 = allocnode ();
  554.             j = m / 2;
  555.             if (lo <= j)
  556.                 j--;
  557.             *rptr = recptr (j);
  558.             memcpy (rkey,entry (j),length);
  559.             memmove (&nodeptr (j),&nodeptr (j + 1),(nentries - j)*sizeof (long));
  560.             memmove (&recptr (j),&recptr (j + 1),(nentries - j - 1)*sizeof (long));
  561.             memmove (entry (j),entry (j + 1),(nentries - j - 1)*length);
  562.             if (lo <= j + 1)
  563.                 j++;
  564.             memmove (&nodeptr (lo + 1),&nodeptr (lo),(nentries - lo)*sizeof (long));
  565.             memmove (&recptr (lo + 1),&recptr (lo),(nentries - lo - 1)*sizeof (long));
  566.             memmove (entry (lo + 1),entry (lo),(nentries - lo - 1)*length);
  567.             nodeptr (lo) = newnodeptr;
  568.             recptr (lo) = newptr;
  569.             memcpy (entry (lo),newkey,length);
  570.             nentries = j;
  571.             Write (indexfile,n1,node,NODESIZE);
  572.             nentries = m - 1 - j;
  573.             memcpy (&nodeptr (0),&nodeptr (j),(nentries + 1)*sizeof (long));
  574.             memcpy (&recptr (0),&recptr (j),nentries*sizeof (long));
  575.             memcpy (entry (0),entry (j),nentries*length);
  576.             Write (indexfile,t,node,NODESIZE);
  577.             newnodeptr = n1;
  578.             return 0;
  579.         }
  580.         else                                /* Simply insert in current node */
  581.         {
  582.             memmove (&nodeptr (lo + 1),&nodeptr (lo),(nentries - lo + 1)*sizeof (long));
  583.             memmove (&recptr (lo + 1),&recptr (lo),(nentries - lo)*sizeof (long));
  584.             memmove (entry (lo + 1),entry (lo),(nentries - lo)*length);
  585.             nodeptr (lo) = newnodeptr;
  586.             recptr (lo) = newptr;
  587.             memcpy (entry (lo),newkey,length);
  588.             nentries++;
  589.             Write (indexfile,t,node,NODESIZE);
  590.         }
  591.     }
  592.  
  593.     *rptr = -1;
  594.     return 0;
  595. }
  596.  
  597.         /* Allocate a new data record and insert index key in B-tree */
  598.  
  599. void createindex (int file,long *ptr,void *rec,int size,long _miscoff,
  600.         char *key,int _length,int _indexfile,int x,int y,int directions)
  601. {
  602.     long listptr[3];
  603.     long p;
  604.     long newptr;
  605.     char newkey[MAXKEY];
  606.     int lo,hi;
  607.     int i,j;
  608.     int c;
  609.     long n1,n2;
  610.     long splitptr;
  611.     char splitkey[MAXKEY];
  612.  
  613.     indexfile = _indexfile;
  614.     miscoff = _miscoff;
  615.     length = _length;
  616.     calcm ();
  617.  
  618.     Read (miscfile,miscoff,listptr,sizeof listptr);
  619.     if (listptr[0] < 0)                /* If free list is empty */
  620.         p = filelength (file);        /* get new record from end of file */
  621.     else                                    /* get first record from free list */
  622.     {
  623.         p = listptr[0];
  624.         Read (file,p,listptr,sizeof (long));
  625.     }
  626.  
  627. REDO:
  628.  
  629.             /* Ask user for key value */
  630.  
  631.     editstr (key,length,x,y,directions);
  632.  
  633.     if (dir == DIR_ESC)        /* User hit ESC, so cancel */
  634.     {
  635.         *ptr = -1;
  636.         return;
  637.     }
  638.  
  639.     if (filelength (indexfile))        /* If index file not empty */
  640.     {
  641.         newnodeptr = -1;
  642.         if (insert (0,&newptr,newkey,p,key))
  643.         {
  644.             beep ();
  645.             goto REDO;
  646.         }
  647.         if (newptr >= 0)
  648.         {
  649.             Read (indexfile,0,node,NODESIZE);
  650.             lo = 0;
  651.             hi = nentries - 1;
  652.             while (lo <= hi)
  653.             {
  654.                 i = (lo + hi) / 2;
  655.                 c = memicmp (entry (i),newkey,length);
  656.                 assert (c != 0);
  657.                 if (c < 0)
  658.                     lo = i + 1;
  659.                 else
  660.                     hi = i - 1;
  661.             }
  662.             if (nentries == m - 1)
  663.             {
  664.                 n1 = allocnode ();
  665.                 n2 = allocnode ();
  666.                 j = m / 2;
  667.                 if (lo <= j)
  668.                     j--;
  669.                 splitptr = recptr (j);
  670.                 memcpy (splitkey,entry (j),length);
  671.                 memmove (&nodeptr (j),&nodeptr (j + 1),(nentries - j)*sizeof (long));
  672.                 memmove (&recptr (j),&recptr (j + 1),(nentries - j - 1)*sizeof (long));
  673.                 memmove (entry (j),entry (j + 1),(nentries - j - 1)*length);
  674.                 if (lo <= j + 1)
  675.                     j++;
  676.                 memmove (&nodeptr (lo + 1),&nodeptr (lo),(nentries - lo)*sizeof (long));
  677.                 memmove (&recptr (lo + 1),&recptr (lo),(nentries - lo - 1)*sizeof (long));
  678.                 memmove (entry (lo + 1),entry (lo),(nentries - lo - 1)*length);
  679.                 nodeptr (lo) = newnodeptr;
  680.                 recptr (lo) = newptr;
  681.                 memcpy (entry (lo),newkey,length);
  682.                 nentries = j;
  683.                 Write (indexfile,n1,node,NODESIZE);
  684.                 nentries = m - 1 - j;
  685.                 memcpy (&nodeptr (0),&nodeptr (j),(nentries + 1)*sizeof (long));
  686.                 memcpy (&recptr (0),&recptr (j),nentries*sizeof (long));
  687.                 memcpy (entry (0),entry (j),nentries*length);
  688.                 Write (indexfile,n2,node,NODESIZE);
  689.                 nentries = 1;
  690.                 nodeptr (0) = n1;
  691.                 nodeptr (1) = n2;
  692.                 recptr (0) = splitptr;
  693.                 memcpy (entry (0),splitkey,length);
  694.             }
  695.             else
  696.             {
  697.                 memmove (&nodeptr (lo + 1),&nodeptr (lo),(nentries - lo + 1)*sizeof (long));
  698.                 memmove (&recptr (lo + 1),&recptr (lo),(nentries - lo)*sizeof (long));
  699.                 memmove (entry (lo + 1),entry (lo),(nentries - lo)*length);
  700.                 nodeptr (lo) = newnodeptr;
  701.                 recptr (lo) = newptr;
  702.                 memcpy (entry (lo),newkey,length);
  703.                 nentries++;
  704.             }
  705.             Write (indexfile,0,node,NODESIZE);
  706.         }
  707.     }
  708.     else                                        /* Special case for no existing keys */
  709.     {
  710.         memset (node,0xff,sizeof node);
  711.         nentries = 1;
  712.         recptr (0) = p;
  713.         memcpy (entry (0),key,length);
  714.         Write (indexfile,0,node,sizeof node);
  715.     }
  716.  
  717.     if (listptr[2] < 0)        /* If linked list is empty, initialize it */
  718.     {
  719.         listptr[1] = p;
  720.         listptr[2] = p;
  721.     }
  722.     else                            /* add record to linked list */
  723.     {
  724.         ((long *)rec)[1] = listptr[2];
  725.         Write (file,listptr[2],&p,sizeof (long));
  726.         listptr[2] = p;
  727.     }
  728.  
  729.     Write (file,p,rec,size);
  730.     Write (miscfile,miscoff,listptr,sizeof listptr);
  731.     *ptr = p;
  732. }
  733.  
  734.         /* Find data record in file given key value */
  735.  
  736. void find (int file,int _indexfile,long *ptr,void *rec,int size,int _length,
  737.         char *key)
  738. {
  739.     int lo,hi,i,c;
  740.  
  741.     indexfile = _indexfile;
  742.     length = _length;
  743.     calcm ();
  744.  
  745.     *ptr = -1;
  746.  
  747.     if (filelength (indexfile) == 0)        /* Special case for no keys in index */
  748.         return;
  749.  
  750.     Read (indexfile,0,node,NODESIZE);
  751.  
  752.     for (;;)
  753.     {
  754.                 /* Try to find key in current node */
  755.  
  756.         lo = 0;
  757.         hi = nentries - 1;
  758.         while (lo <= hi)
  759.         {
  760.             i = (lo + hi) / 2;
  761.             c = memicmp (entry (i),key,length);
  762.             if (c == 0)        /* Found key, so read data record */
  763.             {
  764.                 *ptr = recptr (i);
  765.                 Read (file,*ptr,rec,size);
  766.                 return;
  767.             }
  768.             if (c < 0)
  769.                 lo = i + 1;
  770.             else
  771.                 hi = i - 1;
  772.         }
  773.  
  774.         if (nodeptr (i) < 0)        /* Bottom of tree, so give up */
  775.             return;
  776.  
  777.         Read (indexfile,nodeptr (i),node,NODESIZE);
  778.     }
  779. }
  780.  
  781.         /* Get key value from user and try to find corresponding data record */
  782.  
  783. void select (int file,int _indexfile,long *ptr,void *rec,int size,char *key,
  784.         int _length,int x,int y,int directions)
  785. {
  786.     indexfile = _indexfile;
  787.     length = _length;
  788.  
  789. REDO:
  790.  
  791.             /* Ask user for key value */
  792.  
  793.     editstr (key,length,x,y,directions);
  794.  
  795.     if (dir == DIR_ESC)        /* User hit ESC, so cancel */
  796.         return;
  797.  
  798.     find (file,indexfile,ptr,rec,size,length,key);
  799.  
  800.     if (*ptr < 0)                /* not found, so ask user for new key value */
  801.     {
  802.         beep ();
  803.         goto REDO;
  804.     }
  805. }
  806.  
  807.         /* Link a data record onto another one */
  808.  
  809. void reclink (int fromfile,long fromptr,long *fromptrs,int fromoffset,
  810.         int tofile,long toptr,long *toptrs,int tooffset)
  811. {
  812.     fromptrs[0] = toptr;
  813.     fromptrs[2] = toptrs[1];
  814.     if (toptrs[1] < 0)
  815.         toptrs[0] = toptrs[1] = fromptr;
  816.     else
  817.     {
  818.         Write (fromfile,toptrs[1] + fromoffset + sizeof (long),&fromptr,sizeof (long));
  819.         toptrs[1] = fromptr;
  820.     }
  821. }
  822.  
  823.         /* Unlink a data record from another one */
  824.  
  825. void recunlink (int fromfile,long fromptr,long *fromptrs,int fromoffset,
  826.         int tofile,long toptr,long *toptrs,int tooffset)
  827. {
  828.     if (toptrs[0] == fromptr)
  829.         toptrs[0] = fromptrs[1];
  830.     else
  831.         Write (fromfile,fromptrs[2] + fromoffset + sizeof (long),&fromptrs[1],sizeof (long));
  832.     if (toptrs[1] == fromptr)
  833.         toptrs[1] = fromptrs[2];
  834.     else
  835.         Write (fromfile,fromptrs[1] + fromoffset + 2*sizeof (long),&fromptrs[2],sizeof (long));
  836.     fromptrs[0] = fromptrs[1] = fromptrs[2] = -1;
  837. }
  838.  
  839.         /* Open a file if it exists, otherwise create it, with error checking */
  840.  
  841. opencreate (char *filename)
  842. {
  843.     int f;
  844.  
  845.     f = open (filename,O_RDWR);
  846.     if (f >= 0)
  847.         return f;
  848.     f = open (filename,O_CREAT | O_TRUNC | O_RDWR,0777);
  849.     if (f < 0)
  850.     {
  851.         printf ("Can't create file %s.\n",filename);
  852.         exit (1);
  853.     }
  854.     return f;
  855. }
  856.  
  857.         /* Functions to initialize data in miscfile */
  858.  
  859. void mwrite (void *buf,int bytes)
  860. {
  861.     if (write (miscfile,buf,bytes) != bytes)
  862.     {
  863.         printf ("Error writing to file misc.dat\n");
  864.         exit (1);
  865.     }
  866. }
  867.  
  868. void mblank3 (void)
  869. {
  870.     static long data[] = { -1,-1,-1 };
  871.  
  872.     mwrite (data,sizeof data);
  873. }
  874.  
  875. void mblank4 (void)
  876. {
  877.     static long data[] = { -1,-1,-1,-1 };
  878.  
  879.     mwrite (data,sizeof data);
  880. }
  881.