vector/Relation.c

   1 #include <stdarg.h>
   2 #include <stdlib.h>
   3 #include <Relation.h>
   4
   5 Relation *Relation_create(TupleSchema *schema) {
   6     Relation *r = (Relation *) malloc( sizeof( Relation ) );
   7     (*r) = (Relation) {
   8         .content = (HashVector) {
   9             .table = (Vector) {
  10                 .variant = Nibble_index_levels,
  11                 .size = 16,
  12                 .entries = 0
  13             },
  14             .fill = 0, .holes = 0, .type = (ItemKeyFun*) schema
  15         },
  16         .constraints = (Vector) {
  17             .variant = single_index_level,
  18             .size = 0,
  19             .entries = 0
  20         },
  21     };
  22     return r;
  23 }
  24
  25 #define COPYA(T,P,N) (T*) memcpy( malloc( N * sizeof(T) ), P, N * sizeof( T ) )
  26 #define COPY(T,P) COPYA(T,P,1)
  27
  28 // Add an indexing HashVector to the Relation using the given column
  29 // flags with 1 indicating key column and 0 indicating value column.
  30 int Relation_add_constraint(Relation *r,...) {
  31     va_list ap;
  32     TupleSchema *ts = (TupleSchema *) r->content.type;
  33     Tuple *columns = (Tuple*) malloc(
  34         sizeof( Tuple ) + ts->arity * sizeof( void* ) );
  35     int i = 0;
  36     va_start( ap, r );
  37     for ( ; i < ts->arity; i++ ) {
  38         if ( va_arg( ap, int ) ) {
  39             columns->elements[i] = ts->columns->elements[i];
  40         }
  41     }
  42     va_end( ap );
  43     ts = TupleSchema_create( ts->arity, columns );
  44     i = (int) r->constraints.size;
  45     Vector_append(
  46         &r->constraints,
  47         HashVector_create( Nibble_index_levels, (ItemKeyFun*) ts ) );
  48     return i;
  49 }
  50
  51 //============== Adding an item =============
  52 // Iteration context for adding or Querying a Relation
  53 typedef struct {
  54     Relation *rel;
  55     HashVector knockouts;
  56     void *item;
  57 } Knockout;
  58
  59 // Determine matches to ((Knockout*)data)->key in
  60 // (HashVector*)item, optionally using ((Knockout*)data)->columns
  61 // for ignoring full matches to the key tuple.
  62 static int knockout_check(VectorIndex index,void *item,void *data) {
  63     Knockout *kod = (Knockout*) data;
  64     void *key = kod->item;
  65     HashVector *hv = (HashVector*) item;
  66     TupleSchema *type = (TupleSchema *)hv->type;
  67     VectorIndex i = 0;
  68     for ( ; i < hv->table.size; i++ ) {
  69         void *old = HashVector_next( hv, &i );
  70         if ( old ) {
  71             if ( key && type->base.haskey( type, old, key ) == 0 ) {
  72                 continue;
  73             }
  74             HashVector_add( &kod->knockouts, old );
  75         }
  76     }
  77     return 0;
  78 }
  79
  80 // delete the (tuple*)item from the (HashVector*)data
  81 static int knockout_delete(VectorIndex index,void *item,void *data) {
  82     HashVector_delete( (HashVector*) item, data );
  83     return 0;
  84 }
  85
  86 // add the (tuple*)data to the (HashVector*)item
  87 static int knockout_add(VectorIndex index,void *item,void *data) {
  88     HashVector_add( (HashVector*)item, data );
  89     return 0;
  90 }
  91
  92 // Find and remove all collisions for a Query, unless "add" is
  93 // non-zero in which case the function aborts if there is any match in
  94 // the main content.
  95 static int knockout_clear(Knockout *this,Relation *r,Tuple *item,int add) {
  96     (*this) = (Knockout) {
  97         .rel = r,
  98         .knockouts = {
  99             .table = {
 100                 .variant = Nibble_index_levels, .size = 16, .entries = 0
 101             },
 102             .fill = 0, .holes = 0, .type = r->content.type,
 103         },
 104         .item = item
 105     };
 106     knockout_check( 0, &r->content, this );
 107     if ( add ) {
 108         if ( this->knockouts.fill > 0 ) {
 109             return 0;
 110         }
 111         // Find all constraint knockouts for addition
 112         Vector_iterate( &r->constraints, 0, knockout_check, this );
 113     }
 114     if ( this->knockouts.fill > 0 ) {
 115         // Delete them from all tables
 116         VectorIndex i;
 117         for ( i = 0; i < this->knockouts.table.size; i++ ) {
 118             void *t = HashVector_next( &this->knockouts, &i );
 119             if ( t ) {
 120                 HashVector_delete( &r->content, t );
 121                 Vector_iterate( &r->constraints, 0, knockout_delete, t );
 122             }
 123         }
 124     }
 125     return 1;
 126 }
 127
 128 // add a tuple to a Relation and return a Vector of knocked out
 129 // tuples, if any, or 0 otherwise.
 130 Vector *Relation_add(Relation *r,Tuple *item) {
 131     Knockout data;
 132     if ( knockout_clear( &data, r, item, 1 ) ) {
 133         // Add the new tuple
 134         HashVector_add( &r->content, item );
 135         Vector_iterate( &r->constraints, 0, knockout_add, item );
 136         return HashVector_contents( &data.knockouts, single_index_level, 0 );
 137     }
 138     return 0;
 139 }
 140
 141 Vector *Relation_delete(Relation *r,Tuple *item) {
 142     Knockout data;
 143     (void) knockout_clear( &data, r, item, 0 );
 144     return HashVector_contents( &data.knockouts, single_index_level, 0 );
 145 }
 146
 147 void *Relation_next(Relation *r,VectorIndex *index,Tuple *query) {
 148     HashVector *hv = &r->content;
 149     void *key = query;
 150     TupleSchema *type = (TupleSchema *) hv->type;
 151     for ( ; (*index) < hv->table.size; (*index)++ ) {
 152         void *old = HashVector_next( hv, index );
 153         if ( old ) {
 154             if ( key && type->base.haskey( type, old, key ) == 0 ) {
 155                 continue;
 156             }
 157             return old;
 158         }
 159     }
 160     (*index) = hv->table.size;
 161     return 0;
 162 }
 163