/***************************************************************************** * table.h * * A simple example of underlying structures for exploring implementation * * of relational operators. * * * * Tuples are simply arrays of strings with fixed max string length and * * fixed max arity * * * * Tables are text files containing a header (arity and tuple of attribute * * names) and one or more tuples all delimited by or * * E.g.: * * |4 | * * |S# SNAME STATUS CITY| * * |S1 Smith 20 London | * * |S2 Jones 10 Paris | * * | ... | * * * * Internally, tables are represented by the TABLE struct which includes * * header information and the current tuple of the table (if any) * * * * Constants: * * STRSIZE, MAXARITY --- max string length and tuple size * * TRUE, FALSE --- Booleans * * * * Types: * * Boolean --- * * TUPLE --- Ordinary tuple of strings * * TUPLEBOOL --- Tuple of Booleans, for selection arguments * * TUPLEINT --- Tuple of ints, for mapping arguments * * TABLE --- In memory representation of a table * * * * Functions: * * * * Table control: * * TABLE *topen( char *, char * ) open existing table * * TABLE *tcreate( char *, int, TUPLE ) create new table (open for write) * * int tclose( TABLE ) close table * * int tdispose( TABLE ) close table and delete file * * int tread( TABLE ) read next tuple of table * * int twrite( TABLE ) write next tuple of table * * void trewind( TABLE ) reposition table to beg of table * * void showTblStr( TABLE ) dump contents of TABLE to stout * * void showTable( TABLE ) dump contents of table to stout * * * * Tuple operations: * * Boolean cmpTuple( TUPLE, TUPLE, int ) compare tuples * * Boolean matchTuple( TUPLE, TUPLE, int ) compare tuples with DoNotCares * * void moveTuple( TUPLE, TUPLE ) copy tuple * * * * Functions not provided here: * * int projTuple( TUPLE, TUPLE, int, TUPLEBOOL ) project tuple * * TABLE *restrict( TABLE *, TUPLE ) restrict TABLE per TUPLE * * TABLE *projm( TABLE *, TUPLEBOOL ) project TABLE per TUPLEBOOL * * TABLE *unique( TABLE *) remove duplicates from TABLE * * TABLE *join( TABLE *, TABLE *, TUPLEINT ) join TABLEs per TUPLEINT * * TABLE *union( TABLE *, TABLE * ) union TABLEs * * * * * ****************************************************************************/ #include #include #include /***************************************************************************** * Global constants * * * * STRSIZE --- Maximum length of attribute names and values * * MAXARITY --- Maximum number of attributes * * * ****************************************************************************/ #define STRSIZE 32 #define MAXARITY 16 /***************************************************************************** * Boolean type * * * ****************************************************************************/ typedef int Boolean; #define TRUE (1==1) #define FALSE (!TRUE) /***************************************************************************** * TUPLE types * * TUPLE --- tuple of strings * * TUPLEINT --- tuple of ints * * TUPLEBOOL --- tuple of Booleans * * * * All implemented as arrays of size MAXARITY * * * ****************************************************************************/ typedef char TUPLE[MAXARITY][STRSIZE]; typedef int TUPLEINT[MAXARITY]; typedef Boolean TUPLEBOOL[MAXARITY]; /***************************************************************************** * Internal TABLE type * * * * file --- FILE pointer * * name --- external filename of table * * arity --- number of attributes * * attributes --- TUPLE of attribute name * * valid --- TRUE iff current contains an actual TUPLE * * (FALSE before first tread() ) * * current --- value of current tuple * * * ****************************************************************************/ typedef struct tblSruct { FILE *file; char name[STRSIZE]; int arity; TUPLE attributes; Boolean valid; TUPLE current; } TABLE; /***************************************************************************** * FUNCTIONS * * * ****************************************************************************/ /***************************************************************************** * TABLE *topen( char *fname, char *mode ) * * Opens table in external file "fname" with access mode "mode". * * Meaning of mode is as in fopen. * * Allocates and initializes TABLE structure. * * Returns pointer to TABLE if successful. * * Returns NULL if allocate fails. * * Does essentially no error checking. * * * ****************************************************************************/ TABLE *topen ( char *, char * ); /***************************************************************************** * TABLE *tcreate( char *fname, int arity, TUPLE attributes ) * * Creates and opens new external table "fname" with arity "arity" and * * attribute names "attributes". * * If fname is null it uses a new unique filename of form "TabXXXXXX". * * File is opened "w+"---read/write---and truncated if it exists. * * Returns pointer to TABLE structure or NULL if something failed. * * Does essentially no error checking. * * * ****************************************************************************/ TABLE *tcreate ( char *, int, TUPLE ); /***************************************************************************** * int tclose( TABLE *t) * * Closes file associated with *t and frees t. * * Returns status from fclose. * * * ****************************************************************************/ int tclose ( TABLE * ); /***************************************************************************** * int tdispose( TABLE *t) * * Closes and deletes file associated with *t and frees t. * * Returns status from fclose. * * * ****************************************************************************/ int tdispose ( TABLE * ); /***************************************************************************** * int tread( TABLE *t ) * * Reads next tuple of t into current. * * Returns 1 if successful. * * Returns 0 if prior to end of tuple * * Returns negative number if error on read * * * ****************************************************************************/ int tread ( TABLE * ); /***************************************************************************** * int twrite( TABLE *t ) * * Writes current tuple of t. * * Returns 1 if successful. * * Any other return value signifies failure. * * * ****************************************************************************/ int twrite ( TABLE * ); /***************************************************************************** * void trewind( TABLE *t ) * * Reposition file associated with t to before first tuple. * * * ****************************************************************************/ void trewind ( TABLE *); /***************************************************************************** * void showTblStr( TABLE * t ) * * Dump TABLE structure to stdout * * * ****************************************************************************/ void showTblStr ( TABLE * ); /***************************************************************************** * void showTable( TABLE * ) * * Dump entire table (all tuples) to stdout * * * ****************************************************************************/ void showTable ( TABLE * ); /***************************************************************************** * int cmpTuple( TUPLE left, TUPLE right, int arity ) * * Returns 0 if first arity attributes of tuples are equal * * < 0 if first unequal attribute in left tuple is < right * * > 0 if first unequal attribute in left tuple is > right * * * ****************************************************************************/ int cmpTuple ( TUPLE, TUPLE, int); /***************************************************************************** * Boolean matchTuple( TUPLE tup, TUPLE pat, int arity ) * * Compares tup and pat for equality of attributes * * Attributes of pat which are null strings are treated as Do-Not-Care. * * * ****************************************************************************/ Boolean matchTuple ( TUPLE, TUPLE, int); /***************************************************************************** * void moveTuple( TUPLE to, TUPLE from, int arity ) * * Moves tuple from to tuple to * * * ****************************************************************************/ void moveTuple ( TUPLE, TUPLE, int ); /***************************************************************************** * int projTuple( TUPLE to, TUPLE from, int arity, TUPLEBOOL select ) * * Projects those attributes of from for which select it TRUE into to * * Returns arity of to * * * ****************************************************************************/ int projTuple ( TUPLE, TUPLE, int, char [] ); /***************************************************************************** * TABLE *restrict( TABLE *tin, TUPLE cond ) * * Writes those tuples of tin in with attributes matching cond (in the * * matchTuple sense) to the file associated with the TABLE it returns. * * This version would create a new temporary table. * * Other signatures you might consider would take a pointer to the output * * TABLE or a string with the filename of the output table as another * * argument. * * * ****************************************************************************/ TABLE *restrict ( TABLE *, TUPLE ); /***************************************************************************** * TABLE *projm( TABLE * tin, TUPLEBOOL select ) * * Writes the projection of the tuples of tin (without removing duplicates)* * to the file associate with the TABLE it returns. * * Otherwise similar to restrict. * * * ****************************************************************************/ TABLE *projm ( TABLE *, TUPLEBOOL ); /***************************************************************************** * TABLE *unique( TABLE *tin ) * * Copies tin to the output table removing duplicates. * * * ****************************************************************************/ TABLE *unique ( TABLE * ); /***************************************************************************** * TABLE *proj( TABLE * tin, TUPLEBOOL select ) * * etc. * * * ****************************************************************************/ TABLE *proj ( TABLE *, TUPLEBOOL ); /**************************************************************************** * TABLE *join( TABLE * touter, TABLE * tinner, TUPLEINT cols ) * * Join touter and tinner and write result to TABLE * * A pair of tuples is joined iff for all i in which col[i] != 0 * * the ith attribute of the outer tuple equals the col[i]th attribute * * of the inner tuple * * * ****************************************************************************/ TABLE *join ( TABLE *, TABLE *, TUPLEINT ); /***************************************************************************** * TABLE *union( TABLE * tleft, TABLE * tright ) * * TABLE gets the union of tleft and tright * * * ****************************************************************************/ TABLE *Union ( TABLE *, TABLE * ); /* end of table.h */