Contiki-NG
index-memhash.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 memory-resident hash map used as a DB index.
33  * \author
34  * Nicolas Tsiftes <nvt@sics.se>
35  */
36 
37 #include <string.h>
38 
39 #include "lib/memb.h"
40 
41 #include "db-options.h"
42 #include "index.h"
43 
44 #define DEBUG DEBUG_NONE
45 #include "net/ipv6/uip-debug.h"
46 
47 static db_result_t create(index_t *);
48 static db_result_t destroy(index_t *);
49 static db_result_t load(index_t *);
50 static db_result_t release(index_t *);
51 static db_result_t insert(index_t *, attribute_value_t *, tuple_id_t);
52 static db_result_t delete(index_t *, attribute_value_t *);
53 static tuple_id_t get_next(index_iterator_t *);
54 
55 index_api_t index_memhash = {
56  INDEX_MEMHASH,
57  INDEX_API_INTERNAL,
58  create,
59  destroy,
60  load,
61  release,
62  insert,
63  delete,
64  get_next
65 };
66 
67 struct hash_item {
68  tuple_id_t tuple_id;
69  attribute_value_t value;
70 };
71 typedef struct hash_item hash_item_t;
72 
73 typedef hash_item_t hash_map_t[DB_MEMHASH_TABLE_SIZE];
74 
75 MEMB(hash_map_memb, hash_map_t, DB_MEMHASH_INDEX_LIMIT);
76 
77 static unsigned
78 calculate_hash(attribute_value_t *value)
79 {
80  unsigned char *cp, *end;
81  unsigned hash_value;
82 
83  cp = (unsigned char *)value;
84  end = cp + sizeof(*value);
85  hash_value = 0;
86 
87  while(cp < end) {
88  hash_value = hash_value * 33 + *cp++;
89  }
90 
91  return hash_value % DB_MEMHASH_TABLE_SIZE;
92 }
93 
94 static db_result_t
95 create(index_t *index)
96 {
97  int i;
98  hash_map_t *hash_map;
99 
100  PRINTF("Creating a memory-resident hash map index\n");
101 
102  hash_map = memb_alloc(&hash_map_memb);
103  if(hash_map == NULL) {
104  return DB_ALLOCATION_ERROR;
105  }
106 
107  for(i = 0; i < DB_MEMHASH_TABLE_SIZE; i++) {
108  hash_map[i]->tuple_id = INVALID_TUPLE;
109  }
110 
111  index->opaque_data = hash_map;
112 
113  return DB_OK;
114 }
115 
116 static db_result_t
117 destroy(index_t *index)
118 {
119  memb_free(&hash_map_memb, index->opaque_data);
120 
121  return DB_OK;
122 }
123 
124 static db_result_t
125 load(index_t *index)
126 {
127  return create(index);
128 }
129 
130 static db_result_t
131 release(index_t *index)
132 {
133  return destroy(index);
134 }
135 
136 static db_result_t
137 insert(index_t *index, attribute_value_t *value, tuple_id_t tuple_id)
138 {
139  hash_map_t *hash_map;
140  uint16_t hash_value;
141 
142  hash_map = index->opaque_data;
143 
144  hash_value = calculate_hash(value);
145  hash_map[hash_value]->tuple_id = tuple_id;
146  hash_map[hash_value]->value = *value;
147 
148  PRINTF("DB: Inserted value %ld into the hash table\n", VALUE_LONG(value));
149 
150  return DB_OK;
151 }
152 
153 static db_result_t
154 delete(index_t *index, attribute_value_t *value)
155 {
156  hash_map_t *hash_map;
157  uint16_t hash_value;
158 
159  hash_map = index->opaque_data;
160 
161  hash_value = calculate_hash(value);
162  if(memcmp(&hash_map[hash_value]->value, value, sizeof(*value)) != 0) {
163  return DB_INDEX_ERROR;
164  }
165 
166  hash_map[hash_value]->tuple_id = INVALID_TUPLE;
167  return DB_OK;
168 }
169 
170 static tuple_id_t
171 get_next(index_iterator_t *iterator)
172 {
173  hash_map_t *hash_map;
174  uint16_t hash_value;
175 
176  if(iterator->next_item_no == 1) {
177  /* The memhash supports only unique values at the moment. */
178  return INVALID_TUPLE;
179  }
180 
181  hash_map = iterator->index->opaque_data;
182 
183  hash_value = calculate_hash(&iterator->min_value);
184  if(memcmp(&hash_map[hash_value]->value, &iterator->min_value, sizeof(iterator->min_value)) != 0) {
185  return INVALID_TUPLE;
186  }
187 
188  iterator->next_item_no++;
189 
190  PRINTF("DB: Found value %ld in the hash table\n",
191  VALUE_LONG(&iterator->min_value));
192 
193  return hash_map[hash_value]->tuple_id;
194 }
A set of debugging macros for the IP stack
Database configuration options.
Memory block allocation routines.
void * memb_alloc(struct memb *m)
Allocate a memory block from a block of memory declared with MEMB().
Definition: memb.c:59
char memb_free(struct memb *m, void *ptr)
Deallocate a memory block from a memory block previously declared with MEMB().
Definition: memb.c:79
#define MEMB(name, structure, num)
Declare a memory block.
Definition: memb.h:89