diff options
41 files changed, 890 insertions, 672 deletions
diff --git a/auth/ChangeLog b/auth/ChangeLog index 2bf57316..caddb11f 100644 --- a/auth/ChangeLog +++ b/auth/ChangeLog @@ -1,3 +1,14 @@ +2003-08-17 Marcus Brinkmann <marcus@gnu.org> + + * auth.c: Include <stddef.h>. + (pending_users, pending_server): Change type to struct hurd_ihash, + initialize with HURD_IHASH_INITIALIZER. + (struct pending): Change type of member LOCP to hurd_ihash_locp_t. + (S_auth_user_authenticate): Use hurd_ihash_* functions instead + ihash_*. + (S_auth_server_authenticate): Likewise. + (main): Do not allocate the hash tables. + 2002-05-07 Roland McGrath <roland@frob.com> * auth.c (S_auth_getids): u_int -> size_t diff --git a/auth/auth.c b/auth/auth.c index e2628760..3c5fa861 100644 --- a/auth/auth.c +++ b/auth/auth.c @@ -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 authhandle *userauth, 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 authhandle *userauth, *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 authhandle *userauth, 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 authhandle *userauth, 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 authhandle *serverauth, 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 authhandle *serverauth, 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 authhandle *serverauth, 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; } } @@ -494,12 +498,6 @@ main (int argc, char **argv) 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) ports_manage_port_operations_multithread (auth_bucket, diff --git a/console-client/ChangeLog b/console-client/ChangeLog index 5a313fa2..a3fdd3f6 100644 --- a/console-client/ChangeLog +++ b/console-client/ChangeLog @@ -1,3 +1,18 @@ +2003-08-17 Marcus Brinkmann <marcus@gnu.org> + + * vga-dynafont.c: Include <stddef.h>. + (struct mapped_character): Change type of LOCP to + hurd_ihash_locp_t. + (struct dynafont): Change type of CHARMAP to struct hurd_ihash. + (dynafont_new): Use hurd_ihash_init instead of ihash_create. + Remove variable ERR. Call hurd_ihash_add instead of ihash_add. + (dynafont_free): Call hurd_ihash_destroy, no ihash_free. + (dynafont_lookup_internal): Use hurd_ihash_find, not ihash_find. + (dynafont_lookup_internal): Call hurd_ihash_locp_remove instead + ihash_locp_remove, and hurd_ihash_add instead ihash_add. + (dynafont_change_font): Likewise. Clean out LOCP if character is + unmapped. + 2004-02-02 Marco Gerards <metgerards@student.han.nl> * pc-kbd.c (KDSETLEDS): New macro. diff --git a/console-client/vga-dynafont.c b/console-client/vga-dynafont.c index 97ca2d83..0cce5176 100644 --- a/console-client/vga-dynafont.c +++ b/console-client/vga-dynafont.c @@ -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_t font_italic, bdf_font_t font_bold, 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_t font_italic, bdf_font_t font_bold, 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_t font_italic, bdf_font_t font_bold, + 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_t font_italic, bdf_font_t font_bold, } *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, bdf_font_t font, 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, bdf_font_t font, 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_font_t font) /* 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 diff --git a/ftpfs/ChangeLog b/ftpfs/ChangeLog index c58cfb3e..b53da74f 100644 --- a/ftpfs/ChangeLog +++ b/ftpfs/ChangeLog @@ -1,3 +1,17 @@ +2003-08-17 Marcus Brinkmann <marcus@gnu.org> + + * ftpfs.h: Include <hurd/ihash.h>. + (struct ftpfs): Change type of INODE_MAPPINGS to struct + hurd_ihash. + (struct ftpfs_dir_entry): Change type of INODE_LOCP to + hurd_ihash_locp_t. + * node.c (ftpfs_create_node): Call hurd_ihash_add, not ihash_add. + (netfs_node_norefs): Call hurd_ihash_locp_remove, not + ihash_locp_remove. + * fs.c: Include <stddef.h>. + (ftpfs_create): Call hurd_ihash_init, not hurd_ihash_create. + Call hurd_ihash_destroy on error. + 2002-10-18 Moritz Schulte <moritz@duesseldorf.ccc.de> * dir.c (ftpfs_dir_lookup): Initialize NES.entry. @@ -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 <miles@gnu.org> 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; diff --git a/ftpfs/ftpfs.h b/ftpfs/ftpfs.h index 0ca67aa4..d1d816d7 100644 --- a/ftpfs/ftpfs.h +++ b/ftpfs/ftpfs.h @@ -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; diff --git a/ftpfs/node.c b/ftpfs/node.c index 73af41f2..1d15a686 100644 --- a/ftpfs/node.c +++ b/ftpfs/node.c @@ -61,7 +61,7 @@ ftpfs_create_node (struct ftpfs_dir_entry *e, const char *rmt_path, 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) diff --git a/libihash/ChangeLog b/libihash/ChangeLog index 093bfe06..5e662950 100644 --- a/libihash/ChangeLog +++ b/libihash/ChangeLog @@ -1,3 +1,11 @@ +2003-08-17 Marcus Brinkmann <marcus@gnu.org> + + * ihash.c: Rewritten. + * ihash.h: Rewritten. + * Makefile (SRCS): Remove sizes.c. + (LCLHDRS): Remove priv.h. + * primes.c, sizes.c, priv.h: Files removed. + 2001-08-15 Roland McGrath <roland@frob.com> * sizes.c: New file, a list of prime numbers useful for table sizes. diff --git a/libihash/Makefile b/libihash/Makefile index 902ff6d3..e0258241 100644 --- a/libihash/Makefile +++ b/libihash/Makefile @@ -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) diff --git a/libihash/ihash.c b/libihash/ihash.c index dfc36b01..51cca82b 100644 --- a/libihash/ihash.c +++ b/libihash/ihash.c @@ -1,11 +1,11 @@ -/* Integer-keyed hash table functions. - - Copyright (C) 1993,94,95,96,97,2001 Free Software Foundation, Inc. - +/* ihash.c - Integer-keyed hash table functions. + Copyright (C) 1993-1997, 2001, 2003 Free Software Foundation, Inc. + Written by Michael I. Bushnell. + Revised by Miles Bader <miles@gnu.org>. + Revised by Marcus Brinkmann <marcus@gnu.org>. + This file is part of the GNU Hurd. - Written by Michael I. Bushnell; revised by Miles Bader <miles@gnu.org>. - The GNU Hurd is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) @@ -20,266 +20,423 @@ along with the GNU Hurd; see the file COPYING. If not, write to the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ +#if HAVE_CONFIG_H +#include <config.h> +#endif + +#include <errno.h> #include <string.h> #include <stdlib.h> +#include <limits.h> +#include <stdint.h> +#include <assert.h> + +#include <hurd/ihash.h> -#include "ihash.h" -#include "priv.h" - -/* ---------------------------------------------------------------- */ - -/* When an entry in a hashtable's TAB array is HASH_EMPTY, that location is - available, and none of the other arrays are valid at that index. */ -#define HASH_EMPTY 0 - -/* When an entry in a hashtable's TAB array is HASH_DEL, that location is - available, and none of the other arrays are valid at that index. The - difference from HASH_EMPTY is that searches continue though HASH_DEL and - stop at HASH_EMPTY. */ -#define HASH_DEL ((void *) -1) - -/* Returns an initial index in HT for the key ID, for search for an entry. */ -#define HASH(ht, id) ((id) % (ht)->size) -/* Returns subsequent indices in HT for the key ID, given the previous one. */ -#define REHASH(ht, id, h) (((id) + (h)) % (ht)->size) -/* ---------------------------------------------------------------- */ +/* The prime numbers of the form 4 * i + 3 for some i, all greater + than twice the previous one and smaller than 2^40 (for now). */ +static const uint64_t ihash_sizes[] = +{ + 3, + 7, + 19, + 43, + 103, + 211, + 431, + 863, + 1747, + 3499, + 7019, + 14051, + 28111, + 56239, + 112507, + 225023, + 450067, + 900139, + 1800311, + 3600659, + 7201351, + 14402743, + 28805519, + 57611039, + 115222091, + 230444239, + 460888499, + 921777067, + 1843554151, + UINT64_C (3687108307), + UINT64_C (7374216631), + UINT64_C (14748433279), + UINT64_C (29496866579), + UINT64_C (58993733159), + UINT64_C (117987466379), + UINT64_C (235974932759), + UINT64_C (471949865531), + UINT64_C (943899731087) +}; + +static const unsigned int ihash_nsizes = (sizeof ihash_sizes + / sizeof ihash_sizes[0]); + +/* Return 1 if the slot with the index IDX in the hash table HT is + empty, and 0 otherwise. */ static inline int -index_empty(ihash_t ht, int index) +index_empty (hurd_ihash_t ht, unsigned int idx) { - return ht->tab[index] == HASH_EMPTY || ht->tab[index] == HASH_DEL; + return ht->items[idx].value == _HURD_IHASH_EMPTY + || ht->items[idx].value == _HURD_IHASH_DELETED; } + +/* Return 1 if the index IDX in the hash table HT is occupied by the + element with the key KEY. */ static inline int -index_valid(ihash_t ht, int index, int id) +index_valid (hurd_ihash_t ht, unsigned int idx, hurd_ihash_key_t key) { - return !index_empty(ht, index) && ht->ids[index] == id; + return !index_empty (ht, idx) && ht->items[idx].key == key; } -/* Given a hash table HT, and a key ID, finds the index in the table of that - key. You must subsequently check to see whether the given index is valid - (with index_valid() or index_empty()). */ + +/* Given a hash table HT, and a key KEY, find the index in the table + of that key. You must subsequently check with index_valid() if the + returned index is valid. */ static inline int -find_index(ihash_t ht, int id) +find_index (hurd_ihash_t ht, hurd_ihash_key_t key) { - int h, firsth = -1; + unsigned int idx; + unsigned int i; + unsigned int up_idx; + unsigned int down_idx; + + idx = key % ht->size; - for (h = HASH(ht, id); - ht->tab[h] != HASH_EMPTY && ht->ids[h] != id && h != firsth; - h = REHASH(ht, id, h)) - if (firsth == -1) - firsth = h; + if (ht->items[idx].value == _HURD_IHASH_EMPTY || ht->items[idx].key == key) + return idx; - return h; + /* Instead of calculating idx + 1, idx + 4, idx + 9, ..., idx + i^2, + we add 1, 3, 5, 7, etc to the previous index. We do this in both + directions separately. */ + i = 1; + up_idx = idx; + down_idx = idx; + + do + { + up_idx = (up_idx + i) % ht->size; + if (ht->items[up_idx].value == _HURD_IHASH_EMPTY + || ht->items[up_idx].key == key) + return up_idx; + + if (down_idx < i) + down_idx += ht->size; + down_idx = (down_idx - i) % ht->size; + if (ht->items[down_idx].value == _HURD_IHASH_EMPTY + || ht->items[down_idx].key == key) + return down_idx; + + /* After (ht->size - 1) / 2 iterations, this will be 0. */ + i = (i + 2) % ht->size; + } + while (i); + + /* If we end up here, the item could not be found. Return any + invalid index. */ + return idx; } - -/* ---------------------------------------------------------------- */ -/* Create an integer hash table and return it in HT. If a memory allocation - error occurs, ENOMEM is returned, otherwise 0. */ -error_t -ihash_create(ihash_t *ht) + +/* Remove the entry pointed to by the location pointer LOCP from the + hashtable HT. LOCP is the location pointer of which the address + was provided to hurd_ihash_add(). */ +static inline void +locp_remove (hurd_ihash_t ht, hurd_ihash_locp_t locp) { - *ht = malloc(sizeof(struct ihash)); - if (*ht == NULL) - return ENOMEM; - (*ht)->size = 0; - (*ht)->cleanup = 0; - (*ht)->cleanup_arg = 0; - return 0; + if (ht->cleanup) + (*ht->cleanup) (*locp, ht->cleanup_data); + *locp = _HURD_IHASH_DELETED; + ht->nr_items--; } -/* Free HT and all resources it consumes. */ + +/* Construction and destruction of hash tables. */ + +/* Initialize the hash table at address HT. */ void -ihash_free(ihash_t ht) +hurd_ihash_init (hurd_ihash_t ht, off_t locp_offs) { - void (*cleanup)(void *value, void *arg) = ht->cleanup; + ht->nr_items = 0; + ht->size = 0; + ht->locp_offset = locp_offs; + ht->max_load = HURD_IHASH_MAX_LOAD_DEFAULT; + ht->cleanup = 0; +} - if (cleanup) + +/* Destroy the hash table at address HT. This first removes all + elements which are still in the hash table, and calling the cleanup + function for them (if any). */ +void +hurd_ihash_destroy (hurd_ihash_t ht) +{ + if (ht->cleanup) { - int i; - void *arg = ht->cleanup_arg; - for (i = 0; i < ht->size; i++) - if (!index_empty(ht, i)) - (*cleanup)(ht->tab[i], arg); + hurd_ihash_cleanup_t cleanup = ht->cleanup; + void *cleanup_data = ht->cleanup_data; + + HURD_IHASH_ITERATE (ht, value) + (*cleanup) (value, cleanup_data); } if (ht->size > 0) - { - free(ht->tab); - free(ht->ids); - free(ht->locps); - } + free (ht->items); +} + + +/* Create a hash table, initialize it and return it in HT. If a + memory allocation error occurs, ENOMEM is returned, otherwise 0. */ +error_t +hurd_ihash_create (hurd_ihash_t *ht, off_t locp_offs) +{ + *ht = malloc (sizeof (struct hurd_ihash)); + if (*ht == NULL) + return ENOMEM; + + hurd_ihash_init (*ht, locp_offs); + + return 0; +} + - free(ht); +/* Destroy the hash table HT and release the memory allocated for it + by hurd_ihash_create(). */ +void +hurd_ihash_free (hurd_ihash_t ht) +{ + hurd_ihash_destroy (ht); + free (ht); } -/* Sets HT's element cleanup function to CLEANUP, and its second argument to - ARG. CLEANUP will be called on the value of any element to be - subsequently overwritten or deleted, with ARG as the second argument. */ + +/* Set the cleanup function for the hash table HT to CLEANUP. The + second argument to CLEANUP will be CLEANUP_DATA on every + invocation. */ void -ihash_set_cleanup(ihash_t ht, - void (*cleanup)(void *value, void *arg), - void *arg) +hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup, + void *cleanup_data) { ht->cleanup = cleanup; - ht->cleanup_arg = arg; + ht->cleanup_data = cleanup_data; } + + +/* Set the maximum load factor in percent to MAX_LOAD, which should be + between 1 and 100. The default is HURD_IHASH_MAX_LOAD_DEFAULT. + New elements are only added to the hash table while the number of + hashed elements is that much percent of the total size of the hash + table. If more elements are added, the hash table is first + expanded and reorganized. A MAX_LOAD of 100 will always fill the + whole table before enlarging it, but note that this will increase + the cost of operations significantly when the table is almost full. + + If the value is set to a smaller value than the current load + factor, the next reorganization will happen when a new item is + added to the hash table. */ +void +hurd_ihash_set_max_load (hurd_ihash_t ht, unsigned int max_load) +{ + ht->max_load = max_load; +} + -/* ---------------------------------------------------------------- */ - -/* Add ITEM to the hash table HT under the key ID. LOCP is the address of a - pointer located in ITEM; If non-NULL, LOCP should point to a variable of - type void **, and will be filled with a pointer that may be used as an - argument to ihash_locp_remove(). The variable pointed to by LOCP may be - written to subsequently between this called and when the element is - deleted, so you can't stash its value elsewhere and hope to use the - stashed value with ihash_locp_remove(). If a memory allocation error - occurs, ENOMEM is returned, otherwise 0. */ -error_t -ihash_add(ihash_t ht, int id, void *item, void ***locp) +/* Helper function for hurd_ihash_add. Return 1 if the item was + added, and 0 if it could not be added because no empty slot was + found. The arguments are identical to hurd_ihash_add. + + We are using open address hashing. As the hash function we use the + division method with quadratic probe. This is guaranteed to try + all slots in the hash table if the prime number is 3 mod 4. */ +static inline int +add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value) { - if (ht->size) - { - int h, firsth = -1; + unsigned int idx; + unsigned int first_free; - /* Search for for an empty or deleted space. */ - for (h = HASH(ht, id); - ht->tab[h] != HASH_EMPTY && ht->tab[h] != HASH_DEL && h != firsth; - h = REHASH(ht, id, h)) - if (firsth == -1) - firsth = h; + idx = key % ht->size; + first_free = idx; - if (index_empty(ht, h) || ht->ids[h] == id) + if (ht->items[idx].value != _HURD_IHASH_EMPTY && ht->items[idx].key != key) + { + /* Instead of calculating idx + 1, idx + 4, idx + 9, ..., idx + + i^2, we add 1, 3, 5, 7, ... 2 * i - 1 to the previous index. + We do this in both directions separately. */ + unsigned int i = 1; + unsigned int up_idx = idx; + unsigned int down_idx = idx; + + do { - if (!index_empty(ht, h) && ht->cleanup) - ht->cleanup(ht->tab[h], ht->cleanup_arg); + up_idx = (up_idx + i) % ht->size; + if (ht->items[up_idx].value == _HURD_IHASH_EMPTY + || ht->items[up_idx].key == key) + { + idx = up_idx; + break; + } + if (first_free == idx + && ht->items[up_idx].value == _HURD_IHASH_DELETED) + first_free = up_idx; + + if (down_idx < i) + down_idx += ht->size; + down_idx = (down_idx - i) % ht->size; + if (down_idx < 0) + down_idx += ht->size; + else + down_idx %= ht->size; + if (ht->items[down_idx].value == _HURD_IHASH_EMPTY + || ht->items[down_idx].key == key) + { + idx = down_idx; + break; + } + if (first_free == idx + && ht->items[down_idx].value == _HURD_IHASH_DELETED) + first_free = down_idx; + + /* After (ht->size - 1) / 2 iterations, this will be 0. */ + i = (i + 2) % ht->size; + } + while (i); + } - ht->tab[h] = item; - ht->ids[h] = id; - ht->locps[h] = locp; + /* Remove the old entry for this key if necessary. */ + if (index_valid (ht, idx, key)) + locp_remove (ht, &ht->items[idx].value); - if (locp) - *locp = &ht->tab[h]; + /* If we have not found an empty slot, maybe the last one we + looked at was empty (or just got deleted). */ + if (!index_empty (ht, first_free)) + first_free = idx; + + if (index_empty (ht, first_free)) + { + ht->nr_items++; + ht->items[first_free].value = value; + ht->items[first_free].key = key; - return 0; - } + if (ht->locp_offset != HURD_IHASH_NO_LOCP) + *((hurd_ihash_locp_t) (((char *) value) + ht->locp_offset)) + = &ht->items[first_free].value; + + return 1; } - { - int i; - void **entry; - int old_size = ht->size; - void **old_tab = ht->tab; - void ****old_locps = ht->locps; - int *old_ids = ht->ids; - - i = 0; - while (_ihash_sizes[i] <= old_size) - if (++i == _ihash_nsizes) - return ENOMEM; /* Surely will be true momentarily. */ - - ht->size = _ihash_sizes[i]; - ht->tab = malloc(ht->size * sizeof (void *)); - ht->locps = malloc (ht->size * sizeof (void ***)); - ht->ids = malloc (ht->size * sizeof (int)); - - if (ht->tab == NULL || ht->locps == NULL || ht->ids == NULL) - /* Memory allocation error; back out our changes and fail... */ - { - if (ht->tab) free(ht->tab); - if (ht->locps) free(ht->locps); - if (ht->ids) free(ht->ids); + return 0; +} - ht->size = old_size; - ht->tab = old_tab; - ht->locps = old_locps; - ht->ids = old_ids; + +/* Add ITEM to the hash table HT under the key KEY. If there already + is an item under this key, call the cleanup function (if any) for + it before overriding the value. If a memory allocation error + occurs, ENOMEM is returned, otherwise 0. */ +error_t +hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item) +{ + struct hurd_ihash old_ht = *ht; + int was_added; + int i; - return ENOMEM; - } + if (ht->size) + { + /* Only fill the hash table up to its maximum load factor. */ + if (ht->nr_items * 100 / ht->size <= ht->max_load) + if (add_one (ht, key, item)) + return 0; + } + + /* The hash table is too small, and we have to increase it. */ + for (i = 0; i < ihash_nsizes; i++) + if (ihash_sizes[i] > old_ht.size) + break; + if (i == ihash_nsizes + || ihash_sizes[i] > SIZE_MAX / sizeof (struct _hurd_ihash_item)) + return ENOMEM; /* Surely will be true momentarily. */ - for (i = ht->size, entry = ht->tab; i > 0; i--, entry++) - *entry = HASH_EMPTY; + ht->nr_items = 0; + ht->size = ihash_sizes[i]; + /* calloc() will initialize all values to _HURD_IHASH_EMPTY implicitely. */ + ht->items = calloc (ht->size, sizeof (struct _hurd_ihash_item)); - /* We have to rehash this again? */ - if (old_size > 0) - for (i = 0; i < old_size; i++) - if (old_tab[i] != HASH_EMPTY && old_tab[i] != HASH_DEL) - ihash_add(ht, old_ids[i], old_tab[i], old_locps[i]); + if (ht->items == NULL) + { + if (ht->items) + free(ht->items); - /* Finally add the new element! */ - ihash_add(ht, id, item, locp); + *ht = old_ht; + return ENOMEM; + } - if (old_size > 0) + /* We have to rehash the old entries. */ + for (i = 0; i < old_ht.size; i++) + if (!index_empty (&old_ht, i)) { - free(old_tab); - free(old_locps); - free(old_ids); + was_added = add_one (ht, old_ht.items[i].key, old_ht.items[i].value); + assert (was_added); } - return 0; - } + /* Finally add the new element! */ + was_added = add_one (ht, key, item); + assert (was_added); + + if (old_ht.size > 0) + free (old_ht.items); + + return 0; } -/* Find and return the item in hash table HT with key ID, or NULL if it - doesn't exist. */ -void * -ihash_find (ihash_t ht, int id) + +/* Find and return the item in the hash table HT with key KEY, or NULL + if it doesn't exist. */ +hurd_ihash_value_t +hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key) { if (ht->size == 0) - return 0; + return NULL; else { - int index = find_index(ht, id); - return index_valid(ht, index, id) ? ht->tab[index] : 0; + int idx = find_index (ht, key); + return index_valid (ht, idx, key) ? ht->items[idx].value : NULL; } } - -/* ---------------------------------------------------------------- */ - -/* Call function FUN of one arg for each element of HT. FUN's only arg is a - pointer to the value stored in the hash table. If FUN ever returns - non-zero, then iteration stops and ihash_iterate returns that value, - otherwise it (eventually) returns 0. */ -error_t -ihash_iterate(ihash_t ht, error_t (*fun)(void *)) -{ - int i; - for (i = 0; i < ht->size; i++) - if (!index_empty(ht, i)) - { - error_t err = fun(ht->tab[i]); - if (err) - return err; - } - return 0; -} -/* Remove the entry at LOCP from the hashtable HT. LOCP is as returned from - an earlier call to ihash_add(). This call should be faster than - ihash_remove(). HT can be NULL, in which case the call still succeeds, - but no cleanup can be done. */ -void -ihash_locp_remove(ihash_t ht, void **locp) -{ - if (ht && ht->cleanup) - ht->cleanup(*locp, ht->cleanup_arg); - *locp = HASH_DEL; -} -/* Remove the entry with a key of ID from HT. If anything was actually - removed, 1 is returned, otherwise (if there was no such element), 0. */ +/* Remove the entry with the key KEY from the hash table HT. If such + an entry was found and removed, 1 is returned, otherwise 0. */ int -ihash_remove(ihash_t ht, int id) +hurd_ihash_remove (hurd_ihash_t ht, hurd_ihash_key_t key) { - int index = find_index(ht, id); - if (index_valid(ht, index, id)) + int idx = find_index (ht, key); + + if (index_valid (ht, idx, key)) { - ihash_locp_remove(ht, &ht->tab[index]); + locp_remove (ht, &ht->items[idx].value); return 1; } else return 0; } + + +/* Remove the entry pointed to by the location pointer LOCP from the + hashtable HT. LOCP is the location pointer of which the address + was provided to hurd_ihash_add(). This call is faster than + hurd_ihash_remove(). */ +void +hurd_ihash_locp_remove (hurd_ihash_t ht, hurd_ihash_locp_t locp) +{ + locp_remove (ht, locp); +} diff --git a/libihash/ihash.h b/libihash/ihash.h index 5d01ea1c..11092532 100644 --- a/libihash/ihash.h +++ b/libihash/ihash.h @@ -1,97 +1,231 @@ -/* Integer-keyed hash table functions. +/* ihash.h - Integer keyed hash table interface. + Copyright (C) 1995, 2003 Free Software Foundation, Inc. + Written by Miles Bader <miles@gnu.org>. + Revised by Marcus Brinkmann <marcus@gnu.org>. - Copyright (C) 1995 Free Software Foundation, Inc. + This file is part of the GNU Hurd. - Written by Miles Bader <miles@gnu.ai.mit.edu> - - This program is free software; you can redistribute it and/or + The GNU Hurd is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. - This program is distributed in the hope that it will be useful, but + The GNU Hurd is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ + along with the GNU Hurd; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ -#ifndef __IHASH_H__ -#define __IHASH_H__ +#ifndef _HURD_IHASH_H +#define _HURD_IHASH_H 1 #include <errno.h> +#include <sys/types.h> +#include <limits.h> +#include <stdint.h> -/* ---------------------------------------------------------------- */ +/* The type of the values corresponding to the keys. Must be a + pointer type. The values (hurd_ihash_value_t) 0 and + (hurd_ihash_value_t) ~0 are reserved for the implementation. */ +typedef void *hurd_ihash_value_t; + +/* When an value entry in the hash table is _HURD_IHASH_EMPTY or + _HURD_IHASH_DELETED, then the location is available, and none of + the other members of the item are valid at that index. The + difference is that searches continue though _HURD_IHASH_DELETED, + but stop at _HURD_IHASH_EMPTY. */ +#define _HURD_IHASH_EMPTY ((hurd_ihash_value_t) 0) +#define _HURD_IHASH_DELETED ((hurd_ihash_value_t) -1) + +/* The type of integer we want to use for the keys. */ +typedef uintptr_t hurd_ihash_key_t; + +/* The type of a location pointer, which is a pointer to the hash + value stored in the hash table. */ +typedef hurd_ihash_value_t *hurd_ihash_locp_t; -typedef struct ihash *ihash_t; + +/* The type of the cleanup function, which is called for every value + removed from the hash table. */ +typedef void (*hurd_ihash_cleanup_t) (hurd_ihash_value_t value, void *arg); -struct ihash + +struct _hurd_ihash_item { - /* An array storing the elements in the hash table (each a void *). */ - void **tab; + /* The value of this hash item. Must be the first element of + the struct for the HURD_IHASH_ITERATE macro. */ + hurd_ihash_value_t value; - /* An array storing the integer key for each element. */ - int *ids; + /* The integer key of this hash item. */ + hurd_ihash_key_t key; +}; +typedef struct _hurd_ihash_item *_hurd_ihash_item_t; - /* An array storing pointers to the `location pointers' for each element. - These are used as cookies for quick 'n' easy removal. */ - void ****locps; /* four, count them, four stars */ +struct hurd_ihash +{ + /* The number of hashed elements. */ + size_t nr_items; - /* The length of all these arrays. */ - int size; + /* An array of (key, value) pairs. */ + _hurd_ihash_item_t items; - /* When freeing or overwriting an element, this function, if non-NULL, is - called with the value as the first argument, and CLEANUP_ARG as the - second argument. */ - void (*cleanup)(void *element, void *arg); - void *cleanup_arg; -}; + /* The length of the array ITEMS. */ + size_t size; -/* Create an integer hash table and return it in HT. If a memory allocation - error occurs, ENOMEM is returned, otherwise 0. */ -error_t ihash_create(ihash_t *ht); - -/* Free HT and all resources it consumes. */ -void ihash_free(ihash_t ht); - -/* Sets HT's element cleanup function to CLEANUP, and its second argument to - ARG. CLEANUP will be called on the value of any element to be - subsequently overwritten or deleted, with ARG as the second argument. */ -void ihash_set_cleanup(ihash_t ht, - void (*cleanup)(void *value, void *arg), - void *arg); - -/* Add ITEM to the hash table HT under the key ID. LOCP is the address of a - pointer located in ITEM; If non-NULL, LOCP should point to a variable of - type void **, and will be filled with a pointer that may be used as an - argument to ihash_locp_remove() [the variable pointed to by LOCP may be - written to subsequently between this call and when the element is - deleted, so you can't stash its value elsewhere and hope to use the - stashed value with ihash_locp_remove()]. If a memory allocation error - occurs, ENOMEM is returned, otherwise 0. */ -error_t ihash_add(ihash_t ht, int id, void *item, void ***locp); + /* The offset of the location pointer from the hash value. */ + off_t locp_offset; -/* Find and return the item in hash table HT with key ID, or NULL if it - doesn't exist. */ -void *ihash_find(ihash_t ht, int id); + /* The maximum load factor in percent. */ + int max_load; -/* Call function FUN of one arg for each element of HT. FUN's only arg is a - pointer to the value stored in the hash table. If FUN ever returns - non-zero, then iteration stops and ihash_iterate returns that value, - otherwise it (eventually) returns 0. */ -error_t ihash_iterate(ihash_t ht, error_t (*fun)(void *)); + /* When freeing or overwriting an element, this function is called + with the value as the first argument, and CLEANUP_DATA as the + second argument. This does not happen if CLEANUP is NULL. */ + hurd_ihash_cleanup_t cleanup; + void *cleanup_data; +}; +typedef struct hurd_ihash *hurd_ihash_t; -/* Remove the entry with a key of ID from HT. If anything was actually - removed, 1 is returned, otherwise (if there was no such element), 0. */ -int ihash_remove(ihash_t ht, int id); + +/* Construction and destruction of hash tables. */ + +/* The default value for the maximum load factor in percent. */ +#define HURD_IHASH_MAX_LOAD_DEFAULT 80 + +/* The LOCP_OFFS to use if no location pointer is available. */ +#define HURD_IHASH_NO_LOCP INT_MIN + +/* The static initializer for a struct hurd_ihash. */ +#define HURD_IHASH_INITIALIZER(locp_offs) \ + { .nr_items = 0, .size = 0, .cleanup = (hurd_ihash_cleanup_t) 0, \ + .max_load = HURD_IHASH_MAX_LOAD_DEFAULT, \ + .locp_offset = (locp_offs)} + +/* Initialize the hash table at address HT. If LOCP_OFFSET is not + HURD_IHASH_NO_LOCP, then this is an offset (in bytes) from the + address of a hash value where a location pointer can be found. The + location pointer must be of type hurd_ihash_locp_t and can be used + for fast removal with hurd_ihash_locp_remove(). */ +void hurd_ihash_init (hurd_ihash_t ht, off_t locp_offs); + +/* Destroy the hash table at address HT. This first removes all + elements which are still in the hash table, and calling the cleanup + function for them (if any). */ +void hurd_ihash_destroy (hurd_ihash_t ht); + +/* Create a hash table, initialize it and return it in HT. If + LOCP_OFFSET is not HURD_IHASH_NO_LOCP, then this is an offset (in + bytes) from the address of a hash value where a location pointer + can be found. The location pointer must be of type + hurd_ihash_locp_t and can be used for fast removal with + hurd_ihash_locp_remove(). If a memory allocation error occurs, + ENOMEM is returned, otherwise 0. */ +error_t hurd_ihash_create (hurd_ihash_t *ht, off_t locp_offs); + +/* Destroy the hash table HT and release the memory allocated for it + by hurd_ihash_create(). */ +void hurd_ihash_free (hurd_ihash_t ht); -/* Remove the entry at LOCP from the hashtable HT. LOCP is as returned from - an earlier call to ihash_add(). This call should be faster than - ihash_remove(). HT can be NULL, in which case the call still succeeds, - but no cleanup can be done. */ -void ihash_locp_remove(ihash_t ht, void **ht_locp); + +/* Configuration of the hash table. */ + +/* Set the cleanup function for the hash table HT to CLEANUP. The + second argument to CLEANUP will be CLEANUP_DATA on every + invocation. */ +void hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup, + void *cleanup_data); + +/* Set the maximum load factor in percent to MAX_LOAD, which should be + between 50 and 100. The default is HURD_IHASH_MAX_LOAD_DEFAULT. + New elements are only added to the hash table while the number of + hashed elements is that much percent of the total size of the hash + table. If more elements are added, the hash table is first + expanded and reorganized. A MAX_LOAD of 100 will always fill the + whole table before enlarging it, but note that this will increase + the cost of operations significantly when the table is almost full. + + If the value is set to a smaller value than the current load + factor, the next reorganization will happen when a new item is + added to the hash table. */ +void hurd_ihash_set_max_load (hurd_ihash_t ht, unsigned int max_load); -#endif /* __IHASH_H__ */ + +/* Add ITEM to the hash table HT under the key KEY. If there already + is an item under this key, call the cleanup function (if any) for + it before overriding the value. If a memory allocation error + occurs, ENOMEM is returned, otherwise 0. */ +error_t hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, + hurd_ihash_value_t item); + +/* Find and return the item in the hash table HT with key KEY, or NULL + if it doesn't exist. */ +hurd_ihash_value_t hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key); + +/* Iterate over all elements in the hash table. You use this macro + with a block, for example like this: + + error_t err; + HURD_IHASH_ITERATE (ht, value) + { + err = foo (value); + if (err) + break; + } + if (err) + cleanup_and_return (); + + Or even like this: + + hurd_ihash_iterate (ht, value) + foo (value); + + The block will be run for every element in the hash table HT. The + value of the current element is available in the variable VALUE + (which is declared for you and local to the block). */ + +/* The implementation of this macro is peculiar. We want the macro to + execute a block following its invocation, so we can only prepend + code. This excludes creating an outer block. However, we must + define two variables: The hash value variable VALUE, and the loop + variable. + + We can define variables inside the for-loop initializer (C99), but + we can only use one basic type to do that. We can not use two + for-loops, because we want a break statement inside the iterator + block to terminate the operation. So we must have both variables + of the same basic type, but we can make one (or both) of them a + pointer type. + + The pointer to the value can be used as the loop variable. This is + also the first element of the hash item, so we can cast the pointer + freely between these two types. The pointer is only dereferenced + after the loop condition is checked (but of course the value the + pointer pointed to must not have an influence on the condition + result, so the comma operator is used to make sure this + subexpression is always true). */ +#define HURD_IHASH_ITERATE(ht, val) \ + for (hurd_ihash_value_t val, \ + *_hurd_ihash_valuep = (ht)->size ? &(ht)->items[0].value : 0; \ + (ht)->size \ + && ((_hurd_ihash_item_t) _hurd_ihash_valuep) - &(ht)->items[0] \ + < (ht)->size \ + && (val = *_hurd_ihash_valuep, 1); \ + _hurd_ihash_valuep = (hurd_ihash_value_t *) \ + (((_hurd_ihash_item_t) _hurd_ihash_valuep)++)) \ + if (val != _HURD_IHASH_EMPTY && val != _HURD_IHASH_DELETED) + +/* Remove the entry with the key KEY from the hash table HT. If such + an entry was found and removed, 1 is returned, otherwise 0. */ +int hurd_ihash_remove (hurd_ihash_t ht, hurd_ihash_key_t key); + +/* Remove the entry pointed to by the location pointer LOCP from the + hash table HT. LOCP is the location pointer of which the address + was provided to hurd_ihash_add(). This call is faster than + hurd_ihash_remove(). */ +void hurd_ihash_locp_remove (hurd_ihash_t ht, hurd_ihash_locp_t locp); + +#endif /* _HURD_IHASH_H */ diff --git a/libihash/primes.c b/libihash/primes.c deleted file mode 100644 index 61b1d7e9..00000000 --- a/libihash/primes.c +++ /dev/null @@ -1,140 +0,0 @@ -/* Prime number generation - Copyright (C) 1994, 1996, 1999 Free Software Foundation - - This program 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 - 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. */ - -#include <stdlib.h> -#include <limits.h> -#include <string.h> -#include <assert.h> -#include <spin-lock.h> -#include "priv.h" - -#define BITS_PER_UNSIGNED (8 * sizeof (unsigned)) -#define SQRT_INT_MAX (1 << (BITS_PER_UNSIGNED / 2)) - -static spin_lock_t table_lock = SPIN_LOCK_INITIALIZER; - -/* Return the next prime greater than or equal to N. */ -int -_ihash_nextprime (unsigned n) -{ - /* Among other things, We guarantee that, for all i (0 <= i < primes_len), - primes[i] is a prime, - next_multiple[i] is a multiple of primes[i], - next_multiple[i] > primes[primes_len - 1], - next_multiple[i] is not a multiple of two unless primes[i] == 2, and - next_multiple[i] is the smallest such value. */ - static unsigned *primes, *next_multiple; - static int primes_len; - static int primes_size; - static unsigned next_sieve; /* always even */ - unsigned max_prime; - - spin_lock (&table_lock); - - if (! primes) - { - primes_size = 128; - primes = (unsigned *) malloc (primes_size * sizeof (*primes)); - next_multiple = (unsigned *) malloc (primes_size - * sizeof (*next_multiple)); - - primes[0] = 2; next_multiple[0] = 6; - primes[1] = 3; next_multiple[1] = 9; - primes[2] = 5; next_multiple[2] = 15; - primes_len = 3; - - next_sieve = primes[primes_len - 1] + 1; - } - - if (n <= primes[0]) - { - spin_unlock (&table_lock); - return primes[0]; - } - - while (n > (max_prime = primes[primes_len - 1])) - { - /* primes doesn't contain any prime large enough. Sieve from - max_prime + 1 to 2 * max_prime, looking for more primes. */ - unsigned start = next_sieve; - unsigned end = start + max_prime + 1; - char sieve[end - start]; - int i; - - bzero (sieve, (end - start) * sizeof (*sieve)); - - /* Make the sieve indexed by prime number, rather than - distance-from-start-to-the-prime-number. When we're done, - sieve[P] will be zero iff P is prime. */ -#define sieve (sieve - start) - - /* Set sieve[i] for all composites i, start <= i < end. - Ignore multiples of 2. */ - for (i = 1; i < primes_len; i++) - { - unsigned twice_prime = 2 * primes[i]; - unsigned multiple; - - for (multiple = next_multiple[i]; - multiple < end; - multiple += twice_prime) - sieve[multiple] = 1; - next_multiple[i] = multiple; - } - - for (i = start + 1; i < end; i += 2) - if (! sieve[i]) - { - if (primes_len >= primes_size) - { - primes_size *= 2; - primes = (int *) realloc (primes, - primes_size * sizeof (*primes)); - next_multiple - = (int *) realloc (next_multiple, - primes_size * sizeof (*next_multiple)); - } - primes[primes_len] = i; - if (i >= SQRT_INT_MAX) - next_multiple[primes_len] = INT_MAX; - else - next_multiple[primes_len] = i * i; - primes_len++; - } - - next_sieve = end; - } - - /* Now we have at least one prime >= n. Find the smallest such. */ - { - int bottom = 0; - int top = primes_len; - - while (bottom < top) - { - int mid = (bottom + top) / 2; - - if (primes[mid] < n) - bottom = mid + 1; - else - top = mid; - } - - spin_unlock (&table_lock); - return primes[top]; - } -} diff --git a/libihash/priv.h b/libihash/priv.h deleted file mode 100644 index f31bf6c6..00000000 --- a/libihash/priv.h +++ /dev/null @@ -1,21 +0,0 @@ -/* Private declarations for ihash library - Copyright (C) 1996,2001 Free Software Foundation, Inc. - - This file is part of the GNU Hurd. - - 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. - - 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., 59 Temple Place - Suite 330, Boston, MA 02111, USA. */ - -extern const unsigned int _ihash_sizes[]; -const unsigned int _ihash_nsizes; diff --git a/libihash/sizes.c b/libihash/sizes.c deleted file mode 100644 index 17f3fb1f..00000000 --- a/libihash/sizes.c +++ /dev/null @@ -1,41 +0,0 @@ -/* Some prime numbers for the ihash library. - I cannot bring myself to assert copyright over a list of prime numbers. - This file is in the public domain. */ - -#include "priv.h" - -/* The prime numbers greater than twice the last and less than 2^32. */ -const unsigned int _ihash_sizes[] = -{ - 2, - 5, - 11, - 23, - 47, - 97, - 197, - 397, - 797, - 1597, - 3203, - 6421, - 12853, - 25717, - 51437, - 102877, - 205759, - 411527, - 823117, - 1646237, - 3292489, - 6584983, - 13169977, - 26339969, - 52679969, - 105359939, - 210719881, - 421439783, -}; - -const unsigned int _ihash_nsizes = (sizeof _ihash_sizes - / sizeof _ihash_sizes[0]); diff --git a/libports/ChangeLog b/libports/ChangeLog index b6d1d054..e650d158 100644 --- a/libports/ChangeLog +++ b/libports/ChangeLog @@ -1,3 +1,33 @@ +2003-08-17 Marcus Brinkmann <marcus@gnu.org> + + * ports.h (struct port_bucket): Change type of HTABLE to struct + hurd_ihash. + (struct port_info): Change type of HENTRY to hurd_ihash_locp_t. + * lookup-port.c (ports_lookup_port): Use hurd_ihash_find instead + ihash_find. + * bucket-iterate.c (_ports_bucket_class_iterate): Use + HURD_IHASH_ITERATE instead ihash_iterate. + * inhibit-all-rpcs.c (ports_inhibit_all_rpcs): Likewise. + * inhibit-bucket-rpcs.c (ports_inhibit_bucket_rpcs): Likewise. + * create-internal.c (_ports_create_port_internal): Use + hurd_ihash_add instead ihash_add. + * import-port.c (ports_import_port): Likewise. + * reallocate-from-external.c (ports_reallocate_from_external): + Likewise. + * reallocate-port.c (ports_reallocate_port): Likewise. + * transfer-right.c (ports_transfer_right): Likewise. + * create-bucket.c: Include <stddef.h>. + (ports_create_bucket): Use hurd_ihash_init instead hurd_ihash_create. + * class-iterate.c: Do not include <hurd/ihash.h>. + * claim-right.c (ports_claim_right): Call hurd_ihash_locp_remove + instead ihash_locp_remove. + * complete-deallocate.c (_ports_complete_deallocate): Likewise. + * destroy-right.c (ports_destroy_right): Likewise. + * reallocate-from-external.c (ports_reallocate_from_external): + Likewise. + * reallocate-port.c (ports_reallocate_port): Likewise. + * transfer-right.c (ports_transfer_right): Likewise. + 2001-03-29 Neal H Walfield <neal@cs.uml.edu> * claim-right.c (ports_claim_right): Include errno.h and diff --git a/libports/bucket-iterate.c b/libports/bucket-iterate.c index 1bfd73e3..d376e6f8 100644 --- a/libports/bucket-iterate.c +++ b/libports/bucket-iterate.c @@ -30,7 +30,7 @@ _ports_bucket_class_iterate (struct port_bucket *bucket, 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_bucket *bucket, 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_bucket *bucket, list = j; pi->refcnt++; } - return 0; } - - mutex_lock (&_ports_lock); - ihash_iterate (bucket->htable, enqueue); mutex_unlock (&_ports_lock); err = 0; diff --git a/libports/claim-right.c b/libports/claim-right.c index 9986ba2e..aef53bb7 100644 --- a/libports/claim-right.c +++ b/libports/claim-right.c @@ -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; diff --git a/libports/class-iterate.c b/libports/class-iterate.c index 1e349497..e2a15173 100644 --- a/libports/class-iterate.c +++ b/libports/class-iterate.c @@ -19,7 +19,6 @@ #include "ports.h" #include <cthreads.h> -#include <hurd/ihash.h> error_t ports_class_iterate (struct port_class *class, diff --git a/libports/complete-deallocate.c b/libports/complete-deallocate.c index a94ab171..52e8f17b 100644 --- a/libports/complete-deallocate.c +++ b/libports/complete-deallocate.c @@ -30,7 +30,7 @@ _ports_complete_deallocate (struct port_info *pi) 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; diff --git a/libports/create-bucket.c b/libports/create-bucket.c index 9e25ab60..6be4bcad 100644 --- a/libports/create-bucket.c +++ b/libports/create-bucket.c @@ -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); diff --git a/libports/create-internal.c b/libports/create-internal.c index b50212ea..5db71129 100644 --- a/libports/create-internal.c +++ b/libports/create-internal.c @@ -82,7 +82,7 @@ _ports_create_port_internal (struct port_class *class, goto loop; } - err = ihash_add (bucket->htable, port, pi, &pi->hentry); + err = hurd_ihash_add (&bucket->htable, port, pi); if (err) goto lose; diff --git a/libports/destroy-right.c b/libports/destroy-right.c index 32085c80..327029a8 100644 --- a/libports/destroy-right.c +++ b/libports/destroy-right.c @@ -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); diff --git a/libports/import-port.c b/libports/import-port.c index b958245f..d7a62960 100644 --- a/libports/import-port.c +++ b/libports/import-port.c @@ -76,7 +76,7 @@ ports_import_port (struct port_class *class, struct port_bucket *bucket, goto loop; } - err = ihash_add (bucket->htable, port, pi, &pi->hentry); + err = hurd_ihash_add (&bucket->htable, port, pi); if (err) goto lose; diff --git a/libports/inhibit-all-rpcs.c b/libports/inhibit-all-rpcs.c index 9efb3c2f..9a72f83e 100644 --- a/libports/inhibit-all-rpcs.c +++ b/libports/inhibit-all-rpcs.c @@ -36,27 +36,26 @@ 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) { _ports_flags |= _PORTS_INHIBIT_WAIT; diff --git a/libports/inhibit-bucket-rpcs.c b/libports/inhibit-bucket-rpcs.c index 06af9c60..7fc55d31 100644 --- a/libports/inhibit-bucket-rpcs.c +++ b/libports/inhibit-bucket-rpcs.c @@ -35,7 +35,8 @@ ports_inhibit_bucket_rpcs (struct port_bucket *bucket) 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_bucket *bucket) else hurd_thread_cancel (rpc->thread); } - - return 0; } - ihash_iterate (bucket->htable, interruptor); while (bucket->rpcs > this_one) { diff --git a/libports/lookup-port.c b/libports/lookup-port.c index d0ee8d00..8eb98a12 100644 --- a/libports/lookup-port.c +++ b/libports/lookup-port.c @@ -32,11 +32,11 @@ ports_lookup_port (struct port_bucket *bucket, 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; } diff --git a/libports/ports.h b/libports/ports.h index 6a406ed0..9a5ccbc2 100644 --- a/libports/ports.h +++ b/libports/ports.h @@ -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; diff --git a/libports/reallocate-from-external.c b/libports/reallocate-from-external.c index 80b2905e..ebddd9f7 100644 --- a/libports/reallocate-from-external.c +++ b/libports/reallocate-from-external.c @@ -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 *portstruct, mach_port_t receive) 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 *portstruct, mach_port_t receive) 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); diff --git a/libports/reallocate-port.c b/libports/reallocate-port.c index bd1b1893..23898e88 100644 --- a/libports/reallocate-port.c +++ b/libports/reallocate-port.c @@ -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, diff --git a/libports/transfer-right.c b/libports/transfer-right.c index 45a6cc52..e7b0ff55 100644 --- a/libports/transfer-right.c +++ b/libports/transfer-right.c @@ -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, diff --git a/libps/ChangeLog b/libps/ChangeLog index a2e48c95..79885024 100644 --- a/libps/ChangeLog +++ b/libps/ChangeLog @@ -1,3 +1,19 @@ +2003-08-17 Marcus Brinkmann <marcus@gnu.org> + + * ps.h (struct ps_context): Change type of members procs, ttys, + ttys_by_cttyid and users to struct hurd_ihash. + * context.c (ps_context_create): Remove variables err_procs, + err_ttys, err_ttys_by_cttyid and err_users. Use hurd_ihash_init + instead of ihash_create. Call hurd_ihash_set_cleanup and the + hurd_ihash_cleanup_t type instead of ihash_set_cleanup. + (ps_context_free): Call hurd_ihash_destroy instead of ihash_free. + (lookup): Call hurd_ihash_find instead ihash_find, hurd_ihash_add + instead ihash_add. + (ps_context_find_proc_stat): Take pointer of hash object. + (ps_context_find_tty): Likewise. + (ps_context_find_tty_by_cttyid): Likewise. + (ps_context_find_user): Likewise. + 2002-06-09 Roland McGrath <roland@frob.com> * Makefile (installhdrs): List just ps.h, not common.h as well. diff --git a/libps/context.c b/libps/context.c index b8ca102a..3082d83b 100644 --- a/libps/context.c +++ b/libps/context.c @@ -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, struct ps_context **pc) 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_context *pc, pid_t pid, struct proc_stat ** { 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 *pc, mach_port_t tty_port, 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_context *pc, mach_port_t cttyid_port, } } - 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); } @@ -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; diff --git a/proc/ChangeLog b/proc/ChangeLog index 0c872093..1a01550c 100644 --- a/proc/ChangeLog +++ b/proc/ChangeLog @@ -1,5 +1,30 @@ 2003-08-17 Marcus Brinkmann <marcus@gnu.org> + * proc.h: Include <hurd/ihash.h>. + (struct proc): Change type of members p_pidhashloc and + p_taskhashloc to hurd_ihash_locp_t. + (struct pgrp): Likewise for pg_hashloc. + (struct session): Likewise for s_hashloc. + * hash.c: Change type of pghash, pidhash, taskhash and sidhash to + struct hurd_ihash and initialize them with HURD_IHASH_INITIALIZER. + Include stddef.h. + (pid_find): Call hurd_ihash_find instead ihash_find. + (pid_find_allow_zombie): Likewise. + (task_find): Likewise. + (task_find_nocreate): Likewise. + (pgrp_find): Likewise. + (session_find): Likewise. + (add_proc_to_hash): Call hurd_ihash_add instead ihash_add. + (add_pgrp_to_hash): Likewise. + (add_session_to_hash): Likewise. + (remove_pgrp_from_hash): Call hurd_ihash_locp_remove instead + ihash_locp_remove, and provide hash table pointer. + (remove_proc_from_hash): Likewise. + (remove_session_from_hash): Likewise. + (prociterate): Use HURD_IHASH_ITERATE instead ihash_iterate. + +2003-08-17 Marcus Brinkmann <marcus@gnu.org> + * mgt.c (S_proc_dostop): Revert last change. 2003-06-16 Ognyan Kulev <ogi@fmi.uni-sofia.bg> diff --git a/proc/hash.c b/proc/hash.c index 76c2369c..ed670a16 100644 --- a/proc/hash.c +++ b/proc/hash.c @@ -20,6 +20,7 @@ the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ /* 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 Ave, Cambridge, MA 02139, USA. */ #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 *s) 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 */ diff --git a/proc/proc.h b/proc/proc.h index 9e79192a..7943e0be 100644 --- a/proc/proc.h +++ b/proc/proc.h @@ -25,6 +25,7 @@ the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ #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 */ diff --git a/trans/ChangeLog b/trans/ChangeLog index 5340d7b3..4b9e6124 100644 --- a/trans/ChangeLog +++ b/trans/ChangeLog @@ -1,3 +1,15 @@ +2003-08-17 Marcus Brinkmann <marcus@gnu.org> + + * fakeroot.c: Include <stddef.h>. + (struct netnode): Change type of member idport_locp + to hurd_ihash_locp_t. + (idport_ihash): Change type to struct hurd_ihash and initialize + with HURD_IHASH_INITIALIZER. + (new_node): Call hurd_ihash_add instead of ihash_add. + (netfs_node_norefs): Call hrd_ihash_locp_remove instead + ihash_locp_remove. + (netfs_S_dir_lookup): Call hurd_ihash_find instead ihash_find. + 2003-09-05 Greg Buchholz <greg@sleepingsquirrel.org> * fifo.c, new-fifo.c, null.c (trivfs_S_io_map): Change return value to diff --git a/trans/fakeroot.c b/trans/fakeroot.c index df261dbd..6f1cd748 100644 --- a/trans/fakeroot.c +++ b/trans/fakeroot.c @@ -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 idport, int locked, int openmodes, { 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 *diruser, 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. */ diff --git a/utils/ChangeLog b/utils/ChangeLog index 1f393ad7..2b6a3dfb 100644 --- a/utils/ChangeLog +++ b/utils/ChangeLog @@ -1,3 +1,19 @@ +2003-08-17 Marcus Brinkmann <marcus@gnu.org> + + * rpctrace.c: Include <stddef.h>. + (struct traced_info): Change type of LOCP to hurd_ihash_locp_t. + (msgid_ihash): Change type to struct hurd_ihash, and initialize + with HURD_IHASH_INITIALIZER, don't set cleanup here. + (traced_names): Likewise. + (main): Call hurd_ihash_set_cleanup for msgid_ihash. Don't create + traced_names. + (parse_msgid_list): Call hurd_ihash_add instead ihash_add. + (new_send_wrapper): Likewise. + (msgid_info): Likewise. Call hurd_ihash_find instead ihash_find. + (rewrite_right): Likewise. + (traced_dropweak): Call hurd_ihash_locp_remove instead + ihash_locp_remove. + 2003-10-26 Roland McGrath <roland@frob.com> * storeread.c (doc, arg_doc): Make arrays, not pointers; make const. diff --git a/utils/rpctrace.c b/utils/rpctrace.c index ec8fa19e..ea06b1b7 100644 --- a/utils/rpctrace.c +++ b/utils/rpctrace.c @@ -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); @@ -63,7 +64,8 @@ msgid_ihash_cleanup (void *element, void *arg) 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 @@ -102,9 +104,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"); } } @@ -118,7 +120,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 @@ -126,7 +128,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); @@ -135,7 +137,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 @@ -186,7 +188,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. */ @@ -205,7 +207,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; @@ -261,7 +264,7 @@ new_send_wrapper (mach_port_t right, mach_port_t *wrapper_right) /* 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); @@ -327,7 +330,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. */ @@ -360,7 +363,7 @@ rewrite_right (mach_port_t *right, mach_msg_type_name_t *type) { 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 @@ -414,7 +417,7 @@ rewrite_right (mach_port_t *right, mach_msg_type_name_t *type) 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. */ @@ -442,8 +445,7 @@ rewrite_right (mach_port_t *right, mach_msg_type_name_t *type) 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); @@ -1104,8 +1106,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 |