i the following code i am getting infinite loop when i search some key.
#include <stdio.h>
#include <pthread.h>
#include <sys/mman.h>
#include <errno.h>
#include <string.h>
#include <stdlib.h>
#define PRIME (3)
#define HPRINTF(args...) printf(args)
#define ALLOCTED (1)
#define UNALLOCATED (0)
inline unsigned int hashfn(unsigned int keyptr);
struct mem_node {
unsigned int keyptr; /* key */
unsigned int size;
int next_free_node;
unsigned short state; /* ALLOCTED : 1, UNALLOCATED:0 */
};
static struct alloc_struct {
pthread_mutex_t hash_lock; /* sync primitive */
struct mem_node *pMem; /* base address of memory block */
int next_reg_node; /* idx of next regular node */
int next_free_node; /* idx of next free node */
unsigned int reg_nodes_left; /* regular nodes left */
unsigned int free_nodes_left; /* free nodes left */
unsigned int nr_nodes; /* # nodes in last mmap/remap */
int hash[PRIME]; /* hash buckets */
}as;
inline unsigned int hashfn(unsigned int keyptr)
{
return keyptr % PRIME;
}
int expand_mem(struct alloc_struct *pas)
{
/* both the lists are empty, replenish */
pas->nr_nodes <<= 1;
printf("Remap attempt: oldMem: %#08x old size: %d, new size: %d \n",
(unsigned int )pas->pMem,
(pas->nr_nodes >> 1) * sizeof(struct mem_node),
pas->nr_nodes * sizeof(struct mem_node));
pas->pMem = (struct mem_node *) mremap (pas->pMem,
pas->nr_nodes >> 1 * sizeof(struct mem_node),
pas->nr_nodes * sizeof(struct mem_node),
MREMAP_MAYMOVE);
if (pas->pMem == MAP_FAILED) {
printf("mremap failed: %s\n", strerror(errno));
pthread_mutex_unlock(&pas->hash_lock);
return 0;
} else {
/* out of n, n/2 are already filled */
pas->next_reg_node = pas->reg_nodes_left =
pas->nr_nodes - pas->reg_nodes_left;
HPRINTF("RE-GRABBED: %d nodes for hpas-> memory at: %#08x \n",
pas->reg_nodes_left,(unsigned int) pas->pMem);
}
return 1; /* success */
}
int hash_init(void)
{
int i = 0;
pthread_mutex_init (&as.hash_lock,NULL);
pthread_mutex_lock(&as.hash_lock);
as.next_free_node = -1;
as.nr_nodes = as.reg_nodes_left = PRIME << 1;
as.pMem = (struct mem_node *) mmap(0, as.reg_nodes_left * sizeof(struct mem_node),
PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
if (as.pMem == MAP_FAILED) {
printf("mmap failed: %s \n", (char*)strerror(errno));
pthread_mutex_unlock(&as.hash_lock);
return -1;
} else {
HPRINTF("GRABBED: %d nodes for hash memory at: %#08x, total size : %d \n",
as.reg_nodes_left, (unsigned int)as.pMem,
as.reg_nodes_left * sizeof(struct mem_node));
}
as.next_reg_node = 0;
for (i=0; i<PRIME; i++)
as.hash[i] = -1;
for(i=0;i<as.reg_nodes_left;i++)
as.pMem[i].state = UNALLOCATED;
pthread_mutex_unlock(&as.hash_lock);
return 0;
}
int hash_insert(unsigned int keyptr, unsigned int size)
{
int next_index = -1;
int hash_index;
pthread_mutex_lock(&as.hash_lock);
/* no nodes left in free list, we have to replenish the regular nodes */
if(as.reg_nodes_left <= 0 && as.free_nodes_left <= 0)
if (!expand_mem(&as)) {
printf("fail, abort\n");
exit(0);
}
/* If regular nodes are available grab the first one*/
if(as.reg_nodes_left > 0) {
/* regular list has nodes to allocate */
as.reg_nodes_left--;
next_index = as.next_reg_node++;
if(as.pMem[next_index].state == ALLOCTED) {
printf("[ R ]Illegal allocation: %#08x next_index: %d \n",
(unsigned int) as.pMem + next_index, next_index);
}
} else if (as.free_nodes_left > 0) {
/* free nodes available, grabe the Most recently freed */
next_index = as.next_free_node;
as.next_free_node = as.pMem[as.next_free_node].next_free_node;
if(as.pMem[next_index].state == ALLOCTED) {
printf("[ F ]Illegal allocation: %#08x next_index: %d \n",
(unsigned int) as.pMem + next_index, next_index);
}
as.free_nodes_left--;
}
if(next_index != -1) {
as.pMem[next_index].keyptr = keyptr;
as.pMem[next_index].size = size;
as.pMem[next_index].state= ALLOCTED;
as.pMem[next_index].size = size;
hash_index = hashfn(keyptr);
as.pMem[next_index].next_free_node = as.hash [hash_index];
as.hash[hash_index] = next_index;
printf("Inserted %#08x at %d\n", keyptr, hash_index);
} else {
printf("Count not get mem. block \n");
}
pthread_mutex_unlock(&as.hash_lock);
}
/* should be called with hash_lock taken */
struct mem_node * hash_find(unsigned int keyptr)
{
unsigned int next_idx = as.hash[hashfn(keyptr)];
while (next_idx != -1) {
if (as.pMem[next_idx].keyptr == keyptr);
return as.pMem + next_idx;
next_idx = as.pMem[next_idx].next_free_node;
}
return (struct mem_node *)NULL;
}
int hash_delete(unsigned int keyptr) {
struct mem_node *pmn = NULL;
pthread_mutex_lock(&as.hash_lock);
if((pmn = hash_find(keyptr)) == (struct mem_node *) NULL) {
return 0; /* failed */
}
as.free_nodes_left++;
pmn->next_reg_node = as.next_free_node;
as.next_free_node
pthread_mutex_unlock(&as.hash_lock);
}
int main() {
hash_init();
hash_insert(0x23456768,1);
hash_insert(0x23456769,1);
hash_insert(0x2345676a,1);
hash_insert(0x2345676b,1);
hash_insert(0x2345676c,1);
hash_insert(0x2345676d,1);
hash_insert(0x23456767,1);
hash_insert(0x2345675e,1);
hash_insert(0x23456756,1);
hash_insert(0x23456757,1);
hash_insert(0x23456756,1);
hash_insert(0x2345673c,1);
hash_insert(0x23456743,1);
hash_insert(0x2345672f,1);
hash_insert(0x2345670f,1);
hash_insert(0x2345674b,1);
hash_insert(0x23456740,1);
hash_insert(0x23456754,1);
hash_insert(0x23456769,1);
hash_insert(0x23456769,1);
hash_insert(0x23456769,1);
hash_insert(0x23456769,1);
hash_insert(0x23456769,1);
hash_insert(0x23456769,1);
hash_insert(0x23456769,1);
}
