324 lines
9.3 KiB
C
324 lines
9.3 KiB
C
#include <stdlib.h>
|
|
#include <string.h>
|
|
#include <limits.h>
|
|
|
|
#include "IdIndex.h"
|
|
#include "report.h"
|
|
/*
|
|
================================================================
|
|
IdIndex - a simple associative array for acquiring an index via a key
|
|
================================================================
|
|
hash_size should be geared towards the amount of elements you think you will be storing. The hash_size defines the size of the hash_index.
|
|
The larger the hash_index's size, the fewer IndexEntry position collisions occur, thereby increasing computational speed at the expense of memory.
|
|
|
|
Note: It is fastest to add an item, then only work with the id/index from there on out (rather than using the name/string/key). However, freeing from Id is slower than freeing from string as it must iterate over every IdIndexEntry to see if its id matches!
|
|
*/
|
|
struct IdIndex *initIdIndex(struct IdIndex *index, int hash_size, int max_ids) {
|
|
if (index == NULL) {
|
|
report(ERROR, "initIdIndex", "passed IdIndex is NULL");
|
|
return NULL;
|
|
}
|
|
if (hash_size <= 0) {
|
|
report(WARNING, "initIdIndex", "hash_size cannot be <= 0, using HASH_DEFAULT");
|
|
hash_size = HASH_DEFAULT;
|
|
}
|
|
index->hash_size = hash_size;
|
|
index->hash_index = malloc(sizeof(struct IndexEntry*)*hash_size);
|
|
int hash_i;
|
|
for (hash_i = 0; hash_i < hash_size;hash_i++) {
|
|
index->hash_index[hash_i] = NULL;
|
|
}
|
|
if ((index->ids = malloc(max_ids * sizeof(char))) == NULL) {
|
|
report(ERROR, "initIdIndex", "could not allocate memory for ids");
|
|
return NULL;
|
|
}
|
|
memset(index->ids, 0, max_ids);
|
|
index->max_ids = max_ids;
|
|
return index;
|
|
}
|
|
int freeIdIndex(struct IdIndex *index) {
|
|
int hash_i;
|
|
for (hash_i = 0; hash_i < index->hash_size;hash_i++) {
|
|
struct IdIndexEntry *entry = index->hash_index[hash_i];
|
|
// first see if the hash location is empty
|
|
if (entry == NULL) {
|
|
continue;
|
|
}
|
|
// nope find and free linked list
|
|
struct IdIndexEntry *next_entry = NULL;
|
|
while (entry != NULL) {
|
|
next_entry = entry->next;
|
|
freeIdIndexEntry(entry);
|
|
entry = next_entry;
|
|
}
|
|
}
|
|
free(index->ids);
|
|
return 0;
|
|
}
|
|
|
|
/*
|
|
========================
|
|
addIdIndex
|
|
Adds an IdIndexEntry to the IdIndex using the given string and id.
|
|
|
|
Returns:
|
|
int Id of the added IdIndexEntry
|
|
========================
|
|
*/
|
|
int addIdIndex(struct IdIndex *index, const char *string, int id) {
|
|
if (index == NULL) {
|
|
report(ERROR, "addIdIndex", "passed IdIndex is NULL");
|
|
return -1;
|
|
}
|
|
if (string == NULL) {
|
|
report(ERROR, "addIdIndex", "passed string is NULL");
|
|
return -2;
|
|
}
|
|
if (id < 0 || id > index->max_ids) {
|
|
report(ERROR, "addIdIndex", "id \"%d\" is out of range", id);
|
|
return -3;
|
|
}
|
|
if (index->ids[id] != 0) {
|
|
report(ERROR, "addIdIndex", "id \"%d\" is not free", id);
|
|
return -4;
|
|
}
|
|
int hash = getStringHash(index->hash_size, string);
|
|
struct IdIndexEntry *entry = index->hash_index[hash];
|
|
// first see if the hash location is empty
|
|
if (entry == NULL) {
|
|
index->hash_index[hash] = newIdIndexEntry(string, id);
|
|
index->ids[id] = 1;
|
|
return id;
|
|
}
|
|
// nope, let's find open spot
|
|
while (entry->next != NULL) {
|
|
if (strcmp(entry->name, string) == 0) {
|
|
report(WARNING, "addIdIndex", "IdIndexEntry \"%s\" already exists", string);
|
|
return id;
|
|
}
|
|
entry = entry->next;
|
|
}
|
|
// found a spot
|
|
entry->next = newIdIndexEntry(string, id);
|
|
index->ids[id] = 1;
|
|
return id;
|
|
}
|
|
|
|
int remIdIndex(struct IdIndex *index, const char *string) {
|
|
if (index == NULL) {
|
|
report(ERROR, "remIdIndex", "passed IdIndex is NULL");
|
|
return -1;
|
|
}
|
|
if (string == NULL) {
|
|
report(ERROR, "remIdIndex", "passed string is NULL");
|
|
return -2;
|
|
}
|
|
int hash = getStringHash(index->hash_size, string);
|
|
struct IdIndexEntry *entry = index->hash_index[hash];
|
|
struct IdIndexEntry *last_entry = NULL;
|
|
// have to check if hash_index is first separately to set to NULL if it is
|
|
if (entry != NULL) {
|
|
if (strcmp(entry->name, string) == 0) {
|
|
index->hash_index[hash] = entry->next;
|
|
int id = entry->id;
|
|
index->ids[id] = 0;
|
|
freeIdIndexEntry(entry);
|
|
return id;
|
|
}
|
|
}
|
|
while (entry != NULL) {
|
|
if (strcmp(entry->name, string) == 0) {
|
|
int id = entry->id;
|
|
index->ids[id] = 0;
|
|
if (last_entry != NULL) {
|
|
last_entry->next = entry->next;
|
|
}
|
|
freeIdIndexEntry(entry);
|
|
return id;
|
|
} else {
|
|
last_entry = entry;
|
|
entry = entry->next;
|
|
}
|
|
}
|
|
//report(WARNING, "remIdIndex", "no IdIndexEntry matching \"%s\" found", string);
|
|
return -3;
|
|
}
|
|
|
|
int remIdIndexById(struct IdIndex *index, int id) {
|
|
if (index == NULL) {
|
|
report(ERROR, "remIdIndexById", "passed IdIndex is NULL");
|
|
return -1;
|
|
}
|
|
if (id < 0 || id > index->hash_size) {
|
|
report(ERROR, "remIdIndexById", "passed id \"%d\" is out of range", id);
|
|
return -2;
|
|
}
|
|
// Hah, it is probably faster to get index by string..
|
|
int hash = 0;
|
|
while (hash < index->hash_size) {
|
|
struct IdIndexEntry *entry = index->hash_index[hash];
|
|
struct IdIndexEntry *last_entry = NULL;
|
|
if (entry != NULL) {
|
|
if (entry->id == id) {
|
|
index->ids[id] = 0;
|
|
freeIdIndexEntry(entry);
|
|
index->hash_index[hash] = NULL;
|
|
entry = NULL;
|
|
}
|
|
}
|
|
while (entry != NULL) {
|
|
if (entry->id == id) {
|
|
index->ids[id] = 0;
|
|
if (last_entry != NULL) {
|
|
last_entry->next = entry->next;
|
|
}
|
|
freeIdIndexEntry(entry);
|
|
entry = NULL;
|
|
return id;
|
|
}
|
|
last_entry = entry;
|
|
entry = entry->next;
|
|
}
|
|
hash++;
|
|
}
|
|
report(WARNING, "remIdIndex", "no IdIndexEntry \"%d\" found", id);
|
|
return -3;
|
|
}
|
|
|
|
int getIdIndex(struct IdIndex *index, const char *string) {
|
|
if (index == NULL) {
|
|
report(ERROR, "getIdIndex", "passed IdIndex is NULL");
|
|
return -1;
|
|
}
|
|
if (string == NULL) {
|
|
report(ERROR, "getIdIndex", "passed string is NULL");
|
|
return -2;
|
|
}
|
|
int hash = getStringHash(index->hash_size, string);
|
|
struct IdIndexEntry *entry = index->hash_index[hash];
|
|
while (entry != NULL) {
|
|
if (strcmp(entry->name, string) == 0) {
|
|
return entry->id;
|
|
}
|
|
entry = entry->next;
|
|
}
|
|
//report(WARNING, "getIdIndex", "No IdIndexEntry matching \"%s\" found", string);
|
|
return -3;
|
|
}
|
|
|
|
/* returns 0 on free, 1 on used */
|
|
int checkIdIndexMemory(struct IdIndex *index, int id) {
|
|
if (index == NULL) {
|
|
report(ERROR, "checkIdIndexMemory", "passed index is NULL");
|
|
return -1;
|
|
}
|
|
if (id < 0 || id > index->max_ids) {
|
|
report(WARNING, "checkIdIndexMemory", "id \"%d\" out of bounds", id);
|
|
return -2;
|
|
}
|
|
return index->ids[id];
|
|
}
|
|
|
|
int resizeIdIndex(struct IdIndex *index, int max_ids) {
|
|
if (index == NULL) {
|
|
report(ERROR, "resizeIdIndex", "passed index is NULL");
|
|
return -1;
|
|
}
|
|
if (max_ids < 0) {
|
|
report(WARNING, "resizeIdIndex", "max_ids cannot be < 0, using 1");
|
|
max_ids = 1;
|
|
}
|
|
int old_max = index->max_ids;
|
|
index->max_ids = max_ids;
|
|
if ((index->ids = realloc(index->ids, index->max_ids * sizeof(char))) == NULL) {
|
|
report(ERROR, "resizeIdIndex", "could not allocate memory for ids");
|
|
return -2;
|
|
}
|
|
if (old_max < max_ids) {
|
|
memset(index->ids+old_max, 0, max_ids-old_max);
|
|
}
|
|
return index->max_ids;
|
|
}
|
|
|
|
int findOpenIdIndex(struct IdIndex *index) {
|
|
int i;
|
|
for(i=0;i <= index->max_ids;i++) {
|
|
if (index->ids[i] == 0) {
|
|
return i;
|
|
}
|
|
}
|
|
// if we got here, we're out of ids
|
|
report(WARNING, "findOpenIdIndex", "No free ids in IdIndex, please resize");
|
|
return -1;
|
|
}
|
|
/*
|
|
================================================================
|
|
IdIndexEntry - a linked list key->index struct stored in an IdIndex
|
|
================================================================
|
|
*/
|
|
|
|
struct IdIndexEntry *newIdIndexEntry(const char *string, int id) {
|
|
if (string == NULL) {
|
|
report(ERROR, "newIdIndexEntry", "passed string is NULL");
|
|
return NULL;
|
|
}
|
|
if (id < 0) {
|
|
report(ERROR, "newIdIndexEntry", "id cannot be < 0");
|
|
return NULL;
|
|
}
|
|
struct IdIndexEntry *entry = malloc(sizeof(struct IdIndexEntry));
|
|
if (entry == NULL) {
|
|
report(ERROR, "newIdIndexEntry", "could not allocate memory for IdIndexEntry");
|
|
return NULL;
|
|
}
|
|
int str_size = strlen(string)+1;
|
|
entry->name = malloc(str_size);
|
|
if (entry->name == NULL) {
|
|
report(ERROR, "newIdIndexEntry", "could not allocate memory for name \"%s\"", string);
|
|
return NULL;
|
|
}
|
|
memcpy(entry->name, string, str_size);
|
|
entry->id = id;
|
|
entry->next = NULL;
|
|
return entry;
|
|
}
|
|
|
|
int freeIdIndexEntry(struct IdIndexEntry *entry) {
|
|
if (entry == NULL) {
|
|
report(WARNING, "freeIdIndexEntry", "passed IdIndexEntry is NULL");
|
|
return 1;
|
|
}
|
|
free(entry->name);
|
|
free(entry);
|
|
return 0;
|
|
}
|
|
|
|
/*
|
|
================================================================
|
|
Helper functions
|
|
================================================================
|
|
*/
|
|
/*
|
|
================================
|
|
getStringHash
|
|
|
|
This function adds each char of *string to an int, the modulos by hash_size
|
|
================================
|
|
*/
|
|
int getStringHash(int hash_size, const char *string) {
|
|
if (hash_size <= 0) {
|
|
report(ERROR, "getStringHash", "hash size is 0, bailing");
|
|
return -1;
|
|
}
|
|
if (string == NULL) {
|
|
report(ERROR, "getStringHash", "string is NULL");
|
|
return -2;
|
|
}
|
|
int hash = 0, i;
|
|
int string_length = strlen(string);
|
|
for(i = 0; hash < INT_MAX && i < string_length;i++) {
|
|
hash += string[i];
|
|
}
|
|
return hash % hash_size;
|
|
}
|