Contiki-NG
relation.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2010, Swedish Institute of Computer Science
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  * notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  * notice, this list of conditions and the following disclaimer in the
12  * documentation and/or other materials provided with the distribution.
13  * 3. Neither the name of the Institute nor the names of its contributors
14  * may be used to endorse or promote products derived from this software
15  * without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27  * SUCH DAMAGE.
28  */
29 
30 /**
31  * \file
32  * Logic for relational databases.
33  * \author
34  * Nicolas Tsiftes <nvt@sics.se>
35  */
36 
37 #include <limits.h>
38 #include <string.h>
39 
40 #include "lib/crc16.h"
41 #include "lib/list.h"
42 #include "lib/memb.h"
43 
44 #define DEBUG DEBUG_NONE
45 #include "net/ipv6/uip-debug.h"
46 
47 #include "db-options.h"
48 #include "index.h"
49 #include "lvm.h"
50 #include "relation.h"
51 #include "result.h"
52 #include "storage.h"
53 #include "aql.h"
54 
55 /*
56  * The source_dest_map structure is used for mapping the pointers to
57  * data in a source row and in the corresponding destination row. The
58  * structure is calculated just before processing a relational
59  * selection, and then used to improve the performance when processing
60  * each row.
61 */
62 struct source_dest_map {
63  attribute_t *from_attr;
64  attribute_t *to_attr;
65  unsigned from_offset;
66  unsigned to_offset;
67 };
68 
69 static struct source_dest_map attr_map[AQL_ATTRIBUTE_LIMIT];
70 
71 #if DB_FEATURE_JOIN
72 /*
73  * The source_map structure is used for mapping attributes to
74  * their offsets in rows.
75  */
76 struct source_map {
77  attribute_t *attr;
78  unsigned char *from_ptr;
79 };
80 
81 static struct source_map source_map[AQL_ATTRIBUTE_LIMIT];
82 #endif /* DB_FEATURE_JOIN */
83 
84 static unsigned char row[DB_MAX_ATTRIBUTES_PER_RELATION * DB_MAX_ELEMENT_SIZE];
85 static unsigned char extra_row[DB_MAX_ATTRIBUTES_PER_RELATION * DB_MAX_ELEMENT_SIZE];
86 static unsigned char result_row[AQL_ATTRIBUTE_LIMIT * DB_MAX_ELEMENT_SIZE];
87 static unsigned char * const left_row = row;
88 static unsigned char * const right_row = extra_row;
89 static unsigned char * const join_row = result_row;
90 
91 LIST(relations);
92 MEMB(relations_memb, relation_t, DB_RELATION_POOL_SIZE);
93 MEMB(attributes_memb, attribute_t, DB_ATTRIBUTE_POOL_SIZE);
94 
95 static relation_t *relation_find(char *);
96 static attribute_t *attribute_find(relation_t *, char *);
97 static int get_attribute_value_offset(relation_t *, attribute_t *);
98 static void attribute_free(relation_t *, attribute_t *);
99 static void purge_relations(void);
100 static void relation_clear(relation_t *);
101 static relation_t *relation_allocate(void);
102 static void relation_free(relation_t *);
103 
104 static relation_t *
105 relation_find(char *name)
106 {
107  relation_t *rel;
108 
109  for(rel = list_head(relations); rel != NULL; rel = rel->next) {
110  if(strcmp(rel->name, name) == 0) {
111  return rel;
112  }
113  }
114 
115  return NULL;
116 }
117 
118 static attribute_t *
119 attribute_find(relation_t *rel, char *name)
120 {
121  attribute_t *attr;
122 
123  for(attr = list_head(rel->attributes); attr != NULL; attr = attr->next) {
124  if(strcmp(attr->name, name) == 0) {
125  return attr;
126  }
127  }
128  return NULL;
129 }
130 
131 static int
132 get_attribute_value_offset(relation_t *rel, attribute_t *attr)
133 {
134  attribute_t *ptr;
135  int offset;
136 
137  for(offset = 0, ptr = list_head(rel->attributes);
138  ptr != NULL;
139  ptr = ptr->next) {
140  if(ptr == attr) {
141  return offset;
142  }
143  offset += ptr->element_size;
144  }
145 
146  return -1;
147 }
148 
149 static void
150 attribute_free(relation_t *rel, attribute_t *attr)
151 {
152  if(attr->index != NULL) {
153  index_release(attr->index);
154  }
155  memb_free(&attributes_memb, attr);
156  rel->attribute_count--;
157 }
158 
159 static void
160 purge_relations(void)
161 {
162  relation_t *rel;
163  relation_t *next;
164 
165  for(rel = list_head(relations); rel != NULL;) {
166  next = rel->next;
167  if(rel->references == 0) {
168  relation_free(rel);
169  }
170  rel = next;
171  }
172 }
173 
174 static void
175 relation_clear(relation_t *rel)
176 {
177  memset(rel, 0, sizeof(*rel));
178  rel->tuple_storage = -1;
179  rel->cardinality = INVALID_TUPLE;
180  rel->dir = DB_STORAGE;
181  LIST_STRUCT_INIT(rel, attributes);
182 }
183 
184 static relation_t *
185 relation_allocate(void)
186 {
187  relation_t *rel;
188 
189  rel = memb_alloc(&relations_memb);
190  if(rel == NULL) {
191  purge_relations();
192  rel = memb_alloc(&relations_memb);
193  if(rel == NULL) {
194  PRINTF("DB: Failed to allocate a relation\n");
195  return NULL;
196  }
197  }
198 
199  relation_clear(rel);
200  return rel;
201 }
202 
203 static void
204 relation_free(relation_t *rel)
205 {
206  attribute_t *attr;
207 
208  while((attr = list_pop(rel->attributes)) != NULL) {
209  attribute_free(rel, attr);
210  }
211 
212  list_remove(relations, rel);
213  memb_free(&relations_memb, rel);
214 }
215 
216 db_result_t
217 relation_init(void)
218 {
219  list_init(relations);
220  memb_init(&relations_memb);
221  memb_init(&attributes_memb);
222 
223  return DB_OK;
224 }
225 
226 relation_t *
227 relation_load(char *name)
228 {
229  relation_t *rel;
230 
231  rel = relation_find(name);
232  if(rel != NULL) {
233  rel->references++;
234  goto end;
235  }
236 
237  rel = relation_allocate();
238  if(rel == NULL) {
239  return NULL;
240  }
241 
242  if(DB_ERROR(storage_get_relation(rel, name))) {
243  memb_free(&relations_memb, rel);
244  return NULL;
245  }
246 
247  memcpy(rel->name, name, sizeof(rel->name));
248  rel->name[sizeof(rel->name) - 1] = '\0';
249  rel->references = 1;
250  list_add(relations, rel);
251 
252 end:
253  if(rel->dir == DB_STORAGE && DB_ERROR(storage_load(rel))) {
254  relation_release(rel);
255  return NULL;
256  }
257 
258  return rel;
259 }
260 
261 db_result_t
262 relation_release(relation_t *rel)
263 {
264  if(rel->references > 0) {
265  rel->references--;
266  }
267 
268  if(rel->references == 0) {
269  storage_unload(rel);
270  }
271 
272  return DB_OK;
273 }
274 
275 relation_t *
276 relation_create(char *name, db_direction_t dir)
277 {
278  relation_t old_rel;
279  relation_t *rel;
280 
281  if(*name != '\0') {
282  relation_clear(&old_rel);
283 
284  if(storage_get_relation(&old_rel, name) == DB_OK) {
285  /* Reject a creation request if the relation already exists. */
286  PRINTF("DB: Attempted to create a relation that already exists (%s)\n",
287  name);
288  return NULL;
289  }
290 
291  rel = relation_allocate();
292  if(rel == NULL) {
293  return NULL;
294  }
295 
296  rel->cardinality = 0;
297 
298  strncpy(rel->name, name, sizeof(rel->name) - 1);
299  rel->name[sizeof(rel->name) - 1] = '\0';
300  rel->dir = dir;
301 
302  if(dir == DB_STORAGE) {
303  storage_drop_relation(rel, 1);
304 
305  if(storage_put_relation(rel) == DB_OK) {
306  list_add(relations, rel);
307  return rel;
308  }
309  memb_free(&relations_memb, rel);
310  } else {
311  list_add(relations, rel);
312  return rel;
313  }
314  }
315 
316  return NULL;
317 }
318 
319 #if DB_FEATURE_REMOVE
320 db_result_t
321 relation_rename(char *old_name, char *new_name)
322 {
323  if(DB_ERROR(relation_remove(new_name, 0)) ||
324  DB_ERROR(storage_rename_relation(old_name, new_name))) {
325  return DB_STORAGE_ERROR;
326  }
327 
328  return DB_OK;
329 }
330 #endif /* DB_FEATURE_REMOVE */
331 
332 attribute_t *
333 relation_attribute_add(relation_t *rel, db_direction_t dir, char *name,
334  domain_t domain, size_t element_size)
335 {
336  attribute_t *attribute;
337  tuple_id_t cardinality;
338 
339  cardinality = relation_cardinality(rel);
340  if(cardinality != INVALID_TUPLE && cardinality > 0) {
341  PRINTF("DB: Attempt to create an attribute in a non-empty relation\n");
342  return NULL;
343  }
344 
345  if(element_size == 0 || element_size > DB_MAX_ELEMENT_SIZE) {
346  PRINTF("DB: Unacceptable element size: %u\n", element_size);
347  return NULL;
348  }
349 
350  attribute = memb_alloc(&attributes_memb);
351  if(attribute == NULL) {
352  PRINTF("DB: Failed to allocate attribute \"%s\"!\n", name);
353  return NULL;
354  }
355 
356  strncpy(attribute->name, name, sizeof(attribute->name) - 1);
357  attribute->name[sizeof(attribute->name) - 1] = '\0';
358  attribute->domain = domain;
359  attribute->element_size = element_size;
360  attribute->aggregator = 0;
361  attribute->index = NULL;
362  attribute->flags = 0 /*ATTRIBUTE_FLAG_UNIQUE*/;
363 
364  rel->row_length += element_size;
365 
366  list_add(rel->attributes, attribute);
367  rel->attribute_count++;
368 
369  if(dir == DB_STORAGE) {
370  if(DB_ERROR(storage_put_attribute(rel, attribute))) {
371  PRINTF("DB: Failed to store attribute %s\n", attribute->name);
372  memb_free(&attributes_memb, attribute);
373  return NULL;
374  }
375  } else {
376  index_load(rel, attribute);
377  }
378 
379  return attribute;
380 }
381 
382 attribute_t *
383 relation_attribute_get(relation_t *rel, char *name)
384 {
385  attribute_t *attr;
386 
387  attr = attribute_find(rel, name);
388  if(attr != NULL && !(attr->flags & ATTRIBUTE_FLAG_INVALID)) {
389  return attr;
390  }
391 
392  return NULL;
393 }
394 
395 db_result_t
396 relation_attribute_remove(relation_t *rel, char *name)
397 {
398  /* Not implemented completely. */
399  return DB_IMPLEMENTATION_ERROR;
400 #if 0
401  attribute_t *attr;
402 
403  if(rel->references > 1) {
404  return DB_BUSY_ERROR;
405  }
406 
407  attr = relation_attribute_get(rel, name);
408  if(attr == NULL) {
409  return DB_NAME_ERROR;
410  }
411 
412  list_remove(rel->attributes, attr);
413  attribute_free(rel, attr);
414  return DB_OK;
415 #endif
416 }
417 
418 db_result_t
419 relation_get_value(relation_t *rel, attribute_t *attr,
420  unsigned char *row_ptr, attribute_value_t *value)
421 {
422  int offset;
423  unsigned char *from_ptr;
424 
425  offset = get_attribute_value_offset(rel, attr);
426  if(offset < 0) {
427  return DB_IMPLEMENTATION_ERROR;
428  }
429  from_ptr = row_ptr + offset;
430 
431  return db_phy_to_value(value, attr, from_ptr);
432 }
433 
434 db_result_t
435 relation_set_primary_key(relation_t *rel, char *name)
436 {
437  attribute_t *attribute;
438 
439  attribute = relation_attribute_get(rel, name);
440  if(attribute == NULL) {
441  return DB_NAME_ERROR;
442  }
443 
444  attribute->flags = ATTRIBUTE_FLAG_PRIMARY_KEY;
445  PRINTF("DB: New primary key: %s\n", attribute->name);
446 
447  return DB_OK;
448 }
449 
450 db_result_t
451 relation_remove(char *name, int remove_tuples)
452 {
453  relation_t *rel;
454  db_result_t result;
455 
456  rel = relation_load(name);
457  if(rel == NULL) {
458  /*
459  * Attempt to remove an inexistent relation. To allow for this
460  * operation to be used for setting up repeatable tests and
461  * experiments, we do not signal an error.
462  */
463  return DB_OK;
464  }
465 
466  if(rel->references > 1) {
467  return DB_BUSY_ERROR;
468  }
469 
470  result = storage_drop_relation(rel, remove_tuples);
471  relation_free(rel);
472  return result;
473 }
474 
475 db_result_t
476 relation_insert(relation_t *rel, attribute_value_t *values)
477 {
478  attribute_t *attr;
479  unsigned char record[rel->row_length];
480  unsigned char *ptr;
481  attribute_value_t *value;
482  db_result_t result;
483 
484  value = values;
485 
486  PRINTF("DB: Relation %s has a record size of %u bytes\n",
487  rel->name, (unsigned)rel->row_length);
488  ptr = record;
489 
490  PRINTF("DB: Insert (");
491 
492  for(attr = list_head(rel->attributes); attr != NULL; attr = attr->next, value++) {
493  /* Verify that the value is in the expected domain. An exception
494  to this rule is that INT may be promoted to LONG. */
495  if(attr->domain != value->domain &&
496  !(attr->domain == DOMAIN_LONG && value->domain == DOMAIN_INT)) {
497  PRINTF("DB: The value domain %d does not match the domain %d of attribute %s\n",
498  value->domain, attr->domain, attr->name);
499  return DB_RELATIONAL_ERROR;
500  }
501 
502  /* Set the data area for removed attributes to 0. */
503  if(attr->flags & ATTRIBUTE_FLAG_INVALID) {
504  memset(ptr, 0, attr->element_size);
505  ptr += attr->element_size;
506  continue;
507  }
508 
509  result = db_value_to_phy((unsigned char *)ptr, attr, value);
510  if(DB_ERROR(result)) {
511  return result;
512  }
513 
514 #if DEBUG
515  switch(attr->domain) {
516  case DOMAIN_INT:
517  PRINTF("%s=%d", attr->name, VALUE_INT(value));
518  break;
519  case DOMAIN_LONG:
520  PRINTF("%s=%ld", attr->name, VALUE_LONG(value));
521  break;
522  case DOMAIN_STRING:
523  PRINTF("%s='%s", attr->name, VALUE_STRING(value));
524  break;
525  default:
526  PRINTF(")\nDB: Unhandled attribute domain: %d\n", attr->domain);
527  return DB_TYPE_ERROR;
528  }
529 
530  if(attr->next != NULL) {
531  PRINTF(", ");
532  }
533 #endif /* DEBUG */
534 
535  ptr += attr->element_size;
536  if(attr->index != NULL) {
537  if(DB_ERROR(index_insert(attr->index, value, rel->next_row))) {
538  return DB_INDEX_ERROR;
539  }
540  }
541  }
542 
543  PRINTF(")\n");
544 
545  rel->cardinality++;
546  rel->next_row++;
547  return storage_put_row(rel, record);
548 }
549 
550 static void
551 aggregate(attribute_t *attr, attribute_value_t *value)
552 {
553  long long_value;
554 
555  switch(value->domain) {
556  case DOMAIN_INT:
557  long_value = VALUE_INT(value);
558  break;
559  case DOMAIN_LONG:
560  long_value = VALUE_LONG(value);
561  break;
562  default:
563  return;
564  }
565 
566  switch(attr->aggregator) {
567  case AQL_COUNT:
568  attr->aggregation_value++;
569  break;
570  case AQL_SUM:
571  attr->aggregation_value += long_value;
572  break;
573  case AQL_MEAN:
574  break;
575  case AQL_MEDIAN:
576  break;
577  case AQL_MAX:
578  if(long_value > attr->aggregation_value) {
579  attr->aggregation_value = long_value;
580  }
581  break;
582  case AQL_MIN:
583  if(long_value < attr->aggregation_value) {
584  attr->aggregation_value = long_value;
585  }
586  break;
587  default:
588  break;
589  }
590 }
591 
592 static db_result_t
593 generate_attribute_map(struct source_dest_map *attr_map, unsigned attribute_count,
594  relation_t *from_rel, relation_t *to_rel,
595  unsigned char *from_row, unsigned char *to_row)
596 {
597  attribute_t *from_attr;
598  attribute_t *to_attr;
599  unsigned size_sum;
600  struct source_dest_map *attr_map_ptr;
601  int offset;
602 
603  attr_map_ptr = attr_map;
604  for(size_sum = 0, to_attr = list_head(to_rel->attributes);
605  to_attr != NULL;
606  to_attr = to_attr->next) {
607  from_attr = attribute_find(from_rel, to_attr->name);
608  if(from_attr == NULL) {
609  PRINTF("DB: Invalid attribute in the result relation: %s\n",
610  to_attr->name);
611  return DB_NAME_ERROR;
612  }
613 
614  attr_map_ptr->from_attr = from_attr;
615  attr_map_ptr->to_attr = to_attr;
616  offset = get_attribute_value_offset(from_rel, from_attr);
617  if(offset < 0) {
618  return DB_IMPLEMENTATION_ERROR;
619  }
620  attr_map_ptr->from_offset = offset;
621  attr_map_ptr->to_offset = size_sum;
622 
623  size_sum += to_attr->element_size;
624  attr_map_ptr++;
625  }
626 
627  return DB_OK;
628 }
629 
630 static void
631 select_index(db_handle_t *handle, lvm_instance_t *lvm_instance)
632 {
633  index_t *index;
634  attribute_t *attr;
635  operand_value_t min;
636  operand_value_t max;
637  attribute_value_t av_min;
638  attribute_value_t av_max;
639  long range;
640  unsigned long min_range;
641 
642  index = NULL;
643  min_range = ULONG_MAX;
644 
645  /* Find all indexed and derived attributes, and select the index of
646  the attribute with the smallest range. */
647  for(attr = list_head(handle->rel->attributes);
648  attr != NULL;
649  attr = attr->next) {
650  if(attr->index != NULL &&
651  !LVM_ERROR(lvm_get_derived_range(lvm_instance, attr->name, &min, &max))) {
652  range = (unsigned long)max.l - (unsigned long)min.l;
653  PRINTF("DB: The search range for attribute \"%s\" comprises %ld values\n",
654  attr->name, range + 1);
655 
656  if(range <= min_range) {
657  index = attr->index;
658  av_min.domain = av_max.domain = DOMAIN_INT;
659  VALUE_LONG(&av_min) = min.l;
660  VALUE_LONG(&av_max) = max.l;
661  }
662  }
663  }
664 
665  if(index != NULL) {
666  /* We found a suitable index; get an iterator for it. */
667  if(index_get_iterator(&handle->index_iterator, index,
668  &av_min, &av_max) == DB_OK) {
669  handle->flags |= DB_HANDLE_FLAG_SEARCH_INDEX;
670  }
671  }
672 }
673 
674 static db_result_t
675 generate_selection_result(db_handle_t *handle, relation_t *rel, aql_adt_t *adt)
676 {
677  relation_t *result_rel;
678  unsigned attribute_count;
679  attribute_t *attr;
680 
681  result_rel = handle->result_rel;
682 
683  handle->current_row = 0;
684  handle->ncolumns = 0;
685  handle->tuple_id = 0;
686  for(attr = list_head(result_rel->attributes); attr != NULL; attr = attr->next) {
687  if(attr->flags & ATTRIBUTE_FLAG_NO_STORE) {
688  continue;
689  }
690  handle->ncolumns++;
691  }
692  handle->tuple = (tuple_t)result_row;
693 
694  attribute_count = result_rel->attribute_count;
695  if(DB_ERROR(generate_attribute_map(attr_map, attribute_count, rel, result_rel, row, result_row))) {
696  return DB_IMPLEMENTATION_ERROR;
697  }
698 
699  if(adt->lvm_instance != NULL) {
700  /* Try to establish acceptable ranges for the attribute values. */
701  if(!LVM_ERROR(lvm_derive(adt->lvm_instance))) {
702  select_index(handle, adt->lvm_instance);
703  }
704  }
705 
706  handle->flags |= DB_HANDLE_FLAG_PROCESSING;
707 
708  return DB_OK;
709 }
710 
711 #if DB_FEATURE_REMOVE
712 db_result_t
713 relation_process_remove(void *handle_ptr)
714 {
715  db_handle_t *handle;
716  aql_adt_t *adt;
717  db_result_t result;
718 
719  handle = (db_handle_t *)handle_ptr;
720  adt = handle->adt;
721 
722  result = relation_process_select(handle_ptr);
723  if(result == DB_FINISHED) {
724  PRINTF("DB: Finished removing tuples. Overwriting relation %s with the result\n",
725  adt->relations[1]);
726  relation_release(handle->rel);
727  relation_rename(adt->relations[0], adt->relations[1]);
728  }
729 
730  return result;
731 }
732 #endif
733 
734 db_result_t
735 relation_process_select(void *handle_ptr)
736 {
737  db_handle_t *handle;
738  aql_adt_t *adt;
739  db_result_t result;
740  unsigned attribute_count;
741  struct source_dest_map *attr_map_ptr, *attr_map_end;
742  attribute_t *result_attr;
743  unsigned char *from_ptr;
744  unsigned char *to_ptr;
745  operand_value_t operand_value;
746  uint8_t intbuf[2];
747  attribute_value_t value;
748  lvm_status_t wanted_result;
749 
750  handle = (db_handle_t *)handle_ptr;
751  adt = (aql_adt_t *)handle->adt;
752 
753  attribute_count = handle->result_rel->attribute_count;
754  attr_map_end = attr_map + attribute_count;
755 
756  if(handle->flags & DB_HANDLE_FLAG_SEARCH_INDEX) {
757  handle->tuple_id = index_get_next(&handle->index_iterator);
758  if(handle->tuple_id == INVALID_TUPLE) {
759  PRINTF("DB: An attribute value could not be found in the index\n");
760  if(handle->index_iterator.next_item_no == 0) {
761  return DB_INDEX_ERROR;
762  }
763 
764  if(adt->flags & AQL_FLAG_AGGREGATE) {
765  goto end_aggregation;
766  }
767 
768  return DB_FINISHED;
769  }
770  }
771 
772  /* Put the tuples fulfilling the given condition into a new relation.
773  The tuples may be projected. */
774  result = storage_get_row(handle->rel, &handle->tuple_id, row);
775  handle->tuple_id++;
776  if(DB_ERROR(result)) {
777  PRINTF("DB: Failed to get a row in relation %s!\n", handle->rel->name);
778  return result;
779  } else if(result == DB_FINISHED) {
780  if(AQL_GET_FLAGS(adt) & AQL_FLAG_AGGREGATE) {
781  goto end_aggregation;
782  }
783  return DB_FINISHED;
784  }
785 
786  /* Process the attributes in the result relation. */
787  for(attr_map_ptr = attr_map; attr_map_ptr < attr_map_end; attr_map_ptr++) {
788  from_ptr = row + attr_map_ptr->from_offset;
789  result_attr = attr_map_ptr->to_attr;
790 
791  /* Update the internal state of the PLE. */
792  if(result_attr->domain == DOMAIN_INT) {
793  operand_value.l = from_ptr[0] << 8 | from_ptr[1];
794  lvm_set_variable_value(result_attr->name, operand_value);
795  } else if(result_attr->domain == DOMAIN_LONG) {
796  operand_value.l = (uint32_t)from_ptr[0] << 24 |
797  (uint32_t)from_ptr[1] << 16 |
798  (uint32_t)from_ptr[2] << 8 |
799  from_ptr[3];
800  lvm_set_variable_value(result_attr->name, operand_value);
801  }
802 
803  if(result_attr->flags & ATTRIBUTE_FLAG_NO_STORE) {
804  /* The attribute is used just for the predicate,
805  so do not copy the current value into the result. */
806  continue;
807  }
808 
809  if(!(AQL_GET_FLAGS(adt) & AQL_FLAG_AGGREGATE)) {
810  /* No aggregators. Copy the original value into the resulting tuple. */
811  memcpy(result_row + attr_map_ptr->to_offset, from_ptr,
812  result_attr->element_size);
813  }
814  }
815 
816  wanted_result = LVM_TRUE;
817  if(AQL_GET_FLAGS(adt) & AQL_FLAG_INVERSE_LOGIC) {
818  wanted_result = LVM_FALSE;
819  }
820 
821  /* Check whether the given predicate is true for this tuple. */
822  if(adt->lvm_instance == NULL ||
823  lvm_execute(adt->lvm_instance) == wanted_result) {
824  if(AQL_GET_FLAGS(adt) & AQL_FLAG_AGGREGATE) {
825  for(attr_map_ptr = attr_map; attr_map_ptr < attr_map_end; attr_map_ptr++) {
826  from_ptr = row + attr_map_ptr->from_offset;
827  result = db_phy_to_value(&value, attr_map_ptr->to_attr, from_ptr);
828  if(DB_ERROR(result)) {
829  return result;
830  }
831  aggregate(attr_map_ptr->to_attr, &value);
832  }
833  } else {
834  if(AQL_GET_FLAGS(adt) & AQL_FLAG_ASSIGN) {
835  if(DB_ERROR(storage_put_row(handle->result_rel, result_row))) {
836  PRINTF("DB: Failed to store a row in the result relation!\n");
837  return DB_STORAGE_ERROR;
838  }
839  }
840  handle->current_row++;
841  return DB_GOT_ROW;
842  }
843  }
844 
845  return DB_OK;
846 
847 end_aggregation:
848  /* Generate aggregated result if requested. */
849  for(attr_map_ptr = attr_map; attr_map_ptr < attr_map_end; attr_map_ptr++) {
850  result_attr = attr_map_ptr->to_attr;
851  to_ptr = result_row + attr_map_ptr->to_offset;
852 
853  intbuf[0] = result_attr->aggregation_value >> 8;
854  intbuf[1] = result_attr->aggregation_value & 0xff;
855  from_ptr = intbuf;
856  memcpy(to_ptr, from_ptr, result_attr->element_size);
857  }
858 
859  if(AQL_GET_FLAGS(adt) & AQL_FLAG_ASSIGN) {
860  if(DB_ERROR(storage_put_row(handle->result_rel, result_row))) {
861  PRINTF("DB: Failed to store a row in the result relation!\n");
862  return DB_STORAGE_ERROR;
863  }
864  }
865 
866  handle->current_row = 1;
867  AQL_GET_FLAGS(adt) &= ~AQL_FLAG_AGGREGATE; /* Stop the aggregation. */
868 
869  return DB_GOT_ROW;
870 }
871 
872 db_result_t
873 relation_select(void *handle_ptr, relation_t *rel, void *adt_ptr)
874 {
875  aql_adt_t *adt;
876  db_handle_t *handle;
877  char *name;
878  db_direction_t dir;
879  char *attribute_name;
880  attribute_t *attr;
881  int i;
882  int normal_attributes;
883 
884  adt = (aql_adt_t *)adt_ptr;
885 
886  handle = (db_handle_t *)handle_ptr;
887  handle->rel = rel;
888  handle->adt = adt;
889 
890  if(AQL_GET_FLAGS(adt) & AQL_FLAG_ASSIGN) {
891  name = adt->relations[0];
892  dir = DB_STORAGE;
893  } else {
894  name = RESULT_RELATION;
895  dir = DB_MEMORY;
896  }
897  relation_remove(name, 1);
898  relation_create(name, dir);
899  handle->result_rel = relation_load(name);
900 
901  if(handle->result_rel == NULL) {
902  PRINTF("DB: Failed to load a relation for the query result\n");
903  return DB_ALLOCATION_ERROR;
904  }
905 
906  for(i = normal_attributes = 0; i < AQL_ATTRIBUTE_COUNT(adt); i++) {
907  attribute_name = adt->attributes[i].name;
908 
909  attr = relation_attribute_get(rel, attribute_name);
910  if(attr == NULL) {
911  PRINTF("DB: Select for invalid attribute %s in relation %s!\n",
912  attribute_name, rel->name);
913  return DB_NAME_ERROR;
914  }
915 
916  PRINTF("DB: Found attribute %s in relation %s\n",
917  attribute_name, rel->name);
918 
919  attr = relation_attribute_add(handle->result_rel, dir,
920  attribute_name,
921  adt->aggregators[i] ? DOMAIN_INT : attr->domain,
922  attr->element_size);
923  if(attr == NULL) {
924  PRINTF("DB: Failed to add a result attribute\n");
925  relation_release(handle->result_rel);
926  return DB_ALLOCATION_ERROR;
927  }
928 
929  attr->aggregator = adt->aggregators[i];
930  switch(attr->aggregator) {
931  case AQL_NONE:
932  if(!(adt->attributes[i].flags & ATTRIBUTE_FLAG_NO_STORE)) {
933  /* Only count attributes projected into the result set. */
934  normal_attributes++;
935  }
936  break;
937  case AQL_MAX:
938  attr->aggregation_value = LONG_MIN;
939  break;
940  case AQL_MIN:
941  attr->aggregation_value = LONG_MAX;
942  break;
943  default:
944  attr->aggregation_value = 0;
945  break;
946  }
947 
948  attr->flags = adt->attributes[i].flags;
949  }
950 
951  /* Preclude mixes of normal attributes and aggregated ones in
952  selection results. */
953  if(normal_attributes > 0 &&
954  handle->result_rel->attribute_count > normal_attributes) {
955  return DB_RELATIONAL_ERROR;
956  }
957 
958  return generate_selection_result(handle, rel, adt);
959 }
960 
961 #if DB_FEATURE_JOIN
962 db_result_t
963 relation_process_join(void *handle_ptr)
964 {
965  db_handle_t *handle;
966  db_result_t result;
967  relation_t *left_rel;
968  relation_t *right_rel;
969  relation_t *join_rel;
970  unsigned char *join_next_attribute_ptr;
971  size_t element_size;
972  tuple_id_t right_tuple_id;
973  attribute_value_t value;
974  int i;
975 
976  handle = (db_handle_t *)handle_ptr;
977  left_rel = handle->left_rel;
978  right_rel = handle->right_rel;
979  join_rel = handle->join_rel;
980 
981  if(!(handle->flags & DB_HANDLE_FLAG_INDEX_STEP)) {
982  goto inner_loop;
983  }
984 
985  /* Equi-join for indexed attributes only. In the outer loop, we iterate over
986  each tuple in the left relation. */
987  for(handle->tuple_id = 0;; handle->tuple_id++) {
988  result = storage_get_row(left_rel, &handle->tuple_id, left_row);
989  if(DB_ERROR(result)) {
990  PRINTF("DB: Failed to get a row in left relation %s!\n", left_rel->name);
991  return result;
992  } else if(result == DB_FINISHED) {
993  return DB_FINISHED;
994  }
995 
996  if(DB_ERROR(relation_get_value(left_rel, handle->left_join_attr, left_row, &value))) {
997  PRINTF("DB: Failed to get a value of the attribute \"%s\" to join on\n",
998  handle->left_join_attr->name);
999  return DB_IMPLEMENTATION_ERROR;
1000  }
1001 
1002  if(DB_ERROR(index_get_iterator(&handle->index_iterator,
1003  handle->right_join_attr->index,
1004  &value, &value))) {
1005  PRINTF("DB: Failed to get an index iterator\n");
1006  return DB_INDEX_ERROR;
1007  }
1008  handle->flags &= ~DB_HANDLE_FLAG_INDEX_STEP;
1009 
1010  /* In the inner loop, we iterate over all rows with a matching value for the
1011  join attribute. The index component provides an iterator for this purpose. */
1012 inner_loop:
1013  for(;;) {
1014  /* Get all rows matching the attribute value in the right relation. */
1015  right_tuple_id = index_get_next(&handle->index_iterator);
1016  if(right_tuple_id == INVALID_TUPLE) {
1017  /* Exclude this row from the left relation in the result,
1018  and step to the next value in the index iteration. */
1019  handle->flags |= DB_HANDLE_FLAG_INDEX_STEP;
1020  break;
1021  }
1022 
1023  result = storage_get_row(right_rel, &right_tuple_id, right_row);
1024  if(DB_ERROR(result)) {
1025  PRINTF("DB: Failed to get a row in right relation %s!\n", right_rel->name);
1026  return result;
1027  } else if(result == DB_FINISHED) {
1028  PRINTF("DB: The index refers to an invalid row: %lu\n",
1029  (unsigned long)right_tuple_id);
1030  return DB_IMPLEMENTATION_ERROR;
1031  }
1032 
1033  /* Use the source attribute map to fill in the physical representation
1034  of the resulting tuple. */
1035  join_next_attribute_ptr = join_row;
1036 
1037  for(i = 0; i < join_rel->attribute_count; i++) {
1038  element_size = source_map[i].attr->element_size;
1039 
1040  memcpy(join_next_attribute_ptr, source_map[i].from_ptr, element_size);
1041  join_next_attribute_ptr += element_size;
1042  }
1043 
1044  if(((aql_adt_t *)handle->adt)->flags & AQL_FLAG_ASSIGN) {
1045  if(DB_ERROR(storage_put_row(join_rel, join_row))) {
1046  return DB_STORAGE_ERROR;
1047  }
1048  }
1049 
1050  handle->current_row++;
1051  return DB_GOT_ROW;
1052  }
1053  }
1054 
1055  return DB_OK;
1056 }
1057 
1058 static db_result_t
1059 generate_join_result(db_handle_t *handle)
1060 {
1061  relation_t *left_rel;
1062  relation_t *right_rel;
1063  relation_t *join_rel;
1064  attribute_t *attr;
1065  attribute_t *result_attr;
1066  struct source_map *source_pair;
1067  int i;
1068  int offset;
1069  unsigned char *from_ptr;
1070 
1071  handle->tuple = (tuple_t)join_row;
1072  handle->tuple_id = 0;
1073 
1074  left_rel = handle->left_rel;
1075  right_rel = handle->right_rel;
1076  join_rel = handle->join_rel;
1077 
1078  /* Generate a map over the source attributes for each
1079  attribute in the join relation. */
1080  for(i = 0, result_attr = list_head(join_rel->attributes);
1081  result_attr != NULL;
1082  result_attr = result_attr->next, i++) {
1083  source_pair = &source_map[i];
1084  attr = attribute_find(left_rel, result_attr->name);
1085  if(attr != NULL) {
1086  offset = get_attribute_value_offset(left_rel, attr);
1087  from_ptr = left_row + offset;
1088  } else if((attr = attribute_find(right_rel, result_attr->name)) != NULL) {
1089  offset = get_attribute_value_offset(right_rel, attr);
1090  from_ptr = right_row + offset;
1091  } else {
1092  PRINTF("DB: The attribute %s could not be found\n", result_attr->name);
1093  return DB_NAME_ERROR;
1094  }
1095 
1096  if(offset < 0) {
1097  PRINTF("DB: Unable to retrieve attribute values for the JOIN result\n");
1098  return DB_IMPLEMENTATION_ERROR;
1099  }
1100 
1101  source_pair->attr = attr;
1102  source_pair->from_ptr = from_ptr;
1103  }
1104 
1105  handle->flags |= DB_HANDLE_FLAG_PROCESSING;
1106 
1107  return DB_OK;
1108 }
1109 
1110 db_result_t
1111 relation_join(void *query_result, void *adt_ptr)
1112 {
1113  aql_adt_t *adt;
1114  db_handle_t *handle;
1115  relation_t *left_rel;
1116  relation_t *right_rel;
1117  relation_t *join_rel;
1118  char *name;
1119  db_direction_t dir;
1120  int i;
1121  char *attribute_name;
1122  attribute_t *attr;
1123 
1124  adt = (aql_adt_t *)adt_ptr;
1125 
1126  handle = (db_handle_t *)query_result;
1127  handle->current_row = 0;
1128  handle->ncolumns = 0;
1129  handle->adt = adt;
1130  handle->flags = DB_HANDLE_FLAG_INDEX_STEP;
1131 
1132  if(AQL_GET_FLAGS(adt) & AQL_FLAG_ASSIGN) {
1133  name = adt->relations[0];
1134  dir = DB_STORAGE;
1135  } else {
1136  name = RESULT_RELATION;
1137  dir = DB_MEMORY;
1138  }
1139  relation_remove(name, 1);
1140  relation_create(name, dir);
1141  join_rel = relation_load(name);
1142  handle->result_rel = join_rel;
1143 
1144  if(join_rel == NULL) {
1145  PRINTF("DB: Failed to create a join relation!\n");
1146  return DB_ALLOCATION_ERROR;
1147  }
1148 
1149  handle->join_rel = handle->result_rel = join_rel;
1150  left_rel = handle->left_rel;
1151  right_rel = handle->right_rel;
1152 
1153  handle->left_join_attr = relation_attribute_get(left_rel, adt->attributes[0].name);
1154  handle->right_join_attr = relation_attribute_get(right_rel, adt->attributes[0].name);
1155  if(handle->left_join_attr == NULL || handle->right_join_attr == NULL) {
1156  PRINTF("DB: The attribute (\"%s\") to join on does not exist in both relations\n",
1157  adt->attributes[0].name);
1158  return DB_RELATIONAL_ERROR;
1159  }
1160 
1161  if(!index_exists(handle->right_join_attr)) {
1162  PRINTF("DB: The attribute to join on is not indexed\n");
1163  return DB_INDEX_ERROR;
1164  }
1165 
1166  /*
1167  * Define the resulting relation. We start from 1 when counting attributes
1168  * because the first attribute is only the one to join, and is not included
1169  * by default in the projected attributes.
1170  */
1171  for(i = 1; i < AQL_ATTRIBUTE_COUNT(adt); i++) {
1172  attribute_name = adt->attributes[i].name;
1173  attr = relation_attribute_get(left_rel, attribute_name);
1174  if(attr == NULL) {
1175  attr = relation_attribute_get(right_rel, attribute_name);
1176  if(attr == NULL) {
1177  PRINTF("DB: The projection attribute \"%s\" does not exist in any of the relations to join\n",
1178  attribute_name);
1179  return DB_RELATIONAL_ERROR;
1180  }
1181  }
1182 
1183  if(relation_attribute_add(join_rel, dir, attr->name, attr->domain,
1184  attr->element_size) == NULL) {
1185  PRINTF("DB: Failed to add an attribute to the join relation\n");
1186  return DB_ALLOCATION_ERROR;
1187  }
1188 
1189  handle->ncolumns++;
1190  }
1191 
1192  return generate_join_result(handle);
1193 }
1194 #endif /* DB_FEATURE_JOIN */
1195 
1196 tuple_id_t
1197 relation_cardinality(relation_t *rel)
1198 {
1199  tuple_id_t tuple_id;
1200 
1201 
1202  if(rel->cardinality != INVALID_TUPLE) {
1203  return rel->cardinality;
1204  }
1205 
1206  if(!RELATION_HAS_TUPLES(rel)) {
1207  return 0;
1208  }
1209 
1210  if(DB_ERROR(storage_get_row_amount(rel, &tuple_id))) {
1211  return INVALID_TUPLE;
1212  }
1213 
1214  rel->cardinality = tuple_id;
1215 
1216  PRINTF("DB: Relation %s has cardinality %lu\n", rel->name,
1217  (unsigned long)tuple_id);
1218 
1219  return tuple_id;
1220 }
#define LIST_STRUCT_INIT(struct_ptr, name)
Initialize a linked list that is part of a structure.
Definition: list.h:125
int memb_free(struct memb *m, void *ptr)
Deallocate a memory block from a memory block previously declared with MEMB().
Definition: memb.c:78
Header file for the CRC16 calculcation
A set of debugging macros for the IP stack
Definitions and declarations for AQL, the Antelope Query Language.
Declarations for the result acquisition API.
Linked list manipulation routines.
void * list_head(list_t list)
Get a pointer to the first element of a list.
Definition: list.c:82
The storage interface used by the database.
Database configuration options.
Memory block allocation routines.
Definitions and declarations for the Propositional Logic Engine.
void list_add(list_t list, void *item)
Add an item at the end of a list.
Definition: list.c:142
void list_init(list_t list)
Initialize a list.
Definition: list.c:65
#define LIST(name)
Declare a linked list.
Definition: list.h:89
void * memb_alloc(struct memb *m)
Allocate a memory block from a block of memory declared with MEMB().
Definition: memb.c:59
void * list_pop(list_t list)
Remove the first object on a list.
Definition: list.c:215
void memb_init(struct memb *m)
Initialize a memory block that was declared with MEMB().
Definition: memb.c:52
void list_remove(list_t list, void *item)
Remove a specific element from a list.
Definition: list.c:237
#define MEMB(name, structure, num)
Declare a memory block.
Definition: memb.h:90