2

When I submit my code to Leetcode, it reported runtime error as:

Line 43: member access within null pointer of type 'struct bucket_item'.

I tested that case in my local, it works fine. I thought it maybe causeed by the platform and compiler are different. I then tried to test it on Leetcode Playground. It also worked very well. The Leetcode problem is: https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/

Very appreciated if anyone could let me know what's wrong with my code.

typedef struct bucket_item {
    char *str;
    int count;
    int ori_count;
} bucket_item;

typedef struct bucket {
    int hashIndex;
    int itemsCount;
    bucket_item *items;
} bucket;

bucket *hash_init(const int bucket_count)
{
    bucket *buckets = malloc(sizeof(bucket) * bucket_count);
    for (int i = 0; i < bucket_count; ++i)
    {
        buckets[i].items = NULL;
        buckets[i].itemsCount = 0;
    }
    return buckets;
}

int get_hash(char *str, const int bucket_count) {
    const int str_len = strlen(str);
    int base = 0;
    int i = 0;
    while (str[i] != '\0')
    {
        base += str[i];
        i++;
    }
    return ((base >> 3) * 2654435761) % bucket_count;
}

bucket_item *hash_lookup(bucket *buckets, char *str, const int bucket_count)
{
    const int hash_index = get_hash(str, bucket_count);
    bucket *bucket = buckets + hash_index;

    for (int i = 0; i < bucket->itemsCount; ++i)
    {
        if (strcmp(str, bucket->items[i].str) == 0) return bucket->items + i;
    }
    return NULL;
}

void hash_add(bucket *buckets, char *str, const int bucket_count)
{
    bucket_item *item = hash_lookup(buckets, str, bucket_count);
    if (item)
    {
        item->count++;
        item->ori_count = item->count;
    }
    else {
        const int hash_index = get_hash(str, bucket_count);
        bucket *bucket = buckets + hash_index;
        bucket->itemsCount++;
        bucket->items = (bucket_item *)realloc(bucket->items, sizeof(bucket_item) * bucket->itemsCount);
        bucket->items[bucket->itemsCount - 1].str = str;
        bucket->items[bucket->itemsCount - 1].count = 1;
        bucket->items[bucket->itemsCount - 1].ori_count = 1;
    }
}

void hash_free(bucket *buckets, const int bucket_count)
{
    for (int i = 0; i < bucket_count; ++i)
    {
        free(buckets[i].items);
        buckets[i].items = NULL;
    }
    free(buckets);
    buckets = NULL;
}

bool is_match(char* str, bucket *hashmap, int bucket_count, char **words, int word_len, int word_size)
{
    bool found = true;
    char *subStr = malloc(sizeof(char) * (word_len + 1));
    subStr[word_len] = '\0';
    for (int i = 0; i < word_size; ++i)
    {
        memcpy(subStr, str + i * word_len, word_len);
        bucket_item *item = hash_lookup(hashmap, subStr, bucket_count);
        if (item)
        {
            item->count--;
        }
        else
        {
            found = false;
        }
    }
    free(subStr);
    subStr = NULL;

    for (int i = 0; i < word_size; ++i)
    {
        bucket_item *item = hash_lookup(hashmap, words[i], bucket_count);
        if (item->count != 0) {
            found = false;
        }
    }
    for (int i = 0; i < word_size; ++i)
    {
        bucket_item *item = hash_lookup(hashmap, words[i], bucket_count);
        item->count = item->ori_count;
    }
    return found;
}

/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* findSubstring(char* s, char** words, int wordsSize, int* returnSize) {
    if (wordsSize == 0) return NULL;

    const int word_len = strlen(words[0]);

    // prepare hashmap
    bucket *hashmap = hash_init(wordsSize);
    for (int i = 0; i < wordsSize; ++i)
    {
        hash_add(hashmap, words[i], wordsSize);
    }

    // loop long string.
    int *ret = malloc(sizeof(int) * 1000);
    *returnSize = 0;
    const int s_len = strlen(s);
    const int sub_strlen = word_len * wordsSize;
    for (int i = 0; i < s_len; ++i)
    {
        const bool found = is_match(s + i, hashmap, wordsSize, words, word_len, wordsSize);

        if (found)
        {
            ret[*returnSize] = i;
            (*returnSize)++;
        }
    }
    hash_free(hashmap, wordsSize);
    ret = (int*)realloc(ret, sizeof(int) * (*returnSize));

    return ret;
}

The case that report error is below:

int main() {
    char *str = "ababaab";
    char **words[] = { "ab", "ba", "ba" };
    int returnSize = 0;

    int *result = findSubstring(str, words, 3, &returnSize);
    return 0;
}
4
  • Can you add more detail? Shows your main code that runs this code. Commented Mar 2, 2018 at 6:29
  • Please give more information on what goes wrong in which way. Reduce the amount of required guessing and finding out. Did you do any debuging with the input data for the failing case? Commented Mar 2, 2018 at 6:34
  • If you do not know anything about which input case fails, then give the test cases you tried. Some people here are good at finding evil test cases. Commented Mar 2, 2018 at 6:36
  • Thanks everybody remind me to add the test case. I have updated my question, and added the test case that reported the error. Commented Mar 2, 2018 at 18:11

1 Answer 1

2

When you call the hash_lookup function, it could return NULL in some cases. So when you use item->count in the next line, you may access a NULL pointer.

You should ensure that item isn't NULL first, and than use item->count, like so:

for (int i = 0; i < word_size; ++i)
{
    bucket_item *item = hash_lookup(hashmap, words[i], bucket_count);
    if (item != NULL && item->count != 0) {
        found = false;
    }
}
for (int i = 0; i < word_size; ++i)
{
    bucket_item *item = hash_lookup(hashmap, words[i], bucket_count);
    if (item != NULL) {
        item->count = item->ori_count;
    }
}
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.