rjfs Posted March 8, 2014 at 02:25 PM Report #547902 Posted March 8, 2014 at 02:25 PM (edited) 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 at 03:29 PM by thoga31 GeSHi
HappyHippyHippo Posted March 8, 2014 at 06:25 PM Report #547924 Posted March 8, 2014 at 06:25 PM 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; } } } 1 Report IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
rjfs Posted March 8, 2014 at 07:36 PM Author Report #547935 Posted March 8, 2014 at 07:36 PM 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 Posted March 8, 2014 at 07:40 PM Report #547936 Posted March 8, 2014 at 07:40 PM (edited) 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 at 07:41 PM by HappyHippyHippo IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
rjfs Posted March 8, 2014 at 07:47 PM Author Report #547937 Posted March 8, 2014 at 07:47 PM 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 Posted March 8, 2014 at 07:59 PM Report #547938 Posted March 8, 2014 at 07:59 PM (edited) 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 at 08:00 PM by HappyHippyHippo IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
rjfs Posted March 8, 2014 at 08:41 PM Author Report #547945 Posted March 8, 2014 at 08:41 PM (edited) 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 at 08:43 PM by rjfs
Rui Carlos Posted March 9, 2014 at 06:35 PM Report #547989 Posted March 9, 2014 at 06:35 PM Se dá erro, indica qual é o erro. Rui Carlos Gonçalves
rjfs Posted March 9, 2014 at 10:32 PM Author Report #548001 Posted March 9, 2014 at 10:32 PM 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 Posted March 9, 2014 at 10:48 PM Report #548004 Posted March 9, 2014 at 10:48 PM 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? Rui Carlos Gonçalves
rjfs Posted March 9, 2014 at 11:08 PM Author Report #548007 Posted March 9, 2014 at 11:08 PM 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 Posted March 9, 2014 at 11:14 PM Report #548009 Posted March 9, 2014 at 11:14 PM 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]). Rui Carlos Gonçalves
rjfs Posted March 9, 2014 at 11:29 PM Author Report #548013 Posted March 9, 2014 at 11:29 PM Obrigado! Era mesmo isso que precisava.
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now