auth/

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.

1 files changed, 202 insertions, 68 deletions

diff --git a/libihash/ihash.h b/libihash/ihash.h
index 5d01ea1c..11092532 100644
--- a/libihash/ihash.h
+++ b/libihash/ihash.h
@@ -1,97 +1,231 @@
-/* Integer-keyed hash table functions.
+/* ihash.h - Integer keyed hash table interface.
+   Copyright (C) 1995, 2003 Free Software Foundation, Inc.
+   Written by Miles Bader <miles@gnu.org>.
+   Revised by Marcus Brinkmann <marcus@gnu.org>.
 
-   Copyright (C) 1995 Free Software Foundation, Inc.
+   This file is part of the GNU Hurd.
 
-   Written by Miles Bader <miles@gnu.ai.mit.edu>
-
-   This program is free software; you can redistribute it and/or
+   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) any later version.
 
-   This program is distributed in the hope that it will be useful, but
+   The GNU Hurd 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, write to the Free Software
-   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
+   along with the GNU Hurd; if not, write to the Free Software
+   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
 
-#ifndef __IHASH_H__
-#define __IHASH_H__
+#ifndef _HURD_IHASH_H
+#define _HURD_IHASH_H	1
 
 #include <errno.h>
+#include <sys/types.h>
+#include <limits.h>
+#include <stdint.h>
 
 
-/* ---------------------------------------------------------------- */
+/* The type of the values corresponding to the keys.  Must be a
+   pointer type.  The values (hurd_ihash_value_t) 0 and
+   (hurd_ihash_value_t) ~0 are reserved for the implementation.  */
+typedef void *hurd_ihash_value_t;
+
+/* When an value entry in the hash table is _HURD_IHASH_EMPTY or
+   _HURD_IHASH_DELETED, then the location is available, and none of
+   the other members of the item are valid at that index.  The
+   difference is that searches continue though _HURD_IHASH_DELETED,
+   but stop at _HURD_IHASH_EMPTY.  */
+#define _HURD_IHASH_EMPTY	((hurd_ihash_value_t) 0)
+#define _HURD_IHASH_DELETED	((hurd_ihash_value_t) -1)
+
+/* The type of integer we want to use for the keys.  */
+typedef uintptr_t hurd_ihash_key_t;
+
+/* The type of a location pointer, which is a pointer to the hash
+   value stored in the hash table.  */
+typedef hurd_ihash_value_t *hurd_ihash_locp_t;
 
-typedef struct ihash *ihash_t;
+
+/* The type of the cleanup function, which is called for every value
+   removed from the hash table.  */
+typedef void (*hurd_ihash_cleanup_t) (hurd_ihash_value_t value, void *arg);
 
-struct ihash
+
+struct _hurd_ihash_item
 {
-  /* An array storing the elements in the hash table (each a void *).  */
-  void **tab;
+  /* The value of this hash item.  Must be the first element of
+     the struct for the HURD_IHASH_ITERATE macro.  */
+  hurd_ihash_value_t value;
 
-  /* An array storing the integer key for each element.  */
-  int *ids;
+  /* The integer key of this hash item.  */
+  hurd_ihash_key_t key;
+};
+typedef struct _hurd_ihash_item *_hurd_ihash_item_t;
 
-  /* An array storing pointers to the `location pointers' for each element.
-     These are used as cookies for quick 'n' easy removal.  */
-  void ****locps;		/* four, count them, four stars */
+struct hurd_ihash
+{
+  /* The number of hashed elements.  */
+  size_t nr_items;
 
-  /* The length of all these arrays.  */
-  int size;
+  /* An array of (key, value) pairs.  */
+  _hurd_ihash_item_t items;
 
-  /* When freeing or overwriting an element, this function, if non-NULL, is
-     called with the value as the first argument, and CLEANUP_ARG as the
-     second argument.  */
-  void (*cleanup)(void *element, void *arg);
-  void *cleanup_arg;
-};
+  /* The length of the array ITEMS.  */
+  size_t size;
 
-/* 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);
-
-/* Free HT and all resources it consumes.  */
-void ihash_free(ihash_t 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.  */
-void ihash_set_cleanup(ihash_t ht,
-		       void (*cleanup)(void *value, void *arg),
-		       void *arg);
-
-/* 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 call 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);
+  /* The offset of the location pointer from the hash value.  */
+  off_t locp_offset;
 
-/* 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);
+  /* The maximum load factor in percent.  */
+  int max_load;
 
-/* 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 *));
+  /* When freeing or overwriting an element, this function is called
+     with the value as the first argument, and CLEANUP_DATA as the
+     second argument.  This does not happen if CLEANUP is NULL.  */
+  hurd_ihash_cleanup_t cleanup;
+  void *cleanup_data;
+};
+typedef struct hurd_ihash *hurd_ihash_t;
 
-/* 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.  */
-int ihash_remove(ihash_t ht, int id);
+
+/* Construction and destruction of hash tables.  */
+
+/* The default value for the maximum load factor in percent.  */
+#define HURD_IHASH_MAX_LOAD_DEFAULT 80
+
+/* The LOCP_OFFS to use if no location pointer is available.  */
+#define HURD_IHASH_NO_LOCP	INT_MIN
+
+/* The static initializer for a struct hurd_ihash.  */
+#define HURD_IHASH_INITIALIZER(locp_offs)				\
+  { .nr_items = 0, .size = 0, .cleanup = (hurd_ihash_cleanup_t) 0,	\
+    .max_load = HURD_IHASH_MAX_LOAD_DEFAULT,				\
+    .locp_offset = (locp_offs)}
+
+/* Initialize the hash table at address HT.  If LOCP_OFFSET is not
+   HURD_IHASH_NO_LOCP, then this is an offset (in bytes) from the
+   address of a hash value where a location pointer can be found.  The
+   location pointer must be of type hurd_ihash_locp_t and can be used
+   for fast removal with hurd_ihash_locp_remove().  */
+void hurd_ihash_init (hurd_ihash_t ht, off_t locp_offs);
+
+/* 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);
+
+/* Create a hash table, initialize it and return it in HT.  If
+   LOCP_OFFSET is not HURD_IHASH_NO_LOCP, then this is an offset (in
+   bytes) from the address of a hash value where a location pointer
+   can be found.  The location pointer must be of type
+   hurd_ihash_locp_t and can be used for fast removal with
+   hurd_ihash_locp_remove().  If a memory allocation error occurs,
+   ENOMEM is returned, otherwise 0.  */
+error_t hurd_ihash_create (hurd_ihash_t *ht, off_t locp_offs);
+
+/* Destroy the hash table HT and release the memory allocated for it
+   by hurd_ihash_create().  */
+void hurd_ihash_free (hurd_ihash_t ht);
 
-/* 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 **ht_locp);
+
+/* Configuration of the hash table.  */
+
+/* Set the cleanup function for the hash table HT to CLEANUP.  The
+   second argument to CLEANUP will be CLEANUP_DATA on every
+   invocation.  */
+void hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup,
+			     void *cleanup_data);
+
+/* Set the maximum load factor in percent to MAX_LOAD, which should be
+   between 50 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);
 
-#endif /* __IHASH_H__ */
+
+/* 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);
+
+/* 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);
+
+/* Iterate over all elements in the hash table.  You use this macro
+   with a block, for example like this:
+
+     error_t err;
+     HURD_IHASH_ITERATE (ht, value)
+       {
+         err = foo (value);
+         if (err)
+           break;
+       }
+     if (err)
+       cleanup_and_return ();
+
+   Or even like this:
+
+     hurd_ihash_iterate (ht, value)
+       foo (value);
+
+   The block will be run for every element in the hash table HT.  The
+   value of the current element is available in the variable VALUE
+   (which is declared for you and local to the block).  */
+
+/* The implementation of this macro is peculiar.  We want the macro to
+   execute a block following its invocation, so we can only prepend
+   code.  This excludes creating an outer block.  However, we must
+   define two variables: The hash value variable VALUE, and the loop
+   variable.
+
+   We can define variables inside the for-loop initializer (C99), but
+   we can only use one basic type to do that.  We can not use two
+   for-loops, because we want a break statement inside the iterator
+   block to terminate the operation.  So we must have both variables
+   of the same basic type, but we can make one (or both) of them a
+   pointer type.
+
+   The pointer to the value can be used as the loop variable.  This is
+   also the first element of the hash item, so we can cast the pointer
+   freely between these two types.  The pointer is only dereferenced
+   after the loop condition is checked (but of course the value the
+   pointer pointed to must not have an influence on the condition
+   result, so the comma operator is used to make sure this
+   subexpression is always true).  */
+#define HURD_IHASH_ITERATE(ht, val)					\
+  for (hurd_ihash_value_t val,						\
+         *_hurd_ihash_valuep = (ht)->size ? &(ht)->items[0].value : 0;	\
+       (ht)->size							\
+         && ((_hurd_ihash_item_t) _hurd_ihash_valuep) - &(ht)->items[0]	\
+            < (ht)->size						\
+         && (val = *_hurd_ihash_valuep, 1);				\
+       _hurd_ihash_valuep = (hurd_ihash_value_t *)			\
+	 (((_hurd_ihash_item_t) _hurd_ihash_valuep)++))			\
+    if (val != _HURD_IHASH_EMPTY && val != _HURD_IHASH_DELETED)
+
+/* 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 hurd_ihash_remove (hurd_ihash_t ht, hurd_ihash_key_t key);
+
+/* Remove the entry pointed to by the location pointer LOCP from the
+   hash table 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);
+
+#endif	/* _HURD_IHASH_H */