/* * 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 "common.h" #include "repository.h" #include "commit.h" static const int default_table_size = 32; static const double max_load_factor = 0.65; static void hashtable_resize(git_hashtable *table) { git_hashtable_node **new_nodes; unsigned int new_size, i; assert(table); new_size = (table->size_mask + 1) * 2; new_nodes = git__malloc(new_size * sizeof(git_hashtable_node *)); if (new_nodes == NULL) return; memset(new_nodes, 0x0, new_size * sizeof(git_hashtable_node *)); for (i = 0; i <= table->size_mask; ++i) { git_hashtable_node *n; unsigned int index; while ((n = table->nodes[i]) != NULL) { table->nodes[i] = n->next; index = n->hash & (new_size - 1); n->next = new_nodes[index]; new_nodes[index] = n; } } free(table->nodes); table->nodes = new_nodes; table->size_mask = (new_size - 1); table->max_count = (unsigned int)(new_size * max_load_factor); } git_hashtable *git_hashtable_alloc(unsigned int min_size, git_hash_ptr hash, git_hash_keyeq_ptr key_eq) { unsigned int i; git_hashtable *table; assert(hash && key_eq); if ((table = git__malloc(sizeof(git_hashtable))) == NULL) return NULL; /* round up size to closest power of 2 */ min_size--; min_size |= min_size >> 1; min_size |= min_size >> 2; min_size |= min_size >> 4; min_size |= min_size >> 8; min_size |= min_size >> 16; table->size_mask = min_size; table->count = 0; table->max_count = (unsigned int)((min_size + 1) * max_load_factor); table->hash = hash; table->key_equal = key_eq; table->nodes = git__malloc((min_size + 1) * sizeof(git_hashtable_node *)); if (table->nodes == NULL) { free(table); return NULL; } for (i = 0; i <= min_size; ++i) table->nodes[i] = NULL; return table; } void git_hashtable_clear(git_hashtable *table) { unsigned int index; assert(table); for (index = 0; index <= table->size_mask; ++index) { git_hashtable_node *node, *next_node; node = table->nodes[index]; while (node != NULL) { next_node = node->next; free(node); node = next_node; } table->nodes[index] = NULL; } table->count = 0; } void git_hashtable_free(git_hashtable *table) { assert(table); git_hashtable_clear(table); free(table->nodes); free(table); } int git_hashtable_insert(git_hashtable *table, const void *key, void *value) { git_hashtable_node *node; uint32_t index, hash; assert(table); if (table->count + 1 > table->max_count) hashtable_resize(table); node = git__malloc(sizeof(git_hashtable_node)); if (node == NULL) return GIT_ENOMEM; hash = table->hash(key); index = (hash & table->size_mask); node->object = value; node->hash = hash; node->next = table->nodes[index]; table->nodes[index] = node; table->count++; return GIT_SUCCESS; } void *git_hashtable_lookup(git_hashtable *table, const void *key) { git_hashtable_node *node; uint32_t index, hash; assert(table); hash = table->hash(key); index = (hash & table->size_mask); node = table->nodes[index]; while (node != NULL) { if (node->hash == hash && table->key_equal(node->object, key)) return node->object; node = node->next; } return NULL; } int git_hashtable_remove(git_hashtable *table, const void *key) { git_hashtable_node *node, *prev_node; uint32_t index, hash; assert(table); hash = table->hash(key); index = (hash & table->size_mask); node = table->nodes[index]; prev_node = NULL; while (node != NULL) { if (node->hash == hash && table->key_equal(node->object, key)) { if (prev_node == NULL) table->nodes[index] = node->next; else prev_node->next = node->next; free(node); return GIT_SUCCESS; } prev_node = node; node = node->next; } return GIT_ENOTFOUND; } void git_hashtable_iterator_init(git_hashtable *table, git_hashtable_iterator *it) { assert(table && it); memset(it, 0x0, sizeof(git_hashtable_iterator)); it->nodes = table->nodes; it->current_node = NULL; it->current_pos = 0; it->size = table->size_mask + 1; } void *git_hashtable_iterator_next(git_hashtable_iterator *it) { git_hashtable_node *next = NULL; assert(it); while (it->current_node == NULL) { if (it->current_pos >= it->size) return NULL; it->current_node = it->nodes[it->current_pos++]; } next = it->current_node; it->current_node = it->current_node->next; return next->object; }