From ac1cab88f6e43ece947ef2e212f0a732f9c39d81 Mon Sep 17 00:00:00 2001 From: Marcus Brinkmann Date: Mon, 1 Mar 2004 09:58:44 +0000 Subject: auth/ 2003-08-17 Marcus Brinkmann * auth.c: Include . (pending_users, pending_server): Change type to struct hurd_ihash, initialize with HURD_IHASH_INITIALIZER. (struct pending): Change type of member LOCP to hurd_ihash_locp_t. (S_auth_user_authenticate): Use hurd_ihash_* functions instead ihash_*. (S_auth_server_authenticate): Likewise. (main): Do not allocate the hash tables. console-client/ 2003-08-17 Marcus Brinkmann * vga-dynafont.c: Include . (struct mapped_character): Change type of LOCP to hurd_ihash_locp_t. (struct dynafont): Change type of CHARMAP to struct hurd_ihash. (dynafont_new): Use hurd_ihash_init instead of ihash_create. Remove variable ERR. Call hurd_ihash_add instead of ihash_add. (dynafont_free): Call hurd_ihash_destroy, no ihash_free. (dynafont_lookup_internal): Use hurd_ihash_find, not ihash_find. (dynafont_lookup_internal): Call hurd_ihash_locp_remove instead ihash_locp_remove, and hurd_ihash_add instead ihash_add. (dynafont_change_font): Likewise. Clean out LOCP if character is unmapped. ftpfs/ 2003-08-17 Marcus Brinkmann * ftpfs.h: Include . (struct ftpfs): Change type of INODE_MAPPINGS to struct hurd_ihash. (struct ftpfs_dir_entry): Change type of INODE_LOCP to hurd_ihash_locp_t. * node.c (ftpfs_create_node): Call hurd_ihash_add, not ihash_add. (netfs_node_norefs): Call hurd_ihash_locp_remove, not ihash_locp_remove. * fs.c: Include . (ftpfs_create): Call hurd_ihash_init, not hurd_ihash_create. Call hurd_ihash_destroy on error. libihash/ 2003-08-17 Marcus Brinkmann * ihash.c: Rewritten. * ihash.h: Rewritten. * Makefile (SRCS): Remove sizes.c. (LCLHDRS): Remove priv.h. * primes.c, sizes.c, priv.h: Files removed. 2003-08-17 Marcus Brinkmann * ports.h (struct port_bucket): Change type of HTABLE to struct hurd_ihash. (struct port_info): Change type of HENTRY to hurd_ihash_locp_t. * lookup-port.c (ports_lookup_port): Use hurd_ihash_find instead ihash_find. * bucket-iterate.c (_ports_bucket_class_iterate): Use HURD_IHASH_ITERATE instead ihash_iterate. * inhibit-all-rpcs.c (ports_inhibit_all_rpcs): Likewise. * inhibit-bucket-rpcs.c (ports_inhibit_bucket_rpcs): Likewise. * create-internal.c (_ports_create_port_internal): Use hurd_ihash_add instead ihash_add. * import-port.c (ports_import_port): Likewise. * reallocate-from-external.c (ports_reallocate_from_external): Likewise. * reallocate-port.c (ports_reallocate_port): Likewise. * transfer-right.c (ports_transfer_right): Likewise. * create-bucket.c: Include . (ports_create_bucket): Use hurd_ihash_init instead hurd_ihash_create. * class-iterate.c: Do not include . * claim-right.c (ports_claim_right): Call hurd_ihash_locp_remove instead ihash_locp_remove. * complete-deallocate.c (_ports_complete_deallocate): Likewise. * destroy-right.c (ports_destroy_right): Likewise. * reallocate-from-external.c (ports_reallocate_from_external): Likewise. * reallocate-port.c (ports_reallocate_port): Likewise. * transfer-right.c (ports_transfer_right): Likewise. libps/ 2003-08-17 Marcus Brinkmann * ps.h (struct ps_context): Change type of members procs, ttys, ttys_by_cttyid and users to struct hurd_ihash. * context.c (ps_context_create): Remove variables err_procs, err_ttys, err_ttys_by_cttyid and err_users. Use hurd_ihash_init instead of ihash_create. Call hurd_ihash_set_cleanup and the hurd_ihash_cleanup_t type instead of ihash_set_cleanup. (ps_context_free): Call hurd_ihash_destroy instead of ihash_free. (lookup): Call hurd_ihash_find instead ihash_find, hurd_ihash_add instead ihash_add. (ps_context_find_proc_stat): Take pointer of hash object. (ps_context_find_tty): Likewise. (ps_context_find_tty_by_cttyid): Likewise. (ps_context_find_user): Likewise. libpthread/ 2003-08-17 Marcus Brinkmann * sysdeps/hurd/pt-key.h (PTHREAD_KEY_MEMBERS): Change type of THREAD_SPECIFICS to hurd_ihash_t. * sysdeps/hurd/pt-setspecific.c (pthread_setspecific): Call hurd_ihash_create instead ihash_create, and hurd_ihash_add instead ihash_add. * sysdeps/hurd/pt-getspecific.c (pthread_getspecific): Call hurd_ihash_find instead of ihash_find. * sysdeps/hurd/pt-destroy-specific.c (__pthread_destroy_specific): Call hurd_ihash_find instead of ihash_find, hurd_ihash_remove instead of ihash_remove, and hurd_ihash_free instead of ihash_free. proc/ 2003-08-17 Marcus Brinkmann * proc.h: Include . (struct proc): Change type of members p_pidhashloc and p_taskhashloc to hurd_ihash_locp_t. (struct pgrp): Likewise for pg_hashloc. (struct session): Likewise for s_hashloc. * hash.c: Change type of pghash, pidhash, taskhash and sidhash to struct hurd_ihash and initialize them with HURD_IHASH_INITIALIZER. Include stddef.h. (pid_find): Call hurd_ihash_find instead ihash_find. (pid_find_allow_zombie): Likewise. (task_find): Likewise. (task_find_nocreate): Likewise. (pgrp_find): Likewise. (session_find): Likewise. (add_proc_to_hash): Call hurd_ihash_add instead ihash_add. (add_pgrp_to_hash): Likewise. (add_session_to_hash): Likewise. (remove_pgrp_from_hash): Call hurd_ihash_locp_remove instead ihash_locp_remove, and provide hash table pointer. (remove_proc_from_hash): Likewise. (remove_session_from_hash): Likewise. (prociterate): Use HURD_IHASH_ITERATE instead ihash_iterate. trans/ 2003-08-17 Marcus Brinkmann * fakeroot.c: Include . (struct netnode): Change type of member idport_locp to hurd_ihash_locp_t. (idport_ihash): Change type to struct hurd_ihash and initialize with HURD_IHASH_INITIALIZER. (new_node): Call hurd_ihash_add instead of ihash_add. (netfs_node_norefs): Call hrd_ihash_locp_remove instead ihash_locp_remove. (netfs_S_dir_lookup): Call hurd_ihash_find instead ihash_find. utils/ 2003-08-17 Marcus Brinkmann * rpctrace.c: Include . (struct traced_info): Change type of LOCP to hurd_ihash_locp_t. (msgid_ihash): Change type to struct hurd_ihash, and initialize with HURD_IHASH_INITIALIZER, don't set cleanup here. (traced_names): Likewise. (main): Call hurd_ihash_set_cleanup for msgid_ihash. Don't create traced_names. (parse_msgid_list): Call hurd_ihash_add instead ihash_add. (new_send_wrapper): Likewise. (msgid_info): Likewise. Call hurd_ihash_find instead ihash_find. (rewrite_right): Likewise. (traced_dropweak): Call hurd_ihash_locp_remove instead ihash_locp_remove. --- libihash/ihash.c | 549 +++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 353 insertions(+), 196 deletions(-) (limited to 'libihash/ihash.c') diff --git a/libihash/ihash.c b/libihash/ihash.c index dfc36b01..51cca82b 100644 --- a/libihash/ihash.c +++ b/libihash/ihash.c @@ -1,11 +1,11 @@ -/* Integer-keyed hash table functions. - - Copyright (C) 1993,94,95,96,97,2001 Free Software Foundation, Inc. - +/* ihash.c - Integer-keyed hash table functions. + Copyright (C) 1993-1997, 2001, 2003 Free Software Foundation, Inc. + Written by Michael I. Bushnell. + Revised by Miles Bader . + Revised by Marcus Brinkmann . + This file is part of the GNU Hurd. - Written by Michael I. Bushnell; revised by Miles Bader . - The GNU Hurd 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, or (at your option) @@ -20,266 +20,423 @@ along with the GNU Hurd; see the file COPYING. If not, write to the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ +#if HAVE_CONFIG_H +#include +#endif + +#include #include #include +#include +#include +#include + +#include -#include "ihash.h" -#include "priv.h" - -/* ---------------------------------------------------------------- */ - -/* When an entry in a hashtable's TAB array is HASH_EMPTY, that location is - available, and none of the other arrays are valid at that index. */ -#define HASH_EMPTY 0 - -/* When an entry in a hashtable's TAB array is HASH_DEL, that location is - available, and none of the other arrays are valid at that index. The - difference from HASH_EMPTY is that searches continue though HASH_DEL and - stop at HASH_EMPTY. */ -#define HASH_DEL ((void *) -1) - -/* Returns an initial index in HT for the key ID, for search for an entry. */ -#define HASH(ht, id) ((id) % (ht)->size) -/* Returns subsequent indices in HT for the key ID, given the previous one. */ -#define REHASH(ht, id, h) (((id) + (h)) % (ht)->size) -/* ---------------------------------------------------------------- */ +/* The prime numbers of the form 4 * i + 3 for some i, all greater + than twice the previous one and smaller than 2^40 (for now). */ +static const uint64_t ihash_sizes[] = +{ + 3, + 7, + 19, + 43, + 103, + 211, + 431, + 863, + 1747, + 3499, + 7019, + 14051, + 28111, + 56239, + 112507, + 225023, + 450067, + 900139, + 1800311, + 3600659, + 7201351, + 14402743, + 28805519, + 57611039, + 115222091, + 230444239, + 460888499, + 921777067, + 1843554151, + UINT64_C (3687108307), + UINT64_C (7374216631), + UINT64_C (14748433279), + UINT64_C (29496866579), + UINT64_C (58993733159), + UINT64_C (117987466379), + UINT64_C (235974932759), + UINT64_C (471949865531), + UINT64_C (943899731087) +}; + +static const unsigned int ihash_nsizes = (sizeof ihash_sizes + / sizeof ihash_sizes[0]); + +/* Return 1 if the slot with the index IDX in the hash table HT is + empty, and 0 otherwise. */ static inline int -index_empty(ihash_t ht, int index) +index_empty (hurd_ihash_t ht, unsigned int idx) { - return ht->tab[index] == HASH_EMPTY || ht->tab[index] == HASH_DEL; + return ht->items[idx].value == _HURD_IHASH_EMPTY + || ht->items[idx].value == _HURD_IHASH_DELETED; } + +/* Return 1 if the index IDX in the hash table HT is occupied by the + element with the key KEY. */ static inline int -index_valid(ihash_t ht, int index, int id) +index_valid (hurd_ihash_t ht, unsigned int idx, hurd_ihash_key_t key) { - return !index_empty(ht, index) && ht->ids[index] == id; + return !index_empty (ht, idx) && ht->items[idx].key == key; } -/* Given a hash table HT, and a key ID, finds the index in the table of that - key. You must subsequently check to see whether the given index is valid - (with index_valid() or index_empty()). */ + +/* Given a hash table HT, and a key KEY, find the index in the table + of that key. You must subsequently check with index_valid() if the + returned index is valid. */ static inline int -find_index(ihash_t ht, int id) +find_index (hurd_ihash_t ht, hurd_ihash_key_t key) { - int h, firsth = -1; + unsigned int idx; + unsigned int i; + unsigned int up_idx; + unsigned int down_idx; + + idx = key % ht->size; - for (h = HASH(ht, id); - ht->tab[h] != HASH_EMPTY && ht->ids[h] != id && h != firsth; - h = REHASH(ht, id, h)) - if (firsth == -1) - firsth = h; + if (ht->items[idx].value == _HURD_IHASH_EMPTY || ht->items[idx].key == key) + return idx; - return h; + /* Instead of calculating idx + 1, idx + 4, idx + 9, ..., idx + i^2, + we add 1, 3, 5, 7, etc to the previous index. We do this in both + directions separately. */ + i = 1; + up_idx = idx; + down_idx = idx; + + do + { + up_idx = (up_idx + i) % ht->size; + if (ht->items[up_idx].value == _HURD_IHASH_EMPTY + || ht->items[up_idx].key == key) + return up_idx; + + if (down_idx < i) + down_idx += ht->size; + down_idx = (down_idx - i) % ht->size; + if (ht->items[down_idx].value == _HURD_IHASH_EMPTY + || ht->items[down_idx].key == key) + return down_idx; + + /* After (ht->size - 1) / 2 iterations, this will be 0. */ + i = (i + 2) % ht->size; + } + while (i); + + /* If we end up here, the item could not be found. Return any + invalid index. */ + return idx; } - -/* ---------------------------------------------------------------- */ -/* Create an integer hash table and return it in HT. If a memory allocation - error occurs, ENOMEM is returned, otherwise 0. */ -error_t -ihash_create(ihash_t *ht) + +/* Remove the entry pointed to by the location pointer LOCP from the + hashtable HT. LOCP is the location pointer of which the address + was provided to hurd_ihash_add(). */ +static inline void +locp_remove (hurd_ihash_t ht, hurd_ihash_locp_t locp) { - *ht = malloc(sizeof(struct ihash)); - if (*ht == NULL) - return ENOMEM; - (*ht)->size = 0; - (*ht)->cleanup = 0; - (*ht)->cleanup_arg = 0; - return 0; + if (ht->cleanup) + (*ht->cleanup) (*locp, ht->cleanup_data); + *locp = _HURD_IHASH_DELETED; + ht->nr_items--; } -/* Free HT and all resources it consumes. */ + +/* Construction and destruction of hash tables. */ + +/* Initialize the hash table at address HT. */ void -ihash_free(ihash_t ht) +hurd_ihash_init (hurd_ihash_t ht, off_t locp_offs) { - void (*cleanup)(void *value, void *arg) = ht->cleanup; + ht->nr_items = 0; + ht->size = 0; + ht->locp_offset = locp_offs; + ht->max_load = HURD_IHASH_MAX_LOAD_DEFAULT; + ht->cleanup = 0; +} - if (cleanup) + +/* Destroy the hash table at address HT. This first removes all + elements which are still in the hash table, and calling the cleanup + function for them (if any). */ +void +hurd_ihash_destroy (hurd_ihash_t ht) +{ + if (ht->cleanup) { - int i; - void *arg = ht->cleanup_arg; - for (i = 0; i < ht->size; i++) - if (!index_empty(ht, i)) - (*cleanup)(ht->tab[i], arg); + hurd_ihash_cleanup_t cleanup = ht->cleanup; + void *cleanup_data = ht->cleanup_data; + + HURD_IHASH_ITERATE (ht, value) + (*cleanup) (value, cleanup_data); } if (ht->size > 0) - { - free(ht->tab); - free(ht->ids); - free(ht->locps); - } + free (ht->items); +} + + +/* Create a hash table, initialize it and return it in HT. If a + memory allocation error occurs, ENOMEM is returned, otherwise 0. */ +error_t +hurd_ihash_create (hurd_ihash_t *ht, off_t locp_offs) +{ + *ht = malloc (sizeof (struct hurd_ihash)); + if (*ht == NULL) + return ENOMEM; + + hurd_ihash_init (*ht, locp_offs); + + return 0; +} + - free(ht); +/* Destroy the hash table HT and release the memory allocated for it + by hurd_ihash_create(). */ +void +hurd_ihash_free (hurd_ihash_t ht) +{ + hurd_ihash_destroy (ht); + free (ht); } -/* Sets HT's element cleanup function to CLEANUP, and its second argument to - ARG. CLEANUP will be called on the value of any element to be - subsequently overwritten or deleted, with ARG as the second argument. */ + +/* Set the cleanup function for the hash table HT to CLEANUP. The + second argument to CLEANUP will be CLEANUP_DATA on every + invocation. */ void -ihash_set_cleanup(ihash_t ht, - void (*cleanup)(void *value, void *arg), - void *arg) +hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup, + void *cleanup_data) { ht->cleanup = cleanup; - ht->cleanup_arg = arg; + ht->cleanup_data = cleanup_data; } + + +/* Set the maximum load factor in percent to MAX_LOAD, which should be + between 1 and 100. The default is HURD_IHASH_MAX_LOAD_DEFAULT. + New elements are only added to the hash table while the number of + hashed elements is that much percent of the total size of the hash + table. If more elements are added, the hash table is first + expanded and reorganized. A MAX_LOAD of 100 will always fill the + whole table before enlarging it, but note that this will increase + the cost of operations significantly when the table is almost full. + + If the value is set to a smaller value than the current load + factor, the next reorganization will happen when a new item is + added to the hash table. */ +void +hurd_ihash_set_max_load (hurd_ihash_t ht, unsigned int max_load) +{ + ht->max_load = max_load; +} + -/* ---------------------------------------------------------------- */ - -/* Add ITEM to the hash table HT under the key ID. LOCP is the address of a - pointer located in ITEM; If non-NULL, LOCP should point to a variable of - type void **, and will be filled with a pointer that may be used as an - argument to ihash_locp_remove(). The variable pointed to by LOCP may be - written to subsequently between this called and when the element is - deleted, so you can't stash its value elsewhere and hope to use the - stashed value with ihash_locp_remove(). If a memory allocation error - occurs, ENOMEM is returned, otherwise 0. */ -error_t -ihash_add(ihash_t ht, int id, void *item, void ***locp) +/* Helper function for hurd_ihash_add. Return 1 if the item was + added, and 0 if it could not be added because no empty slot was + found. The arguments are identical to hurd_ihash_add. + + We are using open address hashing. As the hash function we use the + division method with quadratic probe. This is guaranteed to try + all slots in the hash table if the prime number is 3 mod 4. */ +static inline int +add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value) { - if (ht->size) - { - int h, firsth = -1; + unsigned int idx; + unsigned int first_free; - /* Search for for an empty or deleted space. */ - for (h = HASH(ht, id); - ht->tab[h] != HASH_EMPTY && ht->tab[h] != HASH_DEL && h != firsth; - h = REHASH(ht, id, h)) - if (firsth == -1) - firsth = h; + idx = key % ht->size; + first_free = idx; - if (index_empty(ht, h) || ht->ids[h] == id) + if (ht->items[idx].value != _HURD_IHASH_EMPTY && ht->items[idx].key != key) + { + /* Instead of calculating idx + 1, idx + 4, idx + 9, ..., idx + + i^2, we add 1, 3, 5, 7, ... 2 * i - 1 to the previous index. + We do this in both directions separately. */ + unsigned int i = 1; + unsigned int up_idx = idx; + unsigned int down_idx = idx; + + do { - if (!index_empty(ht, h) && ht->cleanup) - ht->cleanup(ht->tab[h], ht->cleanup_arg); + up_idx = (up_idx + i) % ht->size; + if (ht->items[up_idx].value == _HURD_IHASH_EMPTY + || ht->items[up_idx].key == key) + { + idx = up_idx; + break; + } + if (first_free == idx + && ht->items[up_idx].value == _HURD_IHASH_DELETED) + first_free = up_idx; + + if (down_idx < i) + down_idx += ht->size; + down_idx = (down_idx - i) % ht->size; + if (down_idx < 0) + down_idx += ht->size; + else + down_idx %= ht->size; + if (ht->items[down_idx].value == _HURD_IHASH_EMPTY + || ht->items[down_idx].key == key) + { + idx = down_idx; + break; + } + if (first_free == idx + && ht->items[down_idx].value == _HURD_IHASH_DELETED) + first_free = down_idx; + + /* After (ht->size - 1) / 2 iterations, this will be 0. */ + i = (i + 2) % ht->size; + } + while (i); + } - ht->tab[h] = item; - ht->ids[h] = id; - ht->locps[h] = locp; + /* Remove the old entry for this key if necessary. */ + if (index_valid (ht, idx, key)) + locp_remove (ht, &ht->items[idx].value); - if (locp) - *locp = &ht->tab[h]; + /* If we have not found an empty slot, maybe the last one we + looked at was empty (or just got deleted). */ + if (!index_empty (ht, first_free)) + first_free = idx; + + if (index_empty (ht, first_free)) + { + ht->nr_items++; + ht->items[first_free].value = value; + ht->items[first_free].key = key; - return 0; - } + if (ht->locp_offset != HURD_IHASH_NO_LOCP) + *((hurd_ihash_locp_t) (((char *) value) + ht->locp_offset)) + = &ht->items[first_free].value; + + return 1; } - { - int i; - void **entry; - int old_size = ht->size; - void **old_tab = ht->tab; - void ****old_locps = ht->locps; - int *old_ids = ht->ids; - - i = 0; - while (_ihash_sizes[i] <= old_size) - if (++i == _ihash_nsizes) - return ENOMEM; /* Surely will be true momentarily. */ - - ht->size = _ihash_sizes[i]; - ht->tab = malloc(ht->size * sizeof (void *)); - ht->locps = malloc (ht->size * sizeof (void ***)); - ht->ids = malloc (ht->size * sizeof (int)); - - if (ht->tab == NULL || ht->locps == NULL || ht->ids == NULL) - /* Memory allocation error; back out our changes and fail... */ - { - if (ht->tab) free(ht->tab); - if (ht->locps) free(ht->locps); - if (ht->ids) free(ht->ids); + return 0; +} - ht->size = old_size; - ht->tab = old_tab; - ht->locps = old_locps; - ht->ids = old_ids; + +/* Add ITEM to the hash table HT under the key KEY. If there already + is an item under this key, call the cleanup function (if any) for + it before overriding the value. If a memory allocation error + occurs, ENOMEM is returned, otherwise 0. */ +error_t +hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item) +{ + struct hurd_ihash old_ht = *ht; + int was_added; + int i; - return ENOMEM; - } + if (ht->size) + { + /* Only fill the hash table up to its maximum load factor. */ + if (ht->nr_items * 100 / ht->size <= ht->max_load) + if (add_one (ht, key, item)) + return 0; + } + + /* The hash table is too small, and we have to increase it. */ + for (i = 0; i < ihash_nsizes; i++) + if (ihash_sizes[i] > old_ht.size) + break; + if (i == ihash_nsizes + || ihash_sizes[i] > SIZE_MAX / sizeof (struct _hurd_ihash_item)) + return ENOMEM; /* Surely will be true momentarily. */ - for (i = ht->size, entry = ht->tab; i > 0; i--, entry++) - *entry = HASH_EMPTY; + ht->nr_items = 0; + ht->size = ihash_sizes[i]; + /* calloc() will initialize all values to _HURD_IHASH_EMPTY implicitely. */ + ht->items = calloc (ht->size, sizeof (struct _hurd_ihash_item)); - /* We have to rehash this again? */ - if (old_size > 0) - for (i = 0; i < old_size; i++) - if (old_tab[i] != HASH_EMPTY && old_tab[i] != HASH_DEL) - ihash_add(ht, old_ids[i], old_tab[i], old_locps[i]); + if (ht->items == NULL) + { + if (ht->items) + free(ht->items); - /* Finally add the new element! */ - ihash_add(ht, id, item, locp); + *ht = old_ht; + return ENOMEM; + } - if (old_size > 0) + /* We have to rehash the old entries. */ + for (i = 0; i < old_ht.size; i++) + if (!index_empty (&old_ht, i)) { - free(old_tab); - free(old_locps); - free(old_ids); + was_added = add_one (ht, old_ht.items[i].key, old_ht.items[i].value); + assert (was_added); } - return 0; - } + /* Finally add the new element! */ + was_added = add_one (ht, key, item); + assert (was_added); + + if (old_ht.size > 0) + free (old_ht.items); + + return 0; } -/* Find and return the item in hash table HT with key ID, or NULL if it - doesn't exist. */ -void * -ihash_find (ihash_t ht, int id) + +/* Find and return the item in the hash table HT with key KEY, or NULL + if it doesn't exist. */ +hurd_ihash_value_t +hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key) { if (ht->size == 0) - return 0; + return NULL; else { - int index = find_index(ht, id); - return index_valid(ht, index, id) ? ht->tab[index] : 0; + int idx = find_index (ht, key); + return index_valid (ht, idx, key) ? ht->items[idx].value : NULL; } } - -/* ---------------------------------------------------------------- */ - -/* Call function FUN of one arg for each element of HT. FUN's only arg is a - pointer to the value stored in the hash table. If FUN ever returns - non-zero, then iteration stops and ihash_iterate returns that value, - otherwise it (eventually) returns 0. */ -error_t -ihash_iterate(ihash_t ht, error_t (*fun)(void *)) -{ - int i; - for (i = 0; i < ht->size; i++) - if (!index_empty(ht, i)) - { - error_t err = fun(ht->tab[i]); - if (err) - return err; - } - return 0; -} -/* Remove the entry at LOCP from the hashtable HT. LOCP is as returned from - an earlier call to ihash_add(). This call should be faster than - ihash_remove(). HT can be NULL, in which case the call still succeeds, - but no cleanup can be done. */ -void -ihash_locp_remove(ihash_t ht, void **locp) -{ - if (ht && ht->cleanup) - ht->cleanup(*locp, ht->cleanup_arg); - *locp = HASH_DEL; -} -/* Remove the entry with a key of ID from HT. If anything was actually - removed, 1 is returned, otherwise (if there was no such element), 0. */ +/* Remove the entry with the key KEY from the hash table HT. If such + an entry was found and removed, 1 is returned, otherwise 0. */ int -ihash_remove(ihash_t ht, int id) +hurd_ihash_remove (hurd_ihash_t ht, hurd_ihash_key_t key) { - int index = find_index(ht, id); - if (index_valid(ht, index, id)) + int idx = find_index (ht, key); + + if (index_valid (ht, idx, key)) { - ihash_locp_remove(ht, &ht->tab[index]); + locp_remove (ht, &ht->items[idx].value); return 1; } else return 0; } + + +/* Remove the entry pointed to by the location pointer LOCP from the + hashtable HT. LOCP is the location pointer of which the address + was provided to hurd_ihash_add(). This call is faster than + hurd_ihash_remove(). */ +void +hurd_ihash_locp_remove (hurd_ihash_t ht, hurd_ihash_locp_t locp) +{ + locp_remove (ht, locp); +} -- cgit v1.2.3