Hash Table


 
Thread Tools Search this Thread
Top Forums Programming Hash Table
# 8  
Old 10-31-2014
If you remove the explicit array size from the lookup() call and add it as a separate parameter, you have to add that parameter to the hash() call too.
# 9  
Old 10-31-2014
Good point! Been lazing arund OO land so long! Smilie If NPREF is a macro, maybe hash() uses it, too. Classic C trick is to over-allocate the char*[] by 1 so there is room for a null pointer at the end, like char *argv[], reminiscent of null term string.

Last edited by DGPickett; 10-31-2014 at 04:10 PM..
# 10  
Old 10-31-2014
Thanks a lot guys. Here is the full code, I was looking at:
And would anyone know how to write a function to give the memory back in statetab? As in clean up statetab when it is done

Code:
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "eprintf.h"

enum {
        NPREF   = 2,    /* number of prefix words */
        NHASH   = 4093, /* size of state hash table array */
        MAXGEN  = 10000 /* maximum words generated */
};

typedef struct State State;
typedef struct Suffix Suffix;

struct State {  /* prefix + suffix list */
        char*   pref[NPREF];    /* prefix words */
        Suffix* suf;                    /* list of suffixes */
        State*  next;                   /* next in hash table */
};

struct Suffix { /* list of suffixes */
        char *  word;                   /* suffix */
        Suffix* next;                   /* next in list of suffixes */
};

State* lookup(char *prefix[], int create);
void    build(char *prefix[], FILE*);
void    generate(int nwords);
void    add(char *prefix[], char *word);

State*  statetab[NHASH];        /* hash table of states */

char NONWORD[] = "\n";  /* cannot appear as real word */

/* markov main: markov-chain random text generation */
int main(void)
{
        int i, nwords = MAXGEN;
        char *prefix[NPREF];            /* current input prefix */

        int c;
        long seed;

        setProgName("markov");

        seed = time(NULL);
        srand(seed);

        for (i = 0; i < NPREF; i++)     /* set up initial prefix */
                prefix[i] = NONWORD;

        build(prefix, stdin);
        add(prefix, NONWORD);
        generate(nwords);

        return 0;
}   

const int MULTIPLIER = 31;  /* for hash() */

/* hash: compute hash value for array of NPREF strings */
unsigned int hash(char* s[NPREF])
{
        unsigned int h;
        unsigned char *p;
        int i;

        h = 0;
        for (i = 0; i < NPREF; i++)
                for (p = (unsigned char *) s[i]; *p != '\0'; p++)
                        h = MULTIPLIER * h + *p;
        return h % NHASH;
}

/* lookup: search for prefix; create if requested. */
/*  returns pointer if present or created; NULL if not. */
/*  creation doesn't strdup so strings mustn't change later. */
State* lookup(char* prefix[NPREF], int create)
{
        int i, h;
        State *sp = NULL ;

        h = hash(prefix);
        for (sp = statetab[h]; sp != NULL; sp = sp->next) {
                for (i = 0; i < NPREF; i++)
                        if (strcmp(prefix[i], sp->pref[i]) != 0)
                                break;
                if (i == NPREF)         /* found it */
                        return sp;
        }
        if (create) {
                sp = (State*) emalloc( sizeof( State ));
                for( i=0; i<NPREF; i++ )
                        sp->pref[i] = prefix[i];
                sp->suf = NULL;
                sp->next = statetab[h];
                statetab[h] = sp;
        }
        return sp;
}

/* addsuffix: add to state. suffix must not change later */
void addsuffix(State *sp, char *suffix)
{
        Suffix *suf;

        suf = (Suffix *) emalloc(sizeof(Suffix));
        suf->word = suffix;
        suf->next = sp->suf;
        sp->suf = suf;
}

/* add: add word to suffix list, update prefix */
void add(char *prefix[NPREF], char *suffix)
{
        State *sp;

        sp = lookup(prefix, 1);  /* create if not found */
        addsuffix(sp, suffix);
        /* move the words down the prefix */
        memmove(prefix, prefix+1, (NPREF-1)*sizeof(prefix[0]));
        prefix[NPREF-1] = suffix;
}

/* build: read input, build prefix table */
void build(char *prefix[NPREF], FILE *f)
{
        char buf[100], fmt[10];

        /* create a format string; %s could overflow buf */
        sprintf(fmt, "%%%lus", sizeof(buf)-1);
        while (fscanf(f, fmt, buf) != EOF)
                add(prefix, estrdup(buf));
}

/* generate: produce output, one word per line */
void generate(int nwords)
{
        State *sp;
        Suffix *suf;
        char *prefix[NPREF], *w;
        int i, nmatch;

        for (i = 0; i < NPREF; i++)     /* reset initial prefix */
                prefix[i] = NONWORD;

        for (i = 0; i < nwords; i++) {
                sp = lookup(prefix, 0);
                if (sp == NULL)
                        eprintf("internal error: lookup failed");
                nmatch = 0;
                for (suf = sp->suf; suf != NULL; suf = suf->next)
                        if (rand() % ++nmatch == 0) /* prob = 1/nmatch */
                                w = suf->word;
                if (nmatch == 0)
                        eprintf("internal error: no suffix %d %s", i, prefix[0]);
                if (strcmp(w, NONWORD) == 0)
                        break;
                printf("%s\n", w);
                memmove(prefix, prefix+1, (NPREF-1)*sizeof(prefix[0]));
                prefix[NPREF-1] = w;
        }
}

# 11  
Old 11-05-2014
Well, exit() is real cheap. Otherwise, what you mallo() you must free(). If you use mmap() in 64 bit mode in lieu of malloc(), you are just using up disk and address space until exit(). Otherwise, try JAVA -- anything not referenced is collected, so if you overwrite the parent's only reference, it is collected, which makes the children unreferenced, and so they are collected.
# 12  
Old 11-05-2014
Quote:
Originally Posted by totoro125
Thanks a lot guys. Here is the full code, I was looking at:
And would anyone know how to write a function to give the memory back in statetab? As in clean up statetab when it is done
Here is the cleanup:

Code:
void cleanup()
{
    int h;
    State *sp = NULL ;
    Suffix *suf, *t;

    for(h = 0; h < NHASH; h++) {
        for (sp = statetab[h]; sp != NULL; sp = statetab[h]) {
            for(suf = sp->suf; suf != NULL; suf = t) {
                t = suf->next;
                free(suf);
            }
            statetab[h]=sp->next;
            free(sp);
        }
    }
}

EDIT:

The lookup function is still not working properly the comment "found it" seems to imply the prefix was found however the preceding code calls break on the first string the doesn't match.

The whole prefix array list part is fairly strange. What are you trying to achieve with prefix? I feel things would be much easier and consistent if you used another linked list for prefix rather that an array and the kludgy memmove() calls.

If you could give me a description on how this prefix/suffix relationship is supposed to work I'm sure I could suggest a better structure to store this data. Once we get the structure right it will be much easier to get the add, delete and lookup routines done.

Last edited by Chubler_XL; 11-05-2014 at 05:58 PM..
# 13  
Old 11-05-2014
I suppose hsearch() does some cleanup for you?
# 14  
Old 11-05-2014
@DGPickett Umm, I cant see any reference to hsearch() in this code, are you sure you're posting in the right thread?
Login or Register to Ask a Question

Previous Thread | Next Thread

10 More Discussions You Might Find Interesting

1. Shell Programming and Scripting

Need to print hash of hash in table format

Hi, I have a hash of hash where it has name, activities and count i have data like this - $result->{$name}->{$activities} = $value; content of that are - name - robert tom cat peter activities - running, eating, sleeping , drinking, work i need to print output as below ... (3 Replies)
Discussion started by: asak
3 Replies

2. Shell Programming and Scripting

Return a hash table from a sub routine

hello, i am new to scripting and would like to know how to return a hash table from a sub routine. i tried the following, my %hash_function = (); hash_function = &return_hash(); sub return_hash { my %hash = (); ///populate the hash return %hash; } but it dosent seem to... (1 Reply)
Discussion started by: hemalathak10
1 Replies

3. UNIX for Dummies Questions & Answers

Hash Table like implementation in unix

Hi all, I just downloaded this example from the net. I was looking around for a hash table like implementation in unix when I came across this. ARRAY=( "cow:moo" "dinosaur:roar" "bird:chirp" "bash:rock" ) for animal in ${ARRAY} ; do KEY=${animal%%:*} ... (8 Replies)
Discussion started by: anindyabecs
8 Replies

4. Programming

Hash table

Hi, I hope someone can help me with the following prob.. I need to implement a hashtable whose KEYs are strings and VLAUEs are again hashtables. ie key - is a string and value -is another hashtable . So.... how am I supposed to be implementing my nested hashtable? Thanks in advance (1 Reply)
Discussion started by: andrew.paul
1 Replies

5. UNIX for Advanced & Expert Users

distributed hash table operations(GET,PUT,TRANSFER) implementation

Hi, i want to implement hash table (put, get and transfer operations) using c in unix. so give some nice infromation on how to write my code. (1 Reply)
Discussion started by: kaleab
1 Replies

6. Shell Programming and Scripting

how to import external HASH table in PERL???

hello, I am creating a HASH table using file1.pl :- I want to retrieve the content of the hash table created above from another file named file2.pl :- The problem is that if I separate like this into 2 files.Then it says that HASH table is not created.So can you please tell me how to... (2 Replies)
Discussion started by: nsharath
2 Replies

7. UNIX for Dummies Questions & Answers

nested hash table

Hi, I have a nested hash table say for example as follows: %coins = ( 1 => { "Quarter"=>25, "Dime"=>10, "Nickel"=>5, }, 2 => { "asd"=>34, "qwe"=>45, ... (0 Replies)
Discussion started by: arthi
0 Replies

8. Programming

Creating a Hash Table

Dear Friends, I want to create a hash table using the standard Glib header (if possible) so that I can store a structure and keep the hash key(search key) based on a string. Any example code would be great since I am not able to get the main idea. best regards Skull (4 Replies)
Discussion started by: callmetheskull
4 Replies

9. Programming

hash table implementations in C Language

Hello List, Iam searching for a solution where i can use hash based searching . In Detail , I have linked list which will be dynamically increasing . I need a best searching mechanisim such a way that it can take only one itereation . Right now iam using linear search which is taking... (11 Replies)
Discussion started by: vlrk
11 Replies

10. UNIX for Advanced & Expert Users

Creating a hash table using shell script

Hi, For one of my programs, I need to have a hashtable as in Perl. Unfortunately shell doesnt provide any variable like hash. Is there anyway/trick, I could implement a hash in shell (using shell scripts/sed/awk). JP (2 Replies)
Discussion started by: jyotipg
2 Replies
Login or Register to Ask a Question