petewarden / c_hashmap Goto Github PK
View Code? Open in Web Editor NEWA simple string hashmap in C
Home Page: http://petewarden.typepad.com/
License: Other
A simple string hashmap in C
Home Page: http://petewarden.typepad.com/
License: Other
Obviously, index bug was found here, use i
but not curr
in the loop of hashmap_hash function.
int hashmap_hash(map_t in, char* key){
int curr;
int i;
/* Cast the hashmap */
hashmap_map* m = (hashmap_map *) in;
/* If full, return immediately */
if(m->size >= (m->table_size/2)) return MAP_FULL;
/* Find the best index */
curr = hashmap_hash_int(m, key);
/* Linear probing */
for(i = 0; i< MAX_CHAIN_LENGTH; i++){
if(m->data[curr].in_use == 0)
return curr;
if(m->data[curr].in_use == 1 && (strcmp(m->data[curr].key,key)==0))
return curr;
curr = (curr + 1) % m->table_size;
}
return MAP_FULL;
}
Hi Pete,
hashmap_remove() might open a gap in a sequence of entries which share the same hash value. This might lead to the situation that a hashmap_put() creates a duplicate key rather than updating an existing key.
A remedy would be to insert the "in_use=0" gap at the end of a sequence of entries with the same hash.
Example:
before hashmap_remove()
entry A; hash H; in_use=1
entry B; hash H; in_use=1
entry C; hash H; in_use=1
after hashmap_remove(map, "B")
entry A; hash H; in_use=1
entry -; hash -; in_use=0
entry C; hash H; in_use=1
after hashmap_put(map, "C")
entry A; hash H; in_use=1
entry C; hash H; in_use=1
entry C; hash H; in_use=1
I could write a fixed version, but I am not yet familiar enough with github to deal with pull requests.
Greetings
Axel Kemper
How to recover keys and values to cleanup with memory free ?
if I don't know what the key is,but i want get the both key and value,what should I do?
if the PFany params is key,I can use hashmap_get function to get the key and value when i don't know what the key is.
It should be main(int argc, char ** argv). Parameter names don't matter, but order and type does. Also you should compile with warnings enabled. GCC yields several other warnings for each source file.
I just recognized that inserting the same key twice, the size of the map will be increased, even if inside the keyset there will be just one key (as expected).
#include <stdio.h>
#include <stdlib.h>
#include "../lib/c_hashmap/hashmap.h"
#define MAX (100)
typedef struct idp_s
{
char entity_id[300];
char *display_name;
char *organization;
} idp_t;
int main(int argc, char *argv[]) {
map_t map;
idp_t *value, *value2;
char key_string[MAX];
int map_code, i;
map = hashmap_new();
value = malloc(sizeof(idp_t));
snprintf(value->entity_id, MAX, "%s", "http://login.walterwhite.me/th/");
value->display_name = "ciao";
value->organization = "ciaone";
map_code = hashmap_put(map, value->entity_id, value);
if (map_code == MAP_OK)
printf("Inserted\n");
else
printf("Error\n");
value2 = malloc(sizeof(idp_t));
snprintf(value2->entity_id, MAX, "%s", "http://login.walterwhite.me/th/");
value2->display_name = "ciao2";
value2->organization = "ciaone2";
map_code = hashmap_put(map, value2->entity_id, value2);
if (map_code == MAP_OK)
printf("Inserted\n");
else
printf("Error\n");
snprintf(key_string, MAX, "%s", "http://login.walterwhite.me/th/");
map_code = hashmap_get(map, key_string, (void**)(&value));
if (map_code == MAP_OK)
printf("Found\n");
else
printf("Not found\n");
printf("Size: %d\n", hashmap_length(map));
print_keyset(map);
return 0;
}
The output is:
Inserted
Inserted
Found
Size: 2
Table size: 256
key: http://login.walterwhite.me/th/
Note that I added print_keyset
in hashmap.c
as follows:
void print_keyset(map_t in) {
int i;
hashmap_map* m = (hashmap_map *) in;
if(m != NULL) {
/* Linear probing */
printf("Table size: %d\n", m->table_size);
for(i = 0; i< m->table_size; i++) {
if(m->data[i].in_use != 0) {
printf("key: %s\n", m->data[i].key);
}
}
}
}
High pass ratio of test cases is convincing.
There are no restrictions on how you reuse this code.
Does this mean you have all rights on this code and you release the code into the public domain?
There is a test program to put key: "key=>6" and get key: "key=>-3"
int main() {
char key_string[KEY_MAX_LENGTH];
data_struct_t* value;
int error;
map_t map;
map = hashmap_new();
snprintf(key_string, KEY_MAX_LENGTH, "key=>%d", 6);
value = malloc(sizeof(data_struct_t));
snprintf(value->key_string, KEY_MAX_LENGTH, "value=>%d", 6);
value->number = 6;
hashmap_put(map, key_string, value);
snprintf(key_string, KEY_MAX_LENGTH, "key=>%d", -3);
error = hashmap_get(map, key_string, (void**) (&value));
if (error == MAP_MISSING) {
printf("Missing key:%s\n", key_string);
} else if (error == MAP_OK) {
printf("Has key:%s, value.string:%s, value.number:%d\n", key_string, value->key_string, value->number);
}
value = malloc(sizeof(data_struct_t));
snprintf(value->key_string, KEY_MAX_LENGTH, "value=>%d", -3);
value->number = -3;
error = hashmap_put(map, key_string, value);
if (error != MAP_OK) {
printf("dddddd\n");
}
error = hashmap_get(map, key_string, (void**) (&value));
if (error == MAP_MISSING) {
printf("Missing key:%s\n", key_string);
} else if (error == MAP_OK) {
printf("Has key:%s, value.string:%s, value.number:%d\n", key_string, value->key_string, value->number);
}
}
Test result as following:
Has key:key=>-3, value.string:value=>6, value.number:6
Has key:key=>-3, value.string:value=>-3, value.number:-3
There are many issues with this hashmap implementation, and they have not been addressed for years.
I recommend using this project, instead: https://github.com/DavidLeeds/hashmap
Please all of people search with "hashmap c" do not use this project code.
Unless someone can solve this problem for me!!
Why in hashmap.c the hashmap_hash_int strlen(keystring)
is 0.
I think this is grammatical problems!!!
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.