Contiki-NG
index-inline.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  * A binary search index for attributes that are constrained to be
33  * monotonically increasing, which is a rather common pattern for
34  * time series or keys. Since this index has no storage overhead,
35  * it does not wear out the flash memory nor does it occupy any
36  * space. Furthermore, unlike B+-trees, it has a O(1) memory
37  * footprint in relation to the number of data items.
38  * \author
39  * Nicolas Tsiftes <nvt@sics.se>
40  */
41 
42 #include <stdlib.h>
43 #include <string.h>
44 
45 #include "index.h"
46 #include "relation.h"
47 #include "result.h"
48 #include "storage.h"
49 
50 #define DEBUG DEBUG_NONE
51 #include "net/ipv6/uip-debug.h"
52 
53 struct search_handle {
54  index_t *index;
55  tuple_id_t start_row;
56  tuple_id_t end_row;
57 };
58 
59 struct search_handle handle;
60 
61 static db_result_t null_op(index_t *);
62 static db_result_t insert(index_t *, attribute_value_t *, tuple_id_t);
63 static db_result_t delete(index_t *, attribute_value_t *);
64 static tuple_id_t get_next(index_iterator_t *);
65 
66 /*
67  * The create, destroy, load, release, insert, and delete operations
68  * of the index API always succeed because the index does not store
69  * items separately from the row file. The four former operations share
70  * the same signature, and are thus implemented by the null_op function
71  * to save space.
72  */
73 index_api_t index_inline = {
74  INDEX_INLINE,
75  INDEX_API_EXTERNAL | INDEX_API_COMPLETE | INDEX_API_RANGE_QUERIES,
76  null_op,
77  null_op,
78  null_op,
79  null_op,
80  insert,
81  delete,
82  get_next
83 };
84 
85 static attribute_value_t *
86 get_value(tuple_id_t *index, relation_t *rel, attribute_t *attr)
87 {
88  unsigned char row[rel->row_length];
89  static attribute_value_t value;
90 
91  if(DB_ERROR(storage_get_row(rel, index, row))) {
92  return NULL;
93  }
94 
95  if(DB_ERROR(relation_get_value(rel, attr, row, &value))) {
96  PRINTF("DB: Unable to retrieve a value from tuple %ld\n", (long)(*index));
97  return NULL;
98  }
99 
100  return &value;
101 }
102 
103 static tuple_id_t
104 binary_search(index_iterator_t *index_iterator,
105  attribute_value_t *target_value,
106  int exact_match)
107 {
108  relation_t *rel;
109  attribute_t *attr;
110  attribute_value_t *cmp_value;
111  tuple_id_t min;
112  tuple_id_t max;
113  tuple_id_t center;
114 
115  rel = index_iterator->index->rel;
116  attr = index_iterator->index->attr;
117 
118  max = relation_cardinality(rel);
119  if(max == INVALID_TUPLE) {
120  return INVALID_TUPLE;
121  }
122  max--;
123  min = 0;
124 
125  do {
126  center = min + ((max - min) / 2);
127 
128  cmp_value = get_value(&center, rel, attr);
129  if(cmp_value == NULL) {
130  PRINTF("DB: Failed to get the center value, index = %ld\n",
131  (long)center);
132  return INVALID_TUPLE;
133  }
134 
135  if(db_value_to_long(target_value) > db_value_to_long(cmp_value)) {
136  min = center + 1;
137  } else {
138  max = center - 1;
139  }
140  } while(min <= max &&
141  db_value_to_long(target_value) != db_value_to_long(cmp_value));
142 
143  if(exact_match &&
144  db_value_to_long(target_value) != db_value_to_long(cmp_value)) {
145  PRINTF("DB: Could not find value %ld in the inline index\n",
146  db_value_to_long(target_value));
147  return INVALID_TUPLE;
148  }
149 
150  return center;
151 }
152 
153 static tuple_id_t
154 range_search(index_iterator_t *index_iterator,
155  tuple_id_t *start, tuple_id_t *end)
156 {
157  attribute_value_t *low_target;
158  attribute_value_t *high_target;
159  int exact_match;
160 
161  low_target = &index_iterator->min_value;
162  high_target = &index_iterator->max_value;
163 
164  PRINTF("DB: Search index for value range (%ld, %ld)\n",
165  db_value_to_long(low_target), db_value_to_long(high_target));
166 
167  exact_match = db_value_to_long(low_target) == db_value_to_long(high_target);
168 
169  /* Optimize later so that the other search uses the result
170  from the first one. */
171  *start = binary_search(index_iterator, low_target, exact_match);
172  if(*start == INVALID_TUPLE) {
173  return DB_INDEX_ERROR;
174  }
175 
176  *end = binary_search(index_iterator, high_target, exact_match);
177  if(*end == INVALID_TUPLE) {
178  return DB_INDEX_ERROR;
179  }
180  return DB_OK;
181 }
182 
183 static db_result_t
184 null_op(index_t *index)
185 {
186  return DB_OK;
187 }
188 
189 static db_result_t
190 insert(index_t *index, attribute_value_t *value, tuple_id_t tuple_id)
191 {
192  return DB_OK;
193 }
194 
195 static db_result_t
196 delete(index_t *index, attribute_value_t *value)
197 {
198  return DB_OK;
199 }
200 
201 static tuple_id_t
202 get_next(index_iterator_t *iterator)
203 {
204  static tuple_id_t cached_start;
205  static tuple_id_t cached_end;
206 
207  if(iterator->next_item_no == 0) {
208  /*
209  * We conduct the actual index search when the caller attempts to
210  * access the first item in the iteration. The first and last tuple
211  * id:s of the result get cached for subsequent iterations.
212  */
213  if(DB_ERROR(range_search(iterator, &cached_start, &cached_end))) {
214  cached_start = 0;
215  cached_end = 0;
216  return INVALID_TUPLE;
217  }
218  PRINTF("DB: Cached the tuple range (%ld,%ld)\n",
219  (long)cached_start, (long)cached_end);
220  ++iterator->next_item_no;
221  return cached_start;
222  } else if(cached_start + iterator->next_item_no <= cached_end) {
223  return cached_start + iterator->next_item_no++;
224  }
225 
226  return INVALID_TUPLE;
227 }
A set of debugging macros for the IP stack
Declarations for the result acquisition API.
static void start(void)
Start measurement.
The storage interface used by the database.