473,326 Members | 2,012 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

Array of Pointers to Structs

I'm implementing a hash table. I really think I'm doing
everything acceptably but I'm still getting Seg Faults whenever
I try and search the table and the symbol has not already
been added to the table. I can figure out how to 'stop' on time.

The pointer to the last node never goes NULL as far as I can tell.

The address that the hash_table entry's next pointer is
pointing to is causing the fault.(I think)

I've cut down the code to try and give a good description but it's
still fairly lengthy to allow clarity.

Any ideas much appreciated.

Regards,
Grant

Code Follows;
main.c

#include <stdio.h>
#include "hash_table.h"
int main(void){
unsigned int
hidx;
hashList *hash_head[22];
hash_insert(hash_head,1,-1,"symbol2");
hash_insert(hash_head,1,-1,"symbol1");

hidx = hash("symbol3",22);
hash_search(hash_head[hidx],"symbol3")

hidx = hash("symbol2",22);
hash_search(hash_head[hidx],"symbol2")

return 0;
}

g_hash_table.h
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
struct hashNode{
struct hashNode * next;
lcList * lc_head;
int defined; /*boolean flag non-zero is defined*/
unsigned int lc;
char *symbol;
};
typedef struct hashNode hashList;
int hash(char * s, int T){
int
h = 0;
int
a = 127;

for (; *s != 0; s++)
h = (a * h + *s) % T;
return h;
}

hashList * hash_search(hashList *hash_cur, char * symbol){

if(hash_cur == NULL) return hash_cur;
while(hash_cur){
if(strcmp(hash_cur->symbol,symbol) == 0){
printf("symbol %s found in %d\n",symbol,hash_cur);
return hash_cur;
}
else {
printf("debug: %u %u\n",hash_cur,hash_cur->next);
hash_cur = hash_cur->next;
}
}

printf("end hash search for %s : hash_cur %d\n",symbol,hash_cur);
return hash_cur;
}

int hash_insert(hashList * hash_head[], int defined, unsigned int lc,
char * symbol){
unsigned int hidx;

hashList * hash_cur = malloc(sizeof *hash_cur);
hashList * hash_test = NULL;
if(hash_cur == NULL) return 0;

hidx = hash(symbol,22);
if((hash_cur->symbol = malloc(strlen(symbol)+1)) == NULL){
free(hash_cur);
return -1;
}
strcpy(hash_cur->symbol,symbol);
hash_cur->defined = defined;
hash_cur->lc = lc;
hash_cur->lc_head = NULL;
hash_cur->next = hash_head[hidx];
hash_head[hidx] = hash_cur;
printf("inserted\n");
return 1;
}

unsigned int isDefined(hashList * hash_head[], char * symbol){
/* returns 1 if symbol is defined, 0 else */
unsigned int hidx;
hashList * hash_test = malloc(sizeof *hash_test);
hidx = hash(symbol,22);
if ((hash_test = hash_search(hash_head[hidx], symbol)) != NULL){
return hash_test->defined;
}
return 0;
}

unsigned int symDefine(hashList * hash_head[], char * symbol,unsigned int lc){
unsigned int hidx;

hashList *hash_test = malloc(sizeof *hash_test);
hidx = hash(symbol,22);

if ((hash_test = hash_search(hash_head[hidx], symbol)) != NULL){
hash_test->defined = 1;
hash_test->lc = lc;
return 1;
}
return 0;
}

void hashList_free(hashList **hash_cur){
hashList *tmp;
for( ; *hash_cur; *hash_cur = tmp){
tmp = (*hash_cur)->next;
free((*hash_cur)->symbol);
free(*hash_cur);
}
return;
}

Nov 14 '05 #1
8 1542

"Grant Austin" <ga*****@foo.foo.bar.net> wrote in message
news:pa****************************@foo.foo.bar.ne t...
I'm implementing a hash table. I really think I'm doing
everything acceptably but I'm still getting Seg Faults whenever
I try and search the table and the symbol has not already
been added to the table. I can figure out how to 'stop' on time.

The pointer to the last node never goes NULL as far as I can tell.

The address that the hash_table entry's next pointer is
pointing to is causing the fault.(I think)

I've cut down the code to try and give a good description but it's
still fairly lengthy to allow clarity.

Any ideas much appreciated.


I would have looked at it with a debugger, but alas it
does not compile.

-Mike
Nov 14 '05 #2
I would have looked at it with a debugger, but alas it
does not compile.


I was cutting it down and didn't test it.

My working copy is now included. I also included one of the
test inputs.
(a few more output spam debug statements,but it compiles.)

I'm trying to get gcc to compile with debugging symbols so I can
use gdb. Not having a whole lot of luck.

-Grant "needs a better newsreader" Austin
list.h

#ifndef _LIST_H
#define _LIST_H

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

/* list structures */

struct motNode {
struct motNode * next;
unsigned int opCode;
char type;
unsigned int numArgs;
char *opName;
};
typedef struct motNode motList;

struct lcNode{
struct lcNode *next;
unsigned int lc;
};
typedef struct lcNode lcList;

struct hashNode{
struct hashNode * next;
lcList * lc_head;
int defined; /*boolean flag non-zero is defined*/
unsigned int lc;
char *symbol;
};
typedef struct hashNode hashList;
/* end list structures */

/* hash function */
int hash(char * s, int T){
int
h = 0; /* holds number for bit-wise ops */
int
a = 127;

for (; *s != 0; s++)
h = (a * h + *s) % T;
return h;
}
/* end hash function */

int lcList_insert(lcList **lc_head, unsigned int lc){

lcList *lc_cur = malloc(sizeof *lc_cur);
if(lc_cur == NULL) return 0;
lc_cur->lc = lc;
lc_cur->next = *lc_head;
*lc_head = lc_cur;
return 1;
}
void lcList_free(lcList **lc_cur){
printf("lclist free\n");
lcList *tmp;
for( ; *lc_cur; *lc_cur = tmp){
tmp = (*lc_cur)->next;
free(*lc_cur);
}
return;
}

void lcList_dump(lcList * lc_cur){

while(lc_cur){
printf("lc dump :: %d\n",lc_cur->lc);
lc_cur = lc_cur->next;
}
}

hashList * hash_search(hashList *hash_cur, char * symbol){

printf("hashcur %u\n",hash_cur);
if(hash_cur == NULL) return hash_cur;
while(hash_cur){
if(strcmp(hash_cur->symbol,symbol) == 0){
printf("symbol %s found in %d\n",symbol,hash_cur);
return hash_cur;
}
else {
printf("1else %u %u\n",hash_cur,hash_cur->next);
hash_cur = hash_cur->next;
}
}

printf("end hash search for %s : hash_cur %d\n",symbol,hash_cur);
return hash_cur;
}

int hash_insert(hashList * hash_head[], int defined, unsigned int lc,
char * symbol){
/*
return 0 if unable to insert, return 1 if success, -1 for
other error
care must be taken so that a symbol is not set as defined
without the correct lc value.
*/

unsigned int hidx;

hashList * hash_cur = malloc(sizeof *hash_cur);
hashList * hash_test = NULL;
if(hash_cur == NULL) return 0;

hidx = hash(symbol,22);
printf("Symbol : %s\n",symbol);
printf("hidx : %d\n",hidx);
printf("lc : %d\n",lc);
if((hash_cur->symbol = malloc(strlen(symbol)+1)) == NULL){
free(hash_cur);
return -1;
}
strcpy(hash_cur->symbol,symbol);
hash_cur->defined = defined;
hash_cur->lc = lc;
hash_cur->lc_head = NULL;
hash_cur->next = hash_head[hidx];
hash_head[hidx] = hash_cur;
printf("inserted\n");
return 1;
}

unsigned int isDefined(hashList * hash_head[], char * symbol){
/* returns 1 if symbol is defined, 0 else */
unsigned int hidx;
printf("IsDEFINED FN\n");
hashList * hash_test = malloc(sizeof *hash_test);
hidx = hash(symbol,22);
printf("PRESEARCH\n");
if ((hash_test = hash_search(hash_head[hidx], symbol)) != NULL){
printf("POSTSEARCH\n");
return hash_test->defined;
}
printf("POST @\n");
return 0;
}

unsigned int symDefine(hashList * hash_head[], char * symbol,unsigned int lc){
unsigned int hidx;

hashList *hash_test = malloc(sizeof *hash_test);
hidx = hash(symbol,22);

if ((hash_test = hash_search(hash_head[hidx], symbol)) != NULL){
hash_test->defined = 1;
hash_test->lc = lc;
return 1;
}
return 0;
}

void hashList_free(hashList **hash_cur){
hashList *tmp;
for( ; *hash_cur; *hash_cur = tmp){
tmp = (*hash_cur)->next;
free((*hash_cur)->symbol);
free(*hash_cur);
}
return;
}

int mot_insert(motList **mot_head,unsigned int opCode, char type,
unsigned int numArgs,const char * opName){

motList *mot_cur = malloc(sizeof *mot_cur);

if(mot_cur == NULL) return 0;
if((mot_cur->opName = malloc(strlen(opName)+1)) == NULL)
{
free(mot_cur);
return 0;
}

mot_cur->opCode = opCode;
mot_cur->type = type;
mot_cur->numArgs= numArgs;
strcpy(mot_cur->opName, opName);
mot_cur->next = *mot_head;
*mot_head = mot_cur;
return 1;
}

motList * mot_search(motList *mot_cur,const char * opTrg){
while(mot_cur){
if(strcmp(mot_cur->opName,opTrg) == 0){
return mot_cur;
}
else {
mot_cur = mot_cur->next;
}
}
return mot_cur;
}

void mot_dump(motList *mot_cur){
while(mot_cur){
printf("%s\n",mot_cur->opName);
mot_cur = mot_cur->next;
}
return;
}

void generate_mot(motList **mot_cur){
mot_insert(mot_cur,0,'r',0,"hlt");
mot_insert(mot_cur,1,'r',3,"add");
mot_insert(mot_cur,2,'r',3,"sub");
mot_insert(mot_cur,3,'r',3,"mul");
mot_insert(mot_cur,4,'r',3,"div");
mot_insert(mot_cur,5,'r',3,"mod");
mot_insert(mot_cur,6,'r',2,"move");
mot_insert(mot_cur,7,'r',3,"and");
mot_insert(mot_cur,8,'r',3,"or");
mot_insert(mot_cur,9,'r',3,"xor");
mot_insert(mot_cur,10,'r',2,"com");
mot_insert(mot_cur,11,'r',3,"sll");
mot_insert(mot_cur,12,'r',3,"srl");
mot_insert(mot_cur,13,'r',3,"sra");
mot_insert(mot_cur,14,'r',3,"jr");
mot_insert(mot_cur,15,'r',1,"rdr");
mot_insert(mot_cur,16,'r',1,"prr");
mot_insert(mot_cur,17,'r',1,"prh");

/* I format */
mot_insert(mot_cur,18,'i',2,"li");
mot_insert(mot_cur,19,'i',3,"addi");
mot_insert(mot_cur,20,'i',3,"subi");
mot_insert(mot_cur,21,'i',3,"muli");
mot_insert(mot_cur,22,'i',3,"divi");
mot_insert(mot_cur,23,'i',3,"modi");
mot_insert(mot_cur,24,'i',3,"lwb");
mot_insert(mot_cur,25,'i',3,"swb");

/* J format */
mot_insert(mot_cur,26,'j',2,"lwa");
mot_insert(mot_cur,27,'i',2,"swa");
mot_insert(mot_cur,28,'i',1,"j");
mot_insert(mot_cur,29,'i',1,"jal");
mot_insert(mot_cur,30,'i',1,"jeq");
mot_insert(mot_cur,31,'i',1,"jne");
mot_insert(mot_cur,32,'i',1,"jlt");
mot_insert(mot_cur,33,'i',1,"jle");
mot_insert(mot_cur,34,'i',1,"jgt");
mot_insert(mot_cur,35,'i',1,"jge");
}

void mot_free(motList **mot_cur){
motList *tmp;
for( ; *mot_cur; *mot_cur = tmp){
tmp = (*mot_cur)->next;
free((*mot_cur)->opName);
free(*mot_cur);
}
return;
}
#endif
assem.h

#include <stdio.h>
#include <string.h>
#define MAX_INPUT 81

int process_token(char * token,motList * mot, hashList * hash_table[],
FILE * lst,FILE * err,int lc){
/*do work
free parts
*/
char * tok;

printf("token %s last char %c\n",token,token[strlen(token)-1]);
if( token[strlen(token)-1] == ':'){
/* symbol in label field */
printf("tok\n");
tok = malloc(strlen(token));
strncpy(tok,token,(strlen(token)-1));
strcat(tok,"\0");
printf("tok malloc and cpy\n");
/* if(isDefined(hash_table,tok) > 0){ */
/* printf("multiply defined\n"); */
/* }else{ */
hash_insert(hash_table,1,lc,tok);
/* } */
}

}
int parseln(char * line, FILE * lst,FILE * err,unsigned int lc,
motList * mot, hashList * hash_table[]){
char * tch;

tch = strtok(line, " \t");
while(tch != NULL){
process_token(tch,mot,hash_table,lst,err,lc);
tch = strtok(NULL," \t");
}
}

void assemble(const char * fnroot,motList * mot,
hashList * hash_table[], FILE * infle){
char inputStr[MAX_INPUT];
char errorStr[255];
char * filename;
char * err_filename;
FILE
* obj,
* lst,
* edt,
* erf;
FILE
* errfle;
unsigned int lc = 1;

filename = malloc(strlen(fnroot) + 4);
strcpy(filename,fnroot);
strcat(filename, ".lst");
if((lst = fopen(filename,"w+")) == NULL){
fprintf(stderr,"Error opening file: %s\n",filename);
}
free(filename);

err_filename = malloc(strlen(fnroot) + 4);
strcpy(err_filename,fnroot);
strcat(err_filename, ".err");
if((errfle = fopen(err_filename,"w+")) == NULL){
fprintf(stderr,"Error opening file: %s\n",err_filename);
}

while(feof(infle) == 0){
fgets(inputStr,81,infle);
if(strlen(inputStr) == 1){
fprintf(lst,"%d\n",lc);
lc++;
continue;
}
if(feof(infle) == 0 ){

if(inputStr[0] == '#'){
fprintf(lst,"%d\t%s",lc,inputStr);
lc++;
continue;
} else{
fprintf(lst,"%d\t%s",lc,inputStr);
parseln(inputStr,lst,errfle,lc,mot,hash_table);
lc++;
continue;
}
}
}

/* copy errors from temp error file to lst file then remove temp */
rewind(errfle);
while(feof(errfle) == 0){
fgets(errorStr,256,errfle);
if(feof(errfle) == 0){
fprintf(lst,"\n");
fprintf(lst,"%s",errorStr);
}
}

fclose(lst);
unlink(err_filename);
free(err_filename);
free(filename);
}

main.c

#include <stdio.h>
#include "list.h"
#include "assem.h"

int main(int argv, char * argc[]){
FILE * infle;
char * fnroot;
int fcount = 2;
char * eor;
char * inputStr;
char * ftest;

motList *mot_head = NULL;
hashList *hash_head[22];
hash_insert(hash_head,1,-1,"dUmMy_HSAH_00"); /* init hash table */
isDefined(hash_head,"dUmMy_HSAH_00");
hash_insert(hash_head,1,-1,"111111dUmMy_HSAH_00");
if(argv < 3){
fprintf(stderr,"Too few arguments\n");
fprintf(stderr,"\tusage:\tp2 <flag> <input files:minimum of one>\n");
exit(1);
}
do{
printf("top of do\n");
printf("infle :: %s\n",argc[fcount]);
if((infle = fopen(argc[fcount],"r")) == NULL){
fprintf(stderr,"Unable to open data file %s\n",argc[fcount]);
}
else{
eor = strrchr(argc[fcount],'.');
fnroot = malloc(eor-argc[fcount]+1);
strncpy(fnroot,argc[fcount],eor-argc[fcount]);
strcat(fnroot,"\0");
//do work
assemble(fnroot,mot_head,hash_head,infle);
free(fnroot);
fclose(infle);
}
fcount++;
} while(fcount < argv);

mot_free(&mot_head);
return 0;
}
test1.asm

#Test case 1 for assembler -- no .edef or .eref.

.text
test1: lwa $1,val1 #Puts -1 in $1.
prh $1

val12: lwa $2,val2
prh $2
sll $3,$2,16
prh $3

val123: srl $4,$1,16
prh $4

val1234: sra $5,$1,16
prh $5

#A label with 8 characters.
val12345: xor $6,$1,$2
prh $6
lwb $7,0($1)
prh $7
hlt

.data
val1: .word -1:4
val2: .word 65535:1

#No more lines.

Nov 14 '05 #3
Grant Austin wrote:

I'm implementing a hash table. I really think I'm doing
everything acceptably but I'm still getting Seg Faults whenever
I try and search the table and the symbol has not already
been added to the table. I can figure out how to 'stop' on time.

The pointer to the last node never goes NULL as far as I can tell.

The address that the hash_table entry's next pointer is
pointing to is causing the fault.(I think)

I've cut down the code to try and give a good description but
it's still fairly lengthy to allow clarity.

Any ideas much appreciated.

.... snip code ...

I didn't even read the code, but this is just to let you know that
a generic portable hashtable implementation is available, under
GPL. You can read it, use it, etc. I think it is fairly clear.

<http://cbfalconer.home.att.net/download/hashlib.zip>

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #4
I didn't even read the code, but this is just to let you know that
a generic portable hashtable implementation is available, under
GPL. You can read it, use it, etc. I think it is fairly clear.

<http://cbfalconer.home.att.net/download/hashlib.zip>

Very cool. Thanks a bunch. Doesn't look too hard(for me) to use.

-Grant
Nov 14 '05 #5
What is the rehash function for?
Nov 14 '05 #6
Grant Austin wrote:
I would have looked at it with a debugger, but alas it
does not compile.
I was cutting it down and didn't test it.

My working copy is now included. I also included one of the
test inputs.
(a few more output spam debug statements,but it compiles.)

I'm trying to get gcc to compile with debugging symbols so I can
use gdb. Not having a whole lot of luck.


It has a few problems.
For very strong stylistic reasons, these header files of yours
should each be split into a C file and a header file.
list.h

#ifndef _LIST_H
The leading underscore followed by an upper case letter,
is reserved for use by your implementation.
void lcList_free(lcList **lc_cur){
printf("lclist free\n");
lcList *tmp;
You have to declare your variables before the printf statement.
Function definitions belong in C files.

unsigned int isDefined(hashList * hash_head[], char * symbol){
/* returns 1 if symbol is defined, 0 else */
unsigned int hidx;
printf("IsDEFINED FN\n");
hashList * hash_test = malloc(sizeof *hash_test);
Same problem: declaring a variable after a statement.
assem.h int process_token(char * token,motList * mot, hashList * hash_table[],
FILE * lst,FILE * err,int lc){ int parseln(char * line, FILE * lst,FILE * err,unsigned int lc,
motList * mot, hashList * hash_table[]){
char * tch;

tch = strtok(line, " \t");
while(tch != NULL){
process_token(tch,mot,hash_table,lst,err,lc);
tch = strtok(NULL," \t");
}
}
Should be
void process_token
and
void parseln
main.c fprintf(stderr,"\tusage:\tp2 <flag> <input files:minimum of
one>\n");
What should I use for a flag ?
exit(1);


exit(1) doesn't have a portable meaning in C.

--
pete
Nov 14 '05 #7
Grant Austin wrote:

What is the rehash function for?


I assume you are asking about hashlib.

The table never overflows, in that it is expanded as needed. If
the primary hash does not find the correct slot, the table is
searched further for a suitable (matching or free) slot, and that
further search is controlled by the rehash. The rehash needs to
be different from the primary hash (which has just collided) so
that different key values search the table in different order, and
the entries do not cluster. The result is that most queriess are
satisfied in under two probes. The statistics include the cost of
reorganizing the table during expansion, but the per probe cost is
much lower there.

At any rate, that overall organization means that the user need
not worry about the size of the hashtable.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

Nov 14 '05 #8
On Thu, 04 Mar 2004 07:19:34 +0000, CBFalconer wrote:
Grant Austin wrote:

What is the rehash function for?
I assume you are asking about hashlib.


Yup.
At any rate, that overall organization means that the user need
not worry about the size of the hashtable.


Thanks!
Nov 14 '05 #9

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
by: Koster | last post by:
Just a quickie: I heard that arrays declared in the global scope are automatically initialised with a block of zeros. To help with making my C source compatible with multiple compilers, I'd like...
1
by: mrhicks | last post by:
Hello all, I need some advice/help on a particular problem I am having. I have a basic struct called "indv_rpt_rply" that holds information for a particular device in our system which I will...
2
by: Simon Morgan | last post by:
I hope this isn't OT, I looked for a newsgroup dealing purely with algorithms but none were to be found and seeing as I'm trying to implement this in C I thought this would be the best place. I...
5
by: Paminu | last post by:
Why make an array of pointers to structs, when it is possible to just make an array of structs? I have this struct: struct test { int a; int b;
1
by: Jeff | last post by:
Given a struct, TEST, I'd like to create a static end of array marker, also of type test. This way static arrays of type TEST could be easily created and their end could be marked with the end of...
15
by: Paminu | last post by:
Still having a few problems with malloc and pointers. I have made a struct. Now I would like to make a pointer an array with 4 pointers to this struct. #include <stdlib.h> #include <stdio.h>...
11
by: Cliff Martin | last post by:
Hi, I am reading a fairly large file a line at a time, doing some processing, and filtering out bits of the line. I am storing the interesting information in a struct and then printing it out....
5
by: dev_15 | last post by:
Hi, I'm going through some code and thought that this allocates an array of structs but its supposed according to comments to allocate an array of pointer to structs. What does it actually do ...
0
by: mjaaland | last post by:
Hi! I've been working with DLLimports passing structs and various other parameters to unmanaged code. I had problems earlier sending pointer to structs to the unmanaged code, and this forum solved...
2
by: hal | last post by:
Hi, I'm trying to make an array of pointers to 'TwoCounts' structs, where the size of the array is arraySize. Right now I'm just mallocing enough space for all the pointers to the structs, and...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.