Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/5/84; site yetti.UUCP
Path: utzoo!utcs!mnetor!yetti!oz
From: oz@yetti.UUCP (Ozan Yigit)
Newsgroups: net.sources
Subject: a small dbms (reposting sources) 3 of 3
Message-ID: <247@yetti.UUCP>
Date: Mon, 2-Sep-85 16:43:34 EDT
Article-I.D.: yetti.247
Posted: Mon Sep  2 16:43:34 1985
Date-Received: Mon, 2-Sep-85 19:16:25 EDT
Reply-To: oz@yetti.UUCP (Ozan Yigit)
Organization: York University Computer Science
Lines: 1520
Keywords: dbms

---------------- SNIP ----------- SNIP -------------- SNIP --------
#!/bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #!/bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create the files:
#	sdb.c
#	sel.c
#	srt.c
#	tbl.c
#	sdbio.h
# This archive created: Mon Sep  2 16:31:17 1985
export PATH; PATH=/bin:$PATH
echo shar: extracting "'sdb.c'" '(367 characters)'
if test -f 'sdb.c'
then
	echo shar: over-writing existing file "'sdb.c'"
fi
sed 's/^X//' << \SHAR_EOF > 'sdb.c'
X/* SDB - main routine */
X
X#include "stdio.h"
X#include "sdbio.h"
X
Xextern int dbv_errcode;
X
Xmain()
X{
X    printf("SDB - version 2.0\n");
X    db_sinit();
X    db_ifile("sdb.ini");
X
X    while (TRUE) {
X        db_prompt("SDB> ","\t> ");
X        if (!db_parse(NULL)) {
X            printf("** error: %s ***\n",db_ertxt(dbv_errcode));
X            db_kill();
X        }
X    }
X}
X
SHAR_EOF
if test 367 -ne "`wc -c 'sdb.c'`"
then
	echo shar: error transmitting "'sdb.c'" '(should have been 367 characters)'
fi
echo shar: extracting "'sel.c'" '(20482 characters)'
if test -f 'sel.c'
then
	echo shar: over-writing existing file "'sel.c'"
fi
sed 's/^X//' << \SHAR_EOF > 'sel.c'
X/* SDB - select data from the database */
X
X#include "sdbio.h"
X
Xextern int dbv_token;
Xextern char dbv_tstring[];
Xextern int dbv_tvalue;
X
X/* db_select - select a set of tuples from a set of relations */
Xstruct sel *db_select(fmt,a1,a2,a3,a4,a5,a6,a7,a8,a9)
X  char *fmt;
X{
X    struct sel *slptr;
X
X    /* check for a command line */
X    if (fmt != NULL)
X        db_scan(fmt,a1,a2,a3,a4,a5,a6,a7,a8,a9);
X
X    /* allocate a sel structure */
X    if ((slptr = malloc(sizeof(struct sel))) == NULL)
X        return (db_nerror(INSMEM));
X
X    /* initialize the structure */
X    slptr->sl_rels = NULL;
X    slptr->sl_attrs = NULL;
X    slptr->sl_where = NULL;
X    slptr->sl_bindings = NULL;
X
X    /* parse the list of selected attributes */
X    if (!get_sattrs(slptr)) {
X        db_done(slptr);
X        return (NULL);
X    }
X
X    /* check for "from" clause */
X    if (db_token() == FROM) {
X        db_ntoken();
X        if (!get_srels(slptr)) {
X            db_done(slptr);
X            return (NULL);
X        }
X    }
X    else {
X        if (!srelation(slptr,"sdbcur",NULL)) {
X            db_done(slptr);
X            return (NULL);
X        }
X    }
X
X    /* check the list of selected attributes */
X    if (!check_attrs(slptr)) {
X        db_done(slptr);
X        return (NULL);
X    }
X
X    /* check for the existance of a "where" clause */
X    if (db_token() == WHERE) {
X        db_ntoken();
X
X        /* parse the boolean expression */
X        if (!db_compile(slptr)) {
X            db_done(slptr);
X            return (FALSE);
X        }
X    }
X
X    /* return the new selection structure */
X    return (slptr);
X}
X
X/* db_retrieve - retrieve a set of tuples from a set of relations */
Xstruct sel *db_retrieve(fmt,a1,a2,a3,a4,a5,a6,a7,a8,a9)
X  char *fmt;
X{
X    struct sel *slptr;
X
X    /* check for a command line */
X    if (fmt != NULL)
X        db_scan(fmt,a1,a2,a3,a4,a5,a6,a7,a8,a9);
X
X    /* allocate a sel structure */
X    if ((slptr = malloc(sizeof(struct sel))) == NULL)
X        return (db_nerror(INSMEM));
X
X    /* initialize the structure */
X    slptr->sl_rels = NULL;
X    slptr->sl_attrs = NULL;
X    slptr->sl_where = NULL;
X    slptr->sl_bindings = NULL;
X
X    /* check for selected relations clause */
X    if (db_token() == ID) {
X        if (!get_srels(slptr)) {
X            db_done(slptr);
X            return (NULL);
X        }
X    }
X    else {
X        if (!srelation(slptr,"sdbcur",NULL)) {
X            db_done(slptr);
X            return (NULL);
X        }
X    }
X
X    /* check the list of selected attributes */
X    if (!check_attrs(slptr)) {
X        db_done(slptr);
X        return (NULL);
X    }
X
X    /* check for the existance of a "where" clause */
X    if (db_token() == WHERE) {
X        db_ntoken();
X
X        /* parse the boolean expression */
X        if (!db_compile(slptr)) {
X            db_done(slptr);
X            return (FALSE);
X        }
X    }
X
X    /* return the new selection structure */
X    return (slptr);
X}
X
X/* db_done(slptr) - finish a selection */
Xdb_done(slptr)
X  struct sel *slptr;
X{
X    struct sattr *saptr,*nxtsa;
X    struct srel *srptr,*nxtsr;
X    struct binding *bdptr,*nxtbd;
X
X    /* free the selected attribute blocks */
X    for (saptr = slptr->sl_attrs; saptr != NULL; saptr = nxtsa) {
X        nxtsa = saptr->sa_next;
X        if (saptr->sa_rname != NULL)
X            free(saptr->sa_rname);
X        free(saptr->sa_aname);
X        if (saptr->sa_name != NULL)
X            free(saptr->sa_name);
X        free(saptr);
X    }
X
X    /* close the scans and free the selected relation blocks */
X    for (srptr = slptr->sl_rels; srptr != NULL; srptr = nxtsr) {
X        nxtsr = srptr->sr_next;
X        if (srptr->sr_name != NULL)
X            free(srptr->sr_name);
X        db_rclose(srptr->sr_scan);
X        free(srptr);
X    }
X
X    /* free the where clause */
X    db_fcode(slptr);
X
X    /* free the user bindings */
X    for (bdptr = slptr->sl_bindings; bdptr != NULL; bdptr = nxtbd) {
X        nxtbd = bdptr->bd_next;
X        free(bdptr);
X    }
X
X    /* free the selection structure */
X    free(slptr);
X}
X
X/* db_fetch(slptr) - fetch the next tuple from a selection */
Xint db_fetch(slptr)
X  struct sel *slptr;
X{
X    struct srel *srptr;
X    struct binding *bdptr;
X
X    /* clear the update flags */
X    for (srptr = slptr->sl_rels; srptr != NULL; srptr = srptr->sr_next)
X        srptr->sr_update = FALSE;
X
X    /* find a matching tuple */
X    while (process(slptr->sl_rels))
X        if (db_interpret(slptr)) {
X            for (bdptr = slptr->sl_bindings; bdptr != NULL; bdptr = bdptr->bd_next)
X                db_aget(bdptr->bd_attr,bdptr->bd_vtuple,bdptr->bd_vuser);
X            return (TRUE);
X        }
X
X    /* no matches, failure return */
X    return (FALSE);
X}
X
X/* db_update - update modified tuples */
Xint db_update(slptr)
X  struct sel *slptr;
X{
X    struct srel *srptr;
X
X    /* check each selected relation for updates */
X    for (srptr = slptr->sl_rels; srptr != NULL; srptr = srptr->sr_next)
X        if (srptr->sr_update)
X            if (!db_rupdate(srptr->sr_scan))
X                return (FALSE);
X
X    /* return successfully */
X    return (TRUE);
X}
X
X/* db_store - store tuples */
Xint db_store(slptr)
X  struct sel *slptr;
X{
X    struct srel *srptr;
X
X    /* check each selected relation for stores */
X    for (srptr = slptr->sl_rels; srptr != NULL; srptr = srptr->sr_next)
X        if (srptr->sr_update)
X            if (!db_rstore(srptr->sr_scan))
X                return (FALSE);
X
X    /* return successfully */
X    return (TRUE);
X}
X
X/* db_bind - bind a user buffer to the value of an attribute */
Xint db_bind(slptr,rname,aname,avalue)
X  struct sel *slptr; char *rname,*aname,*avalue;
X{
X    struct binding *newbd;
X    struct srel *srptr;
X
X    /* allocate and initialize a binding structure */
X    if ((newbd = malloc(sizeof(struct binding))) == NULL)
X        return (db_ferror(INSMEM));
X    newbd->bd_vuser = avalue;
X
X    /* find the attribute */
X    if (!find_attr(slptr,rname,aname,&newbd->bd_vtuple,&srptr,&newbd->bd_attr))
X        return (FALSE);
X
X    /* link the new binding into the binding list */
X    newbd->bd_next = slptr->sl_bindings;
X    slptr->sl_bindings = newbd;
X
X    /* return successfully */
X    return (TRUE);
X}
X
X/* db_get - get the value of an attribute */
Xint db_get(slptr,rname,aname,avalue)
X  struct sel *slptr; char *rname,*aname,*avalue;
X{
X    struct srel *srptr;
X    struct attribute *aptr;
X    char *vptr;
X
X    /* find the attribute */
X    if (!find_attr(slptr,rname,aname,&vptr,&srptr,&aptr))
X        return (FALSE);
X
X    /* get the attribute value */
X    db_aget(aptr,vptr,avalue);
X
X    /* return successfully */
X    return (TRUE);
X}
X
X/* db_put - put the value of an attribute */
Xint db_put(slptr,rname,aname,avalue)
X  struct sel *slptr; char *rname,*aname,*avalue;
X{
X    struct srel *srptr;
X    struct attribute *aptr;
X    char *vptr;
X
X    /* find the attribute */
X    if (!find_attr(slptr,rname,aname,&vptr,&srptr,&aptr))
X        return (FALSE);
X
X    /* put the attribute value */
X    db_aput(aptr,vptr,avalue);
X
X    /* mark the tuple as updated */
X    srptr->sr_update = TRUE;
X
X    /* return successfully */
X    return (TRUE);
X}
X
X/* db_sattr - get selected attribute type, pointer, and length */
Xint db_sattr(slptr,rname,aname,ptype,pptr,plen)
X  struct sel *slptr; char *rname,*aname;
X  int *ptype; char **pptr; int *plen;
X{
X    struct srel *srptr;
X    struct attribute *aptr;
X
X    if (!find_attr(slptr,rname,aname,pptr,&srptr,&aptr))
X        return (FALSE);
X    *ptype = aptr->at_type;
X    *plen = aptr->at_size;
X    return (TRUE);
X}
X
X/* get_sattrs(slptr) - get selected attributes */
Xstatic get_sattrs(slptr)
X  struct sel *slptr;
X{
X    struct sattr *newsattr,*lastsattr;
X
X    /* check for "*" or blank field meaning all attributes are selected */
X    if (db_token() == '*') {
X        db_ntoken();
X        return (TRUE);
X    }
X    else if (db_token() != ID)
X        return (TRUE);
X
X    /* parse a list of attribute names */
X    lastsattr = NULL;
X    while (TRUE) {
X
X        /* get attribute name */
X        if (db_ntoken() != ID)
X            return (db_ferror(SYNTAX));
X
X        /* allocate a selected attribute structure */
X        if ((newsattr = malloc(sizeof(struct sattr))) == NULL)
X            return (db_ferror(INSMEM));
X
X        /* initialize the selected attribute structure */
X        newsattr->sa_next = NULL;
X
X        /* save the attribute name */
X        if ((newsattr->sa_aname = malloc(strlen(dbv_tstring)+1)) == NULL) {
X            free(newsattr);
X            return (db_ferror(INSMEM));
X        }
X        strcpy(newsattr->sa_aname,dbv_tstring);
X
X        /* check for "." meaning "<rel-name>.<att-name>" */
X        if (db_token() == '.') {
X            db_ntoken();
X
X            /* the previous ID was really the relation name */
X            newsattr->sa_rname = newsattr->sa_aname;
X
X            /* check for attribute name */
X            if (db_ntoken() != ID) {
X                free(newsattr->sa_aname); free(newsattr);
X                return (db_ferror(SYNTAX));
X            }
X
X            /* save the attribute name */
X            if ((newsattr->sa_aname = malloc(strlen(dbv_tstring)+1)) == NULL) {
X                free(newsattr->sa_aname); free(newsattr);
X                return (db_ferror(INSMEM));
X            }
X            strcpy(newsattr->sa_aname,dbv_tstring);
X        }
X        else
X            newsattr->sa_rname = NULL;
X
X        /* check for alternate attribute name */
X        if (db_token() == ID) {
X            db_ntoken();
X
X            /* allocate space for the alternate name */
X            if ((newsattr->sa_name = malloc(strlen(dbv_tstring)+1)) == NULL) {
X                if (newsattr->sa_rname != NULL)
X                    free(newsattr->sa_rname);
X                free(newsattr->sa_aname);
X                free(newsattr);
X                return (db_ferror(INSMEM));
X            }
X            strcpy(newsattr->sa_name,dbv_tstring);
X        }
X        else
X            newsattr->sa_name = NULL;
X
X        /* link the selected attribute structure into the list */
X        if (lastsattr == NULL)
X            slptr->sl_attrs = newsattr;
X        else
X            lastsattr->sa_next = newsattr;
X        lastsattr = newsattr;
X
X        /* check for more attributes */
X        if (db_token() != ',')
X            break;
X        db_ntoken();
X    }
X
X    /* return successfully */
X    return (TRUE);
X}
X
X/* get_srels(slptr) - get selected relations */
Xstatic get_srels(slptr)
X  struct sel *slptr;
X{
X    char rname[KEYWORDMAX+1],*aname;
X
X    /* get the list of selected relations */
X    while (TRUE) {
X
X        /* check for relation name */
X        if (db_ntoken() != ID)
X            return (db_ferror(SYNTAX));
X        strcpy(rname,dbv_tstring);
X
X        /* check for alternate relation name */
X        if (db_token() == ID) {
X            db_ntoken();
X            aname = dbv_tstring;
X        }
X        else
X            aname = NULL;
X
X        /* add the relation name to the list */
X        if (!srelation(slptr,rname,aname))
X            return (FALSE);
X
X        /* check for more selected relations */
X        if (db_token() != ',')
X            break;
X        db_ntoken();
X    }
X
X    /* return successfully */
X    return (TRUE);
X}
X
X/* srelation - select a relation */
Xstatic srelation(slptr,rname,aname)
X  struct sel *slptr; char *rname,*aname;
X{
X    struct srel *srptr,*newsrel;
X
X    /* allocate a new selected relation structure */
X    if ((newsrel = malloc(sizeof(struct srel))) == NULL)
X        return (db_ferror(INSMEM));
X
X    /* initialize the new selected relation structure */
X    newsrel->sr_ctuple = FALSE;
X    newsrel->sr_update = FALSE;
X    newsrel->sr_next = NULL;
X
X    /* open the relation */
X    if ((newsrel->sr_scan = db_ropen(rname)) == NULL) {
X        free(newsrel);
X        return (FALSE);
X    }
X
X    /* check for alternate relation name */
X    if (aname != NULL) {
X
X        /* allocate space for the alternate name */
X        if ((newsrel->sr_name = malloc(strlen(aname)+1)) == NULL) {
X            free(newsrel);
X            return (db_ferror(INSMEM));
X        }
X        strcpy(newsrel->sr_name,aname);
X    }
X    else
X        newsrel->sr_name = NULL;
X
X    /* find the end of the list of relation names */
X    for (srptr = slptr->sl_rels; srptr != NULL; srptr = srptr->sr_next)
X        if (srptr->sr_next == NULL)
X            break;
X
X    /* link the new selected relation structure into the list */
X    if (srptr == NULL)
X        slptr->sl_rels = newsrel;
X    else
X        srptr->sr_next = newsrel;
X
X    /* return successfully */
X    return (TRUE);
X}
X
X/* check_attrs(slptr) - check the list of selected attributes */
Xstatic int check_attrs(slptr)
X  struct sel *slptr;
X{
X    struct sattr *saptr;
X
X    /* check for all attributes selected */
X    if (slptr->sl_attrs == NULL)
X        return (all_attrs(slptr));
X
X    /* check each selected attribute */
X    for (saptr = slptr->sl_attrs; saptr != NULL; saptr = saptr->sa_next)
X        if (!find_attr(slptr,saptr->sa_rname,saptr->sa_aname,
X                        &saptr->sa_aptr,&saptr->sa_srel,&saptr->sa_attr))
X            return (FALSE);
X
X    /* return successfully */
X    return (TRUE);
X}
X
X/* all_attrs(slptr) - create a list of all attributes */
Xstatic int all_attrs(slptr)
X  struct sel *slptr;
X{
X    struct sattr *newsattr,*lastsattr;
X    struct srel *srptr;
X    struct attribute *aptr;
X    int i,astart;
X
X    /* loop through each selected relation */
X    lastsattr = NULL;
X    for (srptr = slptr->sl_rels; srptr != NULL; srptr = srptr->sr_next) {
X
X        /* loop through each attribute within the relation */
X        astart = 1;
X        for (i = 0; i < NATTRS; i++) {
X
X            /* get a pointer to the current attribute */
X            aptr = &srptr->sr_scan->sc_relation->rl_header.hd_attrs[i];
X
X            /* check for last attribute */
X            if (aptr->at_name[0] == 0)
X                break;
X
X            /* allocate a new selected attribute structure */
X            if ((newsattr = malloc(sizeof(struct sattr))) == NULL)
X                return (db_ferror(INSMEM));
X
X            /* initialize the new selected attribute structure */
X            newsattr->sa_name = NULL;
X            newsattr->sa_srel = srptr;
X            newsattr->sa_aptr = srptr->sr_scan->sc_tuple + astart;
X            newsattr->sa_attr = aptr;
X            newsattr->sa_next = NULL;
X
X            /* save the relation name */
X            if ((newsattr->sa_rname = malloc(RNSIZE+1)) == NULL) {
X                free(newsattr);
X                return (db_ferror(INSMEM));
X            }
X            strncpy(newsattr->sa_rname,
X                    srptr->sr_scan->sc_relation->rl_name,
X                    RNSIZE);
X            newsattr->sa_rname[RNSIZE] = 0;
X
X            /* save the attribute name */
X            if ((newsattr->sa_aname = malloc(ANSIZE+1)) == NULL) {
X                free(newsattr->sa_rname);
X                free(newsattr);
X                return (db_ferror(INSMEM));
X            }
X            strncpy(newsattr->sa_aname,
X                    srptr->sr_scan->sc_relation->rl_header.hd_attrs[i].at_name,
X                    ANSIZE);
X            newsattr->sa_aname[ANSIZE] = 0;
X
X            /* link the selected attribute into the list */
X            if (lastsattr == NULL)
X                slptr->sl_attrs = newsattr;
X            else
X                lastsattr->sa_next = newsattr;
X            lastsattr = newsattr;
X
X            /* update the attribute start */
X            astart += aptr->at_size;
X        }
X    }
X
X    /* return successfully */
X    return (TRUE);
X}
X
X/* find_attr - find a named attribute */
Xstatic int find_attr(slptr,rname,aname,paptr,psrel,pattr)
X  struct sel *slptr; char *rname,*aname;
X  char **paptr; struct attribute **pattr;
X{
X    /* check for unqualified or qualified attribute names */
X    if (rname == NULL)
X        return (uattr(slptr,aname,paptr,psrel,pattr));
X    else
X        return (qattr(slptr,rname,aname,paptr,psrel,pattr));
X}
X
X/* uattr - find an unqualified attribute name */
Xstatic int uattr(slptr,aname,paptr,psrel,pattr)
X  struct sel *slptr; char *aname;
X  char **paptr; struct srel **psrel; struct attribute **pattr;
X{
X    struct srel *srptr;
X    struct attribute *aptr;
X    int i,astart;
X
X    /* loop through each selected relation */
X    *pattr = NULL;
X    for (srptr = slptr->sl_rels; srptr != NULL; srptr = srptr->sr_next) {
X
X        /* loop through each attribute within the relation */
X        astart = 1;
X        for (i = 0; i < NATTRS; i++) {
X
X            /* get a pointer to the current attribute */
X            aptr = &srptr->sr_scan->sc_relation->rl_header.hd_attrs[i];
X
X            /* check for last attribute */
X            if (aptr->at_name[0] == 0)
X                break;
X
X            /* check for attribute name match */
X            if (db_sncmp(aname,aptr->at_name,ANSIZE) == 0) {
X                if (*pattr != NULL)
X                    return (db_ferror(ATAMBG));
X                *paptr = srptr->sr_scan->sc_tuple + astart;
X                *psrel = srptr;
X                *pattr = aptr;
X            }
X
X            /* update the attribute start */
X            astart += aptr->at_size;
X        }
X    }
X
X    /* check whether attribute was found */
X    if (*pattr == NULL)
X        return (db_ferror(ATUNDF));
X
X    /* return successfully */
X    return (TRUE);
X}
X
X/* qattr - find a qualified attribute name */
Xstatic int qattr(slptr,rname,aname,paptr,psrel,pattr)
X  struct sel *slptr; char *rname,*aname;
X  char **paptr; struct srel **psrel; struct attribute **pattr;
X{
X    struct srel *srptr;
X    struct attribute *aptr;
X    char *crname;
X    int i,astart;
X
X    /* loop through each selected relation */
X    for (srptr = slptr->sl_rels; srptr != NULL; srptr = srptr->sr_next) {
X
X        /* get relation name */
X        if ((crname = srptr->sr_name) == NULL)
X            crname = srptr->sr_scan->sc_relation->rl_name;
X
X        /* check for relation name match */
X        if (db_sncmp(rname,crname,RNSIZE) == 0) {
X
X            /* loop through each attribute within the relation */
X            astart = 1;
X            for (i = 0; i < NATTRS; i++) {
X
X                /* get a pointer to the current attribute */
X                aptr = &srptr->sr_scan->sc_relation->rl_header.hd_attrs[i];
X
X                /* check for last attribute */
X                if (aptr->at_name[0] == 0)
X                    break;
X
X                /* check for attribute name match */
X                if (db_sncmp(aname,aptr->at_name,ANSIZE) == 0) {
X                    *paptr = srptr->sr_scan->sc_tuple + astart;
X                    *psrel = srptr;
X                    *pattr = aptr;
X                    return (TRUE);
X                }
X
X                /* update the attribute start */
X                astart += aptr->at_size;
X            }
X
X            /* attribute name not found */
X            return (db_ferror(ATUNDF));
X        }
X    }
X
X    /* relation name not found */
X    return (db_ferror(RLUNDF));
X}
X
X/* process(srptr) - process each tuple in a relation cross-product */
Xstatic int process(srptr)
X  struct srel *srptr;
X{
X    /* always get a new tuple if this is the last relation in the list */
X    if (srptr->sr_next == NULL) {
X
X        /* check for beginning of new scan */
X        if (!srptr->sr_ctuple)
X            db_rbegin(srptr->sr_scan);
X
X        /* return the next tuple in the relation */
X        return (srptr->sr_ctuple = db_rfetch(srptr->sr_scan));
X    }
X
X    /* check for beginning of new scan */
X    if (!srptr->sr_ctuple) {
X        db_rbegin(srptr->sr_scan);
X
X        /* get the first tuple */
X        if (!db_rfetch(srptr->sr_scan))
X            return (FALSE);
X    }
X
X    /* look for a match with the remaining relations in list */
X    while (!process(srptr->sr_next))
X
X        /* get the next tuple in the scan */
X        if (!db_rfetch(srptr->sr_scan))
X            return (srptr->sr_ctuple = FALSE);
X
X    /* found a match at this level */
X    return (srptr->sr_ctuple = TRUE);
X}
X
X/* db_aget - get the value of an attribute */
Xdb_aget(aptr,vptr,avalue)
X  struct attribute *aptr; char *vptr,*avalue;
X{
X    int i;
X
X    /* get the attribute value */
X    for (i = 0; i < aptr->at_size; i++)
X        *avalue++ = vptr[i];
X    *avalue = EOS;
X}
X
X/* db_aput - put the value of an attribute */
Xdb_aput(aptr,vptr,avalue)
X  struct attribute *aptr; char *vptr,*avalue;
X{
X    int i;
X
X    /* initialize counter */
X    i = 0;
X
X    /* right justify numbers */
X    if (aptr->at_type == TNUM)
X        for (; i < aptr->at_size - strlen(avalue); i++)
X            vptr[i] = ' ';
X
X    /* put the attribute value */
X    for (; i < aptr->at_size; i++)
X        if (*avalue == 0)
X            vptr[i] = 0;
X        else
X            vptr[i] = *avalue++;
X}
X
SHAR_EOF
if test 20482 -ne "`wc -c 'sel.c'`"
then
	echo shar: error transmitting "'sel.c'" '(should have been 20482 characters)'
fi
echo shar: extracting "'srt.c'" '(8289 characters)'
if test -f 'srt.c'
then
	echo shar: over-writing existing file "'srt.c'"
fi
sed 's/^X//' << \SHAR_EOF > 'srt.c'
X/* SDB - sort routines */
X
X#include "stdio.h"
X#include "sdbio.h"
X
Xextern int dbv_token;
Xextern char dbv_tstring[];
Xextern int dbv_tvalue;
X
X/* get_skeys - get sort key list */
Xstatic struct skey *get_skeys(sptr)
X  struct scan *sptr;
X{
X    struct skey *skeys,*newskey,*lastskey;
X
X    /* parse a list of attribute names */
X    skeys = lastskey = NULL;
X    while (TRUE) {
X
X        /* get attribute name */
X        if (db_ntoken() != ID)
X            return (db_nerror(SYNTAX));
X
X        /* allocate a sort key structure */
X        if ((newskey = malloc(sizeof(struct skey))) == NULL)
X            return (db_nerror(INSMEM));
X
X        /* initialize the sort key structure */
X        newskey->sk_next = NULL;
X
X        /* lookup the attribute name */
X        if (!find_attr(sptr,newskey,dbv_tstring)) {
X            free(newskey);
X            return (NULL);
X        }
X
X        /* check for ascending or descending */
X        if (db_token() == ASCENDING || dbv_token == DESCENDING) {
X            newskey->sk_type = dbv_token;
X            db_ntoken();
X        }
X        else
X            newskey->sk_type = ASCENDING;
X
X        /* link the sort key structure into the list */
X        if (lastskey == NULL)
X            skeys = newskey;
X        else
X            lastskey->sk_next = newskey;
X        lastskey = newskey;
X
X        /* check for more attributes */
X        if (db_token() != ',')
X            break;
X        db_ntoken();
X    }
X
X    /* return successfully */
X    return (skeys);
X}
X
X/* db_sort - sort tuples in a relation */
Xint *db_sort(fmt,a1,a2,a3,a4,a5,a6,a7,a8,a9)
X  char *fmt;
X{
X    struct scan *sptr1,*sptr2,*sptr3;   /*dns*/
X    struct skey *skeys;
X    int result;
X
X    /* check for a command line */
X    if (fmt != NULL)
X        db_scan(fmt,a1,a2,a3,a4,a5,a6,a7,a8,a9);
X
X    /* checks for relation name */
X    if (db_token() == ID)
X        db_ntoken();
X    else
X        strcpy(dbv_tstring,"sdbcur");
X
X    /* open the relation */
X    if ((sptr1 = db_ropen(dbv_tstring)) == NULL)
X        return (FALSE);
X    if ((sptr2 = db_ropen(dbv_tstring)) == NULL) {
X        db_rclose(sptr1);
X        return (FALSE);
X        }
X    if ((sptr3 = db_ropen(dbv_tstring)) == NULL) {   /*dns*/
X        db_rclose(sptr1);                            /*dns*/
X        db_rclose(sptr2);                            /*dns*/
X        return (FALSE);                              /*dns*/
X        }
X
X    /* checks for "<relation-name> by <sort-list>" */
X    if (db_ntoken() != BY)
X        return (db_ferror(SYNTAX));
X    if ((skeys = get_skeys(sptr1)) == NULL) {
X        db_rclose(sptr1);
X        db_rclose(sptr2);
X        db_rclose(sptr3);  /*dns*/
X        return (FALSE);
X       }
X
X    /* do the sort */
X    result = sort(skeys,sptr1,sptr2,sptr3);  /*dns*/
X
X    /* close the relation */
X    db_rclose(sptr1);
X    db_rclose(sptr2);
X    db_rclose(sptr3);     /*dns*/
X
X    /* free the sort keys */
X    free_skeys(skeys);
X
X    return (result);
X}
X
X/* free_skeys - free a list of sort keys */
Xstatic free_skeys(skeys)
X  struct skey *skeys;
X{
X    struct skey *thisskey;
X
X    for (thisskey = skeys; skeys != NULL; thisskey = skeys) {
X        skeys = skeys->sk_next;
X        free(thisskey);
X    }
X}
X
X/* find_attr - find an attribute */
Xstatic int find_attr(sptr,newskey,aname)
X  struct scan *sptr; struct skey *newskey; char *aname;
X{
X    struct attribute *aptr;
X    int i,astart;
X
X    /* loop through each attribute within the relation */
X    astart = 1;
X    for (i = 0; i < NATTRS; i++) {
X
X        /* get a pointer to the current attribute */
X        aptr = &sptr->sc_relation->rl_header.hd_attrs[i];
X
X        /* check for last attribute */
X        if (aptr->at_name[0] == 0)
X            break;
X
X        /* check for attribute name match */
X        if (db_sncmp(aname,aptr->at_name,ANSIZE) == 0) {
X            newskey->sk_start = astart;
X            newskey->sk_aptr = aptr;
X            return (TRUE);
X        }
X
X        /* update the attribute start */
X        astart += aptr->at_size;
X    }
X
X    /* attribute name not found */
X    return (db_ferror(ATUNDF));
X}
X
X/* sort - sort the relation */
Xstatic int sort(skeys,sptr1,sptr2,sptr3)
X  struct skey *skeys; struct scan *sptr1,*sptr2,*sptr3;
X{
X/*  unsigned int j,k,l,r;          dns */
X    long int passes,swaps;           /*dns*/
X    int i, j, m, n;         /*dns*/
X    int rec1 = 0;           /*dns*/
X    int rec2 = 0;           /*dns*/
X    int rec3 = 0;           /*dns*/
X    int dns = 0;            /*dns*/
X    FILE *test;             /*dns*/
X
X    passes = 0L;
X    swaps = 0L;
X
X    /*dns --->   */
X    test = fopen("sort.dat", "w");
X    n = sptr1->sc_relation->rl_tcnt;
X    m = n;
X
X    while( m>1 )   {
X       passes++;
X       if ((m/=3.14159) < 1)  m = 1;
X       for ( j=1; j<=n-m; j++ )  {
X          if( rec1 != j+m )  {
X             if(dns) fprintf(test,"Read1: %d\n", j+m);
X             if (!db_rget(sptr1, rec1=j+m))  return (FALSE);
X             }
X          for ( i=j; i>=1; i-=m ) {
X             if( rec2 != i )   {
X                if(dns) fprintf(test,"Read2: %d\n", i);
X                if (!db_rget(sptr2, rec2=i))  return (FALSE);
X                }
X             if (compare(skeys,sptr1,sptr2) > 0)
X                break;
X             if(rec3 != i+m)  {
X                if(dns) fprintf(test,"Read3: %d\n", i+m);
X                if (!db_rget(sptr3, rec3=i+m))  return (FALSE);
X                }
X             if(dns) fprintf(test,"Write 3,2: %d from %d\n", i+m, i);
X             assign( sptr3, sptr2 );
X             swaps++;
X             }
X          if(rec1 != i+m)  {
X             if(rec3 != i+m)  {
X                if(dns) fprintf(test,"Read 3: %d\n", i+m);
X                if (!db_rget(sptr3, rec3=i+m))  return (FALSE);
X                }
X             if(dns) fprintf(test,"Write 3,1: %d from %d\n", i+m, j+m);
X             assign( sptr3, sptr1 );
X             swaps++;
X             }
X          }
X       }
X       fclose(test);
X
X/*
X    l = 2;
X    r = sptr1->sc_relation->rl_tcnt;
X    k = r;
X
X    do {
X        for (j = r; j >= l; j--) {
X            if (!db_rget(sptr1,j-1))
X                return (FALSE);
X            if (!db_rget(sptr2,j))
X                return (FALSE);
X            if (compare(skeys,sptr1,sptr2) > 0) {
X                swap(sptr1,sptr2);
X                k = j;
X                swaps++;
X            }
X        }
X        l = k + 1;
X        for (j = l; j <= r; j++) {
X            if (!db_rget(sptr1,j-1))
X                return (FALSE);
X            if (!db_rget(sptr2,j))
X                return (FALSE);
X            if (compare(skeys,sptr1,sptr2) > 0) {
X                swap(sptr1,sptr2);
X                k = j;
X                swaps++;
X            }
X        }
X        r = k - 1;
X        passes++;
X    } while (l <= r);
X*/
X
X    printf("[ Passes: %ld  Swaps: %ld ]\n",passes,swaps);
X
X    return (TRUE);
X}
X
X/* compare - compare two tuples */
Xstatic int compare(skeys,sptr1,sptr2)
X  struct skey *skeys; struct scan *sptr1,*sptr2;
X{
X    struct skey *cskey;
X    int result;
X
X    for (cskey = skeys; cskey != NULL; cskey = cskey->sk_next)
X        if ((result = cattr(cskey,sptr1,sptr2)) != 0)
X            break;
X
X    return (result);
X}
X
X/* cattr - compare two attributes */
Xstatic int cattr(cskey,sptr1,sptr2)
X  struct skey *cskey; struct scan *sptr1,*sptr2;
X{
X    int astart,aend,i;
X
X    astart = cskey->sk_start;
X    aend = astart + cskey->sk_aptr->at_size;
X
X    for (i = astart; i < aend; i++)
X        if (sptr1->sc_tuple[i] != sptr2->sc_tuple[i])
X            break;
X
X    if (i == aend)
X        return (0);
X
X    if (sptr1->sc_tuple[i] < sptr2->sc_tuple[i])
X        if (cskey->sk_type == ASCENDING)
X            return (-1);
X        else
X            return (1);
X    else
X        if (cskey->sk_type == ASCENDING)
X            return (1);
X        else
X            return (-1);
X}
X
X/* swap - swap two tuples */
X/* dns
Xstatic int swap(sptr1,sptr2)
X  struct scan *sptr1,*sptr2;
X{
X    unsigned int tnum1,tnum2;
X
X    tnum1 = sptr1->sc_atnum;
X    tnum2 = sptr2->sc_atnum;
X
X    if (!db_rput(sptr1,tnum2))
X        return (FALSE);
X    if (!db_rput(sptr2,tnum1))
X        return (FALSE);
X
X    return (TRUE);
X}
X  dns  */
X
X
X/* assign - assign one tupple to another */
Xstatic int assign(sptr1,sptr2)
X  struct scan *sptr1,*sptr2;
X{
X    unsigned int tnum1,tnum2;
X
X    tnum1 = sptr1->sc_atnum;
X
X    if (!db_rput(sptr2,tnum1))
X        return (FALSE);
X
X    return (TRUE);
X}
X
SHAR_EOF
if test 8289 -ne "`wc -c 'srt.c'`"
then
	echo shar: error transmitting "'srt.c'" '(should have been 8289 characters)'
fi
echo shar: extracting "'tbl.c'" '(2554 characters)'
if test -f 'tbl.c'
then
	echo shar: over-writing existing file "'tbl.c'"
fi
sed 's/^X//' << \SHAR_EOF > 'tbl.c'
X/* SDB - table output routines */
X
X#include "stdio.h"
X#include "sdbio.h"
X
Xstatic char buffer[TABLEMAX+1];
Xint bndx;
X
X/* db_thead - print a table header */
Xdb_thead(fp,slptr)
X  FILE *fp; struct sel *slptr;
X{
X    struct sattr *saptr;
X    int twidth,fwidth,i;
X    char *aname;
X
X    /* compute the table width */
X    twidth = 1;
X    for (saptr = slptr->sl_attrs; saptr != NULL; saptr = saptr->sa_next)
X        twidth += saptr->sa_attr->at_size + 3;
X
X    /* print the top line of the table */
X    bstart();
X    for (i = 0; i < twidth; i++)
X        binsert('-');
X    bprint(fp);
X
X    /* print the label line of the table */
X    bstart();
X    for (saptr = slptr->sl_attrs; saptr != NULL; saptr = saptr->sa_next) {
X        fwidth = saptr->sa_attr->at_size;
X        binsert('|'); binsert(' ');
X        if ((aname = saptr->sa_name) == NULL)
X            aname = saptr->sa_aname;
X        for (i = 0; i < fwidth; i++)
X            if (*aname != 0)
X                binsert(*aname++);
X            else
X                binsert(' ');
X        binsert(' ');
X    }
X    binsert('|');
X    bprint(fp);
X
X    /* print the line under the labels */
X    bstart();
X    for (i = 0; i < twidth; i++)
X        binsert('-');
X    bprint(fp);
X}
X
X/* db_tfoot - print a table foot */
Xdb_tfoot(fp,slptr)
X  FILE *fp; struct sel *slptr;
X{
X    struct sattr *saptr;
X    int twidth,i;
X
X    /* compute the table width */
X    twidth = 1;
X    for (saptr = slptr->sl_attrs; saptr != NULL; saptr = saptr->sa_next)
X        twidth += saptr->sa_attr->at_size + 3;
X
X    /* print the line at the foot of the table */
X    bstart();
X    for (i = 0; i < twidth; i++)
X        binsert('-');
X    bprint(fp);
X}
X
X/* db_tentry - print a table entry */
Xdb_tentry(fp,slptr)
X  FILE *fp; struct sel *slptr;
X{
X    struct sattr *saptr;
X    int fwidth,i;
X
X    /* print a table entry */
X    bstart();
X    for (saptr = slptr->sl_attrs; saptr != NULL; saptr = saptr->sa_next) {
X        fwidth = saptr->sa_attr->at_size;
X        binsert('|'); binsert(' ');
X        for (i = 0; i < fwidth; i++)
X            if (saptr->sa_aptr[i] != 0)
X                binsert(saptr->sa_aptr[i]);
X            else
X                binsert(' ');
X        binsert(' ');
X    }
X    binsert('|');
X    bprint(fp);
X}
X
X/* bstart - start building a line */
Xstatic bstart()
X{
X    bndx = 0;
X}
X
X/* binsert - insert a character into the buffer */
Xstatic binsert(ch)
X  int ch;
X{
X    if (bndx < TABLEMAX)
X        buffer[bndx++] = ch;
X}
X
X/* bprint - print the current line */
Xstatic bprint(fp)
X  FILE *fp;
X{
X    buffer[bndx] = EOS;
X    fprintf(fp,"%s\n",buffer);
X}
X
SHAR_EOF
if test 2554 -ne "`wc -c 'tbl.c'`"
then
	echo shar: error transmitting "'tbl.c'" '(should have been 2554 characters)'
fi
echo shar: extracting "'sdbio.h'" '(7764 characters)'
if test -f 'sdbio.h'
then
	echo shar: over-writing existing file "'sdbio.h'"
fi
sed 's/^X//' << \SHAR_EOF > 'sdbio.h'
X/* SDB - definition file */
X
X#include "ctype.h"  /*dns*/
X
X/* compiler specific stuff  (dns) */
X#define Lattice
X
X/* useful definitions */
X#define TRUE            1
X#define FALSE           0
X#ifndef NULL
X#define NULL            0
X#endif
X
X/* Character definitions   (dns) */
X#define BS  0x8       /*dns*/
X#define CR  0xD       /*dns*/
X#define FF  0xC       /*dns*/
X#define ESC 0x1B      /*dns*/
X
X/* program limits */
X#define LINEMAX         132     /* maximum input line length */
X#define TABLEMAX        132     /* maximum table output line */
X#define KEYWORDMAX      10      /* maximum keyword length */
X#define NUMBERMAX       20      /* maximum number length */
X#define STRINGMAX       132     /* maximum string length */
X#define CODEMAX         100     /* maximum length of code array */
X#define STACKMAX        20      /* maximum interpreter stack size */
X
X/* token definitions */
X#define EOS             0
X#define LSS             -1
X#define LEQ             -2
X#define EQL             -3
X#define NEQ             -4
X#define GEQ             -5
X#define GTR             -6
X#define SELECT          -7
X#define FROM            -8
X#define WHERE           -9
X#define CREATE          -10
X#define DELETE          -11
X#define INSERT          -12
X#define EXIT            -13
X#define CHAR            -14
X#define NUM             -15
X#define ID              -16
X#define STRING          -17
X#define NUMBER          -18
X#define UPDATE          -19
X#define PRINT           -20
X#define IMPORT          -21
X#define EXPORT          -22
X#define INTO            -23
X#define HELP            -24
X#define COMPRESS        -25
X#define EXTRACT         -26
X#define DEFINE          -27
X#define SHOW            -28
X#define USING           -29
X#define SORT            -30
X#define BY              -31
X#define ASCENDING       -32
X#define DESCENDING      -33
X#define SET             -34
X
X/* operand types */
X#define LITERAL 1
X#define ATTR    2
X#define TEMP    3
X
X/* attribute data types */
X#define TCHAR   1
X#define TNUM    2
X
X/* tuple status codes */
X#define UNUSED  0
X#define ACTIVE  1
X#define DELETED 2
X
X/* relation header page format definitions */
X#define RNSIZE          10      /* size of a relation name */
X#define HSIZE           16      /* size of a relation entry */
X#define ASIZE           16      /* size of a attribute entry */
X#define ANSIZE          10      /* size of a attribute name */
X#define NATTRS          31      /* number of attributes in header block */
X
X/* error code definitions */
X#define END             0       /* end of retrieval set */
X#define INSMEM          1       /* insufficient memory */
X#define RELFNF          2       /* relation file not found */
X#define BADHDR          3       /* bad relation file header */
X#define TUPINP          4       /* tuple input error */
X#define TUPOUT          5       /* tuple output error */
X#define RELFUL          6       /* relation file full */
X#define RELCRE          7       /* error creating relation file */
X#define DUPATT          8       /* duplicate attribute on relation create */
X#define MAXATT          9       /* too many attributes on relation create */
X#define INSBLK          10      /* insufficient disk blocks */
X#define SYNTAX          11      /* command syntax error */
X#define ATUNDF          12      /* attribute name undefined */
X#define ATAMBG          13      /* attribute name ambiguous */
X#define RLUNDF          14      /* relation name undefined */
X#define CDSIZE          15      /* boolean expression code too big */
X#define INPFNF          16      /* input file not found */
X#define OUTCRE          17      /* output file creation error */
X#define INDFNF          18      /* indirect command file not found */
X#define BADSET          19      /* bad set parameter */
X
Xstruct attribute {
X    char at_name[ANSIZE];       /* attribute name */
X    char at_type;               /* attribute type */
X    char at_size;               /* attribute size in bytes */
X    char at_scale;              /* attribute scale factor (for numeric only) */
X    char at_unused[ASIZE-ANSIZE-3];     /* unused space */
X};
X
Xstruct header {         /* sizeof(struct header) must be 512 bytes */
X    char hd_tcnt[2];            /* # of tuples in relation */
X    char hd_tmax[2];            /* maximum # of tuples */
X    char hd_data[2];            /* offset to first data byte */
X    char hd_size[2];            /* size of each tuple in bytes */
X    char hd_unused[HSIZE-8];    /* unused space */
X    struct attribute hd_attrs[NATTRS];  /* table of attributes */
X};
X
Xstruct relation {
X    char rl_name[RNSIZE];       /* relation name */
X    unsigned int rl_tcnt;       /* # of tuples in relation (from hd_tcnt) */
X    unsigned int rl_tmax;       /* maximum # of tuples (from hd_tmax) */
X    int rl_data;                /* offset to first data byte (from hd_data) */
X    int rl_size;                /* size of eachtuple in bytes (from hd_size) */
X    int rl_store;               /* flag indicating a store happened */
X    int rl_fd;                  /* file descriptor for relation file */
X    int rl_scnref;              /* number of scans referencing this relation */
X    struct header rl_header;    /* the relation file header block */
X    struct relation *rl_next;   /* pointer to next relation */
X};
X
Xstruct scan {
X    struct relation *sc_relation;       /* pointer to relation definition */
X    unsigned int sc_dtnum;              /* desired tuple number */
X    unsigned int sc_atnum;              /* actual tuple number */
X    int sc_store;                       /* flag indicating a store happened */
X    char *sc_tuple;                     /* tuple buffer */
X};
X
Xstruct srel {
X    char *sr_name;                      /* alternate relation name */
X    struct scan *sr_scan;               /* relation scan structure ptr */
X    int sr_ctuple;                      /* current tuple flag */
X    int sr_update;                      /* updated tuple flag */
X    struct srel *sr_next;               /* next selected relation in list */
X};
X
Xstruct sattr {
X    char *sa_rname;                     /* relation name */
X    char *sa_aname;                     /* attribute name */
X    char *sa_name;                      /* alternate attribute name */
X    char *sa_aptr;                      /* pointer to attr in tuple buffer */
X    struct srel *sa_srel;               /* pointer to the selected relation */
X    struct attribute *sa_attr;          /* attribute structure ptr */
X    struct sattr *sa_next;              /* next selected attribute in list */
X};
X
Xstruct operand {
X    int o_type;
X    union  {
X        struct {
X            int ovc_type;
X            char *ovc_string;
X            int ovc_length;
X        } ov_char;
X        int ov_boolean;
X    } o_value;
X};
X
Xunion codecell {
X    int (*c_operator)();
X    struct operand *c_operand;
X};
X
Xstruct binding {
X    struct attribute *bd_attr;          /* bound attribute */
X    char *bd_vtuple;                    /* pointer to value in tuple */
X    char *bd_vuser;                     /* pointer to user buffer */
X    struct binding *bd_next;            /* next binding */
X};
X
Xstruct sel {
X    struct srel *sl_rels;               /* selected relations */
X    struct sattr *sl_attrs;             /* selected attributes */
X    union codecell *sl_where;           /* where clause */
X    struct binding *sl_bindings;        /* user variable bindings */
X};
X
Xstruct mtext {
X    char *mt_text;
X    struct mtext *mt_next;
X};
X
Xstruct macro {
X    char *mc_name;
X    struct mtext *mc_mtext;
X    struct macro *mc_next;
X};
X
Xstruct ifile {
X    char *if_fp;
X    struct mtext *if_mtext;
X    char *if_cmdline;
X    int if_savech;
X    char *if_lptr;
X    struct ifile *if_next;
X};
X
Xstruct skey {
X    int sk_type;
X    struct attribute *sk_aptr;
X    int sk_start;
X    struct skey *sk_next;
X};
X
SHAR_EOF
if test 7764 -ne "`wc -c 'sdbio.h'`"
then
	echo shar: error transmitting "'sdbio.h'" '(should have been 7764 characters)'
fi
#	End of shell archive
exit 0
-- 
Usenet: [decvax|allegra|linus|ihnp4]!utzoo!yetti!oz
Bitnet: oz@[yusol|yuyetti]
	You see things; and you say "WHY?"
	But I dream things that never were;
	and say "WHY NOT?"
			G. Bernard Shaw (Back to Methuselah)