Alocar memória para uma estrutura

[rjfs]

Olá

Quero criar um HashMap, mas estou com uns problemas com a alocação de memória. A estrutura que defini é:

typedef struct Bucket{
   char *key;
   void *data;
   struct Bucket *next;
} Bucket;
typedef struct HashMap{
   Bucket *bucket;
   unsigned int keyspace;
} HashMap;

Tenho que criar uma função create_hashmap que retorne um apontador para a estrutura HashMap e que tenha como parâmetro key_space (size_t que indica o número de buckets no hashmap). A função deve alocar memória suficiente para os key_space buckets e deve ser inicializada a 0 (i.e. NULLed). Há uma lista dentro de cada bucket, porque podem haver diferentes keys que devem ser alocadas no mesmo bucket.

A minha tentativa é a seguinte:

HashMap *create_hashmap(size_t key_space){
   HashMap *hm=NULL;
   Bucket *bptr=NULL;
   unsigned int i=0;

   if ( (hm=malloc(sizeof(HashMap))) == NULL){
       printf("Memory Allocation Error.\n");
       return NULL;
   }

   hm->keyspace=key_space; // save keyspace to be used afterwards

   for(i=0;i<key_space;i++){
       bptr=(hm->bucket)+i;
       if ((bptr=calloc(1,sizeof(Bucket))) == NULL){
           printf("Memory Allocation Error.\n");
           return NULL;
       }
       bptr=NULL;
   }

   return hm;
}

Isto está-me a dar problemas mais à frente (segmentation fault) porque parece que o Bucket não está a ficar NULL como devia. Para além disso também não percebo porque fico com erro de compilação quando faço:

if (( ((hm->bucket)+i) =calloc(1,sizeof(Bucket))) == NULL)

Obrigado desde já!

Edited March 8, 2014 by thoga31
GeSHi

[HappyHippyHippo]

mas quem te ensinou a fazer isto ?

       bptr=(hm->bucket)+i;

fazes ideia do que estás a fazer ? estás a dizer para apontar para a posição de memória :

hm->bucket + i * sizeof(Bucket)

não é assim que funciona uma lista ligada

o que queres será:

if (key_space > 0) {
 if ((hm->bucket = calloc(1, sizeof(Bucket))) == NULL){
   printf("Memory Allocation Error.\n");
   return NULL;
 }

 for(i = 1, bptr = hm->bucket;
     i < key_space;
     ++i, bptr = bptr->next){
   if ((bptr->next = calloc(1, sizeof(Bucket))) == NULL){
     printf("Memory Allocation Error.\n");
     return NULL;
   }
 }
}

[rjfs]

Realmente ninguém me ensinou isso, mas pareceu-me fazer sentido para aquilo que queria implementar. É que eu preciso de ter uma maneira rápida de aceder ao elemento número N da lista. Como posso fazer no caso em que inicializo a lista como disseste, sem ser percorrer os elementos um a um, através de aux=aux->next?

[HappyHippyHippo]

não existe

todas as estruturas de dados tem vantagens e desvantagens.

a desvantagens de uma lista ligada é o acesso a um elemento. para isso existem arrays

Edited March 8, 2014 by HappyHippyHippo

[rjfs]

Acho que o que disse em cima não é bem o que procuro então. O que quero é criar um vector de buckets, todos eles inicializados a NULL. A lista não é criada neste ponto. Apenas mais tarde, se por acaso houver duas ou mais keys às quais a hash function atribua o mesmo Bucket. Quero algo como o que está aqui http://upload.wikimedia.org/wikipedia/commons/d/d0/Hash_table_5_0_1_1_1_1_1_LL.svg

[HappyHippyHippo]

struct BucketEntry {
 // bucket data fields
 struct Bucket * next;
};

struct Bucket {
 struct BucketEntry * entries;
};

struct HashMap {
 struct Bucket * buckets;
 size_t alloc_size;
};

int hashmapInit(struct HashMap * hashmap) {
 hashmap->buckets = NULL;
 hashmap->alloc_size = 0;

 return 0;
}

int hashmapResize(struct HashMap * hashmap,
                 size_t size) {
 struct Bucket * aux = NULL;

 if (hashmap->buckets == NULL) {
   if ((hashmap->buckets = malloc(sizeof(struct Bucket) * size)) == NULL)
     return -1;
 } else {
   if ((aux = realloc(hashmap->buckets,
                      sizeof(struct Bucket) * size)) == NULL)
     return -1;

   hashmap->buckets = aux;
 }
 hashmap->alloc_size = size;

 return 0;
}

int main(void) {
 struct HashMap hashmap;

 hashmapInit(&hashmap);
 hashmapResize(&hashmap, 10);
 hashmapResize(&hashmap, 100);
 hashmapResize(&hashmap, 50);  // cuidado, este código tem memory leak ao não libertar as entries dos buckets libertados com o realloc
}

Edited March 8, 2014 by HappyHippyHippo

[rjfs]

Muito obrigado pela ajuda até agora. Realmente definir assim as estruturas faz muito mais sentido. Fiquei então com:

typedef struct BucketEntry{
void *data;
struct BucketEntry *next;
} BucketEntry;

typedef struct Bucket{
char *key;
BucketEntry *entries;
} Bucket;

typedef struct HashMap{
Bucket *buckets;
size_t keyspace;  
unsigned int (*hashfunction)(char *key);
} HashMap;

Mas agora, como acedo à posição N do vector? Estou a tentar da seguinte forma, mas dá erro de compilação:

void insert_element(HashMap *hm, const char key[], const void *data, size_t length){
  unsigned int pos=hash(key)%(hm->keyspace);
  Bucket *new=NULL;

  if (hm->buckets[pos]==NULL){
     // create new element
     // (...)
  }


  return;
}

length indica o tamanho da data.

Edited March 8, 2014 by rjfs

[Rui Carlos]

Se dá erro, indica qual é o erro.

[rjfs]

Para já, só quero saber como acedo à posição i do vector de estruturas, quando aloco da forma como HappyHippyHippo disse.

Quando faço:

   Bucket *aux;    
   aux=hm->bucket[pos];

Obtenho o erro:

error: incompatible types when assigning to type ‘struct Bucket *’ from type ‘Bucket’

[Rui Carlos]

Não há qualquer problema em aceder à posição i do array.

O problema são os tipos de dados e as atribuições que queres fazer. A mensagem de erro é mais ou menos clara. 🙂

Qual é o tipo de hm->bucket[pos]?

Qual é o tipo de aux?

[rjfs]

aux é apontador para Bucket, o outro não sei mas pensava que era o mesmo.

O que devo fazer então para corrigir? Estou a ficar com alguma pressa que isto é para entregar até amanhã às 8h.

[Rui Carlos]

buckets é um apontador (ou neste caso, um array). Cada elemento, do array será então do tipo Bucket.

Penso que deves resolver o problema com algo do género &(hm->bucket[pos]).

[rjfs]

Obrigado! Era mesmo isso que precisava.