Category : Databases and related files
Archive : DPG.ZIP
Filename : FILES.C
Output of file : FILES.C contained in archive : DPG.ZIP
#include
#include
#include
#include
#include
#include "video.h"
#include "files.h"
#define MAXKEY 32 /* Maximum depth a tree can achieve */
#define NODESIZE 512 /* Physical size of each node */
/* Macros to access values from nodes in memory */
#define nentries (*(short *)(node + NODESIZE - sizeof (short)))
#define nodeptr(i) ((long *)node)[i]
#define recptr(i) ((long *)node)[i + m]
#define entry(i) (node + (m*2 - 1)*sizeof (long) + (i)*length)
#define nentries2 (*(short *)(node2 + NODESIZE - sizeof (short)))
#define nodeptr2(i) ((long *)node2)[i]
#define recptr2(i) ((long *)node2)[i + m]
#define entry2(i) (node2 + (m*2 - 1)*sizeof (long) + (i)*length)
#define nentries3 (*(short *)(node3 + NODESIZE - sizeof (short)))
#define nodeptr3(i) ((long *)node3)[i]
#define recptr3(i) ((long *)node3)[i + m]
#define entry3(i) (node3 + (m*2 - 1)*sizeof (long) + (i)*length)
/* Storage for nodes in memory */
static char node[NODESIZE];
static char node2[NODESIZE];
static char node3[NODESIZE];
static m; /* Maximum branching factor */
static length; /* Length of keys */
static indexfile; /* Handle for index file */
static miscoff; /* Offset of data in miscfile */
static long newnodeptr; /* Pointer to newly created node */
int miscfile;
/* Read data from file with error checking */
void Read (int file,long p,void *buf,int bytes)
{
lseek (file,p,SEEK_SET);
if (read (file,buf,bytes) != bytes)
{
printf ("Read Error\n");
exit (1);
}
}
/* Write data to file with error checking */
void Write (int file,long p,void *buf,int bytes)
{
lseek (file,p,SEEK_SET);
if (write (file,buf,bytes) != bytes)
{
printf ("Write Error\n");
exit (1);
}
}
/* Calculate the maximum branching factor given the key length for the
current index file */
static void calcm (void)
{
m = (NODESIZE + length + sizeof (long) - sizeof (short)) /
(length + 2*sizeof (long));
}
/* Allocate a new node */
static long allocnode (void)
{
long p;
long next;
/* Pointer to first node on free list */
Read (miscfile,miscoff + 3*sizeof (long),&p,sizeof p);
if (p < 0) /* If no nodes on free list, add one to end of file */
return filelength (indexfile);
/* Return first node on free list and update list pointer */
Read (indexfile,p,&next,sizeof next);
Write (miscfile,miscoff + 3*sizeof (long),&next,sizeof next);
return p;
}
/* Add a node to free list */
static void freenode (long t)
{
long p;
Read (miscfile,miscoff + 3*sizeof (long),&p,sizeof p);
Write (indexfile,t,&p,sizeof p);
Write (miscfile,miscoff + 3*sizeof (long),&t,sizeof t);
}
/* Delete a record from linked list of records, and add it to list of
free data records */
void delete (int file,long ptr,void *rec,long _miscoff)
{
long listptr[3];
long next;
long prev;
miscoff = _miscoff;
next = ((long *)rec)[0]; /* Pointer to next record */
prev = ((long *)rec)[1]; /* Pointer to previous record */
/* Remove record from linked list */
if (next >= 0)
Write (file,next + sizeof (long),&prev,sizeof prev);
if (prev >= 0)
Write (file,prev,&next,sizeof next);
Read (miscfile,miscoff,listptr,sizeof listptr);
if (listptr[1] == ptr)
listptr[1] = next;
if (listptr[2] == ptr)
listptr[2] = prev;
/* Add record to free list */
Write (file,ptr,&listptr[0],sizeof listptr[0]);
listptr[0] = ptr;
Write (miscfile,miscoff,listptr,sizeof listptr);
}
/* Delete a data record from an indexed file */
void deleteindex (int file,long ptr,void *rec,long _miscoff,
char *key,int _length,int _indexfile)
{
long t,t2;
int n;
int lo,hi;
int i,j,k;
int c;
int iv[MAXKEY];
long chain[MAXKEY];
indexfile = _indexfile;
miscoff = _miscoff;
length = _length;
calcm ();
/* Delete record from linked list */
delete (file,ptr,rec,miscoff);
t = 0;
n = -1;
for (;;)
{
Read (indexfile,t,node,NODESIZE);
lo = 0;
hi = nentries - 1;
while (lo <= hi)
{
i = (lo + hi) / 2;
c = memicmp (entry (i),key,length);
if (c == 0)
break;
if (c < 0)
lo = i + 1;
else
hi = i - 1;
}
if (c == 0)
break;
n++;
assert (n < MAXKEY);
iv[n] = lo;
chain[n] = t;
t = nodeptr (lo);
assert (t >= 0);
}
if (nodeptr (0) >= 0)
{
t2 = t;
lo++;
n++;
assert (n < MAXKEY);
iv[n] = lo;
chain[n] = t;
t = nodeptr (lo);
assert (t >= 0);
Read (indexfile,t,node,NODESIZE);
do
{
n++;
assert (n < MAXKEY);
iv[n] = 0;
chain[n] = t;
t = nodeptr (0);
assert (t >= 0);
Read (indexfile,t,node,NODESIZE);
}
while (nodeptr (0) >= 0);
Write (indexfile,t2 + (m+lo)*sizeof (long),&recptr (lo),sizeof (long));
Write (indexfile,t2 + m*2*sizeof (long) + lo*length,entry (lo),length);
}
memmove (&nodeptr (lo),&nodeptr (lo + 1),(nentries - lo)*sizeof (long));
memmove (&recptr (lo),&recptr (lo + 1),(nentries - lo - 1)*sizeof (long));
memmove (entry (lo),entry (lo + 1),(nentries - lo - 1)*length);
nentries--;
Write (indexfile,t,node,NODESIZE);
/* While current node has too few entries */
while (nentries < (m - 1) / 2 && n > 0)
{
/* Read father node */
Read (indexfile,chain[n - 1],node3,NODESIZE);
/* Index for father key */
i = iv[n - 1] - 1;
/* If current node is leftmost, merge with right brother */
if (i < 0)
{
/* Read brother node */
t2 = nodeptr3 (1);
Read (indexfile,t2,node2,NODESIZE);
/* If merged node would have few enough entries */
if (nentries + nentries2 < m - 1)
{
/* Move over brother node keys */
memmove (&nodeptr2 (nentries + 1),&nodeptr2 (0),(nentries2 + 1)*sizeof (long));
memmove (&recptr2 (nentries + 1),&recptr2 (0),nentries2*sizeof (long));
memmove (entry2 (nentries + 1),entry2 (0),nentries2*length);
nentries2 += nentries + 1;
/* Copy current node keys into brother node */
memcpy (&nodeptr2 (0),&nodeptr (0),(nentries + 1)*sizeof (long));
memcpy (&recptr2 (0),&recptr (0),nentries*sizeof (long));
memcpy (entry2 (0),entry (0),nentries*length);
/* Put father key into brother node */
recptr2 (nentries) = recptr3 (0);
memcpy (entry2 (nentries),entry3 (0),length);
/* Delete father key from father node */
memmove (&nodeptr3 (0),&nodeptr3 (1),nentries3*sizeof (long));
memmove (&recptr3 (0),&recptr3 (1),(nentries3 - 1)*sizeof (long));
memmove (entry3 (0),entry3 (1),(nentries3 - 1)*length);
nentries3--;
/* Free current node */
freenode (t);
/* If father node is root node and empty, delete it */
if (n == 1 && nentries3 == 0)
{
/* Free prior location of brother node */
freenode (t2);
/* Write brother node into root node's location */
Write (indexfile,0,node2,NODESIZE);
}
else /* Write back nodes */
{
/* Write back brother node */
Write (indexfile,t2,node2,NODESIZE);
/* Write back father node */
Write (indexfile,chain[n - 1],node3,NODESIZE);
}
/* Finish */
break;
}
else /* Redistribute keys between two nodes */
{
/* Middle key to be used as replacement for father key */
j = (nentries2 + nentries) / 2 - nentries - 1;
/* Copy in father key */
recptr (nentries) = recptr3 (0);
memcpy (entry (nentries),entry3 (0),length);
/* Copy keys from brother node to current node */
memcpy (&nodeptr (nentries + 1),&nodeptr2 (0),(j + 1)*sizeof (long));
memcpy (&recptr (nentries + 1),&recptr2 (0),j*sizeof (long));
memcpy (entry (nentries + 1),entry2 (0),j*length);
/* Copy middle key into father node */
recptr3 (0) = recptr2 (j);
memcpy (entry3 (0),entry2 (j),length);
nentries += j + 1;
/* Move down entries in brother node */
memmove (&nodeptr2 (0),&nodeptr2 (j + 1),(nentries2 - j)*sizeof (long));
memmove (&recptr2 (0),&recptr2 (j + 1),(nentries2 - j - 1)*sizeof (long));
memmove (entry2 (0),entry2 (j + 1),(nentries2 - j - 1)*length);
nentries2 -= j + 1;
/* Write back current node */
Write (indexfile,t,node,NODESIZE);
/* Write back brother node */
Write (indexfile,t2,node2,NODESIZE);
/* Write back father node */
Write (indexfile,chain[n - 1],node3,NODESIZE);
/* Step up to father node and continue */
memcpy (node,node3,NODESIZE);
n--;
t = chain[n];
}
}
else /* Merge with left brother */
{
/* Read brother node */
t2 = nodeptr3 (i);
Read (indexfile,t2,node2,NODESIZE);
/* If merged node would have few enough entries */
if (nentries + nentries2 < m - 1)
{
/* Put father key into brother node */
recptr2 (nentries2) = recptr3 (i);
memcpy (entry2 (nentries2),entry3 (i),length);
nentries2++;
/* Merge current node keys into brother node */
memcpy (&nodeptr2 (nentries2),&nodeptr (0),(nentries + 1)*sizeof (long));
memcpy (&recptr2 (nentries2),&recptr (0),nentries*sizeof (long));
memcpy (entry2 (nentries2),entry (0),nentries*length);
nentries2 += nentries;
/* Delete father key from father node */
memmove (&nodeptr3 (i + 1),&nodeptr3 (i + 2),(nentries3 - i)*sizeof (long));
memmove (&recptr3 (i),&recptr3 (i + 1),(nentries3 - i - 1)*sizeof (long));
memmove (entry3 (i),entry3 (i + 1),(nentries3 - i - 1)*length);
nentries3--;
/* Free current node */
freenode (t);
/* Write back brother node */
Write (indexfile,t2,node2,NODESIZE);
/* Write back father node */
Write (indexfile,chain[n - 1],node3,NODESIZE);
/* Finish */
break;
}
else /* Redistribute keys between two nodes */
{
/* Middle key to be used as replacement for father key */
j = (nentries2 + nentries) / 2;
/* Number of keys to transfer from brother to current node */
k = nentries2 - j;
/* Move over keys in current node to make room */
memmove (&nodeptr (k + 1),&nodeptr (0),(nentries + 1)*sizeof (long));
memmove (&recptr (k + 1),&recptr (0),nentries*sizeof (long));
memmove (entry (k + 1),entry (0),nentries*length);
nentries += k + 1;
/* Copy in father key */
recptr (k) = recptr3 (i);
memcpy (entry (k),entry3 (i),length);
/* Copy keys from brother node to current node */
memcpy (&nodeptr (0),&nodeptr2 (j + 1),(k + 1)*sizeof (long));
memcpy (&recptr (0),&recptr2 (j + 1),k*sizeof (long));
memcpy (entry (0),entry2 (j + 1),k*length);
nentries2 -= k + 1;
/* Copy middle key into father node */
recptr3 (i) = recptr2 (j);
memcpy (entry3 (i),entry2 (j),length);
/* Write back current node */
Write (indexfile,t,node,NODESIZE);
/* Write back brother node */
Write (indexfile,t2,node2,NODESIZE);
/* Write back father node */
Write (indexfile,chain[n - 1],node3,NODESIZE);
/* Step up to father node and continue */
memcpy (node,node3,NODESIZE);
n--;
t = chain[n];
}
}
}
}
/* Allocate a new data record, and add to linked list */
void create (int file,long *ptr,void *rec,int size,long _miscoff)
{
long listptr[3];
long p;
miscoff = _miscoff;
Read (miscfile,miscoff,listptr,sizeof listptr);
if (listptr[0] < 0) /* If free list is empty */
p = filelength (file); /* get new record from end of file */
else /* get first record from free list */
{
p = listptr[0];
Read (file,p,listptr,sizeof (long));
}
if (listptr[2] < 0) /* If linked list is empty, initialize it */
{
listptr[1] = p;
listptr[2] = p;
}
else /* add record to linked list */
{
((long *)rec)[1] = listptr[2];
Write (file,listptr[2],&p,sizeof (long));
listptr[2] = p;
}
Write (file,p,rec,size);
Write (miscfile,miscoff,listptr,sizeof listptr);
*ptr = p;
}
/* Recursively insert key in B-tree and return error if any */
static insert (long t,long *rptr,char *rkey,long ptr,char *key)
{
long newptr;
char newkey[MAXKEY];
int lo,hi;
int i,j;
int c;
long n1;
if (t < 0) /* Run out of tree so have to back up */
{
*rptr = ptr;
memcpy (rkey,key,length);
return 0;
}
Read (indexfile,t,node,NODESIZE);
/* Find where to insert new key in current node */
lo = 0;
hi = nentries - 1;
while (lo <= hi)
{
i = (lo + hi) / 2;
c = memicmp (entry (i),key,length);
if (c == 0) /* Key already exists, so return error */
return 1;
if (c < 0)
lo = i + 1;
else
hi = i - 1;
}
/* Recursively insert key below current node */
if (insert (nodeptr (i),&newptr,newkey,ptr,key))
return 1;
/* If insertion has propagated up from node below */
if (newptr >= 0)
{
Read (indexfile,t,node,NODESIZE);
/* Again find key in current node */
lo = 0;
hi = nentries - 1;
while (lo <= hi)
{
i = (lo + hi) / 2;
c = memicmp (entry (i),newkey,length);
assert (c != 0);
if (c < 0)
lo = i + 1;
else
hi = i - 1;
}
if (nentries == m - 1) /* If node is too full, split it */
{
n1 = allocnode ();
j = m / 2;
if (lo <= j)
j--;
*rptr = recptr (j);
memcpy (rkey,entry (j),length);
memmove (&nodeptr (j),&nodeptr (j + 1),(nentries - j)*sizeof (long));
memmove (&recptr (j),&recptr (j + 1),(nentries - j - 1)*sizeof (long));
memmove (entry (j),entry (j + 1),(nentries - j - 1)*length);
if (lo <= j + 1)
j++;
memmove (&nodeptr (lo + 1),&nodeptr (lo),(nentries - lo)*sizeof (long));
memmove (&recptr (lo + 1),&recptr (lo),(nentries - lo - 1)*sizeof (long));
memmove (entry (lo + 1),entry (lo),(nentries - lo - 1)*length);
nodeptr (lo) = newnodeptr;
recptr (lo) = newptr;
memcpy (entry (lo),newkey,length);
nentries = j;
Write (indexfile,n1,node,NODESIZE);
nentries = m - 1 - j;
memcpy (&nodeptr (0),&nodeptr (j),(nentries + 1)*sizeof (long));
memcpy (&recptr (0),&recptr (j),nentries*sizeof (long));
memcpy (entry (0),entry (j),nentries*length);
Write (indexfile,t,node,NODESIZE);
newnodeptr = n1;
return 0;
}
else /* Simply insert in current node */
{
memmove (&nodeptr (lo + 1),&nodeptr (lo),(nentries - lo + 1)*sizeof (long));
memmove (&recptr (lo + 1),&recptr (lo),(nentries - lo)*sizeof (long));
memmove (entry (lo + 1),entry (lo),(nentries - lo)*length);
nodeptr (lo) = newnodeptr;
recptr (lo) = newptr;
memcpy (entry (lo),newkey,length);
nentries++;
Write (indexfile,t,node,NODESIZE);
}
}
*rptr = -1;
return 0;
}
/* Allocate a new data record and insert index key in B-tree */
void createindex (int file,long *ptr,void *rec,int size,long _miscoff,
char *key,int _length,int _indexfile,int x,int y,int directions)
{
long listptr[3];
long p;
long newptr;
char newkey[MAXKEY];
int lo,hi;
int i,j;
int c;
long n1,n2;
long splitptr;
char splitkey[MAXKEY];
indexfile = _indexfile;
miscoff = _miscoff;
length = _length;
calcm ();
Read (miscfile,miscoff,listptr,sizeof listptr);
if (listptr[0] < 0) /* If free list is empty */
p = filelength (file); /* get new record from end of file */
else /* get first record from free list */
{
p = listptr[0];
Read (file,p,listptr,sizeof (long));
}
REDO:
/* Ask user for key value */
editstr (key,length,x,y,directions);
if (dir == DIR_ESC) /* User hit ESC, so cancel */
{
*ptr = -1;
return;
}
if (filelength (indexfile)) /* If index file not empty */
{
newnodeptr = -1;
if (insert (0,&newptr,newkey,p,key))
{
beep ();
goto REDO;
}
if (newptr >= 0)
{
Read (indexfile,0,node,NODESIZE);
lo = 0;
hi = nentries - 1;
while (lo <= hi)
{
i = (lo + hi) / 2;
c = memicmp (entry (i),newkey,length);
assert (c != 0);
if (c < 0)
lo = i + 1;
else
hi = i - 1;
}
if (nentries == m - 1)
{
n1 = allocnode ();
n2 = allocnode ();
j = m / 2;
if (lo <= j)
j--;
splitptr = recptr (j);
memcpy (splitkey,entry (j),length);
memmove (&nodeptr (j),&nodeptr (j + 1),(nentries - j)*sizeof (long));
memmove (&recptr (j),&recptr (j + 1),(nentries - j - 1)*sizeof (long));
memmove (entry (j),entry (j + 1),(nentries - j - 1)*length);
if (lo <= j + 1)
j++;
memmove (&nodeptr (lo + 1),&nodeptr (lo),(nentries - lo)*sizeof (long));
memmove (&recptr (lo + 1),&recptr (lo),(nentries - lo - 1)*sizeof (long));
memmove (entry (lo + 1),entry (lo),(nentries - lo - 1)*length);
nodeptr (lo) = newnodeptr;
recptr (lo) = newptr;
memcpy (entry (lo),newkey,length);
nentries = j;
Write (indexfile,n1,node,NODESIZE);
nentries = m - 1 - j;
memcpy (&nodeptr (0),&nodeptr (j),(nentries + 1)*sizeof (long));
memcpy (&recptr (0),&recptr (j),nentries*sizeof (long));
memcpy (entry (0),entry (j),nentries*length);
Write (indexfile,n2,node,NODESIZE);
nentries = 1;
nodeptr (0) = n1;
nodeptr (1) = n2;
recptr (0) = splitptr;
memcpy (entry (0),splitkey,length);
}
else
{
memmove (&nodeptr (lo + 1),&nodeptr (lo),(nentries - lo + 1)*sizeof (long));
memmove (&recptr (lo + 1),&recptr (lo),(nentries - lo)*sizeof (long));
memmove (entry (lo + 1),entry (lo),(nentries - lo)*length);
nodeptr (lo) = newnodeptr;
recptr (lo) = newptr;
memcpy (entry (lo),newkey,length);
nentries++;
}
Write (indexfile,0,node,NODESIZE);
}
}
else /* Special case for no existing keys */
{
memset (node,0xff,sizeof node);
nentries = 1;
recptr (0) = p;
memcpy (entry (0),key,length);
Write (indexfile,0,node,sizeof node);
}
if (listptr[2] < 0) /* If linked list is empty, initialize it */
{
listptr[1] = p;
listptr[2] = p;
}
else /* add record to linked list */
{
((long *)rec)[1] = listptr[2];
Write (file,listptr[2],&p,sizeof (long));
listptr[2] = p;
}
Write (file,p,rec,size);
Write (miscfile,miscoff,listptr,sizeof listptr);
*ptr = p;
}
/* Find data record in file given key value */
void find (int file,int _indexfile,long *ptr,void *rec,int size,int _length,
char *key)
{
int lo,hi,i,c;
indexfile = _indexfile;
length = _length;
calcm ();
*ptr = -1;
if (filelength (indexfile) == 0) /* Special case for no keys in index */
return;
Read (indexfile,0,node,NODESIZE);
for (;;)
{
/* Try to find key in current node */
lo = 0;
hi = nentries - 1;
while (lo <= hi)
{
i = (lo + hi) / 2;
c = memicmp (entry (i),key,length);
if (c == 0) /* Found key, so read data record */
{
*ptr = recptr (i);
Read (file,*ptr,rec,size);
return;
}
if (c < 0)
lo = i + 1;
else
hi = i - 1;
}
if (nodeptr (i) < 0) /* Bottom of tree, so give up */
return;
Read (indexfile,nodeptr (i),node,NODESIZE);
}
}
/* Get key value from user and try to find corresponding data record */
void select (int file,int _indexfile,long *ptr,void *rec,int size,char *key,
int _length,int x,int y,int directions)
{
indexfile = _indexfile;
length = _length;
REDO:
/* Ask user for key value */
editstr (key,length,x,y,directions);
if (dir == DIR_ESC) /* User hit ESC, so cancel */
return;
find (file,indexfile,ptr,rec,size,length,key);
if (*ptr < 0) /* not found, so ask user for new key value */
{
beep ();
goto REDO;
}
}
/* Link a data record onto another one */
void reclink (int fromfile,long fromptr,long *fromptrs,int fromoffset,
int tofile,long toptr,long *toptrs,int tooffset)
{
fromptrs[0] = toptr;
fromptrs[2] = toptrs[1];
if (toptrs[1] < 0)
toptrs[0] = toptrs[1] = fromptr;
else
{
Write (fromfile,toptrs[1] + fromoffset + sizeof (long),&fromptr,sizeof (long));
toptrs[1] = fromptr;
}
}
/* Unlink a data record from another one */
void recunlink (int fromfile,long fromptr,long *fromptrs,int fromoffset,
int tofile,long toptr,long *toptrs,int tooffset)
{
if (toptrs[0] == fromptr)
toptrs[0] = fromptrs[1];
else
Write (fromfile,fromptrs[2] + fromoffset + sizeof (long),&fromptrs[1],sizeof (long));
if (toptrs[1] == fromptr)
toptrs[1] = fromptrs[2];
else
Write (fromfile,fromptrs[1] + fromoffset + 2*sizeof (long),&fromptrs[2],sizeof (long));
fromptrs[0] = fromptrs[1] = fromptrs[2] = -1;
}
/* Open a file if it exists, otherwise create it, with error checking */
opencreate (char *filename)
{
int f;
f = open (filename,O_RDWR);
if (f >= 0)
return f;
f = open (filename,O_CREAT | O_TRUNC | O_RDWR,0777);
if (f < 0)
{
printf ("Can't create file %s.\n",filename);
exit (1);
}
return f;
}
/* Functions to initialize data in miscfile */
void mwrite (void *buf,int bytes)
{
if (write (miscfile,buf,bytes) != bytes)
{
printf ("Error writing to file misc.dat\n");
exit (1);
}
}
void mblank3 (void)
{
static long data[] = { -1,-1,-1 };
mwrite (data,sizeof data);
}
void mblank4 (void)
{
static long data[] = { -1,-1,-1,-1 };
mwrite (data,sizeof data);
}
Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!
This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.
But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/