vector/Query.c

   1 #include <stdarg.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <Query.h>
   5 #include <BindingTable.h>
   6
   7 enum next_state {
   8     /**
   9      * This state tells the "next" function that it should capture the
  10      * incoming BindingTable state and provide the initial Binding of
  11      * a new sucession of bindings.
  12      */
  13     initial,
  14     /**
  15      * This state tells the "next" function that it should update the
  16      * bidning table with a subsequent Binding in the current
  17      * succession of bindings.
  18      */
  19     subsequent,
  20     /**
  21      * This state tells the "next" function that it should just
  22      * restore the Binding table to its incoming state.
  23      */
  24     restore
  25 };
  26
  27 //enum compound_state { reset, started, ended };
  28
  29 /**
  30  * A struct query_callbacks record defines the callbacks for a
  31  * specific query type.
  32  */
  33 struct query_callbacks {
  34     /**
  35      * \brief Callback function to reclaim the query memory for a
  36      * given query.
  37      *
  38      * \param this is the specific \ref query concerned.
  39      *
  40      * Ground queries recalim their own state memory. Composite
  41      * queries first propagate the reclaim call to its components, and
  42      * thereafter reclaim their local state memory.
  43      */
  44     void (*reclaim)(query *this);
  45     void (*start)(query *this,BindingTable *bt,enum next_state s);
  46     /**
  47      * \brief Callback function to update the Binding table with a
  48      * succession of alternative bindings.
  49      *
  50      * \param this is the specific \ref query concerned.
  51      *
  52      * \param bt is the Binding table to set bindings in.
  53      *
  54      * \param s is the call "sub-command" for the function.
  55      *
  56      * \returns 1 if a new Binding is provided and 0 otherwise.
  57      *
  58      * This function is called repeatedly for successively obtaining
  59      * the alternative bindings that satisfy the query. The "initial"
  60      * state sub-command tells the function to capture the incoming
  61      * BindingTable state so that the function can later restore it
  62      * upon the "restore" sub-command. Upon the "initial" command, the
  63      * function also sets up the Binding table with its first Binding
  64      * alternative. This is followed by a series of "subsequent"
  65      * sub-command calls for the function to change the BindingTable
  66      * for its succession of Binding alternatives. The function should
  67      * return 1 after any successful Binding setup, and return 0 when
  68      * it cannot setup any (more) Binding.
  69      */
  70     int (*next)(query *this,BindingTable *bt,enum next_state state);
  71 };
  72
  73 /* ==================== AssignmentQuery ==================== */
  74 typedef struct {
  75     struct query_callbacks *def;
  76     int arity;
  77     tuple *names;
  78     tuple *values;
  79     tuple *saved;
  80 } AssignmentQuery;
  81
  82 // Release any memory.
  83 static void AssignmentQuery_reclaim(query *this) {
  84     AssignmentQuery *q = (AssignmentQuery*) this;
  85     free( q->saved );
  86     free( this );
  87 }
  88
  89 static int AssignmentQuery_check(int arity,tuple *a,tuple *b) {
  90     int i;
  91     for ( i = 0; i < arity; i++ ) {
  92         char *value = (*a)[i];
  93         char *current = (*b)[i];
  94         if ( value && current && current != value &&
  95              strcmp( current, value ) != 0 ) {
  96             return 0;
  97         }
  98     }
  99     return 1;
 100 }
 101
 102 static void AssignmentQuery_assign(
 103     BindingTable *bt,int n,tuple *names,tuple *values,int all)
 104 {
 105     int i;
 106     for ( i = 0; i < n; i++ ) {
 107         if ( all || (*values)[i] ) {
 108             BindingTable_set( bt, (*names)[i], (*values)[i] );
 109         }
 110     }
 111 }
 112
 113 // Make names have given values and return 1. If any name has a
 114 // different value then return 0. Values are strings.
 115 static int AssignmentQuery_next(
 116     query *this,BindingTable *bt,enum next_state state) {
 117     AssignmentQuery *q = (AssignmentQuery*) this;
 118     switch ( state ) {
 119     case initial:
 120         if ( q->saved == 0 ) {
 121             q->saved = (tuple*) malloc( q->arity * sizeof( void* ) );
 122         }
 123         memcpy( q->saved, q->names, q->arity * sizeof( void* ) );
 124         BindingTable_deref( bt, q->arity, q->saved );
 125         // Check with new values
 126         if ( AssignmentQuery_check( q->arity, q->values, q->saved ) ) {
 127             AssignmentQuery_assign( bt, q->arity, q->names, q->values, 0 );
 128             return 1;
 129         }
 130         // Fall through
 131     case subsequent:
 132     case restore:
 133         if ( q->saved ) {
 134             AssignmentQuery_assign( bt, q->arity, q->names, q->saved, 1 );
 135             free( q->saved );
 136             q->saved = 0;
 137         }
 138         return 0;
 139     }
 140     return 0;
 141 }
 142
 143 static struct query_callbacks AssignmentQuery_def = {
 144     .reclaim = AssignmentQuery_reclaim,
 145     .next = AssignmentQuery_next
 146 };
 147
 148 /**
 149  * Return a query object representing an assignment of one or more
 150  * variables.
 151  */
 152 query *query_assign(int arity,tuple *names,tuple *values) {
 153     AssignmentQuery *q = (AssignmentQuery*)
 154         malloc( sizeof( AssignmentQuery ) );
 155     (*q) = (AssignmentQuery) {
 156         .def = &AssignmentQuery_def,
 157         .arity = arity,
 158         .names = names,
 159         .values = values,
 160         .saved = 0
 161     };
 162     return (query*) q;
 163 }
 164
 165 /* ==================== conjunction ==================== */
 166 typedef struct {
 167     struct query_callbacks *def;
 168     int active;
 169     int size;
 170     query **conjuncts;
 171 } ConjunctionQuery;
 172
 173 static void ConjunctionQuery_reclaim(query *this) {
 174     ConjunctionQuery *q = (ConjunctionQuery*) this;
 175     int i;
 176     for ( i = 0; i < q->size; i++ ) {
 177         q->conjuncts[i]->def->reclaim( q->conjuncts[i] );
 178     }
 179     free( q->conjuncts );
 180     free( this );
 181 }
 182
 183 static int ConjunctionQuery_next(
 184     query *this,BindingTable *bt,enum next_state state)
 185 {
 186     ConjunctionQuery *q = (ConjunctionQuery*) this;
 187     int i = q->size - 1;
 188     enum next_state s = subsequent;
 189     switch ( state ) {
 190     case initial:
 191         q->active = 1;
 192         i = 0;
 193         s = initial;
 194         // Fall through?
 195     case subsequent:
 196         while ( i < q->size ) {
 197             if ( q->conjuncts[i]->def->next( q->conjuncts[i], bt, s ) ) {
 198                 continue;
 199             }
 200             q->conjuncts[i]->def->next( q->conjuncts[i], bt, restore );
 201             if ( i-- == 0 ) {
 202                 // The first conjunct now exhausted
 203                 q->active = 0;
 204                 return 0;
 205             }
 206             s = subsequent;
 207         }
 208         return 1;
 209     case restore:
 210         if ( q->active ) {
 211             for ( ; i >= 0; i-- ) {
 212                 q->conjuncts[i]->def->next( q->conjuncts[i], bt, restore );
 213             }
 214         }
 215         q->active = 0;
 216         return 0;
 217     }
 218     return 0;
 219 }
 220
 221 static struct query_callbacks ConjunctionQuery_def = {
 222     .reclaim = ConjunctionQuery_reclaim,
 223     .next = ConjunctionQuery_next
 224 };
 225
 226 query *query_and(int n,...) {
 227     va_list args;
 228     ConjunctionQuery *q = (ConjunctionQuery *)
 229         malloc( sizeof( ConjunctionQuery ) );
 230     (*q) = (ConjunctionQuery) {
 231         .def = &ConjunctionQuery_def,
 232         .active = 0,
 233         .size = n,
 234         .conjuncts = (query**) malloc( n * sizeof( query* ) )
 235     };
 236     int i;
 237     va_start( args, n );
 238     for ( i = 0; i < n; i++ ) {
 239         q->conjuncts[i] = va_arg( args, query* );
 240     }
 241     va_end( args );
 242     return (query*) q;
 243 }
 244
 245 /* ==================== disjunction ==================== */
 246 typedef struct {
 247     struct query_callbacks *def;
 248     int index;
 249     int size;
 250     query **disjuncts;
 251 } DisjunctionQuery;
 252
 253 static void DisjunctionQuery_reclaim(query *this) {
 254     DisjunctionQuery *q = (DisjunctionQuery*) this;
 255     int i;
 256     for ( i = 0; i < q->size; i++ ) {
 257         q->disjuncts[i]->def->reclaim( q->disjuncts[i] );
 258     }
 259     free( q->disjuncts );
 260     free( this );
 261 }
 262
 263 static int DisjunctionQuery_next(
 264     query *this,BindingTable *bt,enum next_state state) {
 265     DisjunctionQuery *q = (DisjunctionQuery*) this;
 266     int i = q->index;
 267     enum next_state s = subsequent;
 268     switch ( state ) {
 269     case initial:
 270         i = 0;
 271         s = initial;
 272     case subsequent:
 273         for ( ; i < q->size; i++ ) {
 274             if ( q->disjuncts[i]->def->next( q->disjuncts[i], bt, s ) ) {
 275                 q->index = i;
 276                 return 1;
 277             }
 278             q->disjuncts[i]->def->next( q->disjuncts[i], bt, restore );
 279             s = initial;
 280         }
 281         q->index = -1;
 282         return 0;
 283     case restore:
 284         if ( i >= 0 ) {
 285             q->disjuncts[i]->def->next( q->disjuncts[i], bt, restore );
 286             q->index = -1;
 287         }
 288         return 0;
 289     }
 290     return 0;
 291 }
 292
 293 static struct query_callbacks DisjunctionQuery_def = {
 294     .reclaim = DisjunctionQuery_reclaim,
 295     .next = DisjunctionQuery_next,
 296 };
 297
 298 query *query_or(int n,...) {
 299     va_list args;
 300     DisjunctionQuery *q = (DisjunctionQuery *)
 301         malloc( sizeof( DisjunctionQuery ) );
 302     (*q) = (DisjunctionQuery) {
 303         .def = &DisjunctionQuery_def,
 304         .index = -1,
 305         .size = n,
 306         .disjuncts = (query**) malloc( n * sizeof( query* ) ),
 307     };
 308     int i;
 309     va_start( args, n );
 310     for ( i = 0; i < n; i++ ) {
 311         q->disjuncts[i] = va_arg( args, query* );
 312     }
 313     va_end( args );
 314     return (query*) q;
 315 }
 316
 317 /* ==================== Relation access ==================== */
 318 typedef struct {
 319     struct query_callbacks *def;
 320     Relation *rel;
 321     VectorIndex index;
 322     tuple *names;
 323     tuple *values;
 324     tuple *saved;
 325 } RelationQuery;
 326
 327 // Release any memory.
 328 static void RelationQuery_reclaim(query *this) {
 329     RelationQuery *q = (RelationQuery*) this;
 330     free( q->saved );
 331     free( this );
 332 }
 333
 334 // Make names have given values and return 1. If any name has a
 335 // different value then return 0. Values are strings.
 336 static int RelationQuery_next(
 337     query *this,BindingTable *bt,enum next_state state) {
 338     RelationQuery *q = (RelationQuery*) this;
 339     int arity = ((TupleSchema*) q->rel->content.type)->arity;
 340     VectorIndex index = q->index + 1;
 341     switch ( state ) {
 342     case initial:
 343         if ( q->saved == 0 ) {
 344             q->saved = (tuple*) malloc( arity * sizeof( void* ) );
 345         }
 346         memcpy( q->saved, q->names, arity * sizeof( void* ) );
 347         BindingTable_deref( bt, arity, q->saved );
 348         index = 0;
 349         // Fall through
 350     case subsequent:
 351         for ( ; index < q->rel->content.table.size; index++ ) {
 352             tuple *values = relation_next( q->rel, &index, q->values );
 353             if ( values ) {
 354                 q->index = index;
 355                 AssignmentQuery_assign( bt, arity, q->names, values, 1 );
 356                 return 1;
 357             }
 358         }
 359     case restore:
 360         if ( q->saved ) {
 361             AssignmentQuery_assign( bt, arity, q->names, q->saved, 1 );
 362             free( q->saved );
 363             q->saved = 0;
 364         }
 365         return 0;
 366     }
 367     return 0;
 368 }
 369
 370 static struct query_callbacks RelationQuery_def = {
 371     .reclaim = RelationQuery_reclaim,
 372     .next = RelationQuery_next
 373 };
 374
 375 /**
 376  * Return a query object representing an Relation of one or more
 377  * variables.
 378  */
 379 query *query_Relation(Relation *r,tuple *names,tuple *values) {
 380     RelationQuery *q = (RelationQuery*) malloc( sizeof( RelationQuery ) );
 381     (*q) = (RelationQuery) {
 382         .def = &RelationQuery_def,
 383         .rel = r,
 384         .names = names,
 385         .values = values,
 386         .saved = 0
 387     };
 388     return (query*) q;
 389 }