| Age | Commit message (Collapse) | Author |
|---|
|
* libihash/ihash.c (hurd_ihash_add): Move the code computing the load
factor of the hash table...
* libihash/ihash.h (hurd_ihash_get_load): ... here, together with the
comment describing the method and the rationale for chosing binary
percent.
|
|
Expressing the maximum load in binary percent (where 128b% corresponds
to 100%) allows us to use fast binary scaling to determine if the
maximum load has been reached without losing precision.
Furthermore, the previously used expression 'ht->nr_items * 100'
overflows int at 2^25 (unsigned int at 2^26). When a hash table
reached that limit, it would fail to resize and fill up the table.
This change fixes that.
* libihash/ihash.c (hurd_ihash_set_max_load): Update the comment.
(hurd_ihash_add): Use fast binary scaling to determine the current
load.
* libihash/ihash.h (struct hurd_ihash): Update comment for max_load.
(hurd_ihash_set_max_load): Update the comment.
|
|
libihash uses open addressing. Previously, quadratic probing in both
directions was used to resolve collisions. Quadratic probing might
result in a less efficient use of caches.
Also, prime numbers of the form 4 * i + 3 were used as array sizes.
This was used in combination with the integer modulo operation for
hashing. It has been known for some time that libihash suffers from
collisions, so a integer hash function is now applied to the keys to
derive the index.
Use linear probing instead. Also, use powers of two for the array
sizes, so a bit mask can be used for the modulo operation.
* libihash/ihash.c (ihash_sizes, ihash_nsizes): Remove.
(find_index): Use linear probing and fast modulo operation.
(add_one): Likewise.
* libihash/ihash.h (HURD_IHASH_MIN_SIZE): New macro.
|
|
Previously, int was used for the field max_load of struct hurd_ihash.
There is no reason for this as far as I can tell. Furthermore,
hurd_ihash_set_max_load takes an unsigned int max_load.
* libihash/ihash.h (struct hurd_ihash): Use unsigned int for field
max_load.
|
|
The performance of hash tables depend critically on a low number of
hash collisions. As the table fills up, the chance of collisions
necessarily raises.
Previously, libihash resized the hash table when the load exceeded
80%. This seems a bit optimistic (e. g. java.util.Hashtable uses 75%
as default).
* libihash/ihash.h (HURD_IHASH_MAX_LOAD_DEFAULT): Set to 75.
|
|
Add a macro HURD_IHASH_ITERATE_ITEMS that iterates over all elements
in the hash table making both the key and the value available.
* libihash/ihash.h (HURD_IHASH_ITERATE_ITEMS): New macro.
|
|
* ihash.h (HURD_IHASH_ITERATE): Don't use increment operator in
assignment, but just add one. Reported by Ognyan Kulev.
|
|
* ihash.c (hurd_ihash_remove): Don't look for the index when the
hashtable is empty.
* ihash.h (HURD_IHASH_ITERATE): Doc fix.
|
|
* ihash.h (HURD_IHASH_NO_LOCP): Change to INTPTR_MIN.
(struct hurd_ihash): Change type of locp_offset from off_t to
intptr_t.
(hurd_ihash_init): Likewise in prototype.
(hurd_ihash_create): Likewise in prototype.
* ihash.c (hurd_ihash_init): Likewise in definition.
(hurd_ihash_create): Likewise in definition.
|
|
2003-08-17 Marcus Brinkmann <marcus@gnu.org>
* auth.c: Include <stddef.h>.
(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 <marcus@gnu.org>
* vga-dynafont.c: Include <stddef.h>.
(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 <marcus@gnu.org>
* ftpfs.h: Include <hurd/ihash.h>.
(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 <stddef.h>.
(ftpfs_create): Call hurd_ihash_init, not hurd_ihash_create.
Call hurd_ihash_destroy on error.
libihash/
2003-08-17 Marcus Brinkmann <marcus@gnu.org>
* 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 <marcus@gnu.org>
* 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 <stddef.h>.
(ports_create_bucket): Use hurd_ihash_init instead hurd_ihash_create.
* class-iterate.c: Do not include <hurd/ihash.h>.
* 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 <marcus@gnu.org>
* 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 <marcus@gnu.org>
* 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 <marcus@gnu.org>
* proc.h: Include <hurd/ihash.h>.
(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 <marcus@gnu.org>
* fakeroot.c: Include <stddef.h>.
(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 <marcus@gnu.org>
* rpctrace.c: Include <stddef.h>.
(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.
|
|
|
|
|
|
|
|
|
