-4
Я пытаюсь реализовать идеальную хеш-функцию для заданного набора 0,1 миллион уникальных ключей. В процессе разработки кода iam получает ошибку сегментации. Проблема может быть в функции insert_hash. Но будучи новичком в C, я не могу понять его. Вот полный код.valgrind-invalid операции чтения и записи
# include<stdio.h> # include <stdlib.h> # define array_size 1000000 /* Function to calculate x raised to the power y */ int keys[1000000]; unsigned long long p = 100000000019; int power(int x, unsigned int y) { if (y == 0) return 1; else if (y % 2 == 0) return power(x, y/2) * power(x, y/2); else return x * power(x, y/2) * power(x, y/2); } int rand_number() { //generate 9 digit random numbers with in range a and b; int a = 100000000, b = 999999999, num; num = rand() % (b - a + 1) + a; return num; } struct hash { int count, a, b, m; int *dyn_array; }*ptr[array_size], *tmp = NULL; void insert_hashkey(int hash1, int key) { int arraysize = 1, i, hash_value; static int primaryhashcount = 0, secondhashcount = 0; if (ptr[hash1]->count == 1) { primaryhashcount++; //ptr[hash1]=NULL; ptr[hash1]->dyn_array = (int*) malloc((sizeof(int)) * arraysize); if (ptr[hash1]->dyn_array == NULL) { printf("out of memory\n"); exit(1); } ptr[hash1]->dyn_array[0] = key; printf("\n ptr[%d]->dyn_array[0]=%d %d", hash1, key, primaryhashcount); } else { printf("\n entered in to else part"); //ptr[hash1]=a; secondhashcount++; tmp = (struct hash*) malloc(sizeof(struct hash)); tmp->m = (ptr[hash1]->count) * (ptr[hash1]->count); tmp->count = (ptr[hash1]->count); --(ptr[hash1]->count); arraysize = (ptr[hash1]->count) * (ptr[hash1]->count); //tmp=a; tmp->dyn_array = (int*) malloc((sizeof(int)) * arraysize); if (tmp->dyn_array == NULL) { printf("out of memory\n"); exit(1); } tmp->a = rand_number(); tmp->b = rand_number(); for (i = 0; i < tmp->m; i++) tmp->dyn_array[i] = -1; for (i = 0; i < arraysize; i++) { if (ptr[hash1]->dyn_array[i] != -1) { hash_value = (((tmp->a) * (ptr[hash1]->dyn_array[i]) + tmp->b) % p) % (tmp->m); printf("\n first if success"); if (tmp->dyn_array[hash_value] == -1) { tmp->dyn_array[hash_value] = ptr[hash1]->dyn_array[i]; secondhashcount, tmp->count, hash1, hash_value, (ptr[hash1]->dyn_array[i]), tmp->m); } } } hash_value = (((tmp->a) * key + tmp->b) % p) % (tmp->m); if (tmp->dyn_array[hash_value] == -1) { tmp->dyn_array[hash_value] = key; printf( "\n second hash count=%d count=%d ptr[%d]->dyn_array[%d]=%d,m=%d", secondhashcount, tmp->count, hash1, hash_value, key, tmp->m); } else printf("\n collision"); free(ptr[hash1]->dyn_array); free(ptr[hash1]); ptr[hash1] = tmp; tmp = NULL; } } int hash_fun(int key, int a, int b, unsigned long long p) { int hash_val; hash_val = (((a * key) + b) % p) % 1000000; return hash_val; } void main() { int i = 0, hash1, count = 0, j; char ch; int a, b, m; time_t t; FILE *fp; fp = fopen("input.in", "r"); /* Intializes rand_num number generator */ srand((unsigned) time(&t)); for (i = 0; i < array_size; i++) { ptr[i] = NULL; } a = 774877719; b = 271009528; i = 0; while (fscanf(fp, "%d", &keys[i++]) == 1) ; printf("\n read keys successfully from file"); //finding the hash values of array for (i = 0; i < 100000; i++) { hash1 = hash_fun(keys[i], a, b, p); if (ptr[hash1] == NULL) { // create a structure of ni2 elements for each pointer where ni is the number of collisions // printf("\nmaximum size=%d",malloc(MAX)); ptr[hash1] = (struct hash *) malloc(sizeof(struct hash)); if (ptr[hash1] == NULL) { printf("out of memory\n"); exit(1); } ptr[hash1]->count = 1; insert_hashkey(hash1, keys[i]); } else { ++(ptr[hash1]->count); insert_hashkey(hash1, keys[i]); } } for (i = 0; i < array_size; i++) { if (ptr[hash1] != NULL) free(ptr[hash1]); } }
2.the Ниже приводится отчет Valgrind. но IAM не в состоянии найти точную проблему в моем коде, как все кажется правильным для меня после того, как пытаться исправить за 6 hours.please помочь мне в этом контексте
==3595== LEAK SUMMARY:
==3595== definitely lost: 4 bytes in 1 blocks
==3595== indirectly lost: 0 bytes in 0 blocks
==3595== possibly lost: 0 bytes in 0 blocks
==3595== still reachable: 2,287,100 bytes in 190,411 blocks
==3595== suppressed: 0 bytes in 0 blocks
==3595== Reachable blocks (those to which a pointer was found) are not shown.
==3595== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==3595==
==3595== ERROR SUMMARY: 1026216 errors from 11 contexts (suppressed: 0 from 0)
==3595==
==3595== 62 errors in context 1 of 11:
==3595== Invalid write of size 4
==3595== at 0x8048A46: insert_hashkey (in /home/abhimint/Desktop/hashing/a.out)
==3595== by 0x8048CEA: main (in /home/abhimint/Desktop/hashing/a.out)
==3595== Address 0x449be94 is 4 bytes after a block of size 16 alloc'd
==3595== at 0x402A17C: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==3595== by 0x8048807: insert_hashkey (in /home/abhimint/Desktop/hashing/a.out)
==3595== by 0x8048CEA: main (in /home/abhimint/Desktop/hashing/a.out)
==3595==
==3595==
==3595== 110 errors in context 2 of 11:
==3595== Invalid read of size 4
==3595== at 0x8048976: insert_hashkey (in /home/abhimint/Desktop/hashing/a.out)
==3595== by 0x8048CEA: main (in /home/abhimint/Desktop/hashing/a.out)
==3595== Address 0x439a804 is 0 bytes after a block of size 4 alloc'd
==3595== at 0x402A17C: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==3595== by 0x8048807: insert_hashkey (in /home/abhimint/Desktop/hashing/a.out)
==3595== by 0x8048CEA: main (in /home/abhimint/Desktop/hashing/a.out)
==3595==
==3595==
==3595== 110 errors in context 3 of 11:
==3595== Invalid read of size 4
==3595== at 0x8048955: insert_hashkey (in /home/abhimint/Desktop/hashing/a.out)
==3595== by 0x8048CEA: main (in /home/abhimint/Desktop/hashing/a.out)
==3595== Address 0x439a804 is 0 bytes after a block of size 4 alloc'd
==3595== at 0x402A17C: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==3595== by 0x8048807: insert_hashkey (in /home/abhimint/Desktop/hashing/a.out)
==3595== by 0x8048CEA: main (in /home/abhimint/Desktop/hashing/a.out)
==3595==
==3595==
==3595== 113 errors in context 4 of 11:
==3595== Invalid read of size 4
==3595== at 0x80488C4: insert_hashkey (in /home/abhimint/Desktop/hashing/a.out)
==3595== by 0x8048CEA: main (in /home/abhimint/Desktop/hashing/a.out)
==3595== Address 0x439a804 is 0 bytes after a block of size 4 alloc'd
==3595== at 0x402A17C: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==3595== by 0x8048807: insert_hashkey (in /home/abhimint/Desktop/hashing/a.out)
==3595== by 0x8048CEA: main (in /home/abhimint/Desktop/hashing/a.out)
==3595==
==3595==
==3595== 457 errors in context 5 of 11:
==3595== Invalid read of size 4
==3595== at 0x804889C: insert_hashkey (in /home/abhimint/Desktop/hashing/a.out)
==3595== by 0x8048CEA: main (in /home/abhimint/Desktop/hashing/a.out)
==3595== Address 0x4487004 is 0 bytes after a block of size 4 alloc'd
==3595== at 0x402A17C: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==3595== by 0x8048807: insert_hashkey (in /home/abhimint/Desktop/hashing/a.out)
==3595== by 0x8048CEA: main (in /home/abhimint/Desktop/hashing/a.out)
==3595==
==3595==
==3595== 3552 errors in context 6 of 11:
==3595== Invalid read of size 4
==3595== at 0x8048A2C: insert_hashkey (in /home/abhimint/Desktop/hashing/a.out)
==3595== by 0x8048CEA: main (in /home/abhimint/Desktop/hashing/a.out)
==3595== Address 0x425110c is 8 bytes after a block of size 4 alloc'd
==3595== at 0x402A17C: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==3595== by 0x8048807: insert_hashkey (in /home/abhimint/Desktop/hashing/a.out)
==3595== by 0x8048CEA: main (in /home/abhimint/Desktop/hashing/a.out)
==3595==
==3595==
==3595== 3561 errors in context 7 of 11:
==3595== Invalid write of size 4
==3595== at 0x8048957: insert_hashkey (in /home/abhimint/Desktop/hashing/a.out)
==3595== by 0x8048CEA: main (in /home/abhimint/Desktop/hashing/a.out)
==3595== Address 0x425110c is 8 bytes after a block of size 4 alloc'd
==3595== at 0x402A17C: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==3595== by 0x8048807: insert_hashkey (in /home/abhimint/Desktop/hashing/a.out)
==3595== by 0x8048CEA: main (in /home/abhimint/Desktop/hashing/a.out)
==3595==
==3595==
==3595== 3561 errors in context 8 of 11:
==3595== Invalid read of size 4
==3595== at 0x8048929: insert_hashkey (in /home/abhimint/Desktop/hashing/a.out)
==3595== by 0x8048CEA: main (in /home/abhimint/Desktop/hashing/a.out)
==3595== Address 0x425110c is 8 bytes after a block of size 4 alloc'd
==3595== at 0x402A17C: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==3595== by 0x8048807: insert_hashkey (in /home/abhimint/Desktop/hashing/a.out)
==3595== by 0x8048CEA: main (in /home/abhimint/Desktop/hashing/a.out)
==3595==
==3595==
==3595== 14690 errors in context 9 of 11:
==3595== Invalid write of size 4
==3595== at 0x8048864: insert_hashkey (in /home/abhimint/Desktop/hashing/a.out)
==3595== by 0x8048CEA: main (in /home/abhimint/Desktop/hashing/a.out)
==3595== Address 0x4228b84 is 0 bytes after a block of size 4 alloc'd
==3595== at 0x402A17C: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==3595== by 0x8048807: insert_hashkey (in /home/abhimint/Desktop/hashing/a.out)
==3595== by 0x8048CEA: main (in /home/abhimint/Desktop/hashing/a.out)
==3595==
==3595==
==3595== 999999 errors in context 10 of 11:
==3595== Invalid free()/delete/delete[]/realloc()
==3595== at 0x402B3D8: free (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==3595== by 0x8048D29: main (in /home/abhimint/Desktop/hashing/a.out)
==3595== Address 0x4e3b6b0 is 0 bytes inside a block of size 20 free'd
==3595== at 0x402B3D8: free (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==3595== by 0x8048D29: main (in /home/abhimint/Desktop/hashing/a.out)
==3595==
==3595== ERROR SUMMARY: 1026216 errors from 11 contexts (suppressed: 0 from 0)
Я попробовал и обнаружил, что проблема заключается в функции insert_hash. Но iam не может найти точную проблему. –
Кажется, вы предполагаете, что ptr [hash1] не имеет значения null или nullptr в функции insert_hashkey. Может быть, попробуйте проверить, является ли NULL или nullptr – wjk2a1
да, он возвращает null.but, есть ли ситуация, когда malloc не может выделить память.if так, как исправить его –