From c08a0975036f23f972a16a07efb0c07113c96d2e Mon Sep 17 00:00:00 2001 From: Ralph Ronnquist Date: Tue, 5 Jul 2022 21:55:26 +1000 Subject: [PATCH] Add "relation" implementation based on hashvector --- vector/Makefile | 2 +- vector/relation.c | 100 ++++++++++++++++++++++++++++++++++++++++++++++ vector/relation.h | 40 +++++++++++++++++++ 3 files changed, 141 insertions(+), 1 deletion(-) create mode 100644 vector/relation.c create mode 100644 vector/relation.h diff --git a/vector/Makefile b/vector/Makefile index 7c5268d..d5c718b 100644 --- a/vector/Makefile +++ b/vector/Makefile @@ -1,6 +1,6 @@ LIBRARY = libvector.a LIBOBJS = vector.o hashvector.o -LIBOBJS += integeritem.o stringitem.o tupleitem.o +LIBOBJS += integeritem.o stringitem.o tupleitem.o relation.o default: $(LIBRARY) diff --git a/vector/relation.c b/vector/relation.c new file mode 100644 index 0000000..330b3de --- /dev/null +++ b/vector/relation.c @@ -0,0 +1,100 @@ +#include +#include + +#define COPYA(T,P,N) (T*) memcpy( malloc( N * sizeof(T) ), P, N * sizeof( T ) ) +#define COPY(T,P) COPYA(T,P,1) + +// Add an indexing hashvector to the relation using the nominated +// column indexes being the value part. the key must be a clone of the +// relation columns but with some columns reset. +int relation_addindex(relation *r,tupleschema *key) { + tupleschema *primary = r->columns; + if ( primary->arity != key->arity ) { + return -1; + } + int i = 0; + for ( ; i < primary->arity; i++ ) { + if ( key->columns[i] && primary->columns[i] != key->columns[i] ) { + return -1; + } + } + i = (int) r->indexes.size; + vector_append( &r->indexes, hashvector_create( 1, (itemkeyfun*) key ) ); + return i; +} + +relation *relation_create(int arity,tupleschema *schema) { + relation *r = (relation *) malloc( sizeof( relation ) ); + (*r) = (relation) { + .indexes = { + .variant = 2, + .size = 0, + .entries = 0 + }, + .columns = schema + }; + return r; +} + +// Iteration context for adding or querying a relation +typedef struct { + itemkeyfun *columns; + vector knockouts; + void *key; +} knockoutdata; + +// Determine matches to ((knockoutdata*)data)->key in +// (hashvector*)item, optionally using ((knockoutdata*)data)->columns +// for ignoring full matches to the key tuple. +static int knockout_check(vector_index index,void *item,void *data) { + knockoutdata *kod = (knockoutdata*) data; + void *old = 0; + if ( hashvector_find( (hashvector*) item, kod->key, &old ) ) { + if ( kod->columns == 0 || + kod->columns->haskey( kod->columns, old, kod->key ) == 0 ) { + if ( vector_find( &kod->knockouts, old ) >= kod->knockouts.size ) { + vector_append( &kod->knockouts, old ); + } + } + } + return 0; +} + +// delete the (tuple*)item from the (hashvector*)data +static int knockout_delete_item(vector_index index,void *item,void *data) { + hashvector_delete( (hashvector*)data, item ); + return 0; +} + +// delete the tuples of (vector*)data from the (hashvector*)item +static int knockout_delete(vector_index index,void *item,void *data) { + vector_iterate( (vector*)data, 0, knockout_delete_item, item ); + return 0; +} + +// add the (tuple*)data to the (hashvector*)item +static int knockout_add(vector_index index,void *item,void *data) { + hashvector_add( (hashvector*)item, data ); + return 0; +} + +// add a tuple to a relation and return a vector of knocked out +// tuples, if any, or 0 otherwise. +vector *relation_add(relation *r,tuple *x) { + knockoutdata data = { + .columns = &(r->columns->functions), + .knockouts = { .variant = 2, .size = 0, .entries = 0 }, + .key = x + }; + // Find all knockouts + vector_iterate( &r->indexes, 0, knockout_check, &data ); + // Delete them + vector_iterate( &r->indexes, 0, knockout_delete, &data.knockouts ); + // Add the new tuple + vector_iterate( &r->indexes, 0, knockout_add, x ); + if ( data.knockouts.size == 0 ) { + return 0; + } + return vector_clone( 3, &data.knockouts ); +} + diff --git a/vector/relation.h b/vector/relation.h new file mode 100644 index 0000000..b0996c1 --- /dev/null +++ b/vector/relation.h @@ -0,0 +1,40 @@ +#ifndef relation_H +#define relation_H + +#include +#include + +/** + * A relation is an implementation of a tuple set with a primary key + * through a hashvector whose "type" defines the key. Additional + * hashvectors may be added to impose additional key restrictions and + * the final relation is the intersection of them all. + * + * The relation record itself holds the column schema whereas the + * indexes hold key schemas that in practice are copies of the column + * schema with some columns blanked out. + */ +typedef struct { + vector indexes; // one or more indexes over the tuple collection + tupleschema *columns; +} relation; + +/** + * Create a relation of the given arity and tupleschema. + */ +extern relation *relation_create(int arity,tupleschema *schema); + +/** + * Add a a key index to the relation by identifying the value part for + * this index. + */ +extern int relation_addindex(relation *r,tupleschema *ts); + + +/** + * Add a tuple to a relation. + * \returns a vector of all knocked out tuples. + */ +extern vector *relation_add(relation *r,tuple *t); + +#endif -- 2.39.2