C- Possible stack overflow from a function

Question

I'm writing a HashTable program where the HashTable is full of LinkedLists which counts the word frequencies of a file. In the final implementation of the program, the user is allowed to choose what the chain size of the linked list via a command line argument with any other command line arguments assumed to be files that need to be processed.

Right now I am getting a stack over flow problem from my search function to determine whether the word is already in the table or not and I'm not sure how to fix it. I valgrind the program it said it was a possible over flow

Before I add another node to the hashtable I call a method that returns 1 if the word is found and 0 if it is not found. Here is the call:

 inFile = searchFile(table, data);

table is the HashTable and data is the word

searchFile which calls search which is part of my List class

 int searchFile(HashTablePtr table, char *data) {
     ListPtr tempList;
     HashObjectPtr obj;
     int i;

     for (i = 0; i < table->size; i++) {
         tempList = table->table[i];
         if (tempList->size > 0) {
             obj = search(table->table[i], data);
            if (obj != NULL) {
                obj->frequency++;
                return 1;
            }
        }

    }
    return 0;
}

List search function

 HashObjectPtr search(ListPtr list, char *data) {
     int num = list->size;
     int i;

     NodePtr tempNode;
     HashObjectPtr tempObj;

     tempNode = list->head;

     for (i = 0; i < num; i++) {
         tempObj = tempNode->HashObject;
         while (tempNode != NULL) {
             if (strcmp((char *) tempObj->obj, data) == 0) {
                return tempObj;
             } else {
                tempNode = tempNode->next;
             }
         }
     }

    return NULL;
}

I've used the HashObjectPtr search function before in a previous implementation of this program without any problems and I'm not sure why it would be creating an overflow now.

HashObject

 struct hashobject {
     int frequency;
     void *obj;

     char (*toString)(void *obj);
 };

HashTable

 struct hashtable {
      int size;
      ListPtr *table;
 };

Lise

 struct list {
     int size;
     NodePtr head;
     NodePtr tail;
 };

I'm not entirely sure that it is a stack overflow as all valgrind really shows is that a few words have gone in and then I get a segmentation fault error. I have ran it through the debugger but it fails at my search function after going through about 12 iterations of the for loop.

As far as I can tell, you're doing a linear search, which would make it simply an array of lists, rather than a hash table (which would compute a hash, and access the correct element of the array immediately), but ignoring that, there's no reason for an overflow, your not doing any recursive calls or allocating any obscene amounts on the stack, so could you give us a little more info what made you beleive it's a stack overflow? Did you pull a stacktrace in a debugger? — falstro
– falstro, Commented May 7, 2011 at 6:33
What does your HashTable, HashObject and List types look like (not the pointers but the raw types)? — Jeff Mercado
– Jeff Mercado, Commented May 7, 2011 at 6:34
On a stylistic note, typedefing pointers is normally considered a bad idea. — user2100815
– user2100815, Commented May 7, 2011 at 7:20

Lindydancer · Accepted Answer · 2011-05-07 07:11:16Z

2

One detail, I don't know if it will solve your problem. In your original loop:

     tempObj = tempNode->HashObject;
     while (tempNode != NULL) {
         if (strcmp((char *) tempObj->obj, data) == 0) {
            return tempObj;
         } else {
            tempNode = tempNode->next;
         }
     }

You will assign tempObj to the first tempNode. Then you will loop through all the nodes. In addition to not finding anything except the first node, it will not work when the list is empty.

Instead, place it side the loop:

     while (tempNode != NULL) {
         tempObj = tempNode->HashObject;
         if (strcmp((char *) tempObj->obj, data) == 0) {
            return tempObj;
         } else {
            tempNode = tempNode->next;
         }
     }

answered May 7, 2011 at 7:11

Lindydancer

26.3k4 gold badges54 silver badges72 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

C- Possible stack overflow from a function

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related