I am trying to solve this question "Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target." This code works fine and gives the correct output in my local machine but this does not work in leet code. When I run it in leet code , I get the error message : AddressSanitizer heap-use-after-free. I am not able to figure out where exactly I am using the memory out of bounds here.
typedef struct entries
{
int val;
int index;
}entry_t;
typedef struct table
{
entry_t *entry;
}ht_t;
ht_t *table;
int hash(int key, int size)
{
int slot = key % size;
return slot < 0 ? (slot + size) : slot;
}
void insert(int key, int index, ht_t *table, int size)
{
int slot;
slot = hash(key, size);
table->entry[slot].val = key;
table->entry[slot].index = index;
}
int *search(int key, int num, ht_t *table, int size)
{
int slot;
slot = hash(key, size);
if(table->entry[slot].val == key)
{
return &(table->entry[slot].index);
}
return NULL;
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
int i;
*returnSize = 2;
int *returnArr= (int*) malloc((2)*sizeof(int));
//int i;
int complement;
int *retVal;
//int size = numsSize;
table = (ht_t *)malloc(sizeof(ht_t)*1);
table->entry = malloc(sizeof(entry_t)*100);
for(i=0; i<numsSize; i++)
{
complement = target - nums[i];
// look for the other number
retVal = (search(complement,nums[i], table, numsSize));
if(retVal != NULL)
{
returnArr[0] = *retVal;
returnArr[1] = i;
break;
}
// if not found insert it to the table.
insert(nums[i],i,table, numsSize);
}
free(table);
free(table->entry);
return returnArr;
}
int main(void) {
//int arr[6] = {1,2,3,8,5,6};
int arr[6] = {2,7,11,15};
int target = 9;
int* indices = malloc(sizeof(int)*2);;
indices = twoSum(arr, 4, target, indices);
printf("index1 = %d, index2 = %d\n",indices[0], indices[1]);
free(indices);
}
free(table);
free(table->entry);
Swap these statements.
You first free the memory of table, after that you access table ==> Error.
As a example run it with valgrind (valgrind ./executable)
==3028== Memcheck, a memory error detector
==3028== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3028== Using Valgrind-3.16.1 and LibVEX; rerun with -h for copyright info
==3028== Command: ./a.out
==3028==
==3028== Conditional jump or move depends on uninitialised value(s)
==3028== at 0x109218: search (c.c:35)
==3028== by 0x1092E1: twoSum (c.c:60)
==3028== by 0x1093D5: main (c.c:82)
==3028==
==3028== Invalid read of size 8
==3028== at 0x109358: twoSum (c.c:72)
==3028== by 0x1093D5: main (c.c:82)
==3028== Address 0x4a0f0e0 is 0 bytes inside a block of size 8 free'd
==3028== at 0x48399AB: free (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==3028== by 0x109350: twoSum (c.c:71)
==3028== by 0x1093D5: main (c.c:82)
==3028== Block was alloc'd at
==3028== at 0x483877F: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==3028== by 0x109272: twoSum (c.c:53)
==3028== by 0x1093D5: main (c.c:82)
==3028==
index1 = 0, index2 = 1
==3028==
==3028== HEAP SUMMARY:
==3028== in use at exit: 8 bytes in 1 blocks
==3028== total heap usage: 5 allocs, 4 frees, 1,848 bytes allocated
==3028==
==3028== LEAK SUMMARY:
==3028== definitely lost: 8 bytes in 1 blocks
==3028== indirectly lost: 0 bytes in 0 blocks
==3028== possibly lost: 0 bytes in 0 blocks
==3028== still reachable: 0 bytes in 0 blocks
==3028== suppressed: 0 bytes in 0 blocks
==3028== Rerun with --leak-check=full to see details of leaked memory
==3028==
==3028== Use --track-origins=yes to see where uninitialised values come from
==3028== For lists of detected and suppressed errors, rerun with: -s
==3028== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
You get this output. What does it tell you? You allocated a block of size 8 in line 53, you free'd it in line 71 and tried to access it in line 72.
(And on an unrelated note, you use uninitialised values in line 35).