/* hash.c -- gas hash table code
|
/* hash.c -- gas hash table code
|
Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999,
|
Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999,
|
2000, 2001, 2002, 2003, 2005, 2007
|
2000, 2001, 2002, 2003, 2005, 2007
|
Free Software Foundation, Inc.
|
Free Software Foundation, Inc.
|
|
|
This file is part of GAS, the GNU Assembler.
|
This file is part of GAS, the GNU Assembler.
|
|
|
GAS is free software; you can redistribute it and/or modify
|
GAS is free software; you can redistribute it and/or modify
|
it under the terms of the GNU General Public License as published by
|
it under the terms of the GNU General Public License as published by
|
the Free Software Foundation; either version 3, or (at your option)
|
the Free Software Foundation; either version 3, or (at your option)
|
any later version.
|
any later version.
|
|
|
GAS is distributed in the hope that it will be useful,
|
GAS is distributed in the hope that it will be useful,
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
GNU General Public License for more details.
|
GNU General Public License for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GAS; see the file COPYING. If not, write to the Free
|
along with GAS; see the file COPYING. If not, write to the Free
|
Software Foundation, 51 Franklin Street - Fifth Floor, Boston, MA
|
Software Foundation, 51 Franklin Street - Fifth Floor, Boston, MA
|
02110-1301, USA. */
|
02110-1301, USA. */
|
|
|
/* This version of the hash table code is a wholescale replacement of
|
/* This version of the hash table code is a wholescale replacement of
|
the old hash table code, which was fairly bad. This is based on
|
the old hash table code, which was fairly bad. This is based on
|
the hash table code in BFD, but optimized slightly for the
|
the hash table code in BFD, but optimized slightly for the
|
assembler. The assembler does not need to derive structures that
|
assembler. The assembler does not need to derive structures that
|
are stored in the hash table. Instead, it always stores a pointer.
|
are stored in the hash table. Instead, it always stores a pointer.
|
The assembler uses the hash table mostly to store symbols, and we
|
The assembler uses the hash table mostly to store symbols, and we
|
don't need to confuse the symbol structure with a hash table
|
don't need to confuse the symbol structure with a hash table
|
structure. */
|
structure. */
|
|
|
#include "as.h"
|
#include "as.h"
|
#include "safe-ctype.h"
|
#include "safe-ctype.h"
|
#include "obstack.h"
|
#include "obstack.h"
|
|
|
/* An entry in a hash table. */
|
/* An entry in a hash table. */
|
|
|
struct hash_entry {
|
struct hash_entry {
|
/* Next entry for this hash code. */
|
/* Next entry for this hash code. */
|
struct hash_entry *next;
|
struct hash_entry *next;
|
/* String being hashed. */
|
/* String being hashed. */
|
const char *string;
|
const char *string;
|
/* Hash code. This is the full hash code, not the index into the
|
/* Hash code. This is the full hash code, not the index into the
|
table. */
|
table. */
|
unsigned long hash;
|
unsigned long hash;
|
/* Pointer being stored in the hash table. */
|
/* Pointer being stored in the hash table. */
|
PTR data;
|
PTR data;
|
};
|
};
|
|
|
/* A hash table. */
|
/* A hash table. */
|
|
|
struct hash_control {
|
struct hash_control {
|
/* The hash array. */
|
/* The hash array. */
|
struct hash_entry **table;
|
struct hash_entry **table;
|
/* The number of slots in the hash table. */
|
/* The number of slots in the hash table. */
|
unsigned int size;
|
unsigned int size;
|
/* An obstack for this hash table. */
|
/* An obstack for this hash table. */
|
struct obstack memory;
|
struct obstack memory;
|
|
|
#ifdef HASH_STATISTICS
|
#ifdef HASH_STATISTICS
|
/* Statistics. */
|
/* Statistics. */
|
unsigned long lookups;
|
unsigned long lookups;
|
unsigned long hash_compares;
|
unsigned long hash_compares;
|
unsigned long string_compares;
|
unsigned long string_compares;
|
unsigned long insertions;
|
unsigned long insertions;
|
unsigned long replacements;
|
unsigned long replacements;
|
unsigned long deletions;
|
unsigned long deletions;
|
#endif /* HASH_STATISTICS */
|
#endif /* HASH_STATISTICS */
|
};
|
};
|
|
|
/* The default number of entries to use when creating a hash table.
|
/* The default number of entries to use when creating a hash table.
|
Note this value can be reduced to 4051 by using the command line
|
Note this value can be reduced to 4051 by using the command line
|
switch --reduce-memory-overheads, or set to other values by using
|
switch --reduce-memory-overheads, or set to other values by using
|
the --hash-size=<NUMBER> switch. */
|
the --hash-size=<NUMBER> switch. */
|
|
|
static unsigned long gas_hash_table_size = 65537;
|
static unsigned long gas_hash_table_size = 65537;
|
|
|
void
|
void
|
set_gas_hash_table_size (unsigned long size)
|
set_gas_hash_table_size (unsigned long size)
|
{
|
{
|
gas_hash_table_size = size;
|
gas_hash_table_size = size;
|
}
|
}
|
|
|
/* FIXME: This function should be amalgmated with bfd/hash.c:bfd_hash_set_default_size(). */
|
/* FIXME: This function should be amalgmated with bfd/hash.c:bfd_hash_set_default_size(). */
|
static unsigned long
|
static unsigned long
|
get_gas_hash_table_size (void)
|
get_gas_hash_table_size (void)
|
{
|
{
|
/* Extend this prime list if you want more granularity of hash table size. */
|
/* Extend this prime list if you want more granularity of hash table size. */
|
static const unsigned long hash_size_primes[] =
|
static const unsigned long hash_size_primes[] =
|
{
|
{
|
1021, 4051, 8599, 16699, 65537
|
1021, 4051, 8599, 16699, 65537
|
};
|
};
|
unsigned int index;
|
unsigned int index;
|
|
|
/* Work out the best prime number near the hash_size.
|
/* Work out the best prime number near the hash_size.
|
FIXME: This could be a more sophisticated algorithm,
|
FIXME: This could be a more sophisticated algorithm,
|
but is it really worth implementing it ? */
|
but is it really worth implementing it ? */
|
for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index)
|
for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index)
|
if (gas_hash_table_size <= hash_size_primes[index])
|
if (gas_hash_table_size <= hash_size_primes[index])
|
break;
|
break;
|
|
|
return hash_size_primes[index];
|
return hash_size_primes[index];
|
}
|
}
|
|
|
/* Create a hash table. This return a control block. */
|
/* Create a hash table. This return a control block. */
|
|
|
struct hash_control *
|
struct hash_control *
|
hash_new (void)
|
hash_new (void)
|
{
|
{
|
unsigned long size;
|
unsigned long size;
|
unsigned long alloc;
|
unsigned long alloc;
|
struct hash_control *ret;
|
struct hash_control *ret;
|
|
|
size = get_gas_hash_table_size ();
|
size = get_gas_hash_table_size ();
|
|
|
ret = xmalloc (sizeof *ret);
|
ret = xmalloc (sizeof *ret);
|
obstack_begin (&ret->memory, chunksize);
|
obstack_begin (&ret->memory, chunksize);
|
alloc = size * sizeof (struct hash_entry *);
|
alloc = size * sizeof (struct hash_entry *);
|
ret->table = obstack_alloc (&ret->memory, alloc);
|
ret->table = obstack_alloc (&ret->memory, alloc);
|
memset (ret->table, 0, alloc);
|
memset (ret->table, 0, alloc);
|
ret->size = size;
|
ret->size = size;
|
|
|
#ifdef HASH_STATISTICS
|
#ifdef HASH_STATISTICS
|
ret->lookups = 0;
|
ret->lookups = 0;
|
ret->hash_compares = 0;
|
ret->hash_compares = 0;
|
ret->string_compares = 0;
|
ret->string_compares = 0;
|
ret->insertions = 0;
|
ret->insertions = 0;
|
ret->replacements = 0;
|
ret->replacements = 0;
|
ret->deletions = 0;
|
ret->deletions = 0;
|
#endif
|
#endif
|
|
|
return ret;
|
return ret;
|
}
|
}
|
|
|
/* Delete a hash table, freeing all allocated memory. */
|
/* Delete a hash table, freeing all allocated memory. */
|
|
|
void
|
void
|
hash_die (struct hash_control *table)
|
hash_die (struct hash_control *table)
|
{
|
{
|
obstack_free (&table->memory, 0);
|
obstack_free (&table->memory, 0);
|
free (table);
|
free (table);
|
}
|
}
|
|
|
/* Look up a string in a hash table. This returns a pointer to the
|
/* Look up a string in a hash table. This returns a pointer to the
|
hash_entry, or NULL if the string is not in the table. If PLIST is
|
hash_entry, or NULL if the string is not in the table. If PLIST is
|
not NULL, this sets *PLIST to point to the start of the list which
|
not NULL, this sets *PLIST to point to the start of the list which
|
would hold this hash entry. If PHASH is not NULL, this sets *PHASH
|
would hold this hash entry. If PHASH is not NULL, this sets *PHASH
|
to the hash code for KEY.
|
to the hash code for KEY.
|
|
|
Each time we look up a string, we move it to the start of the list
|
Each time we look up a string, we move it to the start of the list
|
for its hash code, to take advantage of referential locality. */
|
for its hash code, to take advantage of referential locality. */
|
|
|
static struct hash_entry *
|
static struct hash_entry *
|
hash_lookup (struct hash_control *table, const char *key, size_t len,
|
hash_lookup (struct hash_control *table, const char *key, size_t len,
|
struct hash_entry ***plist, unsigned long *phash)
|
struct hash_entry ***plist, unsigned long *phash)
|
{
|
{
|
unsigned long hash;
|
unsigned long hash;
|
size_t n;
|
size_t n;
|
unsigned int c;
|
unsigned int c;
|
unsigned int index;
|
unsigned int index;
|
struct hash_entry **list;
|
struct hash_entry **list;
|
struct hash_entry *p;
|
struct hash_entry *p;
|
struct hash_entry *prev;
|
struct hash_entry *prev;
|
|
|
#ifdef HASH_STATISTICS
|
#ifdef HASH_STATISTICS
|
++table->lookups;
|
++table->lookups;
|
#endif
|
#endif
|
|
|
hash = 0;
|
hash = 0;
|
for (n = 0; n < len; n++)
|
for (n = 0; n < len; n++)
|
{
|
{
|
c = key[n];
|
c = key[n];
|
hash += c + (c << 17);
|
hash += c + (c << 17);
|
hash ^= hash >> 2;
|
hash ^= hash >> 2;
|
}
|
}
|
hash += len + (len << 17);
|
hash += len + (len << 17);
|
hash ^= hash >> 2;
|
hash ^= hash >> 2;
|
|
|
if (phash != NULL)
|
if (phash != NULL)
|
*phash = hash;
|
*phash = hash;
|
|
|
index = hash % table->size;
|
index = hash % table->size;
|
list = table->table + index;
|
list = table->table + index;
|
|
|
if (plist != NULL)
|
if (plist != NULL)
|
*plist = list;
|
*plist = list;
|
|
|
prev = NULL;
|
prev = NULL;
|
for (p = *list; p != NULL; p = p->next)
|
for (p = *list; p != NULL; p = p->next)
|
{
|
{
|
#ifdef HASH_STATISTICS
|
#ifdef HASH_STATISTICS
|
++table->hash_compares;
|
++table->hash_compares;
|
#endif
|
#endif
|
|
|
if (p->hash == hash)
|
if (p->hash == hash)
|
{
|
{
|
#ifdef HASH_STATISTICS
|
#ifdef HASH_STATISTICS
|
++table->string_compares;
|
++table->string_compares;
|
#endif
|
#endif
|
|
|
if (strncmp (p->string, key, len) == 0 && p->string[len] == '\0')
|
if (strncmp (p->string, key, len) == 0 && p->string[len] == '\0')
|
{
|
{
|
if (prev != NULL)
|
if (prev != NULL)
|
{
|
{
|
prev->next = p->next;
|
prev->next = p->next;
|
p->next = *list;
|
p->next = *list;
|
*list = p;
|
*list = p;
|
}
|
}
|
|
|
return p;
|
return p;
|
}
|
}
|
}
|
}
|
|
|
prev = p;
|
prev = p;
|
}
|
}
|
|
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
/* Insert an entry into a hash table. This returns NULL on success.
|
/* Insert an entry into a hash table. This returns NULL on success.
|
On error, it returns a printable string indicating the error. It
|
On error, it returns a printable string indicating the error. It
|
is considered to be an error if the entry already exists in the
|
is considered to be an error if the entry already exists in the
|
hash table. */
|
hash table. */
|
|
|
const char *
|
const char *
|
hash_insert (struct hash_control *table, const char *key, PTR value)
|
hash_insert (struct hash_control *table, const char *key, PTR value)
|
{
|
{
|
struct hash_entry *p;
|
struct hash_entry *p;
|
struct hash_entry **list;
|
struct hash_entry **list;
|
unsigned long hash;
|
unsigned long hash;
|
|
|
p = hash_lookup (table, key, strlen (key), &list, &hash);
|
p = hash_lookup (table, key, strlen (key), &list, &hash);
|
if (p != NULL)
|
if (p != NULL)
|
return "exists";
|
return "exists";
|
|
|
#ifdef HASH_STATISTICS
|
#ifdef HASH_STATISTICS
|
++table->insertions;
|
++table->insertions;
|
#endif
|
#endif
|
|
|
p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
|
p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
|
p->string = key;
|
p->string = key;
|
p->hash = hash;
|
p->hash = hash;
|
p->data = value;
|
p->data = value;
|
|
|
p->next = *list;
|
p->next = *list;
|
*list = p;
|
*list = p;
|
|
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
/* Insert or replace an entry in a hash table. This returns NULL on
|
/* Insert or replace an entry in a hash table. This returns NULL on
|
success. On error, it returns a printable string indicating the
|
success. On error, it returns a printable string indicating the
|
error. If an entry already exists, its value is replaced. */
|
error. If an entry already exists, its value is replaced. */
|
|
|
const char *
|
const char *
|
hash_jam (struct hash_control *table, const char *key, PTR value)
|
hash_jam (struct hash_control *table, const char *key, PTR value)
|
{
|
{
|
struct hash_entry *p;
|
struct hash_entry *p;
|
struct hash_entry **list;
|
struct hash_entry **list;
|
unsigned long hash;
|
unsigned long hash;
|
|
|
p = hash_lookup (table, key, strlen (key), &list, &hash);
|
p = hash_lookup (table, key, strlen (key), &list, &hash);
|
if (p != NULL)
|
if (p != NULL)
|
{
|
{
|
#ifdef HASH_STATISTICS
|
#ifdef HASH_STATISTICS
|
++table->replacements;
|
++table->replacements;
|
#endif
|
#endif
|
|
|
p->data = value;
|
p->data = value;
|
}
|
}
|
else
|
else
|
{
|
{
|
#ifdef HASH_STATISTICS
|
#ifdef HASH_STATISTICS
|
++table->insertions;
|
++table->insertions;
|
#endif
|
#endif
|
|
|
p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
|
p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
|
p->string = key;
|
p->string = key;
|
p->hash = hash;
|
p->hash = hash;
|
p->data = value;
|
p->data = value;
|
|
|
p->next = *list;
|
p->next = *list;
|
*list = p;
|
*list = p;
|
}
|
}
|
|
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
/* Replace an existing entry in a hash table. This returns the old
|
/* Replace an existing entry in a hash table. This returns the old
|
value stored for the entry. If the entry is not found in the hash
|
value stored for the entry. If the entry is not found in the hash
|
table, this does nothing and returns NULL. */
|
table, this does nothing and returns NULL. */
|
|
|
PTR
|
PTR
|
hash_replace (struct hash_control *table, const char *key, PTR value)
|
hash_replace (struct hash_control *table, const char *key, PTR value)
|
{
|
{
|
struct hash_entry *p;
|
struct hash_entry *p;
|
PTR ret;
|
PTR ret;
|
|
|
p = hash_lookup (table, key, strlen (key), NULL, NULL);
|
p = hash_lookup (table, key, strlen (key), NULL, NULL);
|
if (p == NULL)
|
if (p == NULL)
|
return NULL;
|
return NULL;
|
|
|
#ifdef HASH_STATISTICS
|
#ifdef HASH_STATISTICS
|
++table->replacements;
|
++table->replacements;
|
#endif
|
#endif
|
|
|
ret = p->data;
|
ret = p->data;
|
|
|
p->data = value;
|
p->data = value;
|
|
|
return ret;
|
return ret;
|
}
|
}
|
|
|
/* Find an entry in a hash table, returning its value. Returns NULL
|
/* Find an entry in a hash table, returning its value. Returns NULL
|
if the entry is not found. */
|
if the entry is not found. */
|
|
|
PTR
|
PTR
|
hash_find (struct hash_control *table, const char *key)
|
hash_find (struct hash_control *table, const char *key)
|
{
|
{
|
struct hash_entry *p;
|
struct hash_entry *p;
|
|
|
p = hash_lookup (table, key, strlen (key), NULL, NULL);
|
p = hash_lookup (table, key, strlen (key), NULL, NULL);
|
if (p == NULL)
|
if (p == NULL)
|
return NULL;
|
return NULL;
|
|
|
return p->data;
|
return p->data;
|
}
|
}
|
|
|
/* As hash_find, but KEY is of length LEN and is not guaranteed to be
|
/* As hash_find, but KEY is of length LEN and is not guaranteed to be
|
NUL-terminated. */
|
NUL-terminated. */
|
|
|
PTR
|
PTR
|
hash_find_n (struct hash_control *table, const char *key, size_t len)
|
hash_find_n (struct hash_control *table, const char *key, size_t len)
|
{
|
{
|
struct hash_entry *p;
|
struct hash_entry *p;
|
|
|
p = hash_lookup (table, key, len, NULL, NULL);
|
p = hash_lookup (table, key, len, NULL, NULL);
|
if (p == NULL)
|
if (p == NULL)
|
return NULL;
|
return NULL;
|
|
|
return p->data;
|
return p->data;
|
}
|
}
|
|
|
/* Delete an entry from a hash table. This returns the value stored
|
/* Delete an entry from a hash table. This returns the value stored
|
for that entry, or NULL if there is no such entry. */
|
for that entry, or NULL if there is no such entry. */
|
|
|
PTR
|
PTR
|
hash_delete (struct hash_control *table, const char *key)
|
hash_delete (struct hash_control *table, const char *key)
|
{
|
{
|
struct hash_entry *p;
|
struct hash_entry *p;
|
struct hash_entry **list;
|
struct hash_entry **list;
|
|
|
p = hash_lookup (table, key, strlen (key), &list, NULL);
|
p = hash_lookup (table, key, strlen (key), &list, NULL);
|
if (p == NULL)
|
if (p == NULL)
|
return NULL;
|
return NULL;
|
|
|
if (p != *list)
|
if (p != *list)
|
abort ();
|
abort ();
|
|
|
#ifdef HASH_STATISTICS
|
#ifdef HASH_STATISTICS
|
++table->deletions;
|
++table->deletions;
|
#endif
|
#endif
|
|
|
*list = p->next;
|
*list = p->next;
|
|
|
/* Note that we never reclaim the memory for this entry. If gas
|
/* Note that we never reclaim the memory for this entry. If gas
|
ever starts deleting hash table entries in a big way, this will
|
ever starts deleting hash table entries in a big way, this will
|
have to change. */
|
have to change. */
|
|
|
return p->data;
|
return p->data;
|
}
|
}
|
|
|
/* Traverse a hash table. Call the function on every entry in the
|
/* Traverse a hash table. Call the function on every entry in the
|
hash table. */
|
hash table. */
|
|
|
void
|
void
|
hash_traverse (struct hash_control *table,
|
hash_traverse (struct hash_control *table,
|
void (*pfn) (const char *key, PTR value))
|
void (*pfn) (const char *key, PTR value))
|
{
|
{
|
unsigned int i;
|
unsigned int i;
|
|
|
for (i = 0; i < table->size; ++i)
|
for (i = 0; i < table->size; ++i)
|
{
|
{
|
struct hash_entry *p;
|
struct hash_entry *p;
|
|
|
for (p = table->table[i]; p != NULL; p = p->next)
|
for (p = table->table[i]; p != NULL; p = p->next)
|
(*pfn) (p->string, p->data);
|
(*pfn) (p->string, p->data);
|
}
|
}
|
}
|
}
|
|
|
/* Print hash table statistics on the specified file. NAME is the
|
/* Print hash table statistics on the specified file. NAME is the
|
name of the hash table, used for printing a header. */
|
name of the hash table, used for printing a header. */
|
|
|
void
|
void
|
hash_print_statistics (FILE *f ATTRIBUTE_UNUSED,
|
hash_print_statistics (FILE *f ATTRIBUTE_UNUSED,
|
const char *name ATTRIBUTE_UNUSED,
|
const char *name ATTRIBUTE_UNUSED,
|
struct hash_control *table ATTRIBUTE_UNUSED)
|
struct hash_control *table ATTRIBUTE_UNUSED)
|
{
|
{
|
#ifdef HASH_STATISTICS
|
#ifdef HASH_STATISTICS
|
unsigned int i;
|
unsigned int i;
|
unsigned long total;
|
unsigned long total;
|
unsigned long empty;
|
unsigned long empty;
|
|
|
fprintf (f, "%s hash statistics:\n", name);
|
fprintf (f, "%s hash statistics:\n", name);
|
fprintf (f, "\t%lu lookups\n", table->lookups);
|
fprintf (f, "\t%lu lookups\n", table->lookups);
|
fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
|
fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
|
fprintf (f, "\t%lu string comparisons\n", table->string_compares);
|
fprintf (f, "\t%lu string comparisons\n", table->string_compares);
|
fprintf (f, "\t%lu insertions\n", table->insertions);
|
fprintf (f, "\t%lu insertions\n", table->insertions);
|
fprintf (f, "\t%lu replacements\n", table->replacements);
|
fprintf (f, "\t%lu replacements\n", table->replacements);
|
fprintf (f, "\t%lu deletions\n", table->deletions);
|
fprintf (f, "\t%lu deletions\n", table->deletions);
|
|
|
total = 0;
|
total = 0;
|
empty = 0;
|
empty = 0;
|
for (i = 0; i < table->size; ++i)
|
for (i = 0; i < table->size; ++i)
|
{
|
{
|
struct hash_entry *p;
|
struct hash_entry *p;
|
|
|
if (table->table[i] == NULL)
|
if (table->table[i] == NULL)
|
++empty;
|
++empty;
|
else
|
else
|
{
|
{
|
for (p = table->table[i]; p != NULL; p = p->next)
|
for (p = table->table[i]; p != NULL; p = p->next)
|
++total;
|
++total;
|
}
|
}
|
}
|
}
|
|
|
fprintf (f, "\t%g average chain length\n", (double) total / table->size);
|
fprintf (f, "\t%g average chain length\n", (double) total / table->size);
|
fprintf (f, "\t%lu empty slots\n", empty);
|
fprintf (f, "\t%lu empty slots\n", empty);
|
#endif
|
#endif
|
}
|
}
|
|
|
#ifdef TEST
|
#ifdef TEST
|
|
|
/* This test program is left over from the old hash table code. */
|
/* This test program is left over from the old hash table code. */
|
|
|
/* Number of hash tables to maintain (at once) in any testing. */
|
/* Number of hash tables to maintain (at once) in any testing. */
|
#define TABLES (6)
|
#define TABLES (6)
|
|
|
/* We can have 12 statistics. */
|
/* We can have 12 statistics. */
|
#define STATBUFSIZE (12)
|
#define STATBUFSIZE (12)
|
|
|
/* Display statistics here. */
|
/* Display statistics here. */
|
int statbuf[STATBUFSIZE];
|
int statbuf[STATBUFSIZE];
|
|
|
/* Human farts here. */
|
/* Human farts here. */
|
char answer[100];
|
char answer[100];
|
|
|
/* We test many hash tables at once. */
|
/* We test many hash tables at once. */
|
char *hashtable[TABLES];
|
char *hashtable[TABLES];
|
|
|
/* Points to current hash_control. */
|
/* Points to current hash_control. */
|
char *h;
|
char *h;
|
char **pp;
|
char **pp;
|
char *p;
|
char *p;
|
char *name;
|
char *name;
|
char *value;
|
char *value;
|
int size;
|
int size;
|
int used;
|
int used;
|
char command;
|
char command;
|
|
|
/* Number 0:TABLES-1 of current hashed symbol table. */
|
/* Number 0:TABLES-1 of current hashed symbol table. */
|
int number;
|
int number;
|
|
|
int
|
int
|
main ()
|
main ()
|
{
|
{
|
void applicatee ();
|
void applicatee ();
|
void destroy ();
|
void destroy ();
|
char *what ();
|
char *what ();
|
int *ip;
|
int *ip;
|
|
|
number = 0;
|
number = 0;
|
h = 0;
|
h = 0;
|
printf ("type h <RETURN> for help\n");
|
printf ("type h <RETURN> for help\n");
|
for (;;)
|
for (;;)
|
{
|
{
|
printf ("hash_test command: ");
|
printf ("hash_test command: ");
|
gets (answer);
|
gets (answer);
|
command = answer[0];
|
command = answer[0];
|
command = TOLOWER (command); /* Ecch! */
|
command = TOLOWER (command); /* Ecch! */
|
switch (command)
|
switch (command)
|
{
|
{
|
case '#':
|
case '#':
|
printf ("old hash table #=%d.\n", number);
|
printf ("old hash table #=%d.\n", number);
|
whattable ();
|
whattable ();
|
break;
|
break;
|
case '?':
|
case '?':
|
for (pp = hashtable; pp < hashtable + TABLES; pp++)
|
for (pp = hashtable; pp < hashtable + TABLES; pp++)
|
{
|
{
|
printf ("address of hash table #%d control block is %xx\n",
|
printf ("address of hash table #%d control block is %xx\n",
|
pp - hashtable, *pp);
|
pp - hashtable, *pp);
|
}
|
}
|
break;
|
break;
|
case 'a':
|
case 'a':
|
hash_traverse (h, applicatee);
|
hash_traverse (h, applicatee);
|
break;
|
break;
|
case 'd':
|
case 'd':
|
hash_traverse (h, destroy);
|
hash_traverse (h, destroy);
|
hash_die (h);
|
hash_die (h);
|
break;
|
break;
|
case 'f':
|
case 'f':
|
p = hash_find (h, name = what ("symbol"));
|
p = hash_find (h, name = what ("symbol"));
|
printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
|
printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
|
break;
|
break;
|
case 'h':
|
case 'h':
|
printf ("# show old, select new default hash table number\n");
|
printf ("# show old, select new default hash table number\n");
|
printf ("? display all hashtable control block addresses\n");
|
printf ("? display all hashtable control block addresses\n");
|
printf ("a apply a simple display-er to each symbol in table\n");
|
printf ("a apply a simple display-er to each symbol in table\n");
|
printf ("d die: destroy hashtable\n");
|
printf ("d die: destroy hashtable\n");
|
printf ("f find value of nominated symbol\n");
|
printf ("f find value of nominated symbol\n");
|
printf ("h this help\n");
|
printf ("h this help\n");
|
printf ("i insert value into symbol\n");
|
printf ("i insert value into symbol\n");
|
printf ("j jam value into symbol\n");
|
printf ("j jam value into symbol\n");
|
printf ("n new hashtable\n");
|
printf ("n new hashtable\n");
|
printf ("r replace a value with another\n");
|
printf ("r replace a value with another\n");
|
printf ("s say what %% of table is used\n");
|
printf ("s say what %% of table is used\n");
|
printf ("q exit this program\n");
|
printf ("q exit this program\n");
|
printf ("x delete a symbol from table, report its value\n");
|
printf ("x delete a symbol from table, report its value\n");
|
break;
|
break;
|
case 'i':
|
case 'i':
|
p = hash_insert (h, name = what ("symbol"), value = what ("value"));
|
p = hash_insert (h, name = what ("symbol"), value = what ("value"));
|
if (p)
|
if (p)
|
{
|
{
|
printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value,
|
printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value,
|
p);
|
p);
|
}
|
}
|
break;
|
break;
|
case 'j':
|
case 'j':
|
p = hash_jam (h, name = what ("symbol"), value = what ("value"));
|
p = hash_jam (h, name = what ("symbol"), value = what ("value"));
|
if (p)
|
if (p)
|
{
|
{
|
printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, p);
|
printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, p);
|
}
|
}
|
break;
|
break;
|
case 'n':
|
case 'n':
|
h = hashtable[number] = (char *) hash_new ();
|
h = hashtable[number] = (char *) hash_new ();
|
break;
|
break;
|
case 'q':
|
case 'q':
|
exit (EXIT_SUCCESS);
|
exit (EXIT_SUCCESS);
|
case 'r':
|
case 'r':
|
p = hash_replace (h, name = what ("symbol"), value = what ("value"));
|
p = hash_replace (h, name = what ("symbol"), value = what ("value"));
|
printf ("old value was \"%s\"\n", p ? p : "{}");
|
printf ("old value was \"%s\"\n", p ? p : "{}");
|
break;
|
break;
|
case 's':
|
case 's':
|
hash_say (h, statbuf, STATBUFSIZE);
|
hash_say (h, statbuf, STATBUFSIZE);
|
for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
|
for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
|
{
|
{
|
printf ("%d ", *ip);
|
printf ("%d ", *ip);
|
}
|
}
|
printf ("\n");
|
printf ("\n");
|
break;
|
break;
|
case 'x':
|
case 'x':
|
p = hash_delete (h, name = what ("symbol"));
|
p = hash_delete (h, name = what ("symbol"));
|
printf ("old value was \"%s\"\n", p ? p : "{}");
|
printf ("old value was \"%s\"\n", p ? p : "{}");
|
break;
|
break;
|
default:
|
default:
|
printf ("I can't understand command \"%c\"\n", command);
|
printf ("I can't understand command \"%c\"\n", command);
|
break;
|
break;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
char *
|
char *
|
what (description)
|
what (description)
|
char *description;
|
char *description;
|
{
|
{
|
printf (" %s : ", description);
|
printf (" %s : ", description);
|
gets (answer);
|
gets (answer);
|
return xstrdup (answer);
|
return xstrdup (answer);
|
}
|
}
|
|
|
void
|
void
|
destroy (string, value)
|
destroy (string, value)
|
char *string;
|
char *string;
|
char *value;
|
char *value;
|
{
|
{
|
free (string);
|
free (string);
|
free (value);
|
free (value);
|
}
|
}
|
|
|
void
|
void
|
applicatee (string, value)
|
applicatee (string, value)
|
char *string;
|
char *string;
|
char *value;
|
char *value;
|
{
|
{
|
printf ("%.20s-%.20s\n", string, value);
|
printf ("%.20s-%.20s\n", string, value);
|
}
|
}
|
|
|
/* Determine number: what hash table to use.
|
/* Determine number: what hash table to use.
|
Also determine h: points to hash_control. */
|
Also determine h: points to hash_control. */
|
|
|
void
|
void
|
whattable ()
|
whattable ()
|
{
|
{
|
for (;;)
|
for (;;)
|
{
|
{
|
printf (" what hash table (%d:%d) ? ", 0, TABLES - 1);
|
printf (" what hash table (%d:%d) ? ", 0, TABLES - 1);
|
gets (answer);
|
gets (answer);
|
sscanf (answer, "%d", &number);
|
sscanf (answer, "%d", &number);
|
if (number >= 0 && number < TABLES)
|
if (number >= 0 && number < TABLES)
|
{
|
{
|
h = hashtable[number];
|
h = hashtable[number];
|
if (!h)
|
if (!h)
|
{
|
{
|
printf ("warning: current hash-table-#%d. has no hash-control\n", number);
|
printf ("warning: current hash-table-#%d. has no hash-control\n", number);
|
}
|
}
|
return;
|
return;
|
}
|
}
|
else
|
else
|
{
|
{
|
printf ("invalid hash table number: %d\n", number);
|
printf ("invalid hash table number: %d\n", number);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
#endif /* TEST */
|
#endif /* TEST */
|
|
|
