Array of Pointers to Structs

G

Grant Austin

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;
}
 
M

Mike Wahler

Grant Austin said:
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.
Click to expand...

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

-Mike
 
G

Grant Austin

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

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.
 
C

CBFalconer

Grant said:
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.
Click to expand...
.... 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>
 
P

pete

Grant said:
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.
Click to expand...

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
Click to expand...

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;
Click to expand...

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);
Click to expand...

Same problem: declaring a variable after a statement.
assem.h
Click to expand...
int process_token(char * token,motList * mot, hashList * hash_table[],
FILE * lst,FILE * err,int lc){
Click to expand...
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");
}
}
Click to expand...

Should be
void process_token
and
void parseln
main.c
Click to expand...
fprintf(stderr,"\tusage:\tp2 <flag> <input files:minimum of
one>\n");
Click to expand...

What should I use for a flag ?
exit(1);
Click to expand...

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

CBFalconer

Grant said:
What is the rehash function for?
Click to expand...

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.
 
G

Grant Austin

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.
Click to expand...

Thanks!
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Array of structs function pointer 10
Fibonacci 0
Lexical Analysis on C++ 1
Please help with C programming to save GPS reception data in Raspberry Pi. 0
Comparison of Integer and Pointer (that's supposed to be an Integer). Where did I go wrong? 0
pointer to array of structs 1
[union] Pointers to inherited structs are valid ? 104
Dynamic Array Size Problem?? 9

Staff online

Members online

Total: 38 (members: 2, guests: 36)
Robots: 340

Forum statistics

Threads
473,755
Messages
2,569,536
Members
45,012
Latest member
RoxanneDzm

Latest Threads

Top