From e17b0446bd815f7b25f5bf0b838ef3d02d4eb64e Mon Sep 17 00:00:00 2001 From: Allan McRae Date: Fri, 7 Jan 2011 00:32:17 +1000 Subject: Add a hash table for holding packages Signed-off-by: Allan McRae --- lib/libalpm/pkghash.h | 58 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 58 insertions(+) create mode 100644 lib/libalpm/pkghash.h (limited to 'lib/libalpm/pkghash.h') diff --git a/lib/libalpm/pkghash.h b/lib/libalpm/pkghash.h new file mode 100644 index 00000000..7f90cb17 --- /dev/null +++ b/lib/libalpm/pkghash.h @@ -0,0 +1,58 @@ +/* + * pkghash.h + * + * Copyright (c) 2011 Pacman Development Team + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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. If not, see . + */ + +#ifndef _ALPM_PKGHASH_H +#define _ALPM_PKGHASH_H + +#include + +#include "alpm.h" +#include "alpm_list.h" + + +/** + * @brief A hash table for holding pmpkg_t objects. + * + * A combination of a hash table and a list, allowing for fast look-up + * by package name but also iteration over the packages. + */ +struct __pmpkghash_t { + /** data held by the hash table */ + alpm_list_t **hash_table; + /** number of buckets in hash table */ + size_t buckets; + /** number of entries in hash table */ + size_t entries; + /** head node of the hash table data in normal list format */ + alpm_list_t *list; +}; + +pmpkghash_t *_alpm_pkghash_create(size_t size); + +pmpkghash_t *_alpm_pkghash_add(pmpkghash_t *hash, pmpkg_t *pkg); +pmpkghash_t *_alpm_pkghash_add_sorted(pmpkghash_t *hash, pmpkg_t *pkg); +pmpkghash_t *_alpm_pkghash_remove(pmpkghash_t *hash, pmpkg_t *pkg, pmpkg_t *data); + +void _alpm_pkghash_free(pmpkghash_t *hash); + +pmpkg_t *_alpm_pkghash_find(pmpkghash_t *hash, const char *name); + +#define MAX_HASH_LOAD 0.7 + +#endif /* _ALPM_PKGHASH_H */ -- cgit v1.2.3-70-g09d2 From 01c3c7e4f28d837f0b8a6aaaf27d16894d4b762d Mon Sep 17 00:00:00 2001 From: Allan McRae Date: Sun, 30 Jan 2011 22:42:45 +1000 Subject: Actually remove packages from pkghash on removal Fully removes a package from the hash. Also unify prototype with removal from an alpm_list_t, fixing issues when removing a package from the pkgcache. Signed-off-by: Allan McRae --- lib/libalpm/db.c | 2 +- lib/libalpm/pkghash.c | 37 +++++++++++++++++++++++++++++-------- lib/libalpm/pkghash.h | 2 +- 3 files changed, 31 insertions(+), 10 deletions(-) (limited to 'lib/libalpm/pkghash.h') diff --git a/lib/libalpm/db.c b/lib/libalpm/db.c index c0c2f0ca..02f82823 100644 --- a/lib/libalpm/db.c +++ b/lib/libalpm/db.c @@ -617,7 +617,7 @@ int _alpm_db_remove_pkgfromcache(pmdb_t *db, pmpkg_t *pkg) _alpm_log(PM_LOG_DEBUG, "removing entry '%s' from '%s' cache\n", alpm_pkg_get_name(pkg), db->treename); - db->pkgcache = _alpm_pkghash_remove(db->pkgcache, pkg, data); + db->pkgcache = _alpm_pkghash_remove(db->pkgcache, pkg, &data); if(data == NULL) { /* package not found */ _alpm_log(PM_LOG_DEBUG, "cannot remove entry '%s' from '%s' cache: not found\n", diff --git a/lib/libalpm/pkghash.c b/lib/libalpm/pkghash.c index bdff78ea..14056e37 100644 --- a/lib/libalpm/pkghash.c +++ b/lib/libalpm/pkghash.c @@ -219,11 +219,15 @@ pmpkghash_t *_alpm_pkghash_add_sorted(pmpkghash_t *hash, pmpkg_t *pkg) * * @return the resultant hash */ -pmpkghash_t *_alpm_pkghash_remove(pmpkghash_t *hash, pmpkg_t *pkg, pmpkg_t *data) +pmpkghash_t *_alpm_pkghash_remove(pmpkghash_t *hash, pmpkg_t *pkg, pmpkg_t **data) { alpm_list_t *i; size_t position; + if(data) { + *data = NULL; + } + if(pkg == NULL || hash == NULL) { return(hash); } @@ -235,7 +239,6 @@ pmpkghash_t *_alpm_pkghash_remove(pmpkghash_t *hash, pmpkg_t *pkg, pmpkg_t *data if(info->name_hash == pkg->name_hash && strcmp(info->name, pkg->name) == 0) { -#if 0 /* Actually removing items is not a good idea with linear probing... */ /* remove from list */ /* TODO - refactor with alpm_list_remove */ if(i == hash->list) { @@ -266,16 +269,34 @@ pmpkghash_t *_alpm_pkghash_remove(pmpkghash_t *hash, pmpkg_t *pkg, pmpkg_t *data } /* remove from hash */ - data = info; - info = NULL; + if(data) { + *data = info; + } + hash->hash_table[position] = NULL; free(i); - i = NULL; hash->entries -= 1; -#endif - /* fake removal - pkgname can not be blank so 0 hash is impossible */ - info->name_hash = 0; + /* potentially move entries following removed entry to keep + * open addressing collision resolution working */ + size_t next_null = (position + 1) % hash->buckets; + while(hash->hash_table[next_null] != NULL) { + next_null = (next_null + 1) % hash->buckets; + } + + position = (position + 1) % hash->buckets; + + while((i = hash->hash_table[position]) != NULL) { + info = i->data; + size_t new_position = get_hash_position(info->name_hash, hash); + + if(new_position != next_null) { + hash->hash_table[new_position] = i; + hash->hash_table[position] = NULL; + } + + position = (position + 1) % hash->buckets; + } return(hash); } diff --git a/lib/libalpm/pkghash.h b/lib/libalpm/pkghash.h index 7f90cb17..a6c1db71 100644 --- a/lib/libalpm/pkghash.h +++ b/lib/libalpm/pkghash.h @@ -47,7 +47,7 @@ pmpkghash_t *_alpm_pkghash_create(size_t size); pmpkghash_t *_alpm_pkghash_add(pmpkghash_t *hash, pmpkg_t *pkg); pmpkghash_t *_alpm_pkghash_add_sorted(pmpkghash_t *hash, pmpkg_t *pkg); -pmpkghash_t *_alpm_pkghash_remove(pmpkghash_t *hash, pmpkg_t *pkg, pmpkg_t *data); +pmpkghash_t *_alpm_pkghash_remove(pmpkghash_t *hash, pmpkg_t *pkg, pmpkg_t **data); void _alpm_pkghash_free(pmpkghash_t *hash); -- cgit v1.2.3-70-g09d2