From 02859f472bec7ec0049d86847f397d1d581488d5 Mon Sep 17 00:00:00 2001 From: Roland McGrath Date: Mon, 8 Jan 1996 22:44:45 +0000 Subject: Thu Dec 14 02:28:22 1995 Roland McGrath * posix/glob.c (glob_in_dir): Cast result of opendir to __ptr_t, and cast STREAM to DIR * before passing to readdir and closedir. --- locale/Makefile | 4 +- locale/hash.c | 254 -------------------------------------------------- locale/locfile-hash.c | 254 ++++++++++++++++++++++++++++++++++++++++++++++++++ posix/glob/ChangeLog | 5 + 4 files changed, 261 insertions(+), 256 deletions(-) delete mode 100644 locale/hash.c create mode 100644 locale/locfile-hash.c diff --git a/locale/Makefile b/locale/Makefile index 7e9475b974..e4fbe290b1 100644 --- a/locale/Makefile +++ b/locale/Makefile @@ -1,4 +1,4 @@ -# Copyright (C) 1991, 1992, 1995 Free Software Foundation, Inc. +# Copyright (C) 1991, 1992, 1995, 1996 Free Software Foundation, Inc. # This file is part of the GNU C Library. # The GNU C Library is free software; you can redistribute it and/or @@ -37,7 +37,7 @@ extra-objs = $(localedef-modules:=.o) $(locale-modules:=.o) \ localedef-modules := charmap locfile-lex locfile-parse locale-ctype \ monetary messages collate numeric locale-modules := ctypedump -lib-modules := hash xmalloc +lib-modules := locfile-hash xmalloc GPERF = gperf diff --git a/locale/hash.c b/locale/hash.c deleted file mode 100644 index 75cb77f882..0000000000 --- a/locale/hash.c +++ /dev/null @@ -1,254 +0,0 @@ -/* Copyright (C) 1995 Free Software Foundation, Inc. - -The GNU C Library is free software; you can redistribute it and/or -modify it under the terms of the GNU Library General Public License as -published by the Free Software Foundation; either version 2 of the -License, or (at your option) any later version. - -The GNU C Library 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 -Library General Public License for more details. - -You should have received a copy of the GNU Library General Public -License along with the GNU C Library; see the file COPYING.LIB. If -not, write to the Free Software Foundation, Inc., 675 Mass Ave, -Cambridge, MA 02139, USA. */ - -#include -#include -#include -#include - -#include "hash.h" - -#define obstack_chunk_alloc xmalloc -#define obstack_chunk_free free - -void *xmalloc (size_t n); - -typedef struct hash_entry - { - int used; - char *key; - void *data; - struct hash_entry *next; - } -hash_entry; - -/* Prototypes for local functions. */ -static size_t lookup (hash_table *htab, const char *key, size_t keylen, - unsigned long hval); -static unsigned long compute_hashval(const char *key, size_t keylen); -static unsigned long next_prime(unsigned long seed); -static int is_prime(unsigned long candidate); - - -int -init_hash(hash_table *htab, unsigned long init_size) -{ - /* We need the size to be a prime. */ - init_size = next_prime (init_size); - - /* Initialize the data structure. */ - htab->size = init_size; - htab->filled = 0; - htab->first = NULL; - htab->table = calloc (init_size + 1, sizeof (hash_entry)); - obstack_init (&htab->mem_pool); - - return htab->table == NULL; -} - - -int -delete_hash(hash_table *htab) -{ - free (htab->table); - obstack_free (&htab->mem_pool, NULL); - return 0; -} - - -int -insert_entry (hash_table *htab, const char *key, size_t keylen, void *data) -{ - unsigned long hval = compute_hashval (key, keylen); - hash_entry *table = (hash_entry *) htab->table; - size_t idx = lookup (htab, key, keylen, hval); - - if (table[idx].used) - /* We don't want to overwrite the old value. */ - return 1; - else - { - hash_entry **p; - - /* An empty bucket has been found. */ - table[idx].used = hval; - table[idx].key = obstack_copy0 (&htab->mem_pool, key, keylen); - table[idx].data = data; - - /* List the new value in the ordered list. */ - for (p = (hash_entry **) &htab->first; *p != NULL && (*p)->data < data; - p = &(*p)->next); - if (*p == NULL || (*p)->data > data) - /* Insert new value in the list. */ - { - table[idx].next = *p; - *p = &table[idx]; - } - - ++htab->filled; - if (100 * htab->filled > 90 * htab->size) - { - /* Resize the table. */ - unsigned long old_size = htab->size; - - htab->size = next_prime (htab->size * 2); - htab->filled = 0; - htab->first = NULL; - htab->table = calloc (htab->size, sizeof (hash_entry)); - - for (idx = 1; idx <= old_size; ++idx) - if (table[idx].used) - insert_entry (htab, table[idx].key, strlen(table[idx].key), - table[idx].data); - - free (table); - } - return 0; - } - /* NOTREACHED */ -} - - -int -find_entry (hash_table *htab, const char *key, size_t keylen, void **result) -{ - hash_entry *table = (hash_entry *) htab->table; - size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen)); - int retval; - - retval = table[idx].used; - *result = retval ? table[idx].data : NULL; - - return retval; -} - - -int -iterate_table (hash_table *htab, void **ptr, void **result) -{ - if (*ptr == NULL) - *ptr = (void *) htab->first; - else - { - *ptr = (void *) (((hash_entry *) *ptr)->next); - if (*ptr == NULL) - return 0; - } - - *result = ((hash_entry *) *ptr)->data; - return 1; -} - - -static size_t -lookup (hash_table *htab, const char *key, size_t keylen, unsigned long hval) -{ - unsigned long hash; - size_t idx; - hash_entry *table = (hash_entry *) htab->table; - - /* First hash function: simply take the modul but prevent zero. */ - hash = 1 + hval % htab->size; - - idx = hash; - - if (table[idx].used) - { - if (table[idx].used == hval && table[idx].key[keylen] == '\0' - && strncmp (key, table[idx].key, keylen) == 0) - return idx; - - /* Second hash function as suggested in [Knuth]. */ - hash = 1 + hash % (htab->size - 2); - - do - { - if (idx <= hash) - idx = htab->size + idx - hash; - else - idx -= hash; - - /* If entry is found use it. */ - if (table[idx].used == hval && table[idx].key[keylen] == '\0' - && strncmp (key, table[idx].key, keylen) == 0) - return idx; - } - while (table[idx].used); - } - return idx; -} - - -static unsigned long -compute_hashval(const char *key, size_t keylen) -{ - size_t cnt; - unsigned long hval, g; - /* Compute the hash value for the given string. */ - cnt = 0; - hval = keylen; - while (cnt < keylen) - { - hval <<= 4; - hval += key[cnt++]; - g = hval & (0xf << (LONGBITS - 4)); - if (g != 0) - { - hval ^= g >> (LONGBITS - 8); - hval ^= g; - } - } - return hval; -} - - -static unsigned long -next_prime(unsigned long seed) -{ - /* Make it definitely odd. */ - seed |= 1; - - while (!is_prime (seed)) - seed += 2; - - return seed; -} - - -static int -is_prime(unsigned long candidate) -{ - /* No even number and none less than 10 will be passwd here. */ - unsigned long div = 3; - unsigned long sq = div * div; - - while (sq < candidate && candidate % div != 0) - { - ++div; - sq += 4 * div; - ++div; - } - - return candidate % div != 0; -} - -/* - * Local Variables: - * mode:c - * c-basic-offset:2 - * End: - */ diff --git a/locale/locfile-hash.c b/locale/locfile-hash.c new file mode 100644 index 0000000000..75cb77f882 --- /dev/null +++ b/locale/locfile-hash.c @@ -0,0 +1,254 @@ +/* Copyright (C) 1995 Free Software Foundation, Inc. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library 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 +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#include +#include +#include +#include + +#include "hash.h" + +#define obstack_chunk_alloc xmalloc +#define obstack_chunk_free free + +void *xmalloc (size_t n); + +typedef struct hash_entry + { + int used; + char *key; + void *data; + struct hash_entry *next; + } +hash_entry; + +/* Prototypes for local functions. */ +static size_t lookup (hash_table *htab, const char *key, size_t keylen, + unsigned long hval); +static unsigned long compute_hashval(const char *key, size_t keylen); +static unsigned long next_prime(unsigned long seed); +static int is_prime(unsigned long candidate); + + +int +init_hash(hash_table *htab, unsigned long init_size) +{ + /* We need the size to be a prime. */ + init_size = next_prime (init_size); + + /* Initialize the data structure. */ + htab->size = init_size; + htab->filled = 0; + htab->first = NULL; + htab->table = calloc (init_size + 1, sizeof (hash_entry)); + obstack_init (&htab->mem_pool); + + return htab->table == NULL; +} + + +int +delete_hash(hash_table *htab) +{ + free (htab->table); + obstack_free (&htab->mem_pool, NULL); + return 0; +} + + +int +insert_entry (hash_table *htab, const char *key, size_t keylen, void *data) +{ + unsigned long hval = compute_hashval (key, keylen); + hash_entry *table = (hash_entry *) htab->table; + size_t idx = lookup (htab, key, keylen, hval); + + if (table[idx].used) + /* We don't want to overwrite the old value. */ + return 1; + else + { + hash_entry **p; + + /* An empty bucket has been found. */ + table[idx].used = hval; + table[idx].key = obstack_copy0 (&htab->mem_pool, key, keylen); + table[idx].data = data; + + /* List the new value in the ordered list. */ + for (p = (hash_entry **) &htab->first; *p != NULL && (*p)->data < data; + p = &(*p)->next); + if (*p == NULL || (*p)->data > data) + /* Insert new value in the list. */ + { + table[idx].next = *p; + *p = &table[idx]; + } + + ++htab->filled; + if (100 * htab->filled > 90 * htab->size) + { + /* Resize the table. */ + unsigned long old_size = htab->size; + + htab->size = next_prime (htab->size * 2); + htab->filled = 0; + htab->first = NULL; + htab->table = calloc (htab->size, sizeof (hash_entry)); + + for (idx = 1; idx <= old_size; ++idx) + if (table[idx].used) + insert_entry (htab, table[idx].key, strlen(table[idx].key), + table[idx].data); + + free (table); + } + return 0; + } + /* NOTREACHED */ +} + + +int +find_entry (hash_table *htab, const char *key, size_t keylen, void **result) +{ + hash_entry *table = (hash_entry *) htab->table; + size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen)); + int retval; + + retval = table[idx].used; + *result = retval ? table[idx].data : NULL; + + return retval; +} + + +int +iterate_table (hash_table *htab, void **ptr, void **result) +{ + if (*ptr == NULL) + *ptr = (void *) htab->first; + else + { + *ptr = (void *) (((hash_entry *) *ptr)->next); + if (*ptr == NULL) + return 0; + } + + *result = ((hash_entry *) *ptr)->data; + return 1; +} + + +static size_t +lookup (hash_table *htab, const char *key, size_t keylen, unsigned long hval) +{ + unsigned long hash; + size_t idx; + hash_entry *table = (hash_entry *) htab->table; + + /* First hash function: simply take the modul but prevent zero. */ + hash = 1 + hval % htab->size; + + idx = hash; + + if (table[idx].used) + { + if (table[idx].used == hval && table[idx].key[keylen] == '\0' + && strncmp (key, table[idx].key, keylen) == 0) + return idx; + + /* Second hash function as suggested in [Knuth]. */ + hash = 1 + hash % (htab->size - 2); + + do + { + if (idx <= hash) + idx = htab->size + idx - hash; + else + idx -= hash; + + /* If entry is found use it. */ + if (table[idx].used == hval && table[idx].key[keylen] == '\0' + && strncmp (key, table[idx].key, keylen) == 0) + return idx; + } + while (table[idx].used); + } + return idx; +} + + +static unsigned long +compute_hashval(const char *key, size_t keylen) +{ + size_t cnt; + unsigned long hval, g; + /* Compute the hash value for the given string. */ + cnt = 0; + hval = keylen; + while (cnt < keylen) + { + hval <<= 4; + hval += key[cnt++]; + g = hval & (0xf << (LONGBITS - 4)); + if (g != 0) + { + hval ^= g >> (LONGBITS - 8); + hval ^= g; + } + } + return hval; +} + + +static unsigned long +next_prime(unsigned long seed) +{ + /* Make it definitely odd. */ + seed |= 1; + + while (!is_prime (seed)) + seed += 2; + + return seed; +} + + +static int +is_prime(unsigned long candidate) +{ + /* No even number and none less than 10 will be passwd here. */ + unsigned long div = 3; + unsigned long sq = div * div; + + while (sq < candidate && candidate % div != 0) + { + ++div; + sq += 4 * div; + ++div; + } + + return candidate % div != 0; +} + +/* + * Local Variables: + * mode:c + * c-basic-offset:2 + * End: + */ diff --git a/posix/glob/ChangeLog b/posix/glob/ChangeLog index ac27755ce6..1dd02efc03 100644 --- a/posix/glob/ChangeLog +++ b/posix/glob/ChangeLog @@ -1,3 +1,8 @@ +Thu Dec 14 02:28:22 1995 Roland McGrath + + * posix/glob.c (glob_in_dir): Cast result of opendir to __ptr_t, + and cast STREAM to DIR * before passing to readdir and closedir. + Mon Dec 11 20:07:54 1995 Roland McGrath * posix/glob.c [! STDC_HEADERS]: Declare getenv. -- cgit v1.2.3