LinuxQuestions.org
Visit Jeremy's Blog.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices



Reply
 
Search this Thread
Old 02-24-2013, 03:46 PM   #1
kapsikum
Member
 
Registered: Mar 2005
Location: INDIA
Posts: 79

Rep: Reputation: 16
hash table implementation without malloc


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);
}
 
Old 02-25-2013, 10:10 AM   #2
NevemTeve
Senior Member
 
Registered: Oct 2011
Location: Budapest
Distribution: Debian/GNU/Linux, AIX
Posts: 1,935

Rep: Reputation: 524Reputation: 524Reputation: 524Reputation: 524Reputation: 524Reputation: 524
1. Please &#91;code] and &#91;/code] tags.
2. It doesn't compile for me:
Code:
kapiskum.c:171: error: 'struct mem_node' has no member named 'next_reg_node'

Last edited by NevemTeve; 02-25-2013 at 10:14 AM.
 
Old 02-25-2013, 01:06 PM   #3
sundialsvcs
Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 5,455

Rep: Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172
I don't know what the question in this post is. And, I suspect, neither does anybody else.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Hash Table DB performance itags.org Programming 0 08-02-2009 02:02 AM
synchronized hash table danfou Linux - General 0 04-05-2007 02:21 AM
Hash File Implementation jwstric2 Programming 3 04-06-2005 12:58 PM
Updating the hash table Xios Linux - Software 0 02-10-2005 01:02 AM
C++ hash table buckets Penguin Dropout Programming 3 07-22-2003 02:51 PM


All times are GMT -5. The time now is 03:27 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration