Contiki-NG
Loading...
Searching...
No Matches
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
51static index_api_t *index_components[] = {&index_inline,
52 &index_maxheap};
53
54LIST(indices);
55MEMB(index_memb, index_t, DB_INDEX_POOL_SIZE);
56
57static process_event_t load_request_event;
58PROCESS(db_indexer, "DB Indexer");
59
60static index_api_t *
61find_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
74void
75index_init(void)
76{
77 list_init(indices);
78 memb_init(&index_memb);
79 process_start(&db_indexer, NULL);
80}
81
82db_result_t
83index_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
157db_result_t
158index_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
168db_result_t
169index_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
212db_result_t
213index_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
226db_result_t
227index_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
233db_result_t
234index_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
243db_result_t
244index_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
304tuple_id_t
305index_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
332int
333index_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
345static index_t *
346get_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
359PROCESS_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
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++) {
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
421cleanup:
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}
Declarations of the main Antelope functions.
Definitions for attributes.
Database configuration options.
static void list_init(list_t list)
Initialize a list.
Definition list.h:152
#define LIST(name)
Declare a linked list.
Definition list.h:90
void list_remove(list_t list, const void *item)
Remove a specific element from a list.
Definition list.c:134
void list_push(list_t list, void *item)
Add an item to the start of the list.
Definition list.c:90
static void * list_head(const_list_t list)
Get a pointer to the first element of a list.
Definition list.h:169
int memb_free(struct memb *m, void *ptr)
Deallocate a memory block from a memory block previously declared with MEMB().
Definition memb.c:78
void * memb_alloc(struct memb *m)
Allocate a memory block from a block of memory declared with MEMB().
Definition memb.c:59
void memb_init(struct memb *m)
Initialize a memory block that was declared with MEMB().
Definition memb.c:52
#define MEMB(name, structure, num)
Declare a memory block.
Definition memb.h:91
#define PROCESS(name, strname)
Declare a process.
Definition process.h:307
#define PROCESS_PAUSE()
Yield the process for a short while.
Definition process.h:221
int process_post(struct process *p, process_event_t ev, process_data_t data)
Post an asynchronous event.
Definition process.c:325
process_event_t process_alloc_event(void)
Allocate a global event number.
Definition process.c:98
#define PROCESS_BEGIN()
Define the beginning of a process.
Definition process.h:120
#define PROCESS_WAIT_EVENT_UNTIL(c)
Wait for an event to be posted to the process, with an extra condition.
Definition process.h:157
#define PROCESS_END()
Define the end of a process.
Definition process.h:131
void process_start(struct process *p, process_data_t data)
Start a process.
Definition process.c:107
#define PROCESS_THREAD(name, ev, data)
Define the body of a process.
Definition process.h:273
Linked list manipulation routines.
Memory block allocation routines.
The storage interface used by the database.
A set of debugging macros for the IP stack.