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*) calloc( ts->arity, sizeof( void* ) );
  34     int i = 0;
  35     va_start( ap, r );
  36     for ( ; i < ts->arity; i++ ) {
  37         if ( va_arg( ap, int ) ) {
  38             (*columns)[i] = ts->columns[i];
  39         }
  40     }
  41     va_end( ap );
  42     ts = tupleschema_create( ts->arity, columns );
  43     i = (int) r->constraints.size;
  44     vector_append(
  45         &r->constraints,
  46         hashvector_create( nibble_index_levels, (itemkeyfun*) ts ) );
  47     return i;
  48 }
  49
  50 //============== Adding an item =============
  51 // Iteration context for adding or querying a relation
  52 typedef struct {
  53     relation *rel;
  54     vector knockouts;
  55     void *item;
  56 } knockout;
  57
  58 // Determine matches to ((knockout*)data)->key in
  59 // (hashvector*)item, optionally using ((knockout*)data)->columns
  60 // for ignoring full matches to the key tuple.
  61 static int knockout_check(vector_index index,void *item,void *data) {
  62     knockout *kod = (knockout*) data;
  63     vector_index i = 0;
  64     for ( ; i < ((hashvector*) item)->table.size; i++ ) {
  65         void *old = hashvector_next( (hashvector*) item, &i, kod->item );
  66         if ( old ) {
  67             vector_append( &kod->knockouts, old );
  68         }
  69     }
  70     return 0;
  71 }
  72
  73 // delete the (tuple*)item from the (hashvector*)data
  74 static int knockout_delete_item(vector_index index,void *item,void *data) {
  75     hashvector_delete( (hashvector*)data, item );
  76     return 0;
  77 }
  78
  79 // delete the tuples of (vector*)data from the (hashvector*)item
  80 static int knockout_delete(vector_index index,void *item,void *data) {
  81     vector_iterate( (vector*)data, 0, knockout_delete_item, item );
  82     return 0;
  83 }
  84
  85 // add the (tuple*)data to the (hashvector*)item
  86 static int knockout_add(vector_index index,void *item,void *data) {
  87     hashvector_add( (hashvector*)item, data );
  88     return 0;
  89 }
  90
  91 // Find and remove all collisions for a query, unless "add" is
  92 // non-zero in which case the function aborts if there is any match in
  93 // the main content.
  94 static int knockout_clear(knockout *this,relation *r,tuple *item,int add) {
  95     (*this) = (knockout) {
  96         .rel = r,
  97         .knockouts = {
  98             .variant = bitpair_index_levels,
  99             .size = 0, .entries = 0
 100         },
 101         .item = item
 102     };
 103     knockout_check( 0, &r->content, this );
 104     if ( add && this->knockouts.size > 0 ) {
 105         return 0;
 106     }
 107     // Find all constraint knockouts
 108     vector_iterate( &r->constraints, 0, knockout_check, this );
 109     if ( this->knockouts.size > 0 ) {
 110         // Delete them from all tables
 111         vector_iterate(
 112             &this->knockouts, 0, knockout_delete_item, &r->content );
 113         vector_iterate(
 114             &r->constraints, 0, knockout_delete, &this->knockouts );
 115     }
 116     return 1;
 117 }
 118
 119 // add a tuple to a relation and return a vector of knocked out
 120 // tuples, if any, or 0 otherwise.
 121 vector *relation_add(relation *r,tuple *item) {
 122     knockout data;
 123     if ( knockout_clear( &data, r, item, 1 ) ) {
 124         // Add the new tuple
 125         hashvector_add( &r->content, item );
 126         vector_iterate( &r->constraints, 0, knockout_add, item );
 127         if ( data.knockouts.size > 0 ) {
 128             return vector_clone( single_index_level, &data.knockouts );
 129         }
 130     }
 131     return 0;
 132 }
 133
 134 vector *relation_delete(relation *r,tuple *item) {
 135     knockout data;
 136     (void) knockout_clear( &data, r, item, 0 );
 137     if ( data.knockouts.size > 0 ) {
 138         return vector_clone( single_index_level, &data.knockouts );
 139     }
 140     return 0;
 141 }
 142
 143 void *relation_next(relation *r,vector_index *index,tuple *query) {
 144     return hashvector_next( &r->content, index, query );
 145 }
 146