| 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.
|
|
* libihash/ihash.c (hurd_ihash_add): Fix typo.
|
|
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.
|
|
Use an integer hash function to derive the index from the key. This
should reduce the number of collisions.
* libihash/ihash.c (hash_int32): New function.
(find_index): Use hash_int32 on the key to derive the index.
(add_one): Likewise.
|
|
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.
|
|
* libihash/ihash.c (hurd_ihash_add): Remove dead code.
|
|
* libihash/ihash.c: Clean up the included header files.
* libshouldbeinlibc/cacheq.c: Likewise.
* libshouldbeinlibc/canon-host.c: Likewise.
* libshouldbeinlibc/fsysops.c: Likewise.
* libshouldbeinlibc/idvec-auth.c: Likewise.
* libshouldbeinlibc/idvec.c: Likewise.
* libshouldbeinlibc/idvec.h: Likewise.
* libshouldbeinlibc/localhost.c: Likewise.
* libshouldbeinlibc/maptime.c: Likewise.
* libshouldbeinlibc/nullauth.c: Likewise.
* libshouldbeinlibc/portxlate.c: Likewise.
* libshouldbeinlibc/shared-dom.c: Likewise.
* libshouldbeinlibc/ugids-argp.c: Likewise.
* libshouldbeinlibc/ugids-auth.c: Likewise.
* libshouldbeinlibc/ugids-imply.c: Likewise.
* libshouldbeinlibc/ugids-merge.c: Likewise.
* libshouldbeinlibc/ugids-subtract.c: Likewise.
* libshouldbeinlibc/ugids-verify-auth.c: Likewise.
* libshouldbeinlibc/ugids-verify.c: Likewise.
* libshouldbeinlibc/ugids.c: Likewise.
* libshouldbeinlibc/ugids.h: Likewise.
* libshouldbeinlibc/wire.c: Likewise.
|
|
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.c (ihash_add): Change type of i to unsigned int to address gcc
warning.
|
|
* Makeconf (lndist): Remove target.
(dist-hook, dist.tar): New targets.
* Makefile (dist): Rewrite this target's as well as accompanying rules.
(%-lndist, cp-linked-files, $(lf-inst)): Remove targets.
(%.bz2, %.gz, %/dist-hook): New targets.
(DISTFILES): Set.
* doc/Makefile (DISTFILES): Set.
* doc/Makefile (lndist, lndist-info-targets): Remove targets.
* include/Makefile (lndist): Remove target.
* libthreads/Makefile (lndist, lndist-i386-files, lndist-map-file): Remove
targets.
* pfinet/Makefile (lndist, lndist-linux-src-net-core-files)
(lndist-linux-src-net-ethernet-files, lndist-linux-src-net-ipv4-files)
(lndist-linux-src-net-ipv6-files, lndist-linux-src-asm-files)
(lndist-linux-src-include-linux-files, lndist-linux-src-include-net-files)
(lndist-linux-src-include-asm-files, lndist-glue-include-linux-files)
(lndist-glue-include-asm-files): Remove targets.
* auth/Makefile (LCLHDRS): Don't set.
* boot/Makefile (LCLHDRS, DIST_FILES): Likewise.
* bsdfsck/Makefile (LCLHDRS): Likewise.
* config/Makefile (DIST_FILES): Likewise.
* console-client/Makefile (LCLHDRS): Likewise.
* console/Makefile (LCLHDRS, DIST_FILES): Likewise.
* doc/Makefile (DIST_FILES): Likewise.
* exec/Makefile (LCLHDRS, DIST_FILES): Likewise.
* ext2fs/Makefile (LCLHDRS): Likewise.
* fatfs/Makefile (LCLHDRS): Likewise.
* ftpfs/Makefile (LCLHDRS): Likewise.
* hostmux/Makefile (LCLHDRS): Likewise.
* hurd/Makefile (DIST_FILES): Likewise.
* include/Makefile (LCLHDRS): Likewise.
* isofs/Makefile (LCLHDRS, DIST_FILES): Likewise.
* libcons/Makefile (LCLHDRS): Likewise.
* libdirmgt/Makefile (LCLHDRS): Likewise.
* libdiskfs/Makefile (LCLHDRS): Likewise.
* libfshelp/Makefile (LCLHDRS): Likewise.
* libftpconn/Makefile (LCLHDRS): Likewise.
* libihash/Makefile (LCLHDRS): Likewise.
* libiohelp/Makefile (LCLHDRS): Likewise.
* libnetfs/Makefile (LCLHDRS): Likewise.
* libpager/Makefile (LCLHDRS): Likewise.
* libpipe/Makefile (LCLHDRS): Likewise.
* libports/Makefile (LCLHDRS): Likewise.
* libps/Makefile (LCLHDRS): Likewise.
* libshouldbeinlibc/Makefile (LCLHDRS): Likewise.
* libstore/Makefile (LCLHDRS, DIST_FILES): Likewise.
* libthreads/Makefile (LCLHDRS): Likewise.
* libtreefs/Makefile (LCLHDRS): Likewise.
* libtrivfs/Makefile (LCLHDRS): Likewise.
* mach-defpager/Makefile (LCLHDRS): Likewise.
* nfs/Makefile (LCLHDRS): Likewise.
* nfsd/Makefile (LCLHDRS): Likewise.
* pfinet/Makefile (LCLHDRS): Likewise.
* pflocal/Makefile (LCLHDRS): Likewise.
* proc/Makefile (LCLHDRS, DIST_FILES): Likewise.
* release/Makefile (DIST_FILES): Likewise.
* storeio/Makefile (LCLHDRS): Likewise.
* sutils/Makefile (LCLHDRS): Likewise.
* term/Makefile (LCLHDRS, DIST_FILES): Likewise.
* tmpfs/Makefile (LCLHDRS): Likewise.
* ufs-fsck/Makefile (LCLHDRS): Likewise.
* ufs/Makefile (LCLHDRS): Likewise.
* usermux/Makefile (LCLHDRS): Likewise.
* utils/Makefile (LCLHDRS): Likewise.
|
|
* ChangeLog: Wipe out content, and add instructions about how to get it back.
* auth/ChangeLog: Remove file.
* benchmarks/ChangeLog: Likewise.
* boot/ChangeLog: Likewise.
* bsdfsck/ChangeLog: Likewise.
* config/ChangeLog: Likewise.
* console-client/ChangeLog: Likewise.
* console/ChangeLog: Likewise.
* daemons/ChangeLog: Likewise.
* defpager/ChangeLog: Likewise.
* doc/ChangeLog: Likewise.
* exec/ChangeLog: Likewise.
* ext2fs/ChangeLog: Likewise.
* fatfs/ChangeLog: Likewise.
* fstests/ChangeLog: Likewise.
* ftpfs/ChangeLog: Likewise.
* hostmux/ChangeLog: Likewise.
* hurd/ChangeLog: Likewise.
* include/ChangeLog: Likewise.
* init/ChangeLog: Likewise.
* isofs/ChangeLog: Likewise.
* libcons/ChangeLog: Likewise.
* libdirmgt/ChangeLog: Likewise.
* libdiskfs/ChangeLog: Likewise.
* libfshelp/ChangeLog: Likewise.
* libftpconn/ChangeLog: Likewise.
* libhurdbugaddr/ChangeLog: Likewise.
* libihash/ChangeLog: Likewise.
* libiohelp/ChangeLog: Likewise.
* libnetfs/ChangeLog: Likewise.
* libpager/ChangeLog: Likewise.
* libpipe/ChangeLog: Likewise.
* libports/ChangeLog: Likewise.
* libps/ChangeLog: Likewise.
* libshouldbeinlibc/ChangeLog: Likewise.
* libstore/ChangeLog: Likewise.
* libthreads/ChangeLog: Likewise.
* libtrivfs/ChangeLog: Likewise.
* login/ChangeLog: Likewise.
* mach-defpager/ChangeLog: Likewise.
* nfs/ChangeLog: Likewise.
* nfsd/ChangeLog: Likewise.
* pfinet/ChangeLog: Likewise.
* pflocal/ChangeLog: Likewise.
* proc/ChangeLog: Likewise.
* release/ChangeLog: Likewise.
* serverboot/ChangeLog: Likewise.
* storeio/ChangeLog: Likewise.
* sutils/ChangeLog: Likewise.
* term/ChangeLog: Likewise.
* tmpfs/ChangeLog: Likewise.
* trans/ChangeLog: Likewise.
* ufs-fsck/ChangeLog: Likewise.
* ufs-utils/ChangeLog: Likewise.
* ufs/ChangeLog: Likewise.
* usermux/ChangeLog: Likewise.
* utils/ChangeLog: Likewise.
|
|
* ihash.c (add_one): Cast VALUE with (hurd_ihash_locp_t *) instead of
(hurd_ihash_locp_t).
|
|
* 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.
|
|
|
|
* sizes.c: New file, a list of prime numbers useful for table sizes.
* priv.h (_ihash_sizes, _ihash_nsizes): Declare.
(_ihash_nextprime): Don't.
* ihash.c (ihash_add): Select sizes from the _ihash_sizes array
instead of using _ihash_nextprime.
* Makefile: Clean up whitespace, reorder all the variable definitions.
(SRCS): Remove primes.c, add sizes.c instead.
(OBJS): Define dynamically.
|
|
|
|
* primes.c: Fix last change.
|
|
* primes.c (_ihash_nextprime): Use a dynamically-sized array for
`seive' instead of alloca, so that if we are looping we won't
allocate more stack than necessary. Suggested by wesommer@mit.edu
(Bill Sommerfeld).
|
|
|
|
Initialize CLEANUP & CLEANUP_ARG fields.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(table_lock): New variable.
(nextprime): Lock table_lock around operation of routine.
|
|
HASH_DEL when the next position on the chain is empty -- different hash
chains may share this cell, and have different next positions, leading to
random additional entries sometimes disappearing when deleting something.
|
|
|
|
|
|
|
