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