petewarden / c_hashmap Goto Github PK

View Code? Open in Web Editor NEW

517.0 517.0 202.0 9 KB

A simple string hashmap in C

Home Page: http://petewarden.typepad.com/

License: Other

C 100.00%

c_hashmap's People

Contributors

Stargazers

Watchers

Forkers

dshelley66 ntamas stan1y zhurx4g ultimate010 zaikw teardemon xiaopeifenng byteoperator fjordan prakashprabodh wyj2046 raceli moon-fall chandraghale zzs85aa zhanglei wayd2001 littleji pomelolee kofktu youymi techierishi ccoder123 taotown sonnyit bedweather yangchengwork arvin-chou momendev qix- sjokim mooxxnew yangshun2532 garygo magicpanda troelsy liquidradio huqihong168 abhatikar markgorden sophieball vmule lokenetwork koery benwuxiong pktgen human-pose-estimation yeongseon dophist madhusriram tiffanylam2010 machinaut valakkapeddi unclerus gandeevan prazek luogyong hnjiakai hakansel bgokden lishaojun aleclaws yay justanirudh capc5f rahulpyd carsings cvsuser pravez smallpdf ridgeback1982 qichenftw zhouying-bit waldstein1983 yws svdev sy19870112 dvdmuckle pythonpig gypdtc jergusadamec jamesgbl zimuyang chasel-hu jacksonjw12 sgtpepperpt flairyu draculaw clowningaround keunsy xiaorancs gocpp lamraoui denise-amiga zhangzongchen 4second2none vanthaiunghoa seyyah ev2le0

c_hashmap's Issues

Use a different hashmap library

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

Bug when get not exists key

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

Ahem, main's signature is wrong...

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.

Would you please create CI infrastructure, such as Travis CI or Codecov?

High pass ratio of test cases is convincing.

Map size increaded inserting the same key twice

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);
            }
        }
    }
}

Public Domain?

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?

is possible write and read from file ?

why iterate data is not a key,but a value?

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.

Recover keys and values

How to recover keys and values to cleanup with memory free ?

This item is no longer maintained!!!Unless someone can solve this problem for me!!

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!!!

index bug in hashmap_hash function

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;
}

Flaw in hashmap_remove()?

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