sistemas - Error de segmentación pero no puedo razonar cómo, la asignación de memoria se ve bien para mí

primer ajuste mejor ajuste peor ajuste

Question

Tengo un nodo y estoy definiendo su variable puntero global de la siguiente manera:

typedef struct node
{
    char* word;
    struct node* next;
} node;

node* HashTable =  NULL;
node* HeadOfHashTable = NULL;

Ahora, asigné memoria de la siguiente manera:

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

    if(HashTable == NULL)
    {
        printf("### Out Of Memory ###/n");
        exit(0);
    }
    HeadOfHashTable = HashTable;
}

Ahora, estoy pasando un valor HASH y una palabra para poner en la tabla hash, en el siguiente método. He comentado de dónde estoy obteniendo seg fault.

void putInHashTable(char* ch, unsigned int hashValue)
{
    HashTable += hashValue;

    printf("Processing at address: %p and has value was %d/n", HashTable, hashValue);

    if(HashTable == NULL || HashTable == ''/0'' || HashTable == 0)
    {
        printf("Hash table is NULL");
    }

    if(HashTable->word == NULL)
    {
        HashTable->word = malloc(sizeof(char) * (LENGTH + 1));
        strcpy(HashTable->word, ch);
        printf("New word: %s/n", HashTable->word);
    } else {
        printf("### Collision detected ###/n"); // ***** BELOW LINE GIVES SEG FAULT ******
        printf("    Earlier value is %s, new value is %s and its pointer is %p/n", HashTable->word, ch, HashTable->next);
        putInLinkedList(ch);
    }

    HashTable = HeadOfHashTable;
}

A continuación se muestran los registros de la consola:

Allocating 65336 blocks
Processing at address: 0xb7568c28 and has value was 388
New word: a
Processing at address: 0xb756b9a0 and has value was 1843
New word: aaa
Processing at address: 0xb7570c08 and has value was 4480
New word: aaas
Processing at address: 0xb75ae608 and has value was 36032
### Collision detected ###
Segmentation fault (core dumped)

Mis dudas:

• Estoy asignando 65336 bloques de memoria y el punto donde obtengo seg fault tiene un valor hash de 36032, por lo que estoy seguro de que la variable puntero HashTable tiene una dirección de memoria válida. Entonces, ¿por qué falla?
• Si no es una dirección válida, entonces ¿por qué no está atrapada en esta condición IF if(HashTable == NULL || HashTable == ''/0'' || HashTable == 0) . Incluso utilicé el calloc y también obtuve el fallo seg y, por encima de, la condición IF no capta.
• Obtengo seg fault en esta línea printf(" Earlier value is %s, new value is %s and its pointer is %p/n", HashTable->word, ch, HashTable->next); . Esto significa algún problema al desviar el puntero, entonces ¿por qué no obtuve un fallo de seg justo antes de eso, significa que debería haber obtenido un fallo seg solo aquí - if(HashTable->word == NULL) ?

Answer 1

Contando las estrellas.

 FOO * foo_ptr = malloc (sizeof (FOO) * n_foos);
 //  ^                                ^             
 //  |                                |
 //  one star to the left of `=`      one star to the right of `=`

La regla de oro: el número de estrellas debe ser el mismo en cualquier lado de la asignación. ¿Por qué?

      sizeof(FOO)    sizeof(FOO)    sizeof(FOO)   
     _____________  _____________  ______________
    /             //             //              /
     _____________  _____________  ______________
    [_____FOO_____][_____FOO_____][______FOO_____]
    ^
    |
    FOO* foo_ptr; // a FOO* points to a FOO
                  // pointer arithmetic works by incrementing the address/
                  // by sizeof(FOO)
                  // and so on

Otros ejemplos de buen código:

 FOO ** foo_ptr = malloc (sizeof (FOO*) * n_foos); // same number of stars
 FOO *** foo_ptr = malloc (sizeof (FOO**) * n_foos); // still same

Código incorrecto:

 FOO ** foo_ptr = malloc (sizeof (FOO) * n_foos); // numbers don''t match
 FOO * foo_ptr = malloc (sizeof (FOO*) * n_foos); // numbers don''t match

Tu linea

HashTable = malloc(sizeof(node*) * numOfElements);

(después de sustituir el tipo de HashTable que es el node* ) cae directamente en el contenedor de código incorrecto, por lo tanto, intente solucionarlo.

Si quieres una matriz de nodos:

HashTable = malloc(sizeof(node) * numOfElements);

Si quieres una variedad de pouners a nodos, puedes tener eso también. Esto no es realmente recomendable, ya que el ahorro de espacio es pequeño, la degradación del rendimiento probablemente sea sustancial y el código sea menos elegante. Pero puedes tenerlo:

node** HashTable = malloc(sizeof(node*) * numOfElements); // count! the! stars!

¡Felicitaciones! Ahora tiene una matriz de punteros no inicializados numOfElements . Ahora necesita inicializarlos con algún valor, generalmente NULL:

for (i = 0; i < numOfElements; ++i) HashTable[i] = NULL;

Y necesita asignar un nuevo node cada vez que quiera poner un valor a la tabla:

if (HashTable[hashValue] == NULL) 
{
  HashTable[hashValue] = malloc(sizeof(node));
  if (HashTable[hashValue] == NULL) 
  {
    panic ("Out of memory!");
  }
  HashTable[hashValue]->word = ...
  HashTable[hashValue]->next = ...
} 
else 
{
  // collision etc
}

Mientras estamos en ello, tenga en cuenta estos momentos que son tangenciales a la pregunta principal: cómo verificar correctamente NULL, cómo verificar el valor de retorno de malloc y cómo usar un índice de matriz en lugar de mutar una variable de puntero global. y adelante. (Si desea utilizar la aritmética de puntero, tenga una variable de puntero local en putInHashTable ).

(Por supuesto, si no usa n_foos, o usa calloc, necesita hacer ajustes mentales a la cantidad de estrellas).