summaryrefslogtreecommitdiff
path: root/libihash/primes.c
diff options
context:
space:
mode:
authorMarcus Brinkmann <marcus@gnu.org>2004-03-01 09:58:44 +0000
committerMarcus Brinkmann <marcus@gnu.org>2004-03-01 09:58:44 +0000
commitac1cab88f6e43ece947ef2e212f0a732f9c39d81 (patch)
tree38cac8a5bf4151ccb51d733b4fb408f8cc56e56e /libihash/primes.c
parenta2a436b8a8c2d41030ab98e02cad653c254c025a (diff)
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.c140
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];
- }
-}