Contiki-NG
index.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  * This component forwards index calls using the generic index
33  * API to specific implementations.
34  * \author
35  * Nicolas Tsiftes <nvt@sics.se>
36  */
37 
38 #include "contiki.h"
39 #include "lib/memb.h"
40 #include "lib/list.h"
41 
42 #define DEBUG DEBUG_NONE
43 #include "net/ipv6/uip-debug.h"
44 
45 #include "antelope.h"
46 #include "attribute.h"
47 #include "db-options.h"
48 #include "index.h"
49 #include "storage.h"
50 
51 static index_api_t *index_components[] = {&index_inline,
52  &index_maxheap};
53 
54 LIST(indices);
55 MEMB(index_memb, index_t, DB_INDEX_POOL_SIZE);
56 
57 static process_event_t load_request_event;
58 PROCESS(db_indexer, "DB Indexer");
59 
60 static index_api_t *
61 find_index_api(index_type_t index_type)
62 {
63  int i;
64 
65  for(i = 0; i < sizeof(index_components) / sizeof(index_components[0]); i++) {
66  if(index_components[i]->type == index_type) {
67  return index_components[i];
68  }
69  }
70 
71  return NULL;
72 }
73 
74 void
75 index_init(void)
76 {
77  list_init(indices);
78  memb_init(&index_memb);
79  process_start(&db_indexer, NULL);
80 }
81 
82 db_result_t
83 index_create(index_type_t index_type, relation_t *rel, attribute_t *attr)
84 {
85  tuple_id_t cardinality;
86  index_t *index;
87  index_api_t *api;
88 
89  cardinality = relation_cardinality(rel);
90  if(cardinality == INVALID_TUPLE) {
91  return DB_STORAGE_ERROR;
92  }
93 
94  if(attr->domain != DOMAIN_INT && attr->domain != DOMAIN_LONG) {
95  PRINTF("DB: Cannot create an index for a non-number attribute!\n");
96  return DB_INDEX_ERROR;
97  }
98 
99  api = find_index_api(index_type);
100  if(api == NULL) {
101  PRINTF("DB: No API for index type %d\n", (int)index_type);
102  return DB_INDEX_ERROR;
103  }
104 
105  if(attr->index != NULL) {
106  /* Refuse to overwrite the old index. */
107  PRINTF("DB: The attribute %s is already indexed\n", attr->name);
108  return DB_INDEX_ERROR;
109  }
110 
111  index = memb_alloc(&index_memb);
112  if(index == NULL) {
113  PRINTF("DB: Failed to allocate an index\n");
114  return DB_ALLOCATION_ERROR;
115  }
116 
117  index->rel = rel;
118  index->attr = attr;
119  index->api = api;
120  index->flags = 0;
121  index->opaque_data = NULL;
122  index->descriptor_file[0] = '\0';
123  index->type = index_type;
124 
125  if(DB_ERROR(api->create(index))) {
126  memb_free(&index_memb, index);
127  PRINTF("DB: Index-specific creation failed for attribute %s\n", attr->name);
128  return DB_INDEX_ERROR;
129  }
130 
131  attr->index = index;
132  list_push(indices, index);
133 
134  if(index->descriptor_file[0] != '\0' &&
135  DB_ERROR(storage_put_index(index))) {
136  api->destroy(index);
137  memb_free(&index_memb, index);
138  PRINTF("DB: Failed to store index data in file \"%s\"\n",
139  index->descriptor_file);
140  return DB_INDEX_ERROR;
141  }
142 
143  if(!(api->flags & INDEX_API_INLINE) && cardinality > 0) {
144  PRINTF("DB: Created an index for an old relation; issuing a load request\n");
145  index->flags = INDEX_LOAD_NEEDED;
146  process_post(&db_indexer, load_request_event, NULL);
147  } else {
148  /* Inline indexes (i.e., those using the existing storage of the relation)
149  do not need to be reloaded after restarting the system. */
150  PRINTF("DB: Index created for attribute %s\n", attr->name);
151  index->flags |= INDEX_READY;
152  }
153 
154  return DB_OK;
155 }
156 
157 db_result_t
158 index_destroy(index_t *index)
159 {
160  if(DB_ERROR(index_release(index)) ||
161  DB_ERROR(index->api->destroy(index))) {
162  return DB_INDEX_ERROR;
163  }
164 
165  return DB_OK;
166 }
167 
168 db_result_t
169 index_load(relation_t *rel, attribute_t *attr)
170 {
171  index_t *index;
172  index_api_t *api;
173 
174  PRINTF("DB: Attempting to load an index over %s.%s\n", rel->name, attr->name);
175 
176  index = memb_alloc(&index_memb);
177  if(index == NULL) {
178  PRINTF("DB: No more index objects available\n");
179  return DB_ALLOCATION_ERROR;
180  }
181 
182  if(DB_ERROR(storage_get_index(index, rel, attr))) {
183  PRINTF("DB: Failed load an index descriptor from storage\n");
184  memb_free(&index_memb, index);
185  return DB_INDEX_ERROR;
186  }
187 
188  index->rel = rel;
189  index->attr = attr;
190  index->opaque_data = NULL;
191 
192  api = find_index_api(index->type);
193  if(api == NULL) {
194  PRINTF("DB: No API for index type %d\n", index->type);
195  return DB_INDEX_ERROR;
196  }
197 
198  index->api = api;
199 
200  if(DB_ERROR(api->load(index))) {
201  PRINTF("DB: Index-specific load failed\n");
202  return DB_INDEX_ERROR;
203  }
204 
205  list_push(indices, index);
206  attr->index = index;
207  index->flags = INDEX_READY;
208 
209  return DB_OK;
210 }
211 
212 db_result_t
213 index_release(index_t *index)
214 {
215  if(DB_ERROR(index->api->release(index))) {
216  return DB_INDEX_ERROR;
217  }
218 
219  index->attr->index = NULL;
220  list_remove(indices, index);
221  memb_free(&index_memb, index);
222 
223  return DB_OK;
224 }
225 
226 db_result_t
227 index_insert(index_t *index, attribute_value_t *value,
228  tuple_id_t tuple_id)
229 {
230  return index->api->insert(index, value, tuple_id);
231 }
232 
233 db_result_t
234 index_delete(index_t *index, attribute_value_t *value)
235 {
236  if(index->flags != INDEX_READY) {
237  return DB_INDEX_ERROR;
238  }
239 
240  return index->api->delete(index, value);
241 }
242 
243 db_result_t
244 index_get_iterator(index_iterator_t *iterator, index_t *index,
245  attribute_value_t *min_value,
246  attribute_value_t *max_value)
247 {
248  tuple_id_t cardinality;
249  unsigned long range;
250  unsigned long max_range;
251  long max;
252  long min;
253 
254  cardinality = relation_cardinality(index->rel);
255  if(cardinality == INVALID_TUPLE) {
256  return DB_STORAGE_ERROR;
257  }
258 
259  if(index->flags != INDEX_READY) {
260  return DB_INDEX_ERROR;
261  }
262 
263  min = db_value_to_long(min_value);
264  max = db_value_to_long(max_value);
265 
266  range = (unsigned long)max - min;
267  if(range > 0) {
268  /*
269  * Index structures that do not have a natural ability to handle
270  * range queries (e.g., a hash index) can nevertheless emulate them.
271  *
272  * The range query emulation attempts to look up the key for each
273  * value in the search range. If the search range is sparse, this
274  * iteration will incur a considerable overhead per found key.
275  *
276  * Hence, the emulation is preferable when an external module wants
277  * to iterate over a narrow range of keys, for which the total
278  * search cost is smaller than that of an iteration over all tuples
279  * in the relation.
280  */
281  if(!(index->api->flags & INDEX_API_RANGE_QUERIES)) {
282  PRINTF("DB: Range query requested for an index that does not support it\n");
283  max_range = cardinality / DB_INDEX_COST;
284  if(range > max_range) {
285  return DB_INDEX_ERROR;
286  }
287  PRINTF("DB: Using the index anyway because the range is small enough (%lu <= %lu)\n",
288  range, max_range);
289  }
290  }
291 
292  iterator->index = index;
293  iterator->min_value = *min_value;
294  iterator->max_value = *max_value;
295  iterator->next_item_no = 0;
296 
297  PRINTF("DB: Acquired an index iterator for %s.%s over the range (%ld,%ld)\n",
298  index->rel->name, index->attr->name,
299  min_value->u.long_value, max_value->u.long_value);
300 
301  return DB_OK;
302 }
303 
304 tuple_id_t
305 index_get_next(index_iterator_t *iterator)
306 {
307  long min;
308  long max;
309 
310  if(iterator->index == NULL) {
311  /* This attribute is not indexed. */
312  return INVALID_TUPLE;
313  }
314 
315  if((iterator->index->attr->flags & ATTRIBUTE_FLAG_UNIQUE) &&
316  iterator->next_item_no == 1) {
317  min = db_value_to_long(&iterator->min_value);
318  max = db_value_to_long(&iterator->max_value);
319  if(min == max) {
320  /*
321  * We stop if this is an equivalence search on an attribute
322  * whose values are unique, and we already found one item.
323  */
324  PRINTF("DB: Equivalence search finished\n");
325  return INVALID_TUPLE;
326  }
327  }
328 
329  return iterator->index->api->get_next(iterator);
330 }
331 
332 int
333 index_exists(attribute_t *attr)
334 {
335  index_t *index;
336 
337  index = (index_t *)attr->index;
338  if(index == NULL || index->flags != INDEX_READY) {
339  return 0;
340  }
341 
342  return 1;
343 }
344 
345 static index_t *
346 get_next_index_to_load(void)
347 {
348  index_t *index;
349 
350  for(index = list_head(indices); index != NULL; index = index->next) {
351  if(index->flags & INDEX_LOAD_NEEDED) {
352  return index;
353  }
354  }
355 
356  return NULL;
357 }
358 
359 PROCESS_THREAD(db_indexer, ev, data)
360 {
361  static index_t *index;
362  static db_handle_t handle;
363  static tuple_id_t row;
364  db_result_t result;
365  attribute_value_t value;
366  int column;
367 
368  PROCESS_BEGIN();
369  load_request_event = process_alloc_event();
370 
371  for(;;) {
372  PROCESS_WAIT_EVENT_UNTIL(ev == load_request_event);
373 
374  index = get_next_index_to_load();
375  if(index == NULL) {
376  PRINTF("DB: Request to load an index, but no index is set to be loaded\n");
377  continue;
378  }
379 
380  PRINTF("DB: Loading the index for %s.%s...\n",
381  index->rel->name, index->attr->name);
382 
383  /* Project the values of the indexed attribute from all tuples in
384  the relation, and insert them into the index again. */
385  if(DB_ERROR(db_query(&handle, "SELECT %s FROM %s;", index->attr->name, index->rel->name))) {
386  index->flags |= INDEX_LOAD_ERROR;
387  index->flags &= ~INDEX_LOAD_NEEDED;
388  continue;
389  }
390 
391  for(;; row++) {
392  PROCESS_PAUSE();
393 
394  result = db_process(&handle);
395  if(DB_ERROR(result)) {
396  PRINTF("DB: Index loading failed while processing: %s\n",
397  db_get_result_message(result));
398  index->flags |= INDEX_LOAD_ERROR;
399  goto cleanup;
400  }
401  if(result == DB_FINISHED) {
402  break;
403  }
404 
405  for(column = 0; column < handle.ncolumns; column++) {
406  if(DB_ERROR(db_get_value(&value, &handle, column))) {
407  index->flags |= INDEX_LOAD_ERROR;
408  goto cleanup;
409  }
410 
411  if(DB_ERROR(index_insert(index, &value, row))) {
412  index->flags |= INDEX_LOAD_ERROR;
413  goto cleanup;
414  }
415  }
416  }
417 
418  PRINTF("DB: Loaded %lu rows into the index\n",
419  (unsigned long)handle.current_row);
420 
421 cleanup:
422  if(index->flags & INDEX_LOAD_ERROR) {
423  PRINTF("DB: Failed to load the index for %s.%s\n",
424  index->rel->name, index->attr->name);
425  }
426  index->flags &= ~INDEX_LOAD_NEEDED;
427  index->flags |= INDEX_READY;
428  db_free(&handle);
429  }
430 
431 
432  PROCESS_END();
433 }
#define PROCESS(name, strname)
Declare a process.
Definition: process.h:307
void list_push(list_t list, void *item)
Add an item to the start of the list.
Definition: list.c:164
#define PROCESS_BEGIN()
Define the beginning of a process.
Definition: process.h:120
#define PROCESS_END()
Define the end of a process.
Definition: process.h:131
#define PROCESS_WAIT_EVENT_UNTIL(c)
Wait for an event to be posted to the process, with an extra condition.
Definition: process.h:157
A set of debugging macros for the IP stack
#define PROCESS_PAUSE()
Yield the process for a short while.
Definition: process.h:221
Definitions for attributes.
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.
process_event_t process_alloc_event(void)
Allocate a global event number.
Definition: process.c:93
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
int process_post(struct process *p, process_event_t ev, process_data_t data)
Post an asynchronous event.
Definition: process.c:322
PROCESS_THREAD(cc2538_rf_process, ev, data)
Implementation of the cc2538 RF driver process.
Definition: cc2538-rf.c:1097
void memb_init(struct memb *m)
Initialize a memory block that was declared with MEMB().
Definition: memb.c:52
char memb_free(struct memb *m, void *ptr)
Deallocate a memory block from a memory block previously declared with MEMB().
Definition: memb.c:79
Declarations of the main Antelope functions.
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:89
void process_start(struct process *p, process_data_t data)
Start a process.
Definition: process.c:99