diff options
author | Marcus Brinkmann <marcus@gnu.org> | 2004-03-01 09:58:44 +0000 |
---|---|---|
committer | Marcus Brinkmann <marcus@gnu.org> | 2004-03-01 09:58:44 +0000 |
commit | ac1cab88f6e43ece947ef2e212f0a732f9c39d81 (patch) | |
tree | 38cac8a5bf4151ccb51d733b4fb408f8cc56e56e /libihash/primes.c | |
parent | a2a436b8a8c2d41030ab98e02cad653c254c025a (diff) | |
download | hurd-ac1cab88f6e43ece947ef2e212f0a732f9c39d81.tar.gz hurd-ac1cab88f6e43ece947ef2e212f0a732f9c39d81.tar.bz2 hurd-ac1cab88f6e43ece947ef2e212f0a732f9c39d81.zip |
auth/
2003-08-17 Marcus Brinkmann <marcus@gnu.org>
* auth.c: Include <stddef.h>.
(pending_users, pending_server): Change type to struct hurd_ihash,
initialize with HURD_IHASH_INITIALIZER.
(struct pending): Change type of member LOCP to hurd_ihash_locp_t.
(S_auth_user_authenticate): Use hurd_ihash_* functions instead
ihash_*.
(S_auth_server_authenticate): Likewise.
(main): Do not allocate the hash tables.
console-client/
2003-08-17 Marcus Brinkmann <marcus@gnu.org>
* vga-dynafont.c: Include <stddef.h>.
(struct mapped_character): Change type of LOCP to
hurd_ihash_locp_t.
(struct dynafont): Change type of CHARMAP to struct hurd_ihash.
(dynafont_new): Use hurd_ihash_init instead of ihash_create.
Remove variable ERR. Call hurd_ihash_add instead of ihash_add.
(dynafont_free): Call hurd_ihash_destroy, no ihash_free.
(dynafont_lookup_internal): Use hurd_ihash_find, not ihash_find.
(dynafont_lookup_internal): Call hurd_ihash_locp_remove instead
ihash_locp_remove, and hurd_ihash_add instead ihash_add.
(dynafont_change_font): Likewise. Clean out LOCP if character is
unmapped.
ftpfs/
2003-08-17 Marcus Brinkmann <marcus@gnu.org>
* ftpfs.h: Include <hurd/ihash.h>.
(struct ftpfs): Change type of INODE_MAPPINGS to struct
hurd_ihash.
(struct ftpfs_dir_entry): Change type of INODE_LOCP to
hurd_ihash_locp_t.
* node.c (ftpfs_create_node): Call hurd_ihash_add, not ihash_add.
(netfs_node_norefs): Call hurd_ihash_locp_remove, not
ihash_locp_remove.
* fs.c: Include <stddef.h>.
(ftpfs_create): Call hurd_ihash_init, not hurd_ihash_create.
Call hurd_ihash_destroy on error.
libihash/
2003-08-17 Marcus Brinkmann <marcus@gnu.org>
* ihash.c: Rewritten.
* ihash.h: Rewritten.
* Makefile (SRCS): Remove sizes.c.
(LCLHDRS): Remove priv.h.
* primes.c, sizes.c, priv.h: Files removed.
2003-08-17 Marcus Brinkmann <marcus@gnu.org>
* ports.h (struct port_bucket): Change type of HTABLE to struct
hurd_ihash.
(struct port_info): Change type of HENTRY to hurd_ihash_locp_t.
* lookup-port.c (ports_lookup_port): Use hurd_ihash_find instead
ihash_find.
* bucket-iterate.c (_ports_bucket_class_iterate): Use
HURD_IHASH_ITERATE instead ihash_iterate.
* inhibit-all-rpcs.c (ports_inhibit_all_rpcs): Likewise.
* inhibit-bucket-rpcs.c (ports_inhibit_bucket_rpcs): Likewise.
* create-internal.c (_ports_create_port_internal): Use
hurd_ihash_add instead ihash_add.
* import-port.c (ports_import_port): Likewise.
* reallocate-from-external.c (ports_reallocate_from_external):
Likewise.
* reallocate-port.c (ports_reallocate_port): Likewise.
* transfer-right.c (ports_transfer_right): Likewise.
* create-bucket.c: Include <stddef.h>.
(ports_create_bucket): Use hurd_ihash_init instead hurd_ihash_create.
* class-iterate.c: Do not include <hurd/ihash.h>.
* claim-right.c (ports_claim_right): Call hurd_ihash_locp_remove
instead ihash_locp_remove.
* complete-deallocate.c (_ports_complete_deallocate): Likewise.
* destroy-right.c (ports_destroy_right): Likewise.
* reallocate-from-external.c (ports_reallocate_from_external):
Likewise.
* reallocate-port.c (ports_reallocate_port): Likewise.
* transfer-right.c (ports_transfer_right): Likewise.
libps/
2003-08-17 Marcus Brinkmann <marcus@gnu.org>
* ps.h (struct ps_context): Change type of members procs, ttys,
ttys_by_cttyid and users to struct hurd_ihash.
* context.c (ps_context_create): Remove variables err_procs,
err_ttys, err_ttys_by_cttyid and err_users. Use hurd_ihash_init
instead of ihash_create. Call hurd_ihash_set_cleanup and the
hurd_ihash_cleanup_t type instead of ihash_set_cleanup.
(ps_context_free): Call hurd_ihash_destroy instead of ihash_free.
(lookup): Call hurd_ihash_find instead ihash_find, hurd_ihash_add
instead ihash_add.
(ps_context_find_proc_stat): Take pointer of hash object.
(ps_context_find_tty): Likewise.
(ps_context_find_tty_by_cttyid): Likewise.
(ps_context_find_user): Likewise.
libpthread/
2003-08-17 Marcus Brinkmann <marcus@gnu.org>
* sysdeps/hurd/pt-key.h (PTHREAD_KEY_MEMBERS): Change type of
THREAD_SPECIFICS to hurd_ihash_t.
* sysdeps/hurd/pt-setspecific.c (pthread_setspecific): Call
hurd_ihash_create instead ihash_create, and hurd_ihash_add instead
ihash_add.
* sysdeps/hurd/pt-getspecific.c (pthread_getspecific): Call
hurd_ihash_find instead of ihash_find.
* sysdeps/hurd/pt-destroy-specific.c (__pthread_destroy_specific):
Call hurd_ihash_find instead of ihash_find, hurd_ihash_remove
instead of ihash_remove, and hurd_ihash_free instead of
ihash_free.
proc/
2003-08-17 Marcus Brinkmann <marcus@gnu.org>
* proc.h: Include <hurd/ihash.h>.
(struct proc): Change type of members p_pidhashloc and
p_taskhashloc to hurd_ihash_locp_t.
(struct pgrp): Likewise for pg_hashloc.
(struct session): Likewise for s_hashloc.
* hash.c: Change type of pghash, pidhash, taskhash and sidhash to
struct hurd_ihash and initialize them with HURD_IHASH_INITIALIZER.
Include stddef.h.
(pid_find): Call hurd_ihash_find instead ihash_find.
(pid_find_allow_zombie): Likewise.
(task_find): Likewise.
(task_find_nocreate): Likewise.
(pgrp_find): Likewise.
(session_find): Likewise.
(add_proc_to_hash): Call hurd_ihash_add instead ihash_add.
(add_pgrp_to_hash): Likewise.
(add_session_to_hash): Likewise.
(remove_pgrp_from_hash): Call hurd_ihash_locp_remove instead
ihash_locp_remove, and provide hash table pointer.
(remove_proc_from_hash): Likewise.
(remove_session_from_hash): Likewise.
(prociterate): Use HURD_IHASH_ITERATE instead ihash_iterate.
trans/
2003-08-17 Marcus Brinkmann <marcus@gnu.org>
* fakeroot.c: Include <stddef.h>.
(struct netnode): Change type of member idport_locp
to hurd_ihash_locp_t.
(idport_ihash): Change type to struct hurd_ihash and initialize
with HURD_IHASH_INITIALIZER.
(new_node): Call hurd_ihash_add instead of ihash_add.
(netfs_node_norefs): Call hrd_ihash_locp_remove instead
ihash_locp_remove.
(netfs_S_dir_lookup): Call hurd_ihash_find instead ihash_find.
utils/
2003-08-17 Marcus Brinkmann <marcus@gnu.org>
* rpctrace.c: Include <stddef.h>.
(struct traced_info): Change type of LOCP to hurd_ihash_locp_t.
(msgid_ihash): Change type to struct hurd_ihash, and initialize
with HURD_IHASH_INITIALIZER, don't set cleanup here.
(traced_names): Likewise.
(main): Call hurd_ihash_set_cleanup for msgid_ihash. Don't create
traced_names.
(parse_msgid_list): Call hurd_ihash_add instead ihash_add.
(new_send_wrapper): Likewise.
(msgid_info): Likewise. Call hurd_ihash_find instead ihash_find.
(rewrite_right): Likewise.
(traced_dropweak): Call hurd_ihash_locp_remove instead
ihash_locp_remove.
Diffstat (limited to 'libihash/primes.c')
-rw-r--r-- | libihash/primes.c | 140 |
1 files changed, 0 insertions, 140 deletions
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]; - } -} |