diff options
| -rw-r--r-- | src/attr.c | 48 | ||||
| -rw-r--r-- | src/attr.h | 6 | ||||
| -rw-r--r-- | src/attr_file.h | 1 | ||||
| -rw-r--r-- | src/config_cache.c | 1 | ||||
| -rw-r--r-- | src/config_file.c | 58 | ||||
| -rw-r--r-- | src/hashtable.c | 328 | ||||
| -rw-r--r-- | src/hashtable.h | 102 | ||||
| -rw-r--r-- | src/khash_str.h | 54 | ||||
| -rw-r--r-- | src/oidmap.h (renamed from src/khash_oid.h) | 12 | ||||
| -rw-r--r-- | src/refs.c | 46 | ||||
| -rw-r--r-- | src/refs.h | 4 | ||||
| -rw-r--r-- | src/repository.h | 4 | ||||
| -rw-r--r-- | src/revwalk.c | 10 | ||||
| -rw-r--r-- | src/strmap.h | 54 | ||||
| -rw-r--r-- | src/submodule.c | 46 | ||||
| -rw-r--r-- | tests-clar/core/strmap.c | 102 | ||||
| -rw-r--r-- | tests/t07-hashtable.c | 189 | ||||
| -rw-r--r-- | tests/test_main.c | 2 |
18 files changed, 273 insertions, 794 deletions
diff --git a/src/attr.c b/src/attr.c index 1d7f3aa22..3e3a7e749 100644 --- a/src/attr.c +++ b/src/attr.c @@ -3,7 +3,7 @@ #include "config.h" #include <ctype.h> -GIT_KHASH_STR__IMPLEMENTATION; +GIT__USE_STRMAP; static int collect_attr_files( git_repository *repo, const char *path, git_vector *files); @@ -126,14 +126,14 @@ int git_attr_foreach( git_attr_file *file; git_attr_rule *rule; git_attr_assignment *assign; - git_khash_str *seen = NULL; + git_strmap *seen = NULL; if ((error = git_attr_path__init( &path, pathname, git_repository_workdir(repo))) < 0 || (error = collect_attr_files(repo, pathname, &files)) < 0) return error; - seen = git_khash_str_alloc(); + seen = git_strmap_alloc(); GITERR_CHECK_ALLOC(seen); git_vector_foreach(&files, i, file) { @@ -142,10 +142,10 @@ int git_attr_foreach( git_vector_foreach(&rule->assigns, k, assign) { /* skip if higher priority assignment was already seen */ - if (git_khash_str_exists(seen, assign->name)) + if (git_strmap_exists(seen, assign->name)) continue; - git_khash_str_insert(seen, assign->name, assign, error); + git_strmap_insert(seen, assign->name, assign, error); if (error >= 0) error = callback(assign->name, assign->value, payload); @@ -156,7 +156,7 @@ int git_attr_foreach( } cleanup: - git_khash_str_free(seen); + git_strmap_free(seen); git_vector_free(&files); return error; @@ -200,12 +200,12 @@ int git_attr_add_macro( bool git_attr_cache__is_cached(git_repository *repo, const char *path) { const char *cache_key = path; - git_khash_str *files = git_repository_attr_cache(repo)->files; + git_strmap *files = git_repository_attr_cache(repo)->files; if (repo && git__prefixcmp(cache_key, git_repository_workdir(repo)) == 0) cache_key += strlen(git_repository_workdir(repo)); - return git_khash_str_exists(files, cache_key); + return git_strmap_exists(files, cache_key); } int git_attr_cache__lookup_or_create_file( @@ -220,9 +220,9 @@ int git_attr_cache__lookup_or_create_file( git_attr_file *file = NULL; khiter_t pos; - pos = git_khash_str_lookup_index(cache->files, key); - if (git_khash_str_valid_index(cache->files, pos)) { - *file_ptr = git_khash_str_value_at(cache->files, pos); + pos = git_strmap_lookup_index(cache->files, key); + if (git_strmap_valid_index(cache->files, pos)) { + *file_ptr = git_strmap_value_at(cache->files, pos); return 0; } @@ -240,7 +240,7 @@ int git_attr_cache__lookup_or_create_file( error = git_attr_file__set_path(repo, key, file); if (!error) { - git_khash_str_insert(cache->files, file->path, file, error); + git_strmap_insert(cache->files, file->path, file, error); if (error > 0) error = 0; } @@ -383,13 +383,13 @@ int git_attr_cache__init(git_repository *repo) /* allocate hashtable for attribute and ignore file contents */ if (cache->files == NULL) { - cache->files = git_khash_str_alloc(); + cache->files = git_strmap_alloc(); GITERR_CHECK_ALLOC(cache->files); } /* allocate hashtable for attribute macros */ if (cache->macros == NULL) { - cache->macros = git_khash_str_alloc(); + cache->macros = git_strmap_alloc(); GITERR_CHECK_ALLOC(cache->macros); } @@ -416,21 +416,21 @@ void git_attr_cache_flush( if (cache->files != NULL) { git_attr_file *file; - git_khash_str_foreach_value(cache->files, file, { + git_strmap_foreach_value(cache->files, file, { git_attr_file__free(file); }); - git_khash_str_free(cache->files); + git_strmap_free(cache->files); } if (cache->macros != NULL) { git_attr_rule *rule; - git_khash_str_foreach_value(cache->macros, rule, { + git_strmap_foreach_value(cache->macros, rule, { git_attr_rule__free(rule); }); - git_khash_str_free(cache->macros); + git_strmap_free(cache->macros); } git_pool_clear(&cache->pool); @@ -440,28 +440,28 @@ void git_attr_cache_flush( int git_attr_cache__insert_macro(git_repository *repo, git_attr_rule *macro) { - git_khash_str *macros = git_repository_attr_cache(repo)->macros; + git_strmap *macros = git_repository_attr_cache(repo)->macros; int error; /* TODO: generate warning log if (macro->assigns.length == 0) */ if (macro->assigns.length == 0) return 0; - git_khash_str_insert(macros, macro->match.pattern, macro, error); + git_strmap_insert(macros, macro->match.pattern, macro, error); return (error < 0) ? -1 : 0; } git_attr_rule *git_attr_cache__lookup_macro( git_repository *repo, const char *name) { - git_khash_str *macros = git_repository_attr_cache(repo)->macros; + git_strmap *macros = git_repository_attr_cache(repo)->macros; khiter_t pos; - pos = git_khash_str_lookup_index(macros, name); + pos = git_strmap_lookup_index(macros, name); - if (!git_khash_str_valid_index(macros, pos)) + if (!git_strmap_valid_index(macros, pos)) return NULL; - return (git_attr_rule *)git_khash_str_value_at(macros, pos); + return (git_attr_rule *)git_strmap_value_at(macros, pos); } diff --git a/src/attr.h b/src/attr.h index 75e98607f..43caf1b81 100644 --- a/src/attr.h +++ b/src/attr.h @@ -8,7 +8,7 @@ #define INCLUDE_attr_h__ #include "attr_file.h" -#include "khash_str.h" +#include "strmap.h" #define GIT_ATTR_CONFIG "core.attributesfile" #define GIT_IGNORE_CONFIG "core.excludesfile" @@ -16,8 +16,8 @@ typedef struct { int initialized; git_pool pool; - git_khash_str *files; /* hash path to git_attr_file of rules */ - git_khash_str *macros; /* hash name to vector<git_attr_assignment> */ + git_strmap *files; /* hash path to git_attr_file of rules */ + git_strmap *macros; /* hash name to vector<git_attr_assignment> */ const char *cfg_attr_file; /* cached value of core.attributesfile */ const char *cfg_excl_file; /* cached value of core.excludesfile */ } git_attr_cache; diff --git a/src/attr_file.h b/src/attr_file.h index 9788a2295..677534158 100644 --- a/src/attr_file.h +++ b/src/attr_file.h @@ -9,7 +9,6 @@ #include "git2/attr.h" #include "vector.h" -#include "hashtable.h" #include "pool.h" #define GIT_ATTR_FILE ".gitattributes" diff --git a/src/config_cache.c b/src/config_cache.c index 5e20847f5..3679a9646 100644 --- a/src/config_cache.c +++ b/src/config_cache.c @@ -7,7 +7,6 @@ #include "common.h" #include "fileops.h" -#include "hashtable.h" #include "config.h" #include "git2/config.h" #include "vector.h" diff --git a/src/config_file.c b/src/config_file.c index a0ce329fc..7841ea00f 100644 --- a/src/config_file.c +++ b/src/config_file.c @@ -12,13 +12,13 @@ #include "buffer.h" #include "git2/config.h" #include "git2/types.h" -#include "khash_str.h" +#include "strmap.h" #include <ctype.h> #include <sys/types.h> #include <regex.h> -GIT_KHASH_STR__IMPLEMENTATION; +GIT__USE_STRMAP; typedef struct cvar_t { struct cvar_t *next; @@ -72,7 +72,7 @@ typedef struct { typedef struct { git_config_file parent; - git_khash_str *values; + git_strmap *values; struct { git_buf buffer; @@ -132,21 +132,21 @@ static int normalize_name(const char *in, char **out) return 0; } -static void free_vars(git_khash_str *values) +static void free_vars(git_strmap *values) { cvar_t *var = NULL; if (values == NULL) return; - git_khash_str_foreach_value(values, var, + git_strmap_foreach_value(values, var, while (var != NULL) { cvar_t *next = CVAR_LIST_NEXT(var); cvar_free(var); var = next; }); - git_khash_str_free(values); + git_strmap_free(values); } static int config_open(git_config_file *cfg) @@ -154,7 +154,7 @@ static int config_open(git_config_file *cfg) int res; diskfile_backend *b = (diskfile_backend *)cfg; - b->values = git_khash_str_alloc(); + b->values = git_strmap_alloc(); GITERR_CHECK_ALLOC(b->values); git_buf_init(&b->reader.buffer, 0); @@ -196,7 +196,7 @@ static int file_foreach(git_config_file *backend, int (*fn)(const char *, const if (!b->values) return 0; - git_khash_str_foreach(b->values, key, var, + git_strmap_foreach(b->values, key, var, do { if (fn(key, var->value, data) < 0) break; @@ -223,9 +223,9 @@ static int config_set(git_config_file *cfg, const char *name, const char *value) * Try to find it in the existing values and update it if it * only has one value. */ - pos = git_khash_str_lookup_index(b->values, key); - if (git_khash_str_valid_index(b->values, pos)) { - cvar_t *existing = git_khash_str_value_at(b->values, pos); + pos = git_strmap_lookup_index(b->values, key); + if (git_strmap_valid_index(b->values, pos)) { + cvar_t *existing = git_strmap_value_at(b->values, pos); char *tmp = NULL; git__free(key); @@ -258,7 +258,7 @@ static int config_set(git_config_file *cfg, const char *name, const char *value) GITERR_CHECK_ALLOC(var->value); } - git_khash_str_insert2(b->values, key, var, old_var, rval); + git_strmap_insert2(b->values, key, var, old_var, rval); if (rval < 0) return -1; if (old_var != NULL) @@ -284,14 +284,14 @@ static int config_get(git_config_file *cfg, const char *name, const char **out) if (normalize_name(name, &key) < 0) return -1; - pos = git_khash_str_lookup_index(b->values, key); + pos = git_strmap_lookup_index(b->values, key); git__free(key); /* no error message; the config system will write one */ - if (!git_khash_str_valid_index(b->values, pos)) + if (!git_strmap_valid_index(b->values, pos)) return GIT_ENOTFOUND; - *out = ((cvar_t *)git_khash_str_value_at(b->values, pos))->value; + *out = ((cvar_t *)git_strmap_value_at(b->values, pos))->value; return 0; } @@ -311,13 +311,13 @@ static int config_get_multivar( if (normalize_name(name, &key) < 0) return -1; - pos = git_khash_str_lookup_index(b->values, key); + pos = git_strmap_lookup_index(b->values, key); git__free(key); - if (!git_khash_str_valid_index(b->values, pos)) + if (!git_strmap_valid_index(b->values, pos)) return GIT_ENOTFOUND; - var = git_khash_str_value_at(b->values, pos); + var = git_strmap_value_at(b->values, pos); if (regex_str != NULL) { regex_t regex; @@ -374,13 +374,13 @@ static int config_set_multivar( if (normalize_name(name, &key) < 0) return -1; - pos = git_khash_str_lookup_index(b->values, key); - if (!git_khash_str_valid_index(b->values, pos)) { + pos = git_strmap_lookup_index(b->values, key); + if (!git_strmap_valid_index(b->values, pos)) { git__free(key); return GIT_ENOTFOUND; } - var = git_khash_str_value_at(b->values, pos); + var = git_strmap_value_at(b->values, pos); result = regcomp(&preg, regexp, REG_EXTENDED); if (result < 0) { @@ -440,20 +440,20 @@ static int config_delete(git_config_file *cfg, const char *name) if (normalize_name(name, &key) < 0) return -1; - pos = git_khash_str_lookup_index(b->values, key); + pos = git_strmap_lookup_index(b->values, key); git__free(key); - if (!git_khash_str_valid_index(b->values, pos)) + if (!git_strmap_valid_index(b->values, pos)) return GIT_ENOTFOUND; - var = git_khash_str_value_at(b->values, pos); + var = git_strmap_value_at(b->values, pos); if (var->next != NULL) { giterr_set(GITERR_CONFIG, "Cannot delete multivar with a single delete"); return -1; } - git_khash_str_delete_at(b->values, pos); + git_strmap_delete_at(b->values, pos); result = config_write(b, var->key, NULL, NULL); @@ -914,14 +914,14 @@ static int config_parse(diskfile_backend *cfg_file) var->value = var_value; /* Add or append the new config option */ - pos = git_khash_str_lookup_index(cfg_file->values, var->key); - if (!git_khash_str_valid_index(cfg_file->values, pos)) { - git_khash_str_insert(cfg_file->values, var->key, var, result); + pos = git_strmap_lookup_index(cfg_file->values, var->key); + if (!git_strmap_valid_index(cfg_file->values, pos)) { + git_strmap_insert(cfg_file->values, var->key, var, result); if (result < 0) break; result = 0; } else { - existing = git_khash_str_value_at(cfg_file->values, pos); + existing = git_strmap_value_at(cfg_file->values, pos); while (existing->next != NULL) { existing = existing->next; } diff --git a/src/hashtable.c b/src/hashtable.c deleted file mode 100644 index e2f131cf1..000000000 --- a/src/hashtable.c +++ /dev/null @@ -1,328 +0,0 @@ -/* - * Copyright (C) 2009-2012 the libgit2 contributors - * - * This file is part of libgit2, distributed under the GNU GPL v2 with - * a Linking Exception. For full terms see the included COPYING file. - */ - -#include "common.h" -#include "repository.h" -#include "commit.h" - -#define MAX_LOOPS 5 -static const double max_load_factor = 0.65; - -static int resize_to(git_hashtable *self, size_t new_size); -static int set_size(git_hashtable *self, size_t new_size); -static git_hashtable_node *node_with_hash(git_hashtable *self, const void *key, int hash_id); -static void node_swap_with(git_hashtable_node *self, git_hashtable_node *other); -static int node_insert(git_hashtable *self, git_hashtable_node *new_node); -static int insert_nodes(git_hashtable *self, git_hashtable_node *old_nodes, size_t old_size); -static void reinsert_stash(git_hashtable *self); - -static int resize_to(git_hashtable *self, size_t new_size) -{ - git_hashtable_node *old_nodes = self->nodes; - size_t old_size = self->size; - git_hashtable_node old_stash[GIT_HASHTABLE_STASH_SIZE]; - size_t old_stash_count = self->stash_count; - - self->is_resizing = 1; - - if (old_stash_count > 0) - memcpy(old_stash, self->stash, - old_stash_count * sizeof(git_hashtable_node)); - - do { - self->size = new_size; - self->size_mask = new_size - 1; - self->key_count = 0; - self->stash_count = 0; - self->nodes = git__calloc(1, sizeof(git_hashtable_node) * self->size); - GITERR_CHECK_ALLOC(self->nodes); - - if (insert_nodes(self, old_nodes, old_size) == 0 && - insert_nodes(self, old_stash, old_stash_count) == 0) - self->is_resizing = 0; - else { - new_size *= 2; - git__free(self->nodes); - } - } while (self->is_resizing); - - git__free(old_nodes); - return 0; -} - -static int set_size(git_hashtable *self, size_t new_size) -{ - self->nodes = - git__realloc(self->nodes, new_size * sizeof(git_hashtable_node)); - GITERR_CHECK_ALLOC(self->nodes); - - if (new_size > self->size) - memset(&self->nodes[self->size], 0x0, - (new_size - self->size) * sizeof(git_hashtable_node)); - - self->size = new_size; - self->size_mask = new_size - 1; - return 0; -} - -GIT_INLINE(git_hashtable_node *)node_with_hash( - git_hashtable *self, const void *key, int hash_id) -{ - size_t pos = self->hash(key, hash_id) & self->size_mask; - return git_hashtable_node_at(self->nodes, pos); -} - -GIT_INLINE(void) node_swap_with( - git_hashtable_node *self, git_hashtable_node *other) -{ - git_hashtable_node tmp = *self; - *self = *other; - *other = tmp; -} - -static int node_insert(git_hashtable *self, git_hashtable_node *new_node) -{ - int iteration, hash_id; - git_hashtable_node *node; - - for (iteration = 0; iteration < MAX_LOOPS; iteration++) { - for (hash_id = 0; hash_id < GIT_HASHTABLE_HASHES; ++hash_id) { - node = node_with_hash(self, new_node->key, hash_id); - node_swap_with(new_node, node); - if (new_node->key == 0x0) { - self->key_count++; - return 0; - } - } - } - - /* Insert into stash if there is space */ - if (self->stash_count < GIT_HASHTABLE_STASH_SIZE) { - node_swap_with(new_node, &self->stash[self->stash_count++]); - self->key_count++; - return 0; - } - - /* Failed to insert node. Hashtable is currently resizing */ - assert(!self->is_resizing); - - if (resize_to(self, self->size * 2) < 0) - return -1; - - return git_hashtable_insert(self, new_node->key, new_node->value); -} - -static int insert_nodes( - git_hashtable *self, git_hashtable_node *old_nodes, size_t old_size) -{ - size_t i; - - for (i = 0; i < old_size; ++i) { - git_hashtable_node *node = git_hashtable_node_at(old_nodes, i); - if (node->key && node_insert(self, node) < 0) - return -1; - } - - return 0; -} - -static void reinsert_stash(git_hashtable *self) -{ - int stash_count; - struct git_hashtable_node stash[GIT_HASHTABLE_STASH_SIZE]; - - if (self->stash_count <= 0) - return; - - memcpy(stash, self->stash, self->stash_count * sizeof(git_hashtable_node)); - stash_count = self->stash_count; - self->stash_count = 0; - - /* the node_insert() calls *cannot* fail because the stash is empty */ - insert_nodes(self, stash, stash_count); -} - -git_hashtable *git_hashtable_alloc( - size_t min_size, - git_hash_ptr hash, - git_hash_keyeq_ptr key_eq) -{ - git_hashtable *table; - - assert(hash && key_eq); - - if ((table = git__malloc(sizeof(*table))) == NULL) - return NULL; - - memset(table, 0x0, sizeof(git_hashtable)); - - table->hash = hash; - table->key_equal = key_eq; - - min_size = git__size_t_powerof2(min_size < 8 ? 8 : min_size); - set_size(table, min_size); - - return table; -} - -void git_hashtable_clear(git_hashtable *self) -{ - assert(self); - - memset(self->nodes, 0x0, sizeof(git_hashtable_node) * self->size); - - self->stash_count = 0; - self->key_count = 0; -} - -void git_hashtable_free(git_hashtable *self) -{ - assert(self); - - git__free(self->nodes); - git__free(self); -} - - -int git_hashtable_insert2( - git_hashtable *self, const void *key, void *value, void **old_value) -{ - int hash_id; - git_hashtable_node *node; - - assert(self && self->nodes); - - *old_value = NULL; - - for (hash_id = 0; hash_id < GIT_HASHTABLE_HASHES; ++hash_id) { - node = node_with_hash(self, key, hash_id); - - if (!node->key) { - node->key = key; - node->value = value; - self->key_count++; - return 0; - } - - if (key == node->key || self->key_equal(key, node->key) == 0) { - *old_value = node->value; - node->key = key; - node->value = value; - return 0; - } - } - - /* no space in table; must do cuckoo dance */ - { - git_hashtable_node x; - x.key = key; - x.value = value; - return node_insert(self, &x); - } -} - -static git_hashtable_node *find_node(git_hashtable *self, const void *key) -{ - int hash_id, count = 0; - git_hashtable_node *node; - - for (hash_id = 0; hash_id < GIT_HASHTABLE_HASHES; ++hash_id) { - node = node_with_hash(self, key, hash_id); - if (node->key) { - ++count; - if (self->key_equal(key, node->key) == 0) - return node; - } - } - - /* check stash if not found but all slots were filled */ - if (count == GIT_HASHTABLE_HASHES) { - for (count = 0; count < self->stash_count; ++count) - if (self->key_equal(key, self->stash[count].key) == 0) - return &self->stash[count]; - } - - return NULL; -} - -static void reset_stash(git_hashtable *self, git_hashtable_node *node) -{ - /* if node was in stash, then compact stash */ - ssize_t offset = node - self->stash; - - if (offset >= 0 && offset < self->stash_count) { - if (offset < self->stash_count - 1) - memmove(node, node + 1, (self->stash_count - offset) * - sizeof(git_hashtable_node)); - self->stash_count--; - } - - reinsert_stash(self); -} - -void *git_hashtable_lookup(git_hashtable *self, const void *key) -{ - git_hashtable_node *node; - assert(self && key); - node = find_node(self, key); - return node ? node->value : NULL; -} - -int git_hashtable_remove2( - git_hashtable *self, const void *key, void **old_value) -{ - git_hashtable_node *node; - - assert(self && self->nodes); - - node = find_node(self, key); - if (node) { - *old_value = node->value; - - node->key = NULL; - node->value = NULL; - self->key_count--; - - reset_stash(self, node); - return 0; - } - - return GIT_ENOTFOUND; -} - -int git_hashtable_merge(git_hashtable *self, git_hashtable *other) -{ - size_t new_size = git__size_t_powerof2(self->size + other->size); - - if (resize_to(self, new_size) < 0) - return -1; - - if (insert_nodes(self, other->nodes, other->key_count) < 0) - return -1; - - return insert_nodes(self, other->stash, other->stash_count); -} - - -/** - * Standard string - */ -uint32_t git_hash__strhash_cb(const void *key, int hash_id) -{ - static uint32_t hash_seeds[GIT_HASHTABLE_HASHES] = { - 2147483647, - 0x5d20bb23, - 0x7daaab3c - }; - - size_t key_len = strlen((const char *)key); - - /* won't take hash of strings longer than 2^31 right now */ - assert(key_len == (size_t)((int)key_len)); - - return git__hash(key, (int)key_len, hash_seeds[hash_id]); -} diff --git a/src/hashtable.h b/src/hashtable.h deleted file mode 100644 index 448487507..000000000 --- a/src/hashtable.h +++ /dev/null @@ -1,102 +0,0 @@ -/* - * Copyright (C) 2009-2012 the libgit2 contributors - * - * This file is part of libgit2, distributed under the GNU GPL v2 with - * a Linking Exception. For full terms see the included COPYING file. - */ -#ifndef INCLUDE_hashtable_h__ -#define INCLUDE_hashtable_h__ - -#include "git2/common.h" -#include "git2/oid.h" -#include "git2/odb.h" -#include "common.h" - -#define GIT_HASHTABLE_HASHES 3 - -typedef uint32_t (*git_hash_ptr)(const void *, int hash_id); -typedef int (*git_hash_keyeq_ptr)(const void *key_a, const void *key_b); - -struct git_hashtable_node { - const void *key; - void *value; -}; - -#define GIT_HASHTABLE_STASH_SIZE 3 - -struct git_hashtable { - struct git_hashtable_node *nodes; - - size_t size_mask; - size_t size; - size_t key_count; - - struct git_hashtable_node stash[GIT_HASHTABLE_STASH_SIZE]; - int stash_count; - - int is_resizing; - - git_hash_ptr hash; - git_hash_keyeq_ptr key_equal; -}; - -typedef struct git_hashtable_node git_hashtable_node; -typedef struct git_hashtable git_hashtable; - -git_hashtable *git_hashtable_alloc( - size_t min_size, - git_hash_ptr hash, - git_hash_keyeq_ptr key_eq); - -void *git_hashtable_lookup(git_hashtable *h, const void *key); -int git_hashtable_remove2(git_hashtable *table, const void *key, void **old_value); - -GIT_INLINE(int) git_hashtable_remove(git_hashtable *table, const void *key) -{ - void *_unused; - return git_hashtable_remove2(table, key, &_unused); -} - - -void git_hashtable_free(git_hashtable *h); -void git_hashtable_clear(git_hashtable *h); -int git_hashtable_merge(git_hashtable *self, git_hashtable *other); - -int git_hashtable_insert2(git_hashtable *h, const void *key, void *value, void **old_value); - -GIT_INLINE(int) git_hashtable_insert(git_hashtable *h, const void *key, void *value) -{ - void *_unused; - return git_hashtable_insert2(h, key, value, &_unused); -} - -#define git_hashtable_node_at(nodes, pos) ((git_hashtable_node *)(&nodes[pos])) - -#define GIT_HASHTABLE__FOREACH(self,block) { \ - size_t _c; \ - git_hashtable_node *_n = (self)->nodes; \ - for (_c = (self)->size; _c > 0; _c--, _n++) { \ - if (!_n->key) continue; block } } - -#define GIT_HASHTABLE_FOREACH(self, pkey, pvalue, code)\ - GIT_HASHTABLE__FOREACH(self,{(pkey)=_n->key;(pvalue)=_n->value;code;}) - -#define GIT_HASHTABLE_FOREACH_KEY(self, pkey, code)\ - GIT_HASHTABLE__FOREACH(self,{(pkey)=_n->key;code;}) - -#define GIT_HASHTABLE_FOREACH_VALUE(self, pvalue, code)\ - GIT_HASHTABLE__FOREACH(self,{(pvalue)=_n->value;code;}) - -#define GIT_HASHTABLE_FOREACH_DELETE() {\ - _node->key = NULL; _node->value = NULL; _self->key_count--;\ -} - -/* - * If you want a hashtable with standard string keys, you can - * just pass git_hash__strcmp_cb and git_hash__strhash_cb to - * git_hashtable_alloc. - */ -#define git_hash__strcmp_cb git__strcmp_cb -extern uint32_t git_hash__strhash_cb(const void *key, int hash_id); - -#endif diff --git a/src/khash_str.h b/src/khash_str.h deleted file mode 100644 index 0b840d836..000000000 --- a/src/khash_str.h +++ /dev/null @@ -1,54 +0,0 @@ -/* - * Copyright (C) 2012 the libgit2 contributors - * - * This file is part of libgit2, distributed under the GNU GPL v2 with - * a Linking Exception. For full terms see the included COPYING file. - */ -#ifndef INCLUDE_khash_str_h__ -#define INCLUDE_khash_str_h__ - -#include "common.h" - -#define kmalloc git__malloc -#define kcalloc git__calloc -#define krealloc git__realloc -#define kfree git__free -#include "khash.h" - -__KHASH_TYPE(str, const char *, void *); -typedef khash_t(str) git_khash_str; - -#define GIT_KHASH_STR__IMPLEMENTATION \ - __KHASH_IMPL(str, static inline, const char *, void *, 1, kh_str_hash_func, kh_str_hash_equal) - -#define git_khash_str_alloc() kh_init(str) -#define git_khash_str_free(h) kh_destroy(str, h), h = NULL -#define git_khash_str_clear(h) kh_clear(str, h) - -#define git_khash_str_num_entries(h) kh_size(h) - -#define git_khash_str_lookup_index(h, k) kh_get(str, h, k) -#define git_khash_str_valid_index(h, idx) (idx != kh_end(h)) - -#define git_khash_str_exists(h, k) (kh_get(str, h, k) != kh_end(h)) - -#define git_khash_str_value_at(h, idx) kh_val(h, idx) -#define git_khash_str_set_value_at(h, idx, v) kh_val(h, idx) = v -#define git_khash_str_delete_at(h, idx) kh_del(str, h, idx) - -#define git_khash_str_insert(h, key, val, err) do { \ - khiter_t __pos = kh_put(str, h, key, &err); \ - if (err >= 0) kh_val(h, __pos) = val; \ - } while (0) - -#define git_khash_str_insert2(h, key, val, old, err) do { \ - khiter_t __pos = kh_put(str, h, key, &err); \ - if (err >= 0) { \ - old = (err == 0) ? kh_val(h, __pos) : NULL; \ - kh_val(h, __pos) = val; \ - } } while (0) - -#define git_khash_str_foreach kh_foreach -#define git_khash_str_foreach_value kh_foreach_value - -#endif diff --git a/src/khash_oid.h b/src/oidmap.h index 96d82c759..858268c92 100644 --- a/src/khash_oid.h +++ b/src/oidmap.h @@ -4,8 +4,8 @@ * This file is part of libgit2, distributed under the GNU GPL v2 with * a Linking Exception. For full terms see the included COPYING file. */ -#ifndef INCLUDE_khash_oid_h__ -#define INCLUDE_khash_oid_h__ +#ifndef INCLUDE_oidmap_h__ +#define INCLUDE_oidmap_h__ #include "common.h" #include "git2/oid.h" @@ -17,7 +17,7 @@ #include "khash.h" __KHASH_TYPE(oid, const git_oid *, void *); -typedef khash_t(oid) git_khash_oid; +typedef khash_t(oid) git_oidmap; GIT_INLINE(khint_t) hash_git_oid(const git_oid *oid) { @@ -33,10 +33,10 @@ GIT_INLINE(int) hash_git_oid_equal(const git_oid *a, const git_oid *b) return (memcmp(a->id, b->id, sizeof(a->id)) == 0); } -#define GIT_KHASH_OID__IMPLEMENTATION \ +#define GIT__USE_OIDMAP \ __KHASH_IMPL(oid, static inline, const git_oid *, void *, 1, hash_git_oid, hash_git_oid_equal) -#define git_khash_oid_alloc() kh_init(oid) -#define git_khash_oid_free(h) kh_destroy(oid,h), h = NULL +#define git_oidmap_alloc() kh_init(oid) +#define git_oidmap_free(h) kh_destroy(oid,h), h = NULL #endif diff --git a/src/refs.c b/src/refs.c index 7050b4af9..7685d560c 100644 --- a/src/refs.c +++ b/src/refs.c @@ -15,7 +15,7 @@ #include <git2/tag.h> #include <git2/object.h> -GIT_KHASH_STR__IMPLEMENTATION; +GIT__USE_STRMAP; #define DEFAULT_NESTING_LEVEL 5 #define MAX_NESTING_LEVEL 10 @@ -423,7 +423,7 @@ static int packed_load(git_repository *repo) /* First we make sure we have allocated the hash table */ if (ref_cache->packfile == NULL) { - ref_cache->packfile = git_khash_str_alloc(); + ref_cache->packfile = git_strmap_alloc(); GITERR_CHECK_ALLOC(ref_cache->packfile); } @@ -438,7 +438,7 @@ static int packed_load(git_repository *repo) * refresh the packed refs. */ if (result == GIT_ENOTFOUND) { - git_khash_str_clear(ref_cache->packfile); + git_strmap_clear(ref_cache->packfile); return 0; } @@ -452,7 +452,7 @@ static int packed_load(git_repository *repo) * At this point, we want to refresh the packed refs. We already * have the contents in our buffer. */ - git_khash_str_clear(ref_cache->packfile); + git_strmap_clear(ref_cache->packfile); buffer_start = (const char *)packfile.ptr; buffer_end = (const char *)(buffer_start) + packfile.size; @@ -477,7 +477,7 @@ static int packed_load(git_repository *repo) goto parse_failed; } - git_khash_str_insert(ref_cache->packfile, ref->name, ref, err); + git_strmap_insert(ref_cache->packfile, ref->name, ref, err); if (err < 0) goto parse_failed; } @@ -486,7 +486,7 @@ static int packed_load(git_repository *repo) return 0; parse_failed: - git_khash_str_free(ref_cache->packfile); + git_strmap_free(ref_cache->packfile); ref_cache->packfile = NULL; git_buf_free(&packfile); return -1; @@ -512,7 +512,7 @@ static int _dirent_loose_listall(void *_data, git_buf *full_path) /* do not add twice a reference that exists already in the packfile */ if ((data->list_flags & GIT_REF_PACKED) != 0 && - git_khash_str_exists(data->repo->references.packfile, file_path)) + git_strmap_exists(data->repo->references.packfile, file_path)) return 0; if (data->list_flags != GIT_REF_LISTALL) { @@ -539,7 +539,7 @@ static int _dirent_loose_load(void *data, git_buf *full_path) if (loose_lookup_to_packfile(&ref, repository, file_path) < 0) return -1; - git_khash_str_insert2( + git_strmap_insert2( repository->references.packfile, ref->name, ref, old_ref, err); if (err < 0) { git__free(ref); @@ -737,7 +737,7 @@ static int packed_write(git_repository *repo) assert(repo && repo->references.packfile); total_refs = - (unsigned int)git_khash_str_num_entries(repo->references.packfile); + (unsigned int)git_strmap_num_entries(repo->references.packfile); if (git_vector_init(&packing_list, total_refs, packed_sort) < 0) return -1; @@ -747,7 +747,7 @@ static int packed_write(git_repository *repo) struct packref *reference; /* cannot fail: vector already has the right size */ - git_khash_str_foreach_value(repo->references.packfile, reference, { + git_strmap_foreach_value(repo->references.packfile, reference, { git_vector_insert(&packing_list, reference); }); } @@ -873,7 +873,7 @@ static int reference_exists(int *exists, git_repository *repo, const char *ref_n return -1; if (git_path_isfile(ref_path.ptr) == true || - git_khash_str_exists(repo->references.packfile, ref_path.ptr)) + git_strmap_exists(repo->references.packfile, ref_path.ptr)) { *exists = 1; } else { @@ -940,7 +940,7 @@ static int reference_can_write( static int packed_lookup(git_reference *ref) { struct packref *pack_ref = NULL; - git_khash_str *packfile_refs; + git_strmap *packfile_refs; khiter_t pos; if (packed_load(ref->owner) < 0) @@ -959,13 +959,13 @@ static int packed_lookup(git_reference *ref) /* Look up on the packfile */ packfile_refs = ref->owner->references.packfile; - pos = git_khash_str_lookup_index(packfile_refs, ref->name); - if (!git_khash_str_valid_index(packfile_refs, pos)) { + pos = git_strmap_lookup_index(packfile_refs, ref->name); + if (!git_strmap_valid_index(packfile_refs, pos)) { giterr_set(GITERR_REFERENCE, "Reference '%s' not found", ref->name); return GIT_ENOTFOUND; } - pack_ref = git_khash_str_value_at(packfile_refs, pos); + pack_ref = git_strmap_value_at(packfile_refs, pos); ref->flags = GIT_REF_OID | GIT_REF_PACKED; ref->mtime = ref->owner->references.packfile_time; @@ -1011,7 +1011,7 @@ static int reference_delete(git_reference *ref) * We need to reload the packfile, remove the reference from the * packing list, and repack */ if (ref->flags & GIT_REF_PACKED) { - git_khash_str *packfile_refs; + git_strmap *packfile_refs; struct packref *packref; khiter_t pos; @@ -1020,15 +1020,15 @@ static int reference_delete(git_reference *ref) return -1; packfile_refs = ref->owner->references.packfile; - pos = git_khash_str_lookup_index(packfile_refs, ref->name); - if (!git_khash_str_valid_index(packfile_refs, pos)) { + pos = git_strmap_lookup_index(packfile_refs, ref->name); + if (!git_strmap_valid_index(packfile_refs, pos)) { giterr_set(GITERR_REFERENCE, "Reference %s stopped existing in the packfile", ref->name); return -1; } - packref = git_khash_str_value_at(packfile_refs, pos); - git_khash_str_delete_at(packfile_refs, pos); + packref = git_strmap_value_at(packfile_refs, pos); + git_strmap_delete_at(packfile_refs, pos); git__free(packref); if (packed_write(ref->owner) < 0) @@ -1488,7 +1488,7 @@ int git_reference_foreach( if (packed_load(repo) < 0) return -1; - git_khash_str_foreach(repo->references.packfile, ref_name, ref, { + git_strmap_foreach(repo->references.packfile, ref_name, ref, { if (callback(ref_name, payload) < 0) return 0; }); @@ -1555,11 +1555,11 @@ void git_repository__refcache_free(git_refcache *refs) if (refs->packfile) { struct packref *reference; - git_khash_str_foreach_value(refs->packfile, reference, { + git_strmap_foreach_value(refs->packfile, reference, { git__free(reference); }); - git_khash_str_free(refs->packfile); + git_strmap_free(refs->packfile); } } diff --git a/src/refs.h b/src/refs.h index 39648e6d9..369e91e1c 100644 --- a/src/refs.h +++ b/src/refs.h @@ -10,7 +10,7 @@ #include "common.h" #include "git2/oid.h" #include "git2/refs.h" -#include "khash_str.h" +#include "strmap.h" #define GIT_REFS_DIR "refs/" #define GIT_REFS_HEADS_DIR GIT_REFS_DIR "heads/" @@ -46,7 +46,7 @@ struct git_reference { }; typedef struct { - git_khash_str *packfile; + git_strmap *packfile; time_t packfile_time; } git_refcache; diff --git a/src/repository.h b/src/repository.h index f53fa697e..1ffac58f1 100644 --- a/src/repository.h +++ b/src/repository.h @@ -19,7 +19,7 @@ #include "buffer.h" #include "odb.h" #include "attr.h" -#include "khash_str.h" +#include "strmap.h" #define DOT_GIT ".git" #define GIT_DIR DOT_GIT "/" @@ -83,7 +83,7 @@ struct git_repository { git_cache objects; git_refcache references; git_attr_cache attrcache; - git_khash_str *submodules; + git_strmap *submodules; char *path_repository; char *workdir; diff --git a/src/revwalk.c b/src/revwalk.c index 5867e133e..1cfff3674 100644 --- a/src/revwalk.c +++ b/src/revwalk.c @@ -10,14 +10,14 @@ #include "odb.h" #include "pqueue.h" #include "pool.h" -#include "khash_oid.h" +#include "oidmap.h" #include "git2/revwalk.h" #include "git2/merge.h" #include <regex.h> -GIT_KHASH_OID__IMPLEMENTATION; +GIT__USE_OIDMAP; #define PARENT1 (1 << 0) #define PARENT2 (1 << 1) @@ -48,7 +48,7 @@ struct git_revwalk { git_repository *repo; git_odb *odb; - git_khash_oid *commits; + git_oidmap *commits; git_pool commit_pool; commit_list *iterator_topo; @@ -726,7 +726,7 @@ int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo) memset(walk, 0x0, sizeof(git_revwalk)); - walk->commits = git_khash_oid_alloc(); + walk->commits = git_oidmap_alloc(); GITERR_CHECK_ALLOC(walk->commits); if (git_pqueue_init(&walk->iterator_time, 8, commit_time_cmp) < 0 || @@ -757,7 +757,7 @@ void git_revwalk_free(git_revwalk *walk) git_revwalk_reset(walk); git_odb_free(walk->odb); - git_khash_oid_free(walk->commits); + git_oidmap_free(walk->commits); git_pool_clear(&walk->commit_pool); git_pqueue_free(&walk->iterator_time); git_vector_free(&walk->twos); diff --git a/src/strmap.h b/src/strmap.h new file mode 100644 index 000000000..55fbd7c6e --- /dev/null +++ b/src/strmap.h @@ -0,0 +1,54 @@ +/* + * Copyright (C) 2012 the libgit2 contributors + * + * This file is part of libgit2, distributed under the GNU GPL v2 with + * a Linking Exception. For full terms see the included COPYING file. + */ +#ifndef INCLUDE_strmap_h__ +#define INCLUDE_strmap_h__ + +#include "common.h" + +#define kmalloc git__malloc +#define kcalloc git__calloc +#define krealloc git__realloc +#define kfree git__free +#include "khash.h" + +__KHASH_TYPE(str, const char *, void *); +typedef khash_t(str) git_strmap; + +#define GIT__USE_STRMAP \ + __KHASH_IMPL(str, static inline, const char *, void *, 1, kh_str_hash_func, kh_str_hash_equal) + +#define git_strmap_alloc() kh_init(str) +#define git_strmap_free(h) kh_destroy(str, h), h = NULL +#define git_strmap_clear(h) kh_clear(str, h) + +#define git_strmap_num_entries(h) kh_size(h) + +#define git_strmap_lookup_index(h, k) kh_get(str, h, k) +#define git_strmap_valid_index(h, idx) (idx != kh_end(h)) + +#define git_strmap_exists(h, k) (kh_get(str, h, k) != kh_end(h)) + +#define git_strmap_value_at(h, idx) kh_val(h, idx) +#define git_strmap_set_value_at(h, idx, v) kh_val(h, idx) = v +#define git_strmap_delete_at(h, idx) kh_del(str, h, idx) + +#define git_strmap_insert(h, key, val, err) do { \ + khiter_t __pos = kh_put(str, h, key, &err); \ + if (err >= 0) kh_val(h, __pos) = val; \ + } while (0) + +#define git_strmap_insert2(h, key, val, old, err) do { \ + khiter_t __pos = kh_put(str, h, key, &err); \ + if (err >= 0) { \ + old = (err == 0) ? kh_val(h, __pos) : NULL; \ + kh_val(h, __pos) = val; \ + } } while (0) + +#define git_strmap_foreach kh_foreach +#define git_strmap_foreach_value kh_foreach_value + +#endif diff --git a/src/submodule.c b/src/submodule.c index 8072053af..1b5b59f45 100644 --- a/src/submodule.c +++ b/src/submodule.c @@ -89,17 +89,17 @@ static void submodule_release(git_submodule *sm, int decr) } static int submodule_from_entry( - git_khash_str *smcfg, git_index_entry *entry) + git_strmap *smcfg, git_index_entry *entry) { git_submodule *sm; void *old_sm; khiter_t pos; int error; - pos = git_khash_str_lookup_index(smcfg, entry->path); + pos = git_strmap_lookup_index(smcfg, entry->path); - if (git_khash_str_valid_index(smcfg, pos)) - sm = git_khash_str_value_at(smcfg, pos); + if (git_strmap_valid_index(smcfg, pos)) + sm = git_strmap_value_at(smcfg, pos); else sm = submodule_alloc(entry->path); @@ -115,7 +115,7 @@ static int submodule_from_entry( goto fail; } - git_khash_str_insert2(smcfg, sm->path, sm, old_sm, error); + git_strmap_insert2(smcfg, sm->path, sm, old_sm, error); if (error < 0) goto fail; sm->refcount++; @@ -135,7 +135,7 @@ fail: static int submodule_from_config( const char *key, const char *value, void *data) { - git_khash_str *smcfg = data; + git_strmap *smcfg = data; const char *namestart; const char *property; git_buf name = GIT_BUF_INIT; @@ -158,13 +158,13 @@ static int submodule_from_config( if (git_buf_set(&name, namestart, property - namestart - 1) < 0) return -1; - pos = git_khash_str_lookup_index(smcfg, name.ptr); - if (!git_khash_str_valid_index(smcfg, pos) && is_path) - pos = git_khash_str_lookup_index(smcfg, value); - if (!git_khash_str_valid_index(smcfg, pos)) + pos = git_strmap_lookup_index(smcfg, name.ptr); + if (!git_strmap_valid_index(smcfg, pos) && is_path) + pos = git_strmap_lookup_index(smcfg, value); + if (!git_strmap_valid_index(smcfg, pos)) sm = submodule_alloc(name.ptr); else - sm = git_khash_str_value_at(smcfg, pos); + sm = git_strmap_value_at(smcfg, pos); if (!sm) goto fail; @@ -172,7 +172,7 @@ static int submodule_from_config( assert(sm->path == sm->name); sm->name = git_buf_detach(&name); - git_khash_str_insert2(smcfg, sm->name, sm, old_sm, error); + git_strmap_insert2(smcfg, sm->name, sm, old_sm, error); if (error < 0) goto fail; sm->refcount++; @@ -183,7 +183,7 @@ static int submodule_from_config( if (sm->path == NULL) goto fail; - git_khash_str_insert2(smcfg, sm->path, sm, old_sm, error); + git_strmap_insert2(smcfg, sm->path, sm, old_sm, error); if (error < 0) goto fail; sm->refcount++; @@ -247,7 +247,7 @@ static int load_submodule_config(git_repository *repo) git_index *index; unsigned int i, max_i; git_oid gitmodules_oid; - git_khash_str *smcfg; + git_strmap *smcfg; struct git_config_file *mods = NULL; if (repo->submodules) @@ -257,7 +257,7 @@ static int load_submodule_config(git_repository *repo) * under both its name and its path. These are usually the same, but * that is not guaranteed. */ - smcfg = git_khash_str_alloc(); + smcfg = git_strmap_alloc(); GITERR_CHECK_ALLOC(smcfg); /* scan index for gitmodules (and .gitmodules entry) */ @@ -307,13 +307,13 @@ cleanup: if (mods != NULL) git_config_file_free(mods); if (error) - git_khash_str_free(smcfg); + git_strmap_free(smcfg); return error; } void git_submodule_config_free(git_repository *repo) { - git_khash_str *smcfg = repo->submodules; + git_strmap *smcfg = repo->submodules; git_submodule *sm; repo->submodules = NULL; @@ -321,10 +321,10 @@ void git_submodule_config_free(git_repository *repo) if (smcfg == NULL) return; - git_khash_str_foreach_value(smcfg, sm, { + git_strmap_foreach_value(smcfg, sm, { submodule_release(sm,1); }); - git_khash_str_free(smcfg); + git_strmap_free(smcfg); } static int submodule_cmp(const void *a, const void *b) @@ -345,7 +345,7 @@ int git_submodule_foreach( if ((error = load_submodule_config(repo)) < 0) return error; - git_khash_str_foreach_value(repo->submodules, sm, { + git_strmap_foreach_value(repo->submodules, sm, { /* usually the following will not come into play */ if (sm->refcount > 1) { if (git_vector_bsearch(&seen, sm) != GIT_ENOTFOUND) @@ -373,12 +373,12 @@ int git_submodule_lookup( if (load_submodule_config(repo) < 0) return -1; - pos = git_khash_str_lookup_index(repo->submodules, name); - if (!git_khash_str_valid_index(repo->submodules, pos)) + pos = git_strmap_lookup_index(repo->submodules, name); + if (!git_strmap_valid_index(repo->submodules, pos)) return GIT_ENOTFOUND; if (sm_ptr) - *sm_ptr = git_khash_str_value_at(repo->submodules, pos); + *sm_ptr = git_strmap_value_at(repo->submodules, pos); return 0; } diff --git a/tests-clar/core/strmap.c b/tests-clar/core/strmap.c new file mode 100644 index 000000000..f34a4f89f --- /dev/null +++ b/tests-clar/core/strmap.c @@ -0,0 +1,102 @@ +#include "clar_libgit2.h" +#include "strmap.h" + +GIT__USE_STRMAP; + +void test_core_strmap__0(void) +{ + git_strmap *table = git_strmap_alloc(); + cl_assert(table != NULL); + cl_assert(git_strmap_num_entries(table) == 0); + git_strmap_free(table); +} + +static void insert_strings(git_strmap *table, int count) +{ + int i, j, over, err; + char *str; + + for (i = 0; i < count; ++i) { + str = malloc(10); + for (j = 0; j < 10; ++j) + str[j] = 'a' + (i % 26); + str[9] = '\0'; + + /* if > 26, then encode larger value in first letters */ + for (j = 0, over = i / 26; over > 0; j++, over = over / 26) + str[j] = 'A' + (over % 26); + + git_strmap_insert(table, str, str, err); + cl_assert(err >= 0); + } + + cl_assert((int)git_strmap_num_entries(table) == count); +} + +void test_core_strmap__1(void) +{ + int i; + char *str; + git_strmap *table = git_strmap_alloc(); + cl_assert(table != NULL); + + insert_strings(table, 20); + + cl_assert(git_strmap_exists(table, "aaaaaaaaa")); + cl_assert(git_strmap_exists(table, "ggggggggg")); + cl_assert(!git_strmap_exists(table, "aaaaaaaab")); + cl_assert(!git_strmap_exists(table, "abcdefghi")); + + i = 0; + git_strmap_foreach_value(table, str, { i++; free(str); }); + cl_assert(i == 20); + + git_strmap_free(table); +} + +void test_core_strmap__2(void) +{ + khiter_t pos; + int i; + char *str; + git_strmap *table = git_strmap_alloc(); + cl_assert(table != NULL); + + insert_strings(table, 20); + + cl_assert(git_strmap_exists(table, "aaaaaaaaa")); + cl_assert(git_strmap_exists(table, "ggggggggg")); + cl_assert(!git_strmap_exists(table, "aaaaaaaab")); + cl_assert(!git_strmap_exists(table, "abcdefghi")); + + cl_assert(git_strmap_exists(table, "bbbbbbbbb")); + pos = git_strmap_lookup_index(table, "bbbbbbbbb"); + cl_assert(git_strmap_valid_index(table, pos)); + cl_assert_equal_s(git_strmap_value_at(table, pos), "bbbbbbbbb"); + free(git_strmap_value_at(table, pos)); + git_strmap_delete_at(table, pos); + + cl_assert(!git_strmap_exists(table, "bbbbbbbbb")); + + i = 0; + git_strmap_foreach_value(table, str, { i++; free(str); }); + cl_assert(i == 19); + + git_strmap_free(table); +} + +void test_core_strmap__3(void) +{ + int i; + char *str; + git_strmap *table = git_strmap_alloc(); + cl_assert(table != NULL); + + insert_strings(table, 10000); + + i = 0; + git_strmap_foreach_value(table, str, { i++; free(str); }); + cl_assert(i == 10000); + + git_strmap_free(table); +} diff --git a/tests/t07-hashtable.c b/tests/t07-hashtable.c deleted file mode 100644 index 4d45c7fc1..000000000 --- a/tests/t07-hashtable.c +++ /dev/null @@ -1,189 +0,0 @@ -/* - * This file is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License, version 2, - * as published by the Free Software Foundation. - * - * In addition to the permissions in the GNU General Public License, - * the authors give you unlimited permission to link the compiled - * version of this file into combinations with other programs, - * and to distribute those combinations without any restriction - * coming from the use of this file. (The General Public License - * restrictions do apply in other respects; for example, they cover - * modification of the file, and distribution when not linked into - * a combined executable.) - * - * This file is distributed in the hope that it will be useful, but - * WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; see the file COPYING. If not, write to - * the Free Software Foundation, 51 Franklin Street, Fifth Floor, - * Boston, MA 02110-1301, USA. - */ -#include "test_lib.h" -#include "test_helpers.h" - -#include "hashtable.h" -#include "hash.h" - -typedef struct _aux_object { - int __bulk; - git_oid id; - int visited; -} table_item; - -static uint32_t hash_func(const void *key, int hash_id) -{ - uint32_t r; - const git_oid *id = key; - - memcpy(&r, id->id + (hash_id * sizeof(uint32_t)), sizeof(r)); - return r; -} - -static int hash_cmpkey(const void *a, const void *b) -{ - return git_oid_cmp(a, b); -} - -BEGIN_TEST(table0, "create a new hashtable") - - git_hashtable *table = NULL; - - table = git_hashtable_alloc(55, hash_func, hash_cmpkey); - must_be_true(table != NULL); - must_be_true(table->size_mask + 1 == 64); - - git_hashtable_free(table); - -END_TEST - -BEGIN_TEST(table1, "fill the hashtable with random entries") - - const int objects_n = 32; - int i; - - table_item *objects; - git_hashtable *table = NULL; - - table = git_hashtable_alloc(objects_n * 2, hash_func, hash_cmpkey); - must_be_true(table != NULL); - - objects = git__malloc(objects_n * sizeof(table_item)); - memset(objects, 0x0, objects_n * sizeof(table_item)); - - /* populate the hash table */ - for (i = 0; i < objects_n; ++i) { - git_hash_buf(&(objects[i].id), &i, sizeof(int)); - must_pass(git_hashtable_insert(table, &(objects[i].id), &(objects[i]))); - } - - /* make sure all the inserted objects can be found */ - for (i = 0; i < objects_n; ++i) { - git_oid id; - table_item *ob; - - git_hash_buf(&id, &i, sizeof(int)); - ob = (table_item *)git_hashtable_lookup(table, &id); - - must_be_true(ob != NULL); - must_be_true(ob == &(objects[i])); - } - - /* make sure we cannot find inexisting objects */ - for (i = 0; i < 50; ++i) { - int hash_id; - git_oid id; - - hash_id = (rand() % 50000) + objects_n; - git_hash_buf(&id, &hash_id, sizeof(int)); - must_be_true(git_hashtable_lookup(table, &id) == NULL); - } - - git_hashtable_free(table); - git__free(objects); - -END_TEST - - -BEGIN_TEST(table2, "make sure the table resizes automatically") - - const int objects_n = 64; - int i; - size_t old_size; - table_item *objects; - git_hashtable *table = NULL; - - table = git_hashtable_alloc(objects_n, hash_func, hash_cmpkey); - must_be_true(table != NULL); - - objects = git__malloc(objects_n * sizeof(table_item)); - memset(objects, 0x0, objects_n * sizeof(table_item)); - - old_size = table->size_mask + 1; - - /* populate the hash table -- should be automatically resized */ - for (i = 0; i < objects_n; ++i) { - git_hash_buf(&(objects[i].id), &i, sizeof(int)); - must_pass(git_hashtable_insert(table, &(objects[i].id), &(objects[i]))); - } - - must_be_true(table->size_mask > old_size); - - /* make sure all the inserted objects can be found */ - for (i = 0; i < objects_n; ++i) { - git_oid id; - table_item *ob; - - git_hash_buf(&id, &i, sizeof(int)); - ob = (table_item *)git_hashtable_lookup(table, &id); - - must_be_true(ob != NULL); - must_be_true(ob == &(objects[i])); - } - - git_hashtable_free(table); - git__free(objects); - -END_TEST - -BEGIN_TEST(tableit0, "iterate through all the contents of the table") - - const int objects_n = 32; - int i; - table_item *objects, *ob; - - git_hashtable *table = NULL; - - table = git_hashtable_alloc(objects_n * 2, hash_func, hash_cmpkey); - must_be_true(table != NULL); - - objects = git__malloc(objects_n * sizeof(table_item)); - memset(objects, 0x0, objects_n * sizeof(table_item)); - - /* populate the hash table */ - for (i = 0; i < objects_n; ++i) { - git_hash_buf(&(objects[i].id), &i, sizeof(int)); - must_pass(git_hashtable_insert(table, &(objects[i].id), &(objects[i]))); - } - - GIT_HASHTABLE_FOREACH_VALUE(table, ob, ob->visited = 1); - - /* make sure all nodes have been visited */ - for (i = 0; i < objects_n; ++i) - must_be_true(objects[i].visited); - - git_hashtable_free(table); - git__free(objects); -END_TEST - - -BEGIN_SUITE(hashtable) - ADD_TEST(table0); - ADD_TEST(table1); - ADD_TEST(table2); - ADD_TEST(tableit0); -END_SUITE - diff --git a/tests/test_main.c b/tests/test_main.c index 50256e97c..bc07f1ff1 100644 --- a/tests/test_main.c +++ b/tests/test_main.c @@ -37,7 +37,6 @@ DECLARE_SUITE(objwrite); DECLARE_SUITE(commit); DECLARE_SUITE(revwalk); DECLARE_SUITE(index); -DECLARE_SUITE(hashtable); DECLARE_SUITE(tag); DECLARE_SUITE(tree); DECLARE_SUITE(refs); @@ -53,7 +52,6 @@ static libgit2_suite suite_methods[]= { SUITE_NAME(commit), SUITE_NAME(revwalk), SUITE_NAME(index), - SUITE_NAME(hashtable), SUITE_NAME(tag), SUITE_NAME(tree), SUITE_NAME(refs), |