C solution (AC) Resolved: store to address [..] with insufficient space for an object of type 'char **'


  • 0
    S

    The prototype used to be:
    char **anagrams(char *strs[], int n, int *outputSize) {

    It has been changed to:
    char*** groupAnagrams(char** strs, int strsSize, int** columnSizes, int* returnSize) {

    In changing this, it seems like the test cases for C were broken. I get this error on the sample test case:
    store to address 0x000001bae828 with insufficient space for an object of type 'char **'

    Perhaps it is a similar problem to this post: https://discuss.leetcode.com/topic/83263/test-for-c-problem


  • 0
    S

    My statement in the OP about changing prototypes being the cause of the failure was a red herring. The problem can be attributed to malloc/memset versus calloc.

    Line 144: store to address 0x0000019ed828 with insufficient space for an object of type 'char **'
    

    is thrown with this:

    char*** result = malloc(sizeof(*returnSize * sizeof(char**)));
    memset(result, 0, sizeof(*returnSize * sizeof(char**)));
    

    TLDR; My submission became AC once I converted all pairs of malloc/memset to calloc:

    char*** result = calloc(*returnSize, sizeof(char**));
    

    The full code:

    /*
     * https://leetcode.com/problems/group-anagrams/description/
     *
     * Given an array of strings, group anagrams together.
     *
     * For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
     * Return:
     *
     * [
     *   ["ate", "eat","tea"],
     *   ["nat","tan"],
     *   ["bat"]
     * ]
     *
     * $ ./a.out < p49.in1                                                  
     * eat tea ate 
     * tan nat 
     * bat 
     * 
     * Note: All inputs will be in lower-case.
     */
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <stdbool.h>
    #include <math.h>
    #include "/usr/local/include/uthash.h"
    
    #define MAXBUF 100
    
    signed comparison(void const* a, void const* b) {
    	char const* A = a;
    	char const* B = b;
    
    	return strcmp(A, B);
    }
    
    struct my_struct {
    	char const* key;     /* key is string with sorted letters */
    	size_t* value;       /* value is array of indices in the input array */
    	size_t len;          /* cardinality of this set of anagrams */
    	UT_hash_handle hh;   /* makes this structure hashable */
    };
    
    // Example 1. Adding an item to a hash.
    void add_entry(struct my_struct* dict[static 1], struct my_struct s[static 1]) {
    	HASH_ADD_KEYPTR(hh, *dict, s->key, strlen(s->key), s);
    }
    
    // Example 2. Looking up an item in a hash.
    struct my_struct* find_entry(struct my_struct* dict[static 1], char key[static 1]) {
    	struct my_struct *s;
    
    	HASH_FIND_STR(*dict, key, s);
    	return s;
    }
    
    // Example 3. Deleting an item from a hash.
    void delete_entry(struct my_struct* dict[static 1], struct my_struct entry[static 1]) {
    	HASH_DEL(*dict, entry);
    }
    
    // Delete all items from a hash
    void delete_all(struct my_struct* dict[static 1]) {
    	struct my_struct* current_entry, * tmp;
    
    	HASH_ITER(hh, *dict, current_entry, tmp) {
    		HASH_DEL(*dict,current_entry);  /* delete; dict advances to next */
    		free(current_entry->value);
    		free(current_entry);            /* optional- if you want to free  */
    	}
    }
    
    /**
     * Return an array of arrays of size *returnSize.  The sizes of the
     * arrays are returned as *columnSizes array.  Note: Both returned
     * array and *columnSizes array must be malloced, assume caller calls
     * free().
     */
    char*** groupAnagrams(char* strs[static 1], signed strsSize,
    		      signed* columnSizes[static 1], signed returnSize[static 1]) {
    	struct my_struct* dict = 0;
    	char* sortedWord = calloc(MAXBUF, sizeof(char));
    	char* current = 0;
    
    	*returnSize = 0;
    
    	/* Fill dictionary with sets of anagrams. aet ==> {0, 2}, ant ==> {1} */
    	for (size_t i = 0; i < strsSize; ++i) {
    		current = strs[i];
    
    		size_t len = strlen(current);
    		memset(sortedWord, 0, MAXBUF*sizeof(char));
    		memcpy(sortedWord, current, (len+1)*sizeof(char));
    		qsort(sortedWord, len, sizeof(*current), comparison);
    
    		struct my_struct* entry = find_entry(&dict, sortedWord);
    		if (entry) {
    			entry->len = entry->len + 1;
    			entry->value = realloc(entry->value,
    			    entry->len*sizeof(char));
    			entry->value[entry->len-1] = i;
    		} else {
    			struct my_struct* entry = calloc(1, sizeof(struct my_struct));
    
    			len = strlen(sortedWord);
    
    			entry->key = calloc(len+1, sizeof(char));
    			memcpy(entry->key, sortedWord, (len+1)*sizeof(char));
    
    			entry->value = calloc(1, sizeof(size_t));
    			entry->value[0] = i;
    			entry->len = 1;
    
    			add_entry(&dict, entry);
    
    			*returnSize = *returnSize + 1;
    		}
    	}
    
    	/*
    	 * Output stage
    	 *
    	 * [
    	 *   ["ate", "eat","tea"],
    	 *   ["nat","tan"],
    	 *   ["bat"]
    	 * ]
    	 */
    	char*** result = calloc(*returnSize, sizeof(char**));
    	size_t resultIdx = 0;
    
    	struct my_struct* current_entry, * tmp;
    
    	*columnSizes = calloc(*returnSize, sizeof(signed));
    
    	HASH_ITER(hh, dict, current_entry, tmp) {
    		size_t* indices = current_entry->value;
    		size_t len = current_entry->len;
    		size_t index = 0;
    
    		(*columnSizes)[resultIdx] = len; 
    
    		result[resultIdx] = calloc(len, sizeof(char*));
    		for (size_t i = 0; i < len; ++i) {
    			index = indices[i];
    			char* answer = strs[index];
    			size_t ansLen = strlen(answer);
    			result[resultIdx][i] = calloc(ansLen+1, sizeof(char));
    			memcpy(result[resultIdx][i], answer, ansLen+1);
    		}
    
    		++resultIdx;
    	}
    
    	delete_all(&dict);
    	free(sortedWord);
    
    	return result;
    }
    
    signed main(int argc, char* argv[argc+1]) {
    	/* ["eat", "tea", "tan", "ate", "nat", "bat"] */
    	signed numWords = 0;
    	scanf("%d\n", &numWords);
    	char** strs = malloc(numWords * sizeof(char*));
    	char* str = malloc(MAXBUF * sizeof(char));
    	memset(str, 0, MAXBUF * sizeof(char));
    
    	for (size_t i = 0; i < numWords; ++i) {
    		if (!fgets(str, MAXBUF, stdin)) {
    			free(str);
    			return 0;
    		} else {
    			size_t len = strlen(str);
    			strs[i] = realloc(strs[i], len * sizeof(char));
    			memset(strs[i], 0, len * sizeof(char));
    			if (strs[i][0] == '\n') {
    				free(str);
    				return 0;
    			}
    			memcpy(strs[i], str, (len-1) * sizeof(char));
    			strs[i][strcspn(strs[i], "\n")] = 0;
    		}
    	}
    
    	signed* columnSizes = 0;
    	signed returnSize = 0;
    	char*** result = groupAnagrams(strs, numWords, &columnSizes, &returnSize);
    
    	for (size_t i = 0; i < returnSize; ++i) {
    		char** list = result[i];
    		size_t colSz = columnSizes[i];
    		for (size_t j = 0; j < colSz; ++j) {
    			printf("%s ", list[j]);
    		}
    		printf("\n");
    	}
    
    	for (size_t i = 0; i < returnSize; ++i) {
    		char** list = result[i];
    		size_t colSz = columnSizes[i];
    		for (size_t j = 0; j < colSz; ++j) {
    			char* word = list[j];
    			free(word);
    		}
    		free(list);
    	}
    	free(result);
    
    	for (size_t i = 0; i < numWords; ++i) {
    		free(strs[i]);
    	}
    
    	free(str);
    
    	return 0;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.