projects
/
deliverable
/
binutils-gdb.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Rotate ChangeLogs
[deliverable/binutils-gdb.git]
/
gas
/
hash.c
diff --git
a/gas/hash.c
b/gas/hash.c
index 0f129fb3fa1938f4038d80ff960a1fbc5fd192df..a58c9489b6abd0b3f3b48057d4f549ec9bf28996 100644
(file)
--- a/
gas/hash.c
+++ b/
gas/hash.c
@@
-1,12
+1,13
@@
/* hash.c -- gas hash table code
/* hash.c -- gas hash table code
- Copyright (C) 1987, 90, 91, 92, 93, 94, 95, 96, 98, 1999
+ Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999,
+ 2000, 2001, 2002, 2003, 2005, 2007, 2008, 2009, 2011
Free Software Foundation, Inc.
This file is part of GAS, the GNU Assembler.
GAS is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
Free Software Foundation, Inc.
This file is part of GAS, the GNU Assembler.
GAS 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)
+ the Free Software Foundation; either version
3
, or (at your option)
any later version.
GAS is distributed in the hope that it will be useful,
any later version.
GAS is distributed in the hope that it will be useful,
@@
-16,29
+17,25
@@
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
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
- Software Foundation, 5
9 Temple Place - Suite 330
, Boston, MA
- 0211
1-1307
, USA. */
+ Software Foundation, 5
1 Franklin Street - Fifth Floor
, Boston, MA
+ 0211
0-1301
, USA. */
/* 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 hash table code in BFD, but optimized slightly for the
/* 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 hash table code in BFD, but optimized slightly for the
- ass
s
embler. 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.
The assembler uses the hash table mostly to store symbols, and we
don't need to confuse the symbol structure with a hash table
structure. */
#include "as.h"
are stored in the hash table. Instead, it always stores a pointer.
The assembler uses the hash table mostly to store symbols, and we
don't need to confuse the symbol structure with a hash table
structure. */
#include "as.h"
+#include "safe-ctype.h"
#include "obstack.h"
#include "obstack.h"
-/* The default number of entries to use when creating a hash table. */
-
-#define DEFAULT_SIZE (4051)
-
/* An entry in a hash table. */
/* An entry in a hash table. */
-struct hash_entry
-{
+struct hash_entry {
/* Next entry for this hash code. */
struct hash_entry *next;
/* String being hashed. */
/* Next entry for this hash code. */
struct hash_entry *next;
/* String being hashed. */
@@
-47,13
+44,12
@@
struct hash_entry
table. */
unsigned long hash;
/* Pointer being stored in the hash table. */
table. */
unsigned long hash;
/* Pointer being stored in the hash table. */
-
PTR
data;
+
void *
data;
};
/* A hash table. */
};
/* A hash table. */
-struct hash_control
-{
+struct hash_control {
/* The hash array. */
struct hash_entry **table;
/* The number of slots in the hash table. */
/* The hash array. */
struct hash_entry **table;
/* The number of slots in the hash table. */
@@
-72,16
+68,26
@@
struct hash_control
#endif /* HASH_STATISTICS */
};
#endif /* HASH_STATISTICS */
};
+/* 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
+ switch --reduce-memory-overheads, or set to other values by using
+ the --hash-size=<NUMBER> switch. */
+
+static unsigned long gas_hash_table_size = 65537;
+
+void
+set_gas_hash_table_size (unsigned long size)
+{
+ gas_hash_table_size = bfd_hash_set_default_size (size);
+}
+
/* Create a hash table. This return a control block. */
/* Create a hash table. This return a control block. */
-struct hash_control *
-hash_new
(
)
+st
atic st
ruct hash_control *
+hash_new
_sized (unsigned long size
)
{
{
- unsigned
int size
;
+ unsigned
long alloc
;
struct hash_control *ret;
struct hash_control *ret;
- unsigned int alloc;
-
- size = DEFAULT_SIZE;
ret = (struct hash_control *) xmalloc (sizeof *ret);
obstack_begin (&ret->memory, chunksize);
ret = (struct hash_control *) xmalloc (sizeof *ret);
obstack_begin (&ret->memory, chunksize);
@@
-99,14
+105,19
@@
hash_new ()
ret->deletions = 0;
#endif
ret->deletions = 0;
#endif
- return ret;
+ return ret;
+}
+
+struct hash_control *
+hash_new (void)
+{
+ return hash_new_sized (gas_hash_table_size);
}
/* Delete a hash table, freeing all allocated memory. */
void
}
/* Delete a hash table, freeing all allocated memory. */
void
-hash_die (table)
- struct hash_control *table;
+hash_die (struct hash_control *table)
{
obstack_free (&table->memory, 0);
free (table);
{
obstack_free (&table->memory, 0);
free (table);
@@
-121,23
+132,14
@@
hash_die (table)
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. */
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. */
-static struct hash_entry *hash_lookup PARAMS ((struct hash_control *,
- const char *,
- struct hash_entry ***,
- unsigned long *));
-
static struct hash_entry *
static struct hash_entry *
-hash_lookup (table, key, plist, phash)
- struct hash_control *table;
- const char *key;
- struct hash_entry ***plist;
- unsigned long *phash;
+hash_lookup (struct hash_control *table, const char *key, size_t len,
+ struct hash_entry ***plist, unsigned long *phash)
{
{
- register unsigned long hash;
- unsigned int len;
- register const unsigned char *s;
- register unsigned int c;
- unsigned int index;
+ unsigned long hash;
+ size_t n;
+ unsigned int c;
+ unsigned int hindex;
struct hash_entry **list;
struct hash_entry *p;
struct hash_entry *prev;
struct hash_entry **list;
struct hash_entry *p;
struct hash_entry *prev;
@@
-147,13
+149,11
@@
hash_lookup (table, key, plist, phash)
#endif
hash = 0;
#endif
hash = 0;
- len = 0;
- s = (const unsigned char *) key;
- while ((c = *s++) != '\0')
+ for (n = 0; n < len; n++)
{
{
+ c = key[n];
hash += c + (c << 17);
hash ^= hash >> 2;
hash += c + (c << 17);
hash ^= hash >> 2;
- ++len;
}
hash += len + (len << 17);
hash ^= hash >> 2;
}
hash += len + (len << 17);
hash ^= hash >> 2;
@@
-161,8
+161,8
@@
hash_lookup (table, key, plist, phash)
if (phash != NULL)
*phash = hash;
if (phash != NULL)
*phash = hash;
- index = hash % table->size;
- list = table->table + index;
+
h
index = hash % table->size;
+ list = table->table +
h
index;
if (plist != NULL)
*plist = list;
if (plist != NULL)
*plist = list;
@@
-180,7
+180,7
@@
hash_lookup (table, key, plist, phash)
++table->string_compares;
#endif
++table->string_compares;
#endif
- if (str
cmp (p->string, key) == 0
)
+ if (str
ncmp (p->string, key, len) == 0 && p->string[len] == '\0'
)
{
if (prev != NULL)
{
{
if (prev != NULL)
{
@@
-205,16
+205,13
@@
hash_lookup (table, key, plist, phash)
hash table. */
const char *
hash table. */
const char *
-hash_insert (table, key, value)
- struct hash_control *table;
- const char *key;
- PTR value;
+hash_insert (struct hash_control *table, const char *key, void *val)
{
struct hash_entry *p;
struct hash_entry **list;
unsigned long hash;
{
struct hash_entry *p;
struct hash_entry **list;
unsigned long hash;
- p = hash_lookup (table, key, &list, &hash);
+ p = hash_lookup (table, key,
strlen (key),
&list, &hash);
if (p != NULL)
return "exists";
if (p != NULL)
return "exists";
@@
-222,10
+219,10
@@
hash_insert (table, key, value)
++table->insertions;
#endif
++table->insertions;
#endif
- p =
obstack_alloc (&table->memory, sizeof *p
);
+ p =
(struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p)
);
p->string = key;
p->hash = hash;
p->string = key;
p->hash = hash;
- p->data = val
ue
;
+ p->data = val;
p->next = *list;
*list = p;
p->next = *list;
*list = p;
@@
-238,23
+235,20
@@
hash_insert (table, key, value)
error. If an entry already exists, its value is replaced. */
const char *
error. If an entry already exists, its value is replaced. */
const char *
-hash_jam (table, key, value)
- struct hash_control *table;
- const char *key;
- PTR value;
+hash_jam (struct hash_control *table, const char *key, void *val)
{
struct hash_entry *p;
struct hash_entry **list;
unsigned long hash;
{
struct hash_entry *p;
struct hash_entry **list;
unsigned long hash;
- p = hash_lookup (table, key, &list, &hash);
+ p = hash_lookup (table, key,
strlen (key),
&list, &hash);
if (p != NULL)
{
#ifdef HASH_STATISTICS
++table->replacements;
#endif
if (p != NULL)
{
#ifdef HASH_STATISTICS
++table->replacements;
#endif
- p->data = val
ue
;
+ p->data = val;
}
else
{
}
else
{
@@
-262,10
+256,10
@@
hash_jam (table, key, value)
++table->insertions;
#endif
++table->insertions;
#endif
- p =
obstack_alloc (&table->memory, sizeof *p
);
+ p =
(struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p)
);
p->string = key;
p->hash = hash;
p->string = key;
p->hash = hash;
- p->data = val
ue
;
+ p->data = val;
p->next = *list;
*list = p;
p->next = *list;
*list = p;
@@
-278,16
+272,13
@@
hash_jam (table, key, value)
value stored for the entry. If the entry is not found in the hash
table, this does nothing and returns NULL. */
value stored for the entry. If the entry is not found in the hash
table, this does nothing and returns NULL. */
-PTR
-hash_replace (table, key, value)
- struct hash_control *table;
- const char *key;
- PTR value;
+void *
+hash_replace (struct hash_control *table, const char *key, void *value)
{
struct hash_entry *p;
{
struct hash_entry *p;
-
PTR
ret;
+
void *
ret;
- p = hash_lookup (table, key, NULL, NULL);
+ p = hash_lookup (table, key,
strlen (key),
NULL, NULL);
if (p == NULL)
return NULL;
if (p == NULL)
return NULL;
@@
-305,14
+296,27
@@
hash_replace (table, key, value)
/* Find an entry in a hash table, returning its value. Returns NULL
if the entry is not found. */
/* Find an entry in a hash table, returning its value. Returns NULL
if the entry is not found. */
-PTR
-hash_find (table, key)
- struct hash_control *table;
- const char *key;
+void *
+hash_find (struct hash_control *table, const char *key)
{
struct hash_entry *p;
{
struct hash_entry *p;
- p = hash_lookup (table, key, NULL, NULL);
+ p = hash_lookup (table, key, strlen (key), NULL, NULL);
+ if (p == NULL)
+ return NULL;
+
+ return p->data;
+}
+
+/* As hash_find, but KEY is of length LEN and is not guaranteed to be
+ NUL-terminated. */
+
+void *
+hash_find_n (struct hash_control *table, const char *key, size_t len)
+{
+ struct hash_entry *p;
+
+ p = hash_lookup (table, key, len, NULL, NULL);
if (p == NULL)
return NULL;
if (p == NULL)
return NULL;
@@
-322,15
+326,13
@@
hash_find (table, key)
/* Delete an entry from a hash table. This returns the value stored
for that entry, or NULL if there is no such entry. */
/* Delete an entry from a hash table. This returns the value stored
for that entry, or NULL if there is no such entry. */
-PTR
-hash_delete (table, key)
- struct hash_control *table;
- const char *key;
+void *
+hash_delete (struct hash_control *table, const char *key, int freeme)
{
struct hash_entry *p;
struct hash_entry **list;
{
struct hash_entry *p;
struct hash_entry **list;
- p = hash_lookup (table, key, &list, NULL);
+ p = hash_lookup (table, key,
strlen (key),
&list, NULL);
if (p == NULL)
return NULL;
if (p == NULL)
return NULL;
@@
-343,9
+345,8
@@
hash_delete (table, key)
*list = p->next;
*list = p->next;
- /* Note that we never reclaim the memory for this entry. If gas
- ever starts deleting hash table entries in a big way, this will
- have to change. */
+ if (freeme)
+ obstack_free (&table->memory, p);
return p->data;
}
return p->data;
}
@@
-354,9
+355,8
@@
hash_delete (table, key)
hash table. */
void
hash table. */
void
-hash_traverse (table, pfn)
- struct hash_control *table;
- void (*pfn) PARAMS ((const char *key, PTR value));
+hash_traverse (struct hash_control *table,
+ void (*pfn) (const char *key, void *value))
{
unsigned int i;
{
unsigned int i;
@@
-373,10
+373,9
@@
hash_traverse (table, pfn)
name of the hash table, used for printing a header. */
void
name of the hash table, used for printing a header. */
void
-hash_print_statistics (f, name, table)
- FILE *f ATTRIBUTE_UNUSED;
- const char *name ATTRIBUTE_UNUSED;
- struct hash_control *table ATTRIBUTE_UNUSED;
+hash_print_statistics (FILE *f ATTRIBUTE_UNUSED,
+ const char *name ATTRIBUTE_UNUSED,
+ struct hash_control *table ATTRIBUTE_UNUSED)
{
#ifdef HASH_STATISTICS
unsigned int i;
{
#ifdef HASH_STATISTICS
unsigned int i;
@@
-415,14
+414,23
@@
hash_print_statistics (f, name, table)
/* This test program is left over from the old hash table code. */
/* This test program is left over from the old hash table code. */
-#define TABLES (6) /* number of hash tables to maintain */
- /* (at once) in any testing */
-#define STATBUFSIZE (12) /* we can have 12 statistics */
+/* Number of hash tables to maintain (at once) in any testing. */
+#define TABLES (6)
+
+/* We can have 12 statistics. */
+#define STATBUFSIZE (12)
+
+/* Display statistics here. */
+int statbuf[STATBUFSIZE];
-int statbuf[STATBUFSIZE]; /* display statistics here */
-char answer[100]; /* human farts here */
-char *hashtable[TABLES]; /* we test many hash tables at once */
-char *h; /* points to curent hash_control */
+/* Human farts here. */
+char answer[100];
+
+/* We test many hash tables at once. */
+char *hashtable[TABLES];
+
+/* Points to current hash_control. */
+char *h;
char **pp;
char *p;
char *name;
char **pp;
char *p;
char *name;
@@
-430,8
+438,9
@@
char *value;
int size;
int used;
char command;
int size;
int used;
char command;
-int number; /* number 0:TABLES-1 of current hashed */
- /* symbol table */
+
+/* Number 0:TABLES-1 of current hashed symbol table. */
+int number;
int
main ()
int
main ()
@@
-449,8
+458,7
@@
main ()
printf ("hash_test command: ");
gets (answer);
command = answer[0];
printf ("hash_test command: ");
gets (answer);
command = answer[0];
- if (isupper (command))
- command = tolower (command); /* ecch! */
+ command = TOLOWER (command); /* Ecch! */
switch (command)
{
case '#':
switch (command)
{
case '#':
@@
-460,8
+468,8
@@
main ()
case '?':
for (pp = hashtable; pp < hashtable + TABLES; pp++)
{
case '?':
for (pp = hashtable; pp < hashtable + TABLES; pp++)
{
- printf ("address of hash table #%d control block is %xx\n"
-
,
pp - hashtable, *pp);
+ printf ("address of hash table #%d control block is %xx\n"
,
+ pp - hashtable, *pp);
}
break;
case 'a':
}
break;
case 'a':
@@
-537,19
+545,9
@@
char *
what (description)
char *description;
{
what (description)
char *description;
{
- char *retval;
- char *malloc ();
-
printf (" %s : ", description);
gets (answer);
printf (" %s : ", description);
gets (answer);
- /* will one day clean up answer here */
- retval = malloc (strlen (answer) + 1);
- if (!retval)
- {
- error ("room");
- }
- (void) strcpy (retval, answer);
- return (retval);
+ return xstrdup (answer);
}
void
}
void
@@
-561,7
+559,6
@@
destroy (string, value)
free (value);
}
free (value);
}
-
void
applicatee (string, value)
char *string;
void
applicatee (string, value)
char *string;
@@
-570,11
+567,12
@@
applicatee (string, value)
printf ("%.20s-%.20s\n", string, value);
}
printf ("%.20s-%.20s\n", string, value);
}
+/* Determine number: what hash table to use.
+ Also determine h: points to hash_control. */
+
void
void
-whattable () /* determine number: what hash table to use */
- /* also determine h: points to hash_control */
+whattable ()
{
{
-
for (;;)
{
printf (" what hash table (%d:%d) ? ", 0, TABLES - 1);
for (;;)
{
printf (" what hash table (%d:%d) ? ", 0, TABLES - 1);
@@
-596,6
+594,4
@@
whattable () /* determine number: what hash table to use */
}
}
}
}
-#endif /* #ifdef TEST */
-
-/* end of hash.c */
+#endif /* TEST */
This page took
0.029226 seconds
and
4
git commands to generate.