osd-contiki/apps/antelope/index-memhash.c

195 lines
4.8 KiB
C
Raw Permalink Normal View History

/*
* Copyright (c) 2010, Swedish Institute of Computer Science
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. Neither the name of the Institute nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
/**
* \file
* A memory-resident hash map used as a DB index.
* \author
* Nicolas Tsiftes <nvt@sics.se>
*/
#include <string.h>
#include "lib/memb.h"
#include "db-options.h"
#include "index.h"
#define DEBUG DEBUG_NONE
#include "net/ip/uip-debug.h"
static db_result_t create(index_t *);
static db_result_t destroy(index_t *);
static db_result_t load(index_t *);
static db_result_t release(index_t *);
static db_result_t insert(index_t *, attribute_value_t *, tuple_id_t);
static db_result_t delete(index_t *, attribute_value_t *);
static tuple_id_t get_next(index_iterator_t *);
index_api_t index_memhash = {
INDEX_MEMHASH,
INDEX_API_INTERNAL,
create,
destroy,
load,
release,
insert,
delete,
get_next
};
struct hash_item {
tuple_id_t tuple_id;
attribute_value_t value;
};
typedef struct hash_item hash_item_t;
typedef hash_item_t hash_map_t[DB_MEMHASH_TABLE_SIZE];
MEMB(hash_map_memb, hash_map_t, DB_MEMHASH_INDEX_LIMIT);
static unsigned
calculate_hash(attribute_value_t *value)
{
unsigned char *cp, *end;
unsigned hash_value;
cp = (unsigned char *)value;
end = cp + sizeof(*value);
hash_value = 0;
while(cp < end) {
hash_value = hash_value * 33 + *cp++;
}
return hash_value % DB_MEMHASH_TABLE_SIZE;
}
static db_result_t
create(index_t *index)
{
int i;
hash_map_t *hash_map;
PRINTF("Creating a memory-resident hash map index\n");
hash_map = memb_alloc(&hash_map_memb);
if(hash_map == NULL) {
return DB_ALLOCATION_ERROR;
}
for(i = 0; i < DB_MEMHASH_TABLE_SIZE; i++) {
hash_map[i]->tuple_id = INVALID_TUPLE;
}
index->opaque_data = hash_map;
return DB_OK;
}
static db_result_t
destroy(index_t *index)
{
memb_free(&hash_map_memb, index->opaque_data);
return DB_OK;
}
static db_result_t
load(index_t *index)
{
return create(index);
}
static db_result_t
release(index_t *index)
{
return destroy(index);
}
static db_result_t
insert(index_t *index, attribute_value_t *value, tuple_id_t tuple_id)
{
hash_map_t *hash_map;
uint16_t hash_value;
hash_map = index->opaque_data;
hash_value = calculate_hash(value);
hash_map[hash_value]->tuple_id = tuple_id;
hash_map[hash_value]->value = *value;
PRINTF("DB: Inserted value %ld into the hash table\n", VALUE_LONG(value));
return DB_OK;
}
static db_result_t
delete(index_t *index, attribute_value_t *value)
{
hash_map_t *hash_map;
uint16_t hash_value;
hash_map = index->opaque_data;
hash_value = calculate_hash(value);
if(memcmp(&hash_map[hash_value]->value, value, sizeof(*value)) != 0) {
return DB_INDEX_ERROR;
}
hash_map[hash_value]->tuple_id = INVALID_TUPLE;
return DB_OK;
}
static tuple_id_t
get_next(index_iterator_t *iterator)
{
hash_map_t *hash_map;
uint16_t hash_value;
if(iterator->next_item_no == 1) {
/* The memhash supports only unique values at the moment. */
return INVALID_TUPLE;
}
hash_map = iterator->index->opaque_data;
hash_value = calculate_hash(&iterator->min_value);
if(memcmp(&hash_map[hash_value]->value, &iterator->min_value, sizeof(iterator->min_value)) != 0) {
return INVALID_TUPLE;
}
iterator->next_item_no++;
PRINTF("DB: Found value %ld in the hash table\n",
VALUE_LONG(&iterator->min_value));
return hash_map[hash_value]->tuple_id;
}