vector/relation.c

   1 #include <stdlib.h>
   2 #include <relation.h>
   3
   4 relation *relation_create(tupleschema *schema) {
   5     relation *r = (relation *) malloc( sizeof( relation ) );
   6     (*r) = (relation) {
   7         .content = (hashvector) {
   8             .table = (vector) {
   9                 .variant = nibble_index_levels,
  10                 .size = 16,
  11                 .entries = 0
  12             },
  13             .fill = 0, .holes = 0, .type = (itemkeyfun*) schema
  14         },
  15         .constraints = (vector) {
  16             .variant = single_index_level,
  17             .size = 0,
  18             .entries = 0
  19         },
  20     };
  21     return r;
  22 }
  23
  24 #define COPYA(T,P,N) (T*) memcpy( malloc( N * sizeof(T) ), P, N * sizeof( T ) )
  25 #define COPY(T,P) COPYA(T,P,1)
  26
  27 // Add an indexing hashvector to the relation using the nominated
  28 // column indexes being the value part. the key must be a clone of the
  29 // relation columns but with some columns reset.
  30 int relation_add_constraint(relation *r,tupleschema *key) {
  31     tupleschema *primary = (tupleschema *) r->content.type;
  32     if ( primary->arity != key->arity ) {
  33         return -1; // no good
  34     }
  35     int i = 0;
  36     for ( ; i < primary->arity; i++ ) {
  37         if ( key->columns[i] && primary->columns[i] != key->columns[i] ) {
  38             return -1;
  39         }
  40     }
  41     i = (int) r->constraints.size;
  42     vector_append(
  43         &r->constraints,
  44         hashvector_create( nibble_index_levels, &key->base ) );
  45     return i;
  46 }
  47
  48 //============== Adding an item =============
  49 // Iteration context for adding or querying a relation
  50 typedef struct {
  51     relation *rel;
  52     vector knockouts;
  53     void *item;
  54 } knockout;
  55
  56 // Determine matches to ((knockout*)data)->key in
  57 // (hashvector*)item, optionally using ((knockout*)data)->columns
  58 // for ignoring full matches to the key tuple.
  59 static int knockout_check(vector_index index,void *item,void *data) {
  60     knockout *kod = (knockout*) data;
  61     void *old = hashvector_next( (hashvector*) item, 0, kod->item );
  62     if ( old ) {
  63         vector_append( &kod->knockouts, old );
  64     }
  65     return 0;
  66 }
  67
  68 // delete the (tuple*)item from the (hashvector*)data
  69 static int knockout_delete_item(vector_index index,void *item,void *data) {
  70     hashvector_delete( (hashvector*)data, item );
  71     return 0;
  72 }
  73
  74 // delete the tuples of (vector*)data from the (hashvector*)item
  75 static int knockout_delete(vector_index index,void *item,void *data) {
  76     vector_iterate( (vector*)data, 0, knockout_delete_item, item );
  77     return 0;
  78 }
  79
  80 // add the (tuple*)data to the (hashvector*)item
  81 static int knockout_add(vector_index index,void *item,void *data) {
  82     hashvector_add( (hashvector*)item, data );
  83     return 0;
  84 }
  85
  86 // Find and remove all collisions for a query, unless "add" is
  87 // non-zero in which case the function aborts if there is any match in
  88 // the main content.
  89 static int knockout_clear(knockout *this,relation *r,tuple *item,int add) {
  90     (*this) = (knockout) {
  91         .rel = r,
  92         .knockouts = {
  93             .variant = bitpair_index_levels,
  94             .size = 0, .entries = 0
  95         },
  96         .item = item
  97     };
  98     knockout_check( 0, &r->content, this );
  99     if ( add && this->knockouts.size > 0 ) {
 100         return 0;
 101     }
 102     // Find all constraint knockouts
 103     vector_iterate( &r->constraints, 0, knockout_check, this );
 104     if ( this->knockouts.size > 0 ) {
 105         // Delete them from all tables
 106         vector_iterate(
 107             &this->knockouts, 0, knockout_delete_item, &r->content );
 108         vector_iterate(
 109             &r->constraints, 0, knockout_delete, &this->knockouts );
 110     }
 111     return 1;
 112 }
 113
 114 // add a tuple to a relation and return a vector of knocked out
 115 // tuples, if any, or 0 otherwise.
 116 vector *relation_add(relation *r,tuple *item) {
 117     knockout data;
 118     if ( knockout_clear( &data, r, item, 1 ) ) {
 119         // Add the new tuple
 120         hashvector_add( &r->content, item );
 121         vector_iterate( &r->constraints, 0, knockout_add, item );
 122         if ( data.knockouts.size > 0 ) {
 123             return vector_clone( single_index_level, &data.knockouts );
 124         }
 125     }
 126     return 0;
 127 }
 128
 129 vector *relation_delete(relation *r,tuple *item) {
 130     knockout data;
 131     (void) knockout_clear( &data, r, item, 0 );
 132     if ( data.knockouts.size > 0 ) {
 133         return vector_clone( single_index_level, &data.knockouts );
 134     }
 135     return 0;
 136 }
 137
 138 void *relation_next(relation *r,vector_index *index,tuple *query) {
 139     return hashvector_next( &r->content, index, query );
 140 }