Jump to content

Alocar memória para uma estrutura


rjfs
 Share

Recommended Posts

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 by thoga31
GeSHi
Link to comment
Share on other sites

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;
   }
 }
}
  • Vote 1
IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

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?

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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 by HappyHippyHippo
IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

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 by rjfs
Link to comment
Share on other sites

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’
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.