[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
new libihash implementation
|
From: |
Marcus Brinkmann |
|
Subject: |
new libihash implementation |
|
Date: |
Wed, 27 Aug 2003 23:34:49 +0200 |
|
User-agent: |
Mutt/1.5.4i |
Hi,
as promised, I rewrote libihash, at least most parts of it. This
implementation is lightly tested, thanks to Marco Gerards, I hope more
testing follows so that we can be confident about it.
This implementation has the following new features:
* Everything put into the hurd_ namespace.
* Uses unsigned int (I still have to change that to uint32_t) instead of a
signed type.
* Proper typedefs for all important user visible data types.
* Keys and values are interleaved in a single array, to bring them close to
each other. This should be easier on the memory cache. Also, calloc is
used instead malloc with initializer loop - so we don't necessarily need
to touch all pages immediately (depends on calloc implementation of
course).
* No memory is allocated for location pointers. Instead, they are required
to be always in a constant offset from the value pointer. This is always
the case in the Hurd. Also location pointers are optional (you decide if
to use them an initialization/creation time). This cuts down memory usage
by 33%.
* struct hurd_ihash can now officially be inlined in other structs, and even
statically initialized.
* New prime numbers generated of the form 4*i + 3. Instead of the whacky
i*k mod p probing, we use quadratic probing (k +/- i^2). Together with
the primes being 3 mod 4, this guarantees that all indices in the table
are tried. Previously this was only guaranteed if the key was not 0 mod p.
By hashing 3, 6, 7, 14, 17, 34, ... you could force libihash to allocate
a larger hash table with every second item! although there were lots of
free spaces. I think I actually saw this happen with proc (which would
hash all numbers 1, 2, 3, 4, etc and thus grow the hash table up to
whatever the largest PID is, instead of only up to the number of living
processes).
* In addition, hash tables perform badly if their load factor is high. So
I implemented a maximum load factor, that makes libihash to allocate a
bigger table if the number of used entries gets above a certain percentage.
The default is 80%, which is recommended by text books on hashing
algorithms.
* Iterating through the hash is now done by a macro instead of a function
with callback function. Callback functions are slow. Macros are fast.
The macro definition is a bit obscene, but it works well ;)
* Adding the same key twice actually does replace the old entry correctly
with calling the cleanup handler. This is thoroughly broken in the
current implementation.
There is still room for improvement:
* I didn't list all changes in the ihash changelog entry, but just said
"rewritten". I could and probably should fill the details in, though.
* Although _add replaces an existing entry, this is usually not needed and
makes _add perform badly because usually this means the cost for an
unsuccessful search are added. However, to change that I would have to
verify carefully that no user expects this behaviour, or if they do, to
change user code to use a new _replace function or just to not rely on it.
Usually code checks with _find anyway if the key exists.
I verified most of the Hurd code, but not very carefully, it seems
feasible. Auth might be an exception, but auth is broken anyway, for
example, I think it will do the wrong thing if you call authenticate with
the same rendezvous port twice (either in the user side or in the server
side). Auth should have cleanup handlers that cancel the pending
authentication if an existing key is added.
* A minimum load could be added to free memory. If this is an improvement
depends on the usage pattern though.
* An alternative hashing algorithm could use buckets for better deletion (so
you don't accumulate deleted entries over time). Probably only needed if we
don't change _add to not replace by default.
I want to postpone this for later, because I don't want to touch auth, and
also libports seemed peculiar (not to speak of rpctrace and the other users).
Ok to apply? Of course we will have to wait for Roland to come back.
Thanks,
Marcus
Index: auth/ChangeLog
===================================================================
RCS file: /cvsroot/hurd/hurd/auth/ChangeLog,v
retrieving revision 1.15
diff -u -p -r1.15 ChangeLog
--- auth/ChangeLog 8 May 2002 09:26:02 -0000 1.15
+++ auth/ChangeLog 27 Aug 2003 21:00:19 -0000
@@ -1,3 +1,14 @@
+2003-08-17 Marcus Brinkmann <address@hidden>
+
+ * 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.
+
2002-05-07 Roland McGrath <address@hidden>
* auth.c (S_auth_getids): u_int -> size_t
Index: auth/auth.c
===================================================================
RCS file: /cvsroot/hurd/hurd/auth/auth.c,v
retrieving revision 1.23
diff -u -p -r1.23 auth.c
--- auth/auth.c 8 May 2002 09:19:52 -0000 1.23
+++ auth/auth.c 27 Aug 2003 21:00:19 -0000
@@ -18,6 +18,7 @@
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
+#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <mach.h>
@@ -250,14 +251,10 @@ S_auth_makeauth (struct authhandle *auth
/* Transaction handling. */
-/* Table of pending transactions keyed on RENDEZVOUS. */
-struct ihash *pending_users, *pending_servers;
-struct mutex pending_lock = MUTEX_INITIALIZER;
-
/* A pending transaction. */
struct pending
{
- void **locp; /* Position in one of the ihash tables. */
+ hurd_ihash_locp_t locp; /* Position in one of the ihash tables. */
struct condition wakeup; /* The waiter is blocked on this condition. */
/* The user's auth handle. */
@@ -267,6 +264,13 @@ struct pending
mach_port_t passthrough;
};
+/* Table of pending transactions keyed on RENDEZVOUS. */
+struct hurd_ihash pending_users
+ = HURD_IHASH_INITIALIZER (offsetof (struct pending, locp));
+struct hurd_ihash pending_servers
+ = HURD_IHASH_INITIALIZER (offsetof (struct pending, locp));
+struct mutex pending_lock = MUTEX_INITIALIZER;
+
/* Implement auth_user_authenticate as described in <hurd/auth.defs>. */
kern_return_t
S_auth_user_authenticate (struct authhandle *userauth,
@@ -287,7 +291,7 @@ S_auth_user_authenticate (struct authhan
mutex_lock (&pending_lock);
/* Look for this port in the server list. */
- s = ihash_find (pending_servers, rendezvous);
+ s = hurd_ihash_find (&pending_servers, rendezvous);
if (s)
{
/* Found it! Extract the port. */
@@ -295,7 +299,7 @@ S_auth_user_authenticate (struct authhan
*newporttype = MACH_MSG_TYPE_MOVE_SEND;
/* Remove it from the pending list. */
- ihash_locp_remove (pending_servers, s->locp);
+ hurd_ihash_locp_remove (&pending_servers, s->locp);
/* Give the server the auth port and wake the RPC up.
We need to add a ref in case the port dies. */
@@ -315,7 +319,7 @@ S_auth_user_authenticate (struct authhan
struct pending u;
error_t err;
- err = ihash_add (pending_users, rendezvous, &u, &u.locp);
+ err = hurd_ihash_add (&pending_users, rendezvous, &u);
if (! err)
{
/* Store the user auth port and wait for the server RPC to wake
@@ -326,7 +330,7 @@ S_auth_user_authenticate (struct authhan
if (hurd_condition_wait (&u.wakeup, &pending_lock))
/* We were interrupted; remove our record. */
{
- ihash_locp_remove (pending_users, u.locp);
+ hurd_ihash_locp_remove (&pending_users, u.locp);
err = EINTR;
}
}
@@ -373,11 +377,11 @@ S_auth_server_authenticate (struct authh
mutex_lock (&pending_lock);
/* Look for this port in the user list. */
- u = ihash_find (pending_users, rendezvous);
+ u = hurd_ihash_find (&pending_users, rendezvous);
if (u)
{
/* Remove it from the pending list. */
- ihash_locp_remove (pending_users, u->locp);
+ hurd_ihash_locp_remove (&pending_users, u->locp);
/* Found it! We must add a ref because the one held by the
user RPC might die as soon as we unlock pending_lock. */
@@ -397,7 +401,7 @@ S_auth_server_authenticate (struct authh
struct pending s;
error_t err;
- err = ihash_add (pending_servers, rendezvous, &s, &s.locp);
+ err = hurd_ihash_add (&pending_servers, rendezvous, &s);
if (! err)
{
/* Store the new port and wait for the user RPC to wake us up. */
@@ -407,7 +411,7 @@ S_auth_server_authenticate (struct authh
if (hurd_condition_wait (&s.wakeup, &pending_lock))
/* We were interrupted; remove our record. */
{
- ihash_locp_remove (pending_servers, s.locp);
+ hurd_ihash_locp_remove (&pending_servers, s.locp);
err = EINTR;
}
}
@@ -493,12 +497,6 @@ main (int argc, char **argv)
hostpriv);
mach_port_deallocate (mach_task_self (), boot);
mach_port_deallocate (mach_task_self (), hostpriv);
-
- /* Allocate the hash tables. */
- err = ihash_create (&pending_users);
- assert_perror (err);
- err = ihash_create (&pending_servers);
- assert_perror (err);
/* Be a server. */
while (1)
Index: console-client/ChangeLog
===================================================================
RCS file: /cvsroot/hurd/hurd/console-client/ChangeLog,v
retrieving revision 1.12
diff -u -p -r1.12 ChangeLog
--- console-client/ChangeLog 15 Aug 2003 21:07:31 -0000 1.12
+++ console-client/ChangeLog 27 Aug 2003 21:00:20 -0000
@@ -1,3 +1,18 @@
+2003-08-17 Marcus Brinkmann <address@hidden>
+
+ * 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.
+
2003-08-11 Marco Gerards <address@hidden>
* console.c (cons_vcons_set_dimension): New function.
Index: console-client/vga-dynafont.c
===================================================================
RCS file: /cvsroot/hurd/hurd/console-client/vga-dynafont.c,v
retrieving revision 1.2
diff -u -p -r1.2 vga-dynafont.c
--- console-client/vga-dynafont.c 30 Sep 2002 17:13:14 -0000 1.2
+++ console-client/vga-dynafont.c 27 Aug 2003 21:00:22 -0000
@@ -18,6 +18,7 @@
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111, USA. */
+#include <stddef.h>
#include <assert.h>
#include <malloc.h>
#include <wchar.h>
@@ -65,7 +66,7 @@ struct mapped_character
wchar_t character;
/* Used by libihash for fast removal of elements. */
- void **locp;
+ hurd_ihash_locp_t locp;
};
@@ -88,7 +89,7 @@ struct dynafont
/* A hash containing a pointer to a struct mapped_character for each
UCS-4 character we map to a VGA font index. */
- ihash_t charmap;
+ struct hurd_ihash charmap;
/* The struct mapped_characters are preallocated for all vga font
index values. This points to an array of SIZE such elements. */
@@ -468,7 +469,6 @@ error_t
dynafont_new (bdf_font_t font, bdf_font_t font_italic, bdf_font_t font_bold,
bdf_font_t font_bold_italic, int size, dynafont_t *dynafont)
{
- error_t err = 0;
dynafont_t df;
struct bdf_glyph *glyph = NULL;
@@ -491,17 +491,10 @@ dynafont_new (bdf_font_t font, bdf_font_
df->font_bold_italic = font_bold_italic;
df->size = size;
df->cursor_standout = 0;
- err = ihash_create (&df->charmap);
- if (err)
- {
- free (df);
- return err;
- }
df->charmap_data = calloc (size, sizeof (struct mapped_character));
if (!df->charmap_data)
{
- ihash_free (df->charmap);
free (df);
return ENOMEM;
}
@@ -509,11 +502,13 @@ dynafont_new (bdf_font_t font, bdf_font_
df->vga_font = malloc (sizeof (vga_font_glyph) * size);
if (!df->vga_font)
{
- ihash_free (df->charmap);
free (df->charmap_data);
free (df);
return ENOMEM;
}
+
+ hurd_ihash_init (&df->charmap, offsetof (struct mapped_character, locp));
+
if (df->font->bbox.width == 9)
{
/* 32 from 256 font slots are for horizontal line graphic
@@ -556,8 +551,7 @@ dynafont_new (bdf_font_t font, bdf_font_
+ df->font->bbox.height, 0, 32 - df->font->bbox.height);
/* Update the hash table. */
- ihash_add (df->charmap, UNICODE_REPLACEMENT_CHARACTER,
- chr, &chr->locp);
+ hurd_ihash_add (&df->charmap, UNICODE_REPLACEMENT_CHARACTER, chr);
}
else
{
@@ -582,7 +576,7 @@ dynafont_new (bdf_font_t font, bdf_font_
}
*dynafont = df;
- return err;
+ return 0;
}
@@ -600,7 +594,7 @@ dynafont_free (dynafont_t df)
bdf_destroy (df->font_bold);
if (df->font_bold_italic)
bdf_destroy (df->font_bold_italic);
- ihash_free (df->charmap);
+ hurd_ihash_destroy (&df->charmap);
free (df->charmap_data);
free (df->vga_font);
free (df);
@@ -757,8 +751,8 @@ dynafont_lookup_internal (dynafont_t df,
wchar_t wide_chr, wchar_t attr, int *rpos)
{
/* When hashing the character, we mix in the font attribute. */
- struct mapped_character *chr = ihash_find (df->charmap,
- (int) (wide_chr | attr));
+ struct mapped_character *chr = hurd_ihash_find (&df->charmap,
+ (int) (wide_chr | attr));
int lgc;
struct bdf_glyph *glyph;
int pos;
@@ -867,8 +861,8 @@ dynafont_lookup_internal (dynafont_t df,
VGA_FONT_HEIGHT);
/* Update the hash table. */
if (chr->locp)
- ihash_locp_remove (df->charmap, chr->locp);
- ihash_add (df->charmap, (int) (wide_chr | attr), chr, &chr->locp);
+ hurd_ihash_locp_remove (&df->charmap, chr->locp);
+ hurd_ihash_add (&df->charmap, (int) (wide_chr | attr), chr);
*rpos = pos;
return 1;
}
@@ -1000,7 +994,11 @@ dynafont_change_font (dynafont_t df, bdf
/* The glyph is not used. If it is mapped, we need to
remove the mapping to invalidate the glyph. */
if (df->charmap_data[i].locp)
- ihash_locp_remove (df->charmap, df->charmap_data[i].locp);
+ {
+
+ hurd_ihash_locp_remove (&df->charmap, df->charmap_data[i].locp);
+ df->charmap_data[i].locp = NULL;
+ }
}
else
Index: ftpfs/ChangeLog
===================================================================
RCS file: /cvsroot/hurd/hurd/ftpfs/ChangeLog,v
retrieving revision 1.30
diff -u -p -r1.30 ChangeLog
--- ftpfs/ChangeLog 23 Oct 2002 02:36:59 -0000 1.30
+++ ftpfs/ChangeLog 27 Aug 2003 21:00:23 -0000
@@ -1,3 +1,17 @@
+2003-08-17 Marcus Brinkmann <address@hidden>
+
+ * 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.
+
2002-10-18 Moritz Schulte <address@hidden>
* dir.c (ftpfs_dir_lookup): Initialize NES.entry.
Index: ftpfs/fs.c
===================================================================
RCS file: /cvsroot/hurd/hurd/ftpfs/fs.c,v
retrieving revision 1.4
diff -u -p -r1.4 fs.c
--- ftpfs/fs.c 29 Dec 2001 00:19:39 -0000 1.4
+++ ftpfs/fs.c 27 Aug 2003 21:00:24 -0000
@@ -1,6 +1,6 @@
/* Fs operations
- Copyright (C) 1997,2001 Free Software Foundation, Inc.
+ Copyright (C) 1997, 2001, 2003 Free Software Foundation, Inc.
Written by Miles Bader <address@hidden>
This file is part of the GNU Hurd.
@@ -18,6 +18,7 @@
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111, USA. */
+#include <stddef.h>
#include <string.h>
#include <hurd/ihash.h>
@@ -59,24 +60,25 @@ ftpfs_create (char *rmt_path, int fsid,
new->ftp_params = ftp_params;
new->ftp_hooks = ftp_hooks;
- err = ihash_create (&new->inode_mappings);
+ hurd_ihash_init (&new->inode_mappings,
+ offsetof (struct ftpfs_dir_entry, inode_locp));
spin_lock_init (&new->inode_mappings_lock);
- if (! err)
+ super_root = netfs_make_node (0);
+ if (! super_root)
+ err = ENOMEM;
+ else
{
- super_root = netfs_make_node (0);
- if (! super_root)
- err = ENOMEM;
- else
- {
- err = ftpfs_dir_create (new, super_root, rmt_path, &super_root_dir);
- if (! err)
- err = ftpfs_dir_null_lookup (super_root_dir, &new->root);
- }
+ err = ftpfs_dir_create (new, super_root, rmt_path, &super_root_dir);
+ if (! err)
+ err = ftpfs_dir_null_lookup (super_root_dir, &new->root);
}
if (err)
- free (new);
+ {
+ hurd_ihash_destroy (&new->inode_mappings);
+ free (new);
+ }
else
*fs = new;
Index: ftpfs/ftpfs.h
===================================================================
RCS file: /cvsroot/hurd/hurd/ftpfs/ftpfs.h,v
retrieving revision 1.4
diff -u -p -r1.4 ftpfs.h
--- ftpfs/ftpfs.h 18 Aug 1997 18:51:05 -0000 1.4
+++ ftpfs/ftpfs.h 27 Aug 2003 21:00:24 -0000
@@ -25,6 +25,7 @@
#include <cthreads.h>
#include <ftpconn.h>
#include <maptime.h>
+#include <hurd/ihash.h>
/* Anonymous types. */
struct ccache;
@@ -58,7 +59,7 @@ struct ftpfs_dir_entry
/* When the presence/absence of this file was last checked. */
time_t name_timestamp;
- void **inode_locp; /* Used for removing this entry */
+ hurd_ihash_locp_t inode_locp; /* Used for removing this entry */
int noent : 1; /* A negative lookup result. */
int valid : 1; /* Marker for GC'ing. */
@@ -173,7 +174,7 @@ struct ftpfs
int fsid;
/* A hash table mapping inode numbers to directory entries. */
- struct ihash *inode_mappings;
+ struct hurd_ihash inode_mappings;
spin_lock_t inode_mappings_lock;
struct ftpfs_params params;
Index: ftpfs/node.c
===================================================================
RCS file: /cvsroot/hurd/hurd/ftpfs/node.c,v
retrieving revision 1.1
diff -u -p -r1.1 node.c
--- ftpfs/node.c 6 Aug 1997 22:08:35 -0000 1.1
+++ ftpfs/node.c 27 Aug 2003 21:00:24 -0000
@@ -61,7 +61,7 @@ ftpfs_create_node (struct ftpfs_dir_entr
ftpfs_maptime);
spin_lock (&nn->fs->inode_mappings_lock);
- ihash_add (nn->fs->inode_mappings, e->stat.st_ino, new, &e->inode_locp);
+ hurd_ihash_add (&nn->fs->inode_mappings, e->stat.st_ino, new);
spin_unlock (&nn->fs->inode_mappings_lock);
e->node = new;
@@ -92,7 +92,7 @@ netfs_node_norefs (struct node *node)
/* Remove this entry from the set of known inodes. */
spin_lock (&nn->fs->inode_mappings_lock);
- ihash_locp_remove (nn->fs->inode_mappings, nn->dir_entry->inode_locp);
+ hurd_ihash_locp_remove (&nn->fs->inode_mappings, nn->dir_entry->inode_locp);
spin_unlock (&nn->fs->inode_mappings_lock);
if (nn->contents)
Index: libihash/ChangeLog
===================================================================
RCS file: /cvsroot/hurd/hurd/libihash/ChangeLog,v
retrieving revision 1.5
diff -u -p -r1.5 ChangeLog
--- libihash/ChangeLog 15 Aug 2001 09:29:37 -0000 1.5
+++ libihash/ChangeLog 27 Aug 2003 21:00:30 -0000
@@ -1,3 +1,26 @@
+2003-08-17 Marcus Brinkmann <address@hidden>
+
+ * 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 <address@hidden>
+
+ * ihash.h (struct ihash): Change type of IDS to unsigned int *.
+ (ihash_add): Change type of ID argument in prototype to unsigned.
+ (ihash_find): Likewise.
+ (ihash_remove): Likewise.
+ * ihash.c (index_valid): Change type of ID to unsigned.
+ (find_index): Likewise. Also for H and FIRSTH.
+ (ihash_add): Likewise. Also for H and FIRSTH. Change type of
+ OLD_IDS to unsigned int *.
+ (ihash_find): Likewise.
+ (ihash_remove): Likewise.
+ * ihash.c (find_index): Use UINT_MAX instead -1.
+ (ihash_add): Likewise.
+
2001-08-15 Roland McGrath <address@hidden>
* sizes.c: New file, a list of prime numbers useful for table sizes.
Index: libihash/Makefile
===================================================================
RCS file: /cvsroot/hurd/hurd/libihash/Makefile,v
retrieving revision 1.3
diff -u -p -r1.3 Makefile
--- libihash/Makefile 15 Aug 2001 09:29:26 -0000 1.3
+++ libihash/Makefile 27 Aug 2003 21:00:30 -0000
@@ -1,5 +1,5 @@
#
-# Copyright (C) 1995,96,2001 Free Software Foundation, Inc.
+# Copyright (C) 1995, 1996, 2001, 2003 Free Software Foundation, Inc.
#
# This file is part of the GNU Hurd.
#
@@ -21,9 +21,9 @@ dir := libihash
makemode := library
libname := libihash
-SRCS = ihash.c sizes.c
+SRCS = ihash.c
installhdrs = ihash.h
-LCLHDRS = $(installhdrs) priv.h
+LCLHDRS = $(installhdrs)
OBJS = $(SRCS:.c=.o)
Index: libihash/ihash.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libihash/ihash.c,v
retrieving revision 1.6
diff -u -p -r1.6 ihash.c
--- libihash/ihash.c 15 Aug 2001 09:29:26 -0000 1.6
+++ libihash/ihash.c 27 Aug 2003 21:00:30 -0000
@@ -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 <address@hidden>.
+ Revised by Marcus Brinkmann <address@hidden>.
+
This file is part of the GNU Hurd.
- Written by Michael I. Bushnell; revised by Miles Bader <address@hidden>.
-
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,421 @@
along with the GNU Hurd; see the file COPYING. If not, write to
the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
+#include <errno.h>
#include <string.h>
#include <stdlib.h>
+#include <limits.h>
+#include <stdint.h>
+#include <assert.h>
-#include "ihash.h"
-#include "priv.h"
-
-/* ---------------------------------------------------------------- */
+#include <hurd/ihash.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;
+
+ if (ht->items[idx].value == _HURD_IHASH_EMPTY || ht->items[idx].key == key)
+ return idx;
+
+ /* 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;
- 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;
+ /* After (ht->size - 1) / 2 iterations, this will be 0. */
+ i = (i + 2) % ht->size;
+ }
+ while (i);
- return h;
+ /* If we end up here, the item could not be found. Return any
+ invalid index. */
+ return idx;
}
+
+
+/* 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)
+{
+ if (ht->cleanup)
+ (*ht->cleanup) (*locp, ht->cleanup_data);
+ *locp = _HURD_IHASH_DELETED;
+ ht->nr_items--;
+}
+
-/* ---------------------------------------------------------------- */
+/* Construction and destruction of hash tables. */
-/* 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)
+/* Initialize the hash table at address HT. */
+void
+hurd_ihash_init (hurd_ihash_t ht, off_t locp_offs)
{
- *ht = malloc(sizeof(struct ihash));
- if (*ht == NULL)
- return ENOMEM;
- (*ht)->size = 0;
- (*ht)->cleanup = 0;
- (*ht)->cleanup_arg = 0;
- return 0;
+ ht->nr_items = 0;
+ ht->size = 0;
+ ht->locp_offset = locp_offs;
+ ht->max_load = HURD_IHASH_MAX_LOAD_DEFAULT;
+ ht->cleanup = 0;
}
-/* Free HT and all resources it consumes. */
+
+/* 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
-ihash_free(ihash_t ht)
+hurd_ihash_destroy (hurd_ihash_t ht)
{
- void (*cleanup)(void *value, void *arg) = ht->cleanup;
-
- if (cleanup)
+ 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);
- free(ht);
+ return 0;
}
-/* 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. */
+
+/* Destroy the hash table HT and release the memory allocated for it
+ by hurd_ihash_create(). */
void
-ihash_set_cleanup(ihash_t ht,
- void (*cleanup)(void *value, void *arg),
- void *arg)
+hurd_ihash_free (hurd_ihash_t ht)
{
- ht->cleanup = cleanup;
- ht->cleanup_arg = arg;
+ hurd_ihash_destroy (ht);
+ free (ht);
}
+
-/* ---------------------------------------------------------------- */
+/* 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)
+{
+ ht->cleanup = cleanup;
+ ht->cleanup_data = cleanup_data;
+}
-/* 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)
+
+/* 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)
{
- if (ht->size)
- {
- int h, firsth = -1;
+ ht->max_load = max_load;
+}
- /* 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;
+
+/* 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)
+{
+ unsigned int idx;
+ unsigned int first_free;
+
+ 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;
- ht->tab[h] = item;
- ht->ids[h] = id;
- ht->locps[h] = locp;
+ /* After (ht->size - 1) / 2 iterations, this will be 0. */
+ i = (i + 2) % ht->size;
+ }
+ while (i);
+ }
- if (locp)
- *locp = &ht->tab[h];
+ /* Remove the old entry for this key if necessary. */
+ if (index_valid (ht, idx, key))
+ locp_remove (ht, &ht->items[idx].value);
+
+ /* 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;
+
+ if (ht->locp_offset != HURD_IHASH_NO_LOCP)
+ *((hurd_ihash_locp_t) (((char *) value) + ht->locp_offset))
+ = &ht->items[first_free].value;
- return 0;
- }
+ 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));
+ return 0;
+}
- 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);
-
- 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;
+ }
- for (i = ht->size, entry = ht->tab; i > 0; i--, entry++)
- *entry = HASH_EMPTY;
+ /* 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. */
+
+ 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);
}
Index: libihash/ihash.h
===================================================================
RCS file: /cvsroot/hurd/hurd/libihash/ihash.h,v
retrieving revision 1.4
diff -u -p -r1.4 ihash.h
--- libihash/ihash.h 25 Apr 1996 05:01:46 -0000 1.4
+++ libihash/ihash.h 27 Aug 2003 21:00:30 -0000
@@ -1,97 +1,242 @@
-/* Integer-keyed hash table functions.
+/* ihash.h - Integer keyed hash table interface.
+ Copyright (C) 1995, 2003 Free Software Foundation, Inc.
+ Written by Miles Bader <address@hidden>.
+ Revised by Marcus Brinkmann <address@hidden>.
- Copyright (C) 1995 Free Software Foundation, Inc.
+ This file is part of the GNU Hurd.
- Written by Miles Bader <address@hidden>
-
- 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>
+
+
+/* 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 entry in the hash table is _HURD_IHASH_EMPTY or
+ _HURD_IHASH_DELETED, then the location is available, and none of
+ the other arrays 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 unsigned int 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;
+
+
+/* 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 _hurd_ihash_item
+{
+ /* 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;
+
+ /* The integer key of this hash item. */
+ hurd_ihash_key_t key;
+};
+typedef struct _hurd_ihash_item *_hurd_ihash_item_t;
-typedef struct ihash *ihash_t;
-struct ihash
+struct hurd_ihash
{
- /* An array storing the elements in the hash table (each a void *). */
- void **tab;
+ /* The number of hashed elements. */
+ size_t nr_items;
- /* An array storing the integer key for each element. */
- int *ids;
+ /* An array of (key, value) pairs. */
+ _hurd_ihash_item_t items;
- /* 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 */
-
- /* The length of all these arrays. */
- int size;
-
- /* 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;
+
+ /* The offset of the location pointer from the hash value. */
+ off_t locp_offset;
+
+ /* The maximum load factor in percent. */
+ int max_load;
+
+ /* 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;
+
+
+/* Construction and destruction of hash tables. */
+
+/* The default value for the maximum load factor in percent. */
+#define HURD_IHASH_MAX_LOAD_DEFAULT 80
+
+
+#define HURD_IHASH_NO_LOCP INT_MIN
+
-/* 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
+#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);
+
+
+/* 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);
+
+
+/* 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 ihash_add(ihash_t ht, int id, void *item, void ***locp);
+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 hash table HT with key ID, or NULL if it
- doesn't exist. */
-void *ihash_find(ihash_t ht, int id);
-
-/* 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 *));
-
-/* 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);
-
-/* 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);
+/* 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 via the macro
+ HURD_IHASH_ITERATOR_VALUE. */
+
+/* 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 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 /* __IHASH_H__ */
+#endif /* _HURD_IHASH_H */
Index: libports/ChangeLog
===================================================================
RCS file: /cvsroot/hurd/hurd/libports/ChangeLog,v
retrieving revision 1.17
diff -u -p -r1.17 ChangeLog
--- libports/ChangeLog 31 Mar 2001 23:07:03 -0000 1.17
+++ libports/ChangeLog 27 Aug 2003 21:00:31 -0000
@@ -1,3 +1,33 @@
+2003-08-17 Marcus Brinkmann <address@hidden>
+
+ * 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.
+
2001-03-29 Neal H Walfield <address@hidden>
* claim-right.c (ports_claim_right): Include errno.h and
Index: libports/bucket-iterate.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libports/bucket-iterate.c,v
retrieving revision 1.5
diff -u -p -r1.5 bucket-iterate.c
--- libports/bucket-iterate.c 28 Feb 1999 20:50:37 -0000 1.5
+++ libports/bucket-iterate.c 27 Aug 2003 21:00:31 -0000
@@ -30,7 +30,7 @@ _ports_bucket_class_iterate (struct port
struct port_class *class,
error_t (*fun)(void *))
{
- /* This is obsecenely ineffecient. ihash and ports need to cooperate
+ /* This is obscenely ineffecient. ihash and ports need to cooperate
more closely to do it effeciently. */
struct item
{
@@ -40,7 +40,8 @@ _ports_bucket_class_iterate (struct port
struct item *i, *nxt;
error_t err;
- error_t enqueue (void *arg)
+ mutex_lock (&_ports_lock);
+ HURD_IHASH_ITERATE (&bucket->htable, arg)
{
struct port_info *const pi = arg;
struct item *j;
@@ -53,11 +54,7 @@ _ports_bucket_class_iterate (struct port
list = j;
pi->refcnt++;
}
- return 0;
}
-
- mutex_lock (&_ports_lock);
- ihash_iterate (bucket->htable, enqueue);
mutex_unlock (&_ports_lock);
err = 0;
Index: libports/claim-right.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libports/claim-right.c,v
retrieving revision 1.5
diff -u -p -r1.5 claim-right.c
--- libports/claim-right.c 31 Mar 2001 23:06:48 -0000 1.5
+++ libports/claim-right.c 27 Aug 2003 21:00:31 -0000
@@ -35,7 +35,7 @@ ports_claim_right (void *portstruct)
return ret;
mutex_lock (&_ports_lock);
- ihash_locp_remove (pi->bucket->htable, pi->hentry);
+ hurd_ihash_locp_remove (&pi->bucket->htable, pi->hentry);
err = mach_port_move_member (mach_task_self (), ret, MACH_PORT_NULL);
assert_perror (err);
pi->port_right = MACH_PORT_NULL;
Index: libports/class-iterate.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libports/class-iterate.c,v
retrieving revision 1.1
diff -u -p -r1.1 class-iterate.c
--- libports/class-iterate.c 28 Feb 1999 20:51:27 -0000 1.1
+++ libports/class-iterate.c 27 Aug 2003 21:00:33 -0000
@@ -19,7 +19,6 @@
#include "ports.h"
#include <cthreads.h>
-#include <hurd/ihash.h>
error_t
ports_class_iterate (struct port_class *class,
Index: libports/complete-deallocate.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libports/complete-deallocate.c,v
retrieving revision 1.3
diff -u -p -r1.3 complete-deallocate.c
--- libports/complete-deallocate.c 29 Mar 1996 15:22:50 -0000 1.3
+++ libports/complete-deallocate.c 27 Aug 2003 21:00:33 -0000
@@ -30,7 +30,7 @@ _ports_complete_deallocate (struct port_
if (pi->port_right)
{
- ihash_locp_remove (pi->bucket->htable, pi->hentry);
+ hurd_ihash_locp_remove (&pi->bucket->htable, pi->hentry);
mach_port_mod_refs (mach_task_self (), pi->port_right,
MACH_PORT_RIGHT_RECEIVE, -1);
pi->port_right = MACH_PORT_NULL;
Index: libports/create-bucket.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libports/create-bucket.c,v
retrieving revision 1.3
diff -u -p -r1.3 create-bucket.c
--- libports/create-bucket.c 31 Mar 2001 23:06:50 -0000 1.3
+++ libports/create-bucket.c 27 Aug 2003 21:00:33 -0000
@@ -1,5 +1,5 @@
/* Create a port bucket
- Copyright (C) 1995, 1997, 2001 Free Software Foundation, Inc.
+ Copyright (C) 1995, 1997, 2001, 2003 Free Software Foundation, Inc.
Written by Michael I. Bushnell.
This file is part of the GNU Hurd.
@@ -19,6 +19,7 @@
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
#include "ports.h"
+#include <stddef.h>
#include <errno.h>
#include <stdlib.h>
#include <hurd/ihash.h>
@@ -46,16 +47,7 @@ ports_create_bucket ()
return NULL;
}
- err = ihash_create (&ret->htable);
- if (err)
- {
- errno = err;
- mach_port_mod_refs (mach_task_self (), ret->portset,
- MACH_PORT_RIGHT_PORT_SET, -1);
- free (ret);
- return NULL;
- }
-
+ hurd_ihash_init (&ret->htable, offsetof (struct port_info, hentry));
ret->rpcs = ret->flags = ret->count = 0;
mutex_lock (&_ports_lock);
Index: libports/create-internal.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libports/create-internal.c,v
retrieving revision 1.2
diff -u -p -r1.2 create-internal.c
--- libports/create-internal.c 31 Mar 2001 23:06:43 -0000 1.2
+++ libports/create-internal.c 27 Aug 2003 21:00:33 -0000
@@ -82,7 +82,7 @@ _ports_create_port_internal (struct port
goto loop;
}
- err = ihash_add (bucket->htable, port, pi, &pi->hentry);
+ err = hurd_ihash_add (&bucket->htable, port, pi);
if (err)
goto lose;
Index: libports/destroy-right.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libports/destroy-right.c,v
retrieving revision 1.3
diff -u -p -r1.3 destroy-right.c
--- libports/destroy-right.c 28 Feb 1999 20:51:52 -0000 1.3
+++ libports/destroy-right.c 27 Aug 2003 21:00:33 -0000
@@ -32,7 +32,7 @@ ports_destroy_right (void *portstruct)
if (pi->port_right != MACH_PORT_NULL)
{
mutex_lock (&_ports_lock);
- ihash_locp_remove (pi->bucket->htable, pi->hentry);
+ hurd_ihash_locp_remove (&pi->bucket->htable, pi->hentry);
err = mach_port_mod_refs (mach_task_self (), pi->port_right,
MACH_PORT_RIGHT_RECEIVE, -1);
assert_perror (err);
Index: libports/import-port.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libports/import-port.c,v
retrieving revision 1.1
diff -u -p -r1.1 import-port.c
--- libports/import-port.c 18 Jul 1996 04:31:47 -0000 1.1
+++ libports/import-port.c 27 Aug 2003 21:00:33 -0000
@@ -76,7 +76,7 @@ ports_import_port (struct port_class *cl
goto loop;
}
- err = ihash_add (bucket->htable, port, pi, &pi->hentry);
+ err = hurd_ihash_add (&bucket->htable, port, pi);
if (err)
goto lose;
Index: libports/inhibit-all-rpcs.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libports/inhibit-all-rpcs.c,v
retrieving revision 1.6
diff -u -p -r1.6 inhibit-all-rpcs.c
--- libports/inhibit-all-rpcs.c 25 Jul 2000 22:34:00 -0000 1.6
+++ libports/inhibit-all-rpcs.c 27 Aug 2003 21:00:33 -0000
@@ -36,26 +36,25 @@ ports_inhibit_all_rpcs ()
{
struct port_bucket *bucket;
int this_one = 0;
- error_t interruptor (void *portstruct)
- {
- struct rpc_info *rpc;
- struct port_info *pi = portstruct;
- for (rpc = pi->current_rpcs; rpc; rpc = rpc->next)
+ for (bucket = _ports_all_buckets; bucket; bucket = bucket->next)
+ {
+ HURD_IHASH_ITERATE (&bucket->htable, portstruct)
{
- /* Avoid cancelling the calling thread if it's currently
- handling a RPC. */
- if (rpc->thread == hurd_thread_self ())
- this_one = 1;
- else
- hurd_thread_cancel (rpc->thread);
+ struct rpc_info *rpc;
+ struct port_info *pi = portstruct;
+
+ for (rpc = pi->current_rpcs; rpc; rpc = rpc->next)
+ {
+ /* Avoid cancelling the calling thread if it's currently
+ handling a RPC. */
+ if (rpc->thread == hurd_thread_self ())
+ this_one = 1;
+ else
+ hurd_thread_cancel (rpc->thread);
+ }
}
-
- return 0;
}
-
- for (bucket = _ports_all_buckets; bucket; bucket = bucket->next)
- ihash_iterate (bucket->htable, interruptor);
while (_ports_total_rpcs > this_one)
{
Index: libports/inhibit-bucket-rpcs.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libports/inhibit-bucket-rpcs.c,v
retrieving revision 1.5
diff -u -p -r1.5 inhibit-bucket-rpcs.c
--- libports/inhibit-bucket-rpcs.c 25 Jul 2000 22:34:00 -0000 1.5
+++ libports/inhibit-bucket-rpcs.c 27 Aug 2003 21:00:33 -0000
@@ -35,7 +35,8 @@ ports_inhibit_bucket_rpcs (struct port_b
else
{
int this_one = 0;
- error_t interruptor (void *portstruct)
+
+ HURD_IHASH_ITERATE (&bucket->htable, portstruct)
{
struct rpc_info *rpc;
struct port_info *pi = portstruct;
@@ -48,11 +49,8 @@ ports_inhibit_bucket_rpcs (struct port_b
else
hurd_thread_cancel (rpc->thread);
}
-
- return 0;
}
- ihash_iterate (bucket->htable, interruptor);
while (bucket->rpcs > this_one)
{
Index: libports/lookup-port.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libports/lookup-port.c,v
retrieving revision 1.3
diff -u -p -r1.3 lookup-port.c
--- libports/lookup-port.c 22 Jun 1995 17:52:39 -0000 1.3
+++ libports/lookup-port.c 27 Aug 2003 21:00:33 -0000
@@ -32,11 +32,11 @@ ports_lookup_port (struct port_bucket *b
mutex_lock (&_ports_lock);
if (bucket)
- pi = ihash_find (bucket->htable, port);
+ pi = hurd_ihash_find (&bucket->htable, port);
else
for (bucket = _ports_all_buckets; bucket; bucket = bucket->next)
{
- pi = ihash_find (bucket->htable, port);
+ pi = hurd_ihash_find (&bucket->htable, port);
if (pi)
break;
}
Index: libports/ports.h
===================================================================
RCS file: /cvsroot/hurd/hurd/libports/ports.h,v
retrieving revision 1.27
diff -u -p -r1.27 ports.h
--- libports/ports.h 17 Mar 2000 10:24:30 -0000 1.27
+++ libports/ports.h 27 Aug 2003 21:00:34 -0000
@@ -24,6 +24,7 @@
#include <mach.h>
#include <stdlib.h>
#include <hurd.h>
+#include <hurd/ihash.h>
#include <mach/notify.h>
/* These are global values for common flags used in the various structures.
@@ -45,7 +46,7 @@ struct port_info
mach_port_t port_right;
struct rpc_info *current_rpcs;
struct port_bucket *bucket;
- void **hentry;
+ hurd_ihash_locp_t hentry;
struct port_info *next, **prevp; /* links on port_class list */
};
/* FLAGS above are the following: */
@@ -57,7 +58,7 @@ struct port_info
struct port_bucket
{
mach_port_t portset;
- struct ihash *htable;
+ struct hurd_ihash htable;
int rpcs;
int flags;
int count;
Index: libports/reallocate-from-external.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libports/reallocate-from-external.c,v
retrieving revision 1.5
diff -u -p -r1.5 reallocate-from-external.c
--- libports/reallocate-from-external.c 29 Mar 1996 15:23:38 -0000 1.5
+++ libports/reallocate-from-external.c 27 Aug 2003 21:00:34 -0000
@@ -1,5 +1,5 @@
/*
- Copyright (C) 1995, 1996 Free Software Foundation, Inc.
+ Copyright (C) 1995, 1996, 2003 Free Software Foundation, Inc.
Written by Michael I. Bushnell.
This file is part of the GNU Hurd.
@@ -44,7 +44,7 @@ ports_reallocate_from_external (void *po
MACH_PORT_RIGHT_RECEIVE, -1);
assert_perror (err);
- ihash_locp_remove (pi->bucket->htable, pi->hentry);
+ hurd_ihash_locp_remove (&pi->bucket->htable, pi->hentry);
if ((pi->flags & PORT_HAS_SENDRIGHTS) && !stat.mps_srights)
{
@@ -61,7 +61,7 @@ ports_reallocate_from_external (void *po
pi->cancel_threshold = 0;
pi->mscount = stat.mps_mscount;
- ihash_add (pi->bucket->htable, receive, pi, &pi->hentry);
+ hurd_ihash_add (&pi->bucket->htable, receive, pi);
mutex_unlock (&_ports_lock);
mach_port_move_member (mach_task_self (), receive, pi->bucket->portset);
Index: libports/reallocate-port.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libports/reallocate-port.c,v
retrieving revision 1.5
diff -u -p -r1.5 reallocate-port.c
--- libports/reallocate-port.c 31 Mar 2001 23:06:37 -0000 1.5
+++ libports/reallocate-port.c 27 Aug 2003 21:00:34 -0000
@@ -1,5 +1,5 @@
/*
- Copyright (C) 1995, 1996, 2001 Free Software Foundation, Inc.
+ Copyright (C) 1995, 1996, 2001, 2003 Free Software Foundation, Inc.
Written by Michael I. Bushnell.
This file is part of the GNU Hurd.
@@ -37,7 +37,7 @@ ports_reallocate_port (void *portstruct)
MACH_PORT_RIGHT_RECEIVE, -1);
assert_perror (err);
- ihash_locp_remove (pi->bucket->htable, pi->hentry);
+ hurd_ihash_locp_remove (&pi->bucket->htable, pi->hentry);
err = mach_port_allocate (mach_task_self (), MACH_PORT_RIGHT_RECEIVE,
&pi->port_right);
@@ -49,7 +49,7 @@ ports_reallocate_port (void *portstruct)
}
pi->cancel_threshold = 0;
pi->mscount = 0;
- ihash_add (pi->bucket->htable, pi->port_right, pi, &pi->hentry);
+ hurd_ihash_add (&pi->bucket->htable, pi->port_right, pi);
mutex_unlock (&_ports_lock);
err = mach_port_move_member (mach_task_self (), pi->port_right,
Index: libports/transfer-right.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libports/transfer-right.c,v
retrieving revision 1.3
diff -u -p -r1.3 transfer-right.c
--- libports/transfer-right.c 31 Mar 2001 23:06:37 -0000 1.3
+++ libports/transfer-right.c 27 Aug 2003 21:00:35 -0000
@@ -1,5 +1,5 @@
/* Transfer the receive right from one port structure to another
- Copyright (C) 1996 Free Software Foundation, Inc.
+ Copyright (C) 1996, 2003 Free Software Foundation, Inc.
Written by Michael I. Bushnell, p/BSG.
This file is part of the GNU Hurd.
@@ -41,7 +41,7 @@ ports_transfer_right (void *tostruct,
port = frompi->port_right;
if (port != MACH_PORT_NULL)
{
- ihash_locp_remove (frompi->bucket->htable, frompi->hentry);
+ hurd_ihash_locp_remove (&frompi->bucket->htable, frompi->hentry);
frompi->port_right = MACH_PORT_NULL;
if (frompi->flags & PORT_HAS_SENDRIGHTS)
{
@@ -54,7 +54,7 @@ ports_transfer_right (void *tostruct,
/* Destroy the existing right in TOPI. */
if (topi->port_right != MACH_PORT_NULL)
{
- ihash_locp_remove (topi->bucket->htable, topi->hentry);
+ hurd_ihash_locp_remove (&topi->bucket->htable, topi->hentry);
err = mach_port_mod_refs (mach_task_self (), topi->port_right,
MACH_PORT_RIGHT_RECEIVE, -1);
assert_perror (err);
@@ -77,7 +77,7 @@ ports_transfer_right (void *tostruct,
if (port)
{
- ihash_add (topi->bucket->htable, port, topi, &topi->hentry);
+ hurd_ihash_add (&topi->bucket->htable, port, topi);
if (topi->bucket != frompi->bucket)
{
err = mach_port_move_member (mach_task_self (), port,
Index: libps/ChangeLog
===================================================================
RCS file: /cvsroot/hurd/hurd/libps/ChangeLog,v
retrieving revision 1.31
diff -u -p -r1.31 ChangeLog
--- libps/ChangeLog 9 Jun 2002 19:25:33 -0000 1.31
+++ libps/ChangeLog 27 Aug 2003 21:00:38 -0000
@@ -1,3 +1,19 @@
+2003-08-17 Marcus Brinkmann <address@hidden>
+
+ * 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.
+
2002-06-09 Roland McGrath <address@hidden>
* Makefile (installhdrs): List just ps.h, not common.h as well.
Index: libps/context.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libps/context.c,v
retrieving revision 1.8
diff -u -p -r1.8 context.c
--- libps/context.c 8 May 2002 09:22:36 -0000 1.8
+++ libps/context.c 27 Aug 2003 21:00:38 -0000
@@ -34,39 +34,23 @@
error_t
ps_context_create (process_t server, struct ps_context **pc)
{
- error_t err_procs, err_ttys, err_ttys_by_cttyid, err_users;
-
*pc = NEW (struct ps_context);
if (*pc == NULL)
return ENOMEM;
(*pc)->server = server;
(*pc)->user_hooks = 0;
- err_procs = ihash_create (&(*pc)->procs);
- err_ttys = ihash_create (&(*pc)->ttys);
- err_ttys_by_cttyid = ihash_create (&(*pc)->ttys_by_cttyid);
- err_users = ihash_create (&(*pc)->users);
-
- if (err_procs || err_ttys || err_ttys_by_cttyid)
- /* Some allocation error occurred, backout any successful ones and fail. */
- {
- if (!err_procs) ihash_free ((*pc)->procs);
- if (!err_users) ihash_free ((*pc)->users);
- if (!err_ttys) ihash_free ((*pc)->ttys);
- if (!err_ttys_by_cttyid) ihash_free ((*pc)->ttys_by_cttyid);
- free (*pc);
- return ENOMEM;
- }
-
- ihash_set_cleanup ((*pc)->procs,
- (void (*)(void *, void *arg))_proc_stat_free,
- NULL);
- ihash_set_cleanup ((*pc)->ttys,
- (void (*)(void *, void *arg))ps_tty_free,
- NULL);
- ihash_set_cleanup ((*pc)->users,
- (void (*)(void *, void *arg))ps_user_free,
- NULL);
+ hurd_ihash_init (&(*pc)->procs, HURD_IHASH_NO_LOCP);
+ hurd_ihash_init (&(*pc)->ttys, HURD_IHASH_NO_LOCP);
+ hurd_ihash_init (&(*pc)->ttys_by_cttyid, HURD_IHASH_NO_LOCP);
+ hurd_ihash_init (&(*pc)->users, HURD_IHASH_NO_LOCP);
+
+ hurd_ihash_set_cleanup (&(*pc)->procs,
+ (hurd_ihash_cleanup_t) _proc_stat_free, NULL);
+ hurd_ihash_set_cleanup (&(*pc)->ttys,
+ (hurd_ihash_cleanup_t) ps_tty_free, NULL);
+ hurd_ihash_set_cleanup (&(*pc)->users,
+ (hurd_ihash_cleanup_t) ps_user_free, NULL);
return 0;
}
@@ -75,12 +59,13 @@ ps_context_create (process_t server, str
void
ps_context_free (struct ps_context *pc)
{
- ihash_free (pc->procs);
- ihash_free (pc->ttys);
- ihash_free (pc->ttys_by_cttyid);
- ihash_free (pc->users);
+ hurd_ihash_destroy (&pc->procs);
+ hurd_ihash_destroy (&pc->ttys);
+ hurd_ihash_destroy (&pc->ttys_by_cttyid);
+ hurd_ihash_destroy (&pc->users);
free (pc);
}
+
/* ---------------------------------------------------------------- */
@@ -89,15 +74,16 @@ ps_context_free (struct ps_context *pc)
(CREATE should return either an error-code or 0 if no error occurs), and
cache it in HT. */
static error_t
-lookup (int id, ihash_t ht, error_t (*create)(int id, void **), void **value)
+lookup (int id, hurd_ihash_t ht, error_t (*create)(int id, void **),
+ void **value)
{
- *value = ihash_find (ht, id);
+ *value = hurd_ihash_find (ht, id);
if (*value == NULL)
{
error_t err = create (id, value);
if (err)
return err;
- ihash_add (ht, id, *value, NULL);
+ hurd_ihash_add (ht, id, *value);
}
return 0;
}
@@ -111,7 +97,7 @@ ps_context_find_proc_stat (struct ps_con
{
return _proc_stat_create (pid, pc, (struct proc_stat **)value);
}
- return lookup (pid, pc->procs, create, (void **)ps);
+ return lookup (pid, &pc->procs, create, (void **)ps);
}
/* Find a ps_tty for the terminal referred to by the port TTY_PORT, and
@@ -121,9 +107,9 @@ ps_context_find_tty (struct ps_context *
struct ps_tty **tty)
{
return lookup (tty_port,
- pc->ttys,
- (error_t (*)(int id, void **result))ps_tty_create,
- (void **)tty);
+ &pc->ttys,
+ (error_t (*)(int id, void **result))ps_tty_create,
+ (void **)tty);
}
/* Find a ps_tty for the terminal referred to by the ctty id port
@@ -151,7 +137,7 @@ ps_context_find_tty_by_cttyid (struct ps
}
}
- return lookup (cttyid_port, pc->ttys_by_cttyid, create, (void **)tty);
+ return lookup (cttyid_port, &pc->ttys_by_cttyid, create, (void **)tty);
}
/* Find a ps_user for the user referred to by UID, and return it in U. */
@@ -159,7 +145,7 @@ error_t
ps_context_find_user (struct ps_context *pc, uid_t uid, struct ps_user **u)
{
return lookup (uid,
- pc->users,
- (error_t (*)(int id, void **result))ps_user_create,
- (void **)u);
+ &pc->users,
+ (error_t (*)(int id, void **result))ps_user_create,
+ (void **) u);
}
Index: libps/ps.h
===================================================================
RCS file: /cvsroot/hurd/hurd/libps/ps.h,v
retrieving revision 1.35
diff -u -p -r1.35 ps.h
--- libps/ps.h 13 May 2002 22:23:15 -0000 1.35
+++ libps/ps.h 27 Aug 2003 21:00:41 -0000
@@ -125,17 +125,17 @@ struct ps_context
process_t server;
/* proc_stats for every process we know about, indexed by process id. */
- ihash_t procs;
+ struct hurd_ihash procs;
/* ps_ttys for every tty we know about, indexed by the terminal port. */
- ihash_t ttys;
+ struct hurd_ihash ttys;
/* ps_ttys for every tty we know about, indexed by their ctty id port
(from libc). */
- ihash_t ttys_by_cttyid;
+ struct hurd_ihash ttys_by_cttyid;
/* A ps_user for every user we know about, indexed by user-id. */
- ihash_t users;
+ struct hurd_ihash users;
/* Functions that can be set to extend the behavior of proc_stats. */
struct ps_user_hooks *user_hooks;
Index: libpthread/ChangeLog
===================================================================
RCS file: /cvsroot/hurd/hurd/libpthread/ChangeLog,v
retrieving revision 1.7
diff -u -p -r1.7 ChangeLog
--- libpthread/ChangeLog 26 Nov 2002 17:50:48 -0000 1.7
+++ libpthread/ChangeLog 27 Aug 2003 21:00:46 -0000
@@ -1,3 +1,17 @@
+2003-08-17 Marcus Brinkmann <address@hidden>
+
+ * 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.
+
2002-11-26 Neal H. Walfield <address@hidden>
* pthread/pt-create.c [HAVE_USELOCAL]: Include <locale.h>.
Index: libpthread/sysdeps/hurd/pt-destroy-specific.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libpthread/sysdeps/hurd/pt-destroy-specific.c,v
retrieving revision 1.2
diff -u -p -r1.2 pt-destroy-specific.c
--- libpthread/sysdeps/hurd/pt-destroy-specific.c 13 Oct 2002 00:58:03
-0000 1.2
+++ libpthread/sysdeps/hurd/pt-destroy-specific.c 27 Aug 2003 21:00:46
-0000
@@ -50,10 +50,10 @@ __pthread_destroy_specific (struct __pth
if (__pthread_key_destructors[i] == PTHREAD_KEY_INVALID)
break;
- value = ihash_find (thread->thread_specifics, i);
+ value = hurd_ihash_find (thread->thread_specifics, i);
if (value)
{
- err = ihash_remove (thread->thread_specifics, i);
+ err = hurd_ihash_remove (thread->thread_specifics, i);
assert (err == 1);
if (__pthread_key_destructors[i])
@@ -74,6 +74,6 @@ __pthread_destroy_specific (struct __pth
sched_yield ();
}
- ihash_free (thread->thread_specifics);
+ hurd_ihash_free (thread->thread_specifics);
thread->thread_specifics = 0;
}
Index: libpthread/sysdeps/hurd/pt-getspecific.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libpthread/sysdeps/hurd/pt-getspecific.c,v
retrieving revision 1.1
diff -u -p -r1.1 pt-getspecific.c
--- libpthread/sysdeps/hurd/pt-getspecific.c 10 Oct 2002 23:05:05 -0000
1.1
+++ libpthread/sysdeps/hurd/pt-getspecific.c 27 Aug 2003 21:00:46 -0000
@@ -33,5 +33,5 @@ pthread_getspecific (pthread_key_t key)
if (! self->thread_specifics)
return 0;
- return ihash_find (self->thread_specifics, key);
+ return hurd_ihash_find (self->thread_specifics, key);
}
Index: libpthread/sysdeps/hurd/pt-key.h
===================================================================
RCS file: /cvsroot/hurd/hurd/libpthread/sysdeps/hurd/pt-key.h,v
retrieving revision 1.1
diff -u -p -r1.1 pt-key.h
--- libpthread/sysdeps/hurd/pt-key.h 10 Oct 2002 23:05:05 -0000 1.1
+++ libpthread/sysdeps/hurd/pt-key.h 27 Aug 2003 21:00:46 -0000
@@ -21,7 +21,7 @@
#include <hurd/ihash.h>
#define PTHREAD_KEY_MEMBERS \
- ihash_t thread_specifics;
+ hurd_ihash_t thread_specifics;
#define PTHREAD_KEY_INVALID (void *) (-1)
Index: libpthread/sysdeps/hurd/pt-setspecific.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libpthread/sysdeps/hurd/pt-setspecific.c,v
retrieving revision 1.1
diff -u -p -r1.1 pt-setspecific.c
--- libpthread/sysdeps/hurd/pt-setspecific.c 10 Oct 2002 23:05:05 -0000
1.1
+++ libpthread/sysdeps/hurd/pt-setspecific.c 27 Aug 2003 21:00:46 -0000
@@ -30,12 +30,12 @@ pthread_setspecific (pthread_key_t key,
if (! self->thread_specifics)
{
- err = ihash_create (&self->thread_specifics);
+ err = hurd_ihash_create (&self->thread_specifics, HURD_IHASH_NO_LOCP);
if (err)
return ENOMEM;
}
- err = ihash_add (self->thread_specifics, key, (void *) value, 0);
+ err = hurd_ihash_add (self->thread_specifics, key, (void *) value);
if (err)
return ENOMEM;
Index: proc/ChangeLog
===================================================================
RCS file: /cvsroot/hurd/hurd/proc/ChangeLog,v
retrieving revision 1.59
diff -u -p -r1.59 ChangeLog
--- proc/ChangeLog 16 Aug 2003 22:19:37 -0000 1.59
+++ proc/ChangeLog 27 Aug 2003 21:00:52 -0000
@@ -1,3 +1,32 @@
+2003-08-26 Marcus Brinkmann <address@hidden>
+
+ * hash.c:
+
+2003-08-17 Marcus Brinkmann <address@hidden>
+
+ * 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.
+
2003-08-17 Marcus Brinkmann <address@hidden>
* mgt.c (S_proc_dostop): Revert last change.
Index: proc/hash.c
===================================================================
RCS file: /cvsroot/hurd/hurd/proc/hash.c,v
retrieving revision 1.10
diff -u -p -r1.10 hash.c
--- proc/hash.c 4 Feb 1997 03:10:27 -0000 1.10
+++ proc/hash.c 27 Aug 2003 21:00:53 -0000
@@ -20,6 +20,7 @@ the Free Software Foundation, 675 Mass A
/* Written by Michael I. Bushnell. */
#include <mach.h>
+#include <stddef.h>
#include <sys/types.h>
#include <hurd/hurd_types.h>
#include <string.h>
@@ -29,14 +30,22 @@ the Free Software Foundation, 675 Mass A
#include "proc.h"
#include <hurd/ihash.h>
-static struct ihash pghash, pidhash, taskhash, sidhash;
+static struct hurd_ihash pghash
+ = HURD_IHASH_INITIALIZER (offsetof (struct pgrp, pg_hashloc));
+static struct hurd_ihash pidhash
+ = HURD_IHASH_INITIALIZER (offsetof (struct proc, p_pidhashloc));
+static struct hurd_ihash taskhash
+ = HURD_IHASH_INITIALIZER (offsetof (struct proc, p_taskhashloc));
+static struct hurd_ihash sidhash
+ = HURD_IHASH_INITIALIZER (offsetof (struct session, s_hashloc));
+
/* Find the process corresponding to a given pid. */
struct proc *
pid_find (pid_t pid)
{
struct proc *p;
- p = ihash_find (&pidhash, pid);
+ p = hurd_ihash_find (&pidhash, pid);
return (!p || p->p_dead) ? 0 : p;
}
@@ -45,7 +54,7 @@ pid_find (pid_t pid)
struct proc *
pid_find_allow_zombie (pid_t pid)
{
- return ihash_find (&pidhash, pid);
+ return hurd_ihash_find (&pidhash, pid);
}
/* Find the process corresponding to a given task. */
@@ -53,7 +62,7 @@ struct proc *
task_find (task_t task)
{
struct proc *p;
- p = ihash_find (&taskhash, task) ? : add_tasks (task);
+ p = hurd_ihash_find (&taskhash, task) ? : add_tasks (task);
return (!p || p->p_dead) ? 0 : p;
}
@@ -63,7 +72,7 @@ struct proc *
task_find_nocreate (task_t task)
{
struct proc *p;
- p = ihash_find (&taskhash, task);
+ p = hurd_ihash_find (&taskhash, task);
return (!p || p->p_dead) ? 0 : p;
}
@@ -82,58 +91,58 @@ reqport_find (mach_port_t reqport)
struct pgrp *
pgrp_find (pid_t pgid)
{
- return ihash_find (&pghash, pgid);
+ return hurd_ihash_find (&pghash, pgid);
}
/* Find the session corresponding to a given sid. */
struct session *
session_find (pid_t sid)
{
- return ihash_find (&sidhash, sid);
+ return hurd_ihash_find (&sidhash, sid);
}
/* Add a new process to the various hash tables. */
void
add_proc_to_hash (struct proc *p)
{
- ihash_add (&pidhash, p->p_pid, p, &p->p_pidhashloc);
- ihash_add (&taskhash, p->p_task, p, &p->p_taskhashloc);
+ hurd_ihash_add (&pidhash, p->p_pid, p);
+ hurd_ihash_add (&taskhash, p->p_task, p);
}
/* Add a new process group to the various hash tables. */
void
add_pgrp_to_hash (struct pgrp *pg)
{
- ihash_add (&pghash, pg->pg_pgid, pg, &pg->pg_hashloc);
+ hurd_ihash_add (&pghash, pg->pg_pgid, pg);
}
/* Add a new session to the various hash tables. */
void
add_session_to_hash (struct session *s)
{
- ihash_add (&sidhash, s->s_sid, s, &s->s_hashloc);
+ hurd_ihash_add (&sidhash, s->s_sid, s);
}
/* Remove a process group from the various hash tables. */
void
remove_pgrp_from_hash (struct pgrp *pg)
{
- ihash_locp_remove(0, pg->pg_hashloc);
+ hurd_ihash_locp_remove (&pghash, pg->pg_hashloc);
}
/* Remove a process from the various hash tables. */
void
remove_proc_from_hash (struct proc *p)
{
- ihash_locp_remove(0, p->p_pidhashloc);
- ihash_locp_remove(0, p->p_taskhashloc);
+ hurd_ihash_locp_remove (&pidhash, p->p_pidhashloc);
+ hurd_ihash_locp_remove (&taskhash, p->p_taskhashloc);
}
/* Remove a session from the various hash tables. */
void
remove_session_from_hash (struct session *s)
{
- ihash_locp_remove(0, s->s_hashloc);
+ hurd_ihash_locp_remove (&sidhash, s->s_hashloc);
}
/* Call function FUN of two args for each process. FUN's first arg is
@@ -141,14 +150,12 @@ remove_session_from_hash (struct session
void
prociterate (void (*fun) (struct proc *, void *), void *arg)
{
- error_t thunk(void *value)
+ HURD_IHASH_ITERATE (&pidhash, value)
{
struct proc *p = value;
if (!p->p_dead)
(*fun)(p, arg);
- return 0;
}
- ihash_iterate(&pidhash, thunk);
}
/* Tell if a pid is available for use */
Index: proc/proc.h
===================================================================
RCS file: /cvsroot/hurd/hurd/proc/proc.h,v
retrieving revision 1.27
diff -u -p -r1.27 proc.h
--- proc/proc.h 22 Dec 2001 21:00:25 -0000 1.27
+++ proc/proc.h 27 Aug 2003 21:00:53 -0000
@@ -25,6 +25,7 @@ the Free Software Foundation, 675 Mass A
#include <sys/resource.h>
#include <sys/mman.h>
#include <hurd/ports.h>
+#include <hurd/ihash.h>
#include <cthreads.h>
struct proc
@@ -35,8 +36,8 @@ struct proc
struct proc *p_gnext, **p_gprevp; /* process group */
/* Hash table pointers that point here */
- void **p_pidhashloc; /* by pid */
- void **p_taskhashloc; /* by task port */
+ hurd_ihash_locp_t p_pidhashloc; /* by pid */
+ hurd_ihash_locp_t p_taskhashloc; /* by task port */
/* Identification of this process */
task_t p_task;
@@ -89,7 +90,7 @@ typedef struct proc *pstruct_t;
struct pgrp
{
- void **pg_hashloc;
+ hurd_ihash_locp_t pg_hashloc;
struct proc *pg_plist; /* member processes */
struct pgrp *pg_next, **pg_prevp; /* list of pgrps in session */
pid_t pg_pgid;
@@ -99,7 +100,7 @@ struct pgrp
struct session
{
- void **s_hashloc;
+ hurd_ihash_locp_t s_hashloc;
pid_t s_sid;
struct pgrp *s_pgrps; /* list of member pgrps */
mach_port_t s_sessionid; /* receive right */
Index: trans/ChangeLog
===================================================================
RCS file: /cvsroot/hurd/hurd/trans/ChangeLog,v
retrieving revision 1.87
diff -u -p -r1.87 ChangeLog
--- trans/ChangeLog 6 Mar 2003 02:24:58 -0000 1.87
+++ trans/ChangeLog 27 Aug 2003 21:00:56 -0000
@@ -1,3 +1,15 @@
+2003-08-17 Marcus Brinkmann <address@hidden>
+
+ * 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.
+
2003-03-05 Roland McGrath <address@hidden>
Make /hurd/magic support translator delegation via /servers/magic.
Index: trans/fakeroot.c
===================================================================
RCS file: /cvsroot/hurd/hurd/trans/fakeroot.c,v
retrieving revision 1.20
diff -u -p -r1.20 fakeroot.c
--- trans/fakeroot.c 9 Jun 2002 19:46:06 -0000 1.20
+++ trans/fakeroot.c 27 Aug 2003 21:00:58 -0000
@@ -1,5 +1,5 @@
/* fakeroot -- a translator for faking actions that aren't really permitted
- Copyright (C) 2002 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2003 Free Software Foundation, Inc.
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License as
@@ -16,6 +16,7 @@
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
#include <hurd/netfs.h>
+#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <argp.h>
@@ -40,7 +41,7 @@ static auth_t fakeroot_auth_port;
struct netnode
{
- void **idport_locp; /* easy removal pointer in idport ihash */
+ hurd_ihash_locp_t idport_locp;/* easy removal pointer in idport ihash */
mach_port_t idport; /* port from io_identity */
int openmodes; /* O_READ | O_WRITE | O_EXEC */
file_t file; /* port on real file */
@@ -55,7 +56,8 @@ struct netnode
#define FAKE_REFERENCE (1 << 4) /* got node_norefs with st_nlink > 0 */
struct mutex idport_ihash_lock = MUTEX_INITIALIZER;
-struct ihash idport_ihash;
+struct hurd_ihash idport_ihash
+ = HURD_IHASH_INITIALIZER (offsetof (struct netnode, idport_locp));
/* Make a new virtual node. Always consumes the ports. */
@@ -102,7 +104,7 @@ new_node (file_t file, mach_port_t idpor
{
if (!locked)
mutex_lock (&idport_ihash_lock);
- err = ihash_add (&idport_ihash, nn->idport, *np, &nn->idport_locp);
+ err = hurd_ihash_add (&idport_ihash, nn->idport, *np);
if (!err)
netfs_nref (*np); /* Return a reference to the caller. */
mutex_unlock (&idport_ihash_lock);
@@ -149,7 +151,7 @@ netfs_node_norefs (struct node *np)
mutex_unlock (&idport_ihash_lock);
return;
}
- ihash_locp_remove (&idport_ihash, np->nn->idport_locp);
+ hurd_ihash_locp_remove (&idport_ihash, np->nn->idport_locp);
mutex_unlock (&idport_ihash_lock);
mach_port_deallocate (mach_task_self (), np->nn->file);
mach_port_deallocate (mach_task_self (), np->nn->idport);
@@ -299,7 +301,7 @@ netfs_S_dir_lookup (struct protid *dirus
else
{
mutex_lock (&idport_ihash_lock);
- np = ihash_find (&idport_ihash, idport);
+ np = hurd_ihash_find (&idport_ihash, idport);
if (np != 0)
{
/* We already know about this node. */
Index: utils/ChangeLog
===================================================================
RCS file: /cvsroot/hurd/hurd/utils/ChangeLog,v
retrieving revision 1.145
diff -u -p -r1.145 ChangeLog
--- utils/ChangeLog 3 Aug 2003 14:19:32 -0000 1.145
+++ utils/ChangeLog 27 Aug 2003 21:01:03 -0000
@@ -1,3 +1,19 @@
+2003-08-17 Marcus Brinkmann <address@hidden>
+
+ * 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.
+
2002-06-16 James A. Morrison <address@hidden>
* vmstat.c (vm_state_refresh): Use memset instead of bzero.
Index: utils/rpctrace.c
===================================================================
RCS file: /cvsroot/hurd/hurd/utils/rpctrace.c,v
retrieving revision 1.14
diff -u -p -r1.14 rpctrace.c
--- utils/rpctrace.c 28 May 2002 23:56:25 -0000 1.14
+++ utils/rpctrace.c 27 Aug 2003 21:01:05 -0000
@@ -32,6 +32,7 @@
#include <version.h>
#include <sys/wait.h>
#include <inttypes.h>
+#include <stddef.h>
const char *argp_program_version = STANDARD_HURD_VERSION (rpctrace);
@@ -65,7 +66,8 @@ msgid_ihash_cleanup (void *element, void
free (info);
}
-static struct ihash msgid_ihash = { cleanup: msgid_ihash_cleanup };
+static struct hurd_ihash msgid_ihash
+ = HURD_IHASH_INITIALIZER (HURD_IHASH_NO_LOCP);
/* Parse a file of RPC names and message IDs as output by mig's -list
option: "subsystem base-id routine n request-id reply-id". Put each
@@ -104,9 +106,9 @@ parse_msgid_list (const char *filename)
error (1, errno, "malloc");
info->name = name;
info->subsystem = subsystem;
- err = ihash_add (&msgid_ihash, msgid, info, NULL);
+ err = hurd_ihash_add (&msgid_ihash, msgid, info);
if (err)
- error (1, err, "ihash_add");
+ error (1, err, "hurd_ihash_add");
}
}
@@ -120,7 +122,7 @@ parse_msgid_list (const char *filename)
static const struct msgid_info *
msgid_info (mach_msg_id_t msgid)
{
- const struct msgid_info *info = ihash_find (&msgid_ihash, msgid);
+ const struct msgid_info *info = hurd_ihash_find (&msgid_ihash, msgid);
if (info == 0 && (msgid / 100) % 2 == 1)
{
/* This message ID is not in the table, and its number makes it
@@ -128,7 +130,7 @@ msgid_info (mach_msg_id_t msgid)
ID of the corresponding RPC request and synthesize a name from
that. Then stash that name in the table so the next time the
lookup will match directly. */
- info = ihash_find (&msgid_ihash, msgid - 100);
+ info = hurd_ihash_find (&msgid_ihash, msgid - 100);
if (info != 0)
{
struct msgid_info *reply_info = malloc (sizeof *info);
@@ -137,7 +139,7 @@ msgid_info (mach_msg_id_t msgid)
reply_info->subsystem = strdup (info->subsystem);
reply_info->name = 0;
asprintf (&reply_info->name, "%s-reply", info->name);
- ihash_add (&msgid_ihash, msgid, reply_info, NULL);
+ hurd_ihash_add (&msgid_ihash, msgid, reply_info);
info = reply_info;
}
else
@@ -188,7 +190,7 @@ struct traced_info
struct /* For a send right wrapper. */
{
- void **locp; /* position in the traced_names hash table */
+ hurd_ihash_locp_t locp; /* position in the traced_names hash table */
} send;
struct /* For a send-once right wrapper. */
@@ -207,7 +209,8 @@ struct traced_info
static struct traced_info *freelist;
-ihash_t traced_names;
+struct hurd_ihash traced_names
+ = HURD_IHASH_INITIALIZER (offsetof (struct traced_info, u.send.locp));
struct port_class *traced_class;
struct port_bucket *traced_bucket;
FILE *ostream;
@@ -263,7 +266,7 @@ new_send_wrapper (mach_port_t right, mac
/* Store it in the reverse-lookup hash table, so we can
look up this same right again to find the wrapper port.
The entry in the hash table holds a weak ref on INFO. */
- err = ihash_add (traced_names, info->forward, info, &info->u.send.locp);
+ err = hurd_ihash_add (&traced_names, info->forward, info);
assert_perror (err);
ports_port_ref_weak (info);
assert (info->u.send.locp != 0);
@@ -329,7 +332,7 @@ traced_dropweak (void *pi)
assert (info->u.send.locp);
/* Remove INFO from the hash table. */
- ihash_locp_remove (traced_names, info->u.send.locp);
+ hurd_ihash_locp_remove (&traced_names, info->u.send.locp);
ports_port_deref_weak (info);
/* Deallocate the forward port, so the real port also sees no-senders. */
@@ -362,7 +365,7 @@ rewrite_right (mach_port_t *right, mach_
{
case MACH_MSG_TYPE_PORT_SEND:
/* See if we are already tracing this port. */
- info = ihash_find (traced_names, *right);
+ info = hurd_ihash_find (&traced_names, *right);
if (info)
{
/* We are already tracing this port. We will pass on a right
@@ -416,7 +419,7 @@ rewrite_right (mach_port_t *right, mach_
mach_port_t rr; /* B */
char *name;
- info = ihash_find (traced_names, *right);
+ info = hurd_ihash_find (&traced_names, *right);
if (info)
{
/* This is a receive right that we have been tracing sends to. */
@@ -444,8 +447,7 @@ rewrite_right (mach_port_t *right, mach_
assert_perror (err);
info->forward = rr;
- err = ihash_add (traced_names, info->forward, info,
- &info->u.send.locp);
+ err = hurd_ihash_add (&traced_names, info->forward, info);
assert_perror (err);
ports_port_ref_weak (info);
@@ -1106,8 +1108,7 @@ main (int argc, char **argv, char **envp
traced_bucket = ports_create_bucket ();
traced_class = ports_create_class (0, &traced_dropweak);
- err = ihash_create (&traced_names);
- assert_perror (err);
+ hurd_ihash_set_cleanup (&msgid_ihash, msgid_ihash_cleanup, 0);
/* Spawn a single thread that will receive intercepted messages, print
them, and interpose on the ports they carry. The access to the
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- new libihash implementation,
Marcus Brinkmann <=
- Prev by Date:
gone
- Previous by thread:
gone
- Index(es):