0

My hash table works and has good running time but fails for one check (rest all checks pass) - :( handles max length (45-char) words

AFAIK pneumonoultramicroscopicsilicovolcanoconiosis is the longest word in dictionary and is present in dictionaries/large. And I have used large dictionary and I didn't get any issue.

Then why :( handles max length (45-char) words is failing. Anybody knows whats in max length dictionary?

It is failing after I am trying to allocate more memory using HashTable = realloc(HashTable, sizeof(node) * numOfElements);. And when I check if(HashTable == NULL) then it is success and hence exit(0).

If I do not do exit(0) then I get following error from check50 - \ expected output, not standard error of "/opt/sandbox50/bin/run.sh: line 31: 35..."

My memory allocation code:

void allocateMemory(int numOfElements, bool isRealloc, const char* word)
{
    if(!isRealloc)
    {
        //printf("Allocating %d blocks for %s", numOfElements, word);
        HashTable = malloc(sizeof(node) * numOfElements);
    } else {
        //printf("Reallocating %d blocks for %s", numOfElements, word);
        HashTable = realloc(HashTable, sizeof(node) * numOfElements);
    }

    if(HashTable == NULL)
    {
        //printf("> %d element for %s ###\n", numOfElements, word);
        //exit(0);
    }
    HeadOfHashTable = HashTable;
}
1

The max length of a word really is 45. But riddle me this: When you created/declared the buffer and set the size, did you set it to 45 (or set LENGTH = 45 and use LENGTH in the declatation)? Did you remember or forget to allow space for the end of string marker \0 ?

And just for grins, depending on how you are reading from the dictionary file, you may be reading in \n too. Is there room for this as well?

It's possible that you're writing past the end of the buffer if you didn't account for these.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

9
  • Thanks for your inputs. I think length of 45 will come into picture when allocating space for word (anyways I am using malloc(sizeof(char) * (LENGTH + 1)); everywhere), but this is the case different case, this is when I am expanding my hash table. Initially I am starting with size of 65336 but when some hash value greater than 65336 then I realloc and that's when no more memory gets allocated and this IF condition becomes true - if(HashTable == NULL)
    – hagrawal
    Feb 21 '16 at 23:02
  • Yes, I placed some new line \n in my test dictionary and I could not reproduce the issue.
    – hagrawal
    Feb 21 '16 at 23:05
  • "It's possible that you're writing past the end of the buffer if you didn't account for these." .. Means? I am just reallocating using HashTable = realloc(HashTable, sizeof(node) * numOfElements); ..
    – hagrawal
    Feb 21 '16 at 23:06
  • What is the command that you're using to read from the dictionary?
    – Cliff B
    Feb 21 '16 at 23:07
  • FILE* fp = fopen(dictionary, "r");
    – hagrawal
    Feb 21 '16 at 23:08
0

Let me start by thanking @Cliff B, for his time for the discussion because of which I could figure out the issue.

I was getting error when I was trying to expand my hash table using following code - HashTable = realloc(HashTable, sizeof(node) * numOfElements); and so check50 was failing in the max length test. Not because of length of word but because during max length test cs50 server might not had enough space to realloc and hence was failing.

So, what I need was asking for less space. In my hash function I was controlling the maximum value of hash using this global variable - const int Overall_Hash_table_Size = 57701446;. So, to correct the error I just changed to 17701446 and then I it resolved the issue.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .