diff options
Diffstat (limited to 'bfd')
| -rw-r--r-- | bfd/merge.c | 125 |
1 files changed, 64 insertions, 61 deletions
diff --git a/bfd/merge.c b/bfd/merge.c index cb8251c..a4b928d 100644 --- a/bfd/merge.c +++ b/bfd/merge.c @@ -73,8 +73,6 @@ struct sec_merge_hash_entry struct sec_merge_hash { struct bfd_hash_table table; - /* Next available index. */ - bfd_size_type size; /* First entity in the SEC_MERGE sections of this type. */ struct sec_merge_hash_entry *first; /* Last entity in the SEC_MERGE sections of this type. */ @@ -94,10 +92,6 @@ struct sec_merge_hash struct sec_merge_hash_entry **values; }; -/* True when given NEWCOUNT and NBUCKETS indicate that the hash table needs - resizing. */ -#define NEEDS_RESIZE(newcount, nbuckets) ((newcount) > (nbuckets) / 3 * 2) - struct sec_merge_sec_info; /* Information per merged blob. This is the unit of merging and is @@ -163,63 +157,75 @@ struct sec_merge_sec_info }; +/* True when COUNT+ADDED and NBUCKETS indicate that the hash table + needs resizing. */ + +static inline bool +needs_resize (unsigned int count, unsigned int added, unsigned int nbuckets) +{ + /* This doesn't consider the possibility of "count" + "added" + overflowing, because that can't happen given current usage. If + code calling this function changes then that assumption may no + longer be correct. Currently "added" is always 1 and "nbuckets" + is limited to 0x80000000. We'll attempt and fail resizing at + "count" of 0x55555555. */ + return count + added > nbuckets / 3 * 2; +} + /* Given a merge hash table TABLE and a number of entries to be - ADDED, possibly resize the table for this to fit without further - resizing. Returns false if that can't be done for whatever reason. */ + ADDED, resize the table for this to fit. + Returns false if that can't be done for whatever reason. */ static bool -sec_merge_maybe_resize (struct sec_merge_hash *table, unsigned added) +sec_merge_resize (struct sec_merge_hash *table, unsigned added) { struct bfd_hash_table *bfdtab = &table->table; - if (NEEDS_RESIZE (bfdtab->count + added, table->nbuckets)) - { - unsigned i; - unsigned long newnb = table->nbuckets; - struct sec_merge_hash_entry **newv; - uint64_t *newl; - unsigned long alloc; + unsigned i; + unsigned long newnb = table->nbuckets; + struct sec_merge_hash_entry **newv; + uint64_t *newl; + unsigned long alloc; - do - { - if (newnb >> (8 * sizeof(mapofs_type) - 1)) - return false; - newnb *= 2; - } - while (NEEDS_RESIZE (bfdtab->count + added, newnb)); - - alloc = newnb * sizeof (newl[0]); - if (alloc / sizeof (newl[0]) != newnb) - return false; - newl = objalloc_alloc ((struct objalloc *) table->table.memory, alloc); - if (newl == NULL) - return false; - memset (newl, 0, alloc); - alloc = newnb * sizeof (newv[0]); - if (alloc / sizeof (newv[0]) != newnb) - return false; - newv = objalloc_alloc ((struct objalloc *) table->table.memory, alloc); - if (newv == NULL) + do + { + if (newnb >> (8 * sizeof(mapofs_type) - 1)) return false; - memset (newv, 0, alloc); + newnb *= 2; + } + while (needs_resize (bfdtab->count, added, newnb)); + + alloc = newnb * sizeof (newl[0]); + if (alloc / sizeof (newl[0]) != newnb) + return false; + newl = objalloc_alloc ((struct objalloc *) table->table.memory, alloc); + if (newl == NULL) + return false; + memset (newl, 0, alloc); + alloc = newnb * sizeof (newv[0]); + if (alloc / sizeof (newv[0]) != newnb) + return false; + newv = objalloc_alloc ((struct objalloc *) table->table.memory, alloc); + if (newv == NULL) + return false; + memset (newv, 0, alloc); - for (i = 0; i < table->nbuckets; i++) + for (i = 0; i < table->nbuckets; i++) + { + struct sec_merge_hash_entry *v = table->values[i]; + if (v) { - struct sec_merge_hash_entry *v = table->values[i]; - if (v) - { - uint32_t thishash = table->key_lens[i] >> 32; - unsigned idx = thishash & (newnb - 1); - while (newv[idx]) - idx = (idx + 1) & (newnb - 1); - newl[idx] = table->key_lens[i]; - newv[idx] = v; - } + uint32_t thishash = table->key_lens[i] >> 32; + unsigned idx = thishash & (newnb - 1); + while (newv[idx]) + idx = (idx + 1) & (newnb - 1); + newl[idx] = table->key_lens[i]; + newv[idx] = v; } - - table->key_lens = newl; - table->values = newv; - table->nbuckets = newnb; } + + table->key_lens = newl; + table->values = newv; + table->nbuckets = newnb; return true; } @@ -245,9 +251,9 @@ sec_merge_hash_insert (struct sec_merge_hash *table, hashp->u.suffix = NULL; hashp->next = NULL; - if (NEEDS_RESIZE (bfdtab->count + 1, table->nbuckets)) + if (needs_resize (bfdtab->count, 1, table->nbuckets)) { - if (!sec_merge_maybe_resize (table, 1)) + if (!sec_merge_resize (table, 1)) return NULL; uint64_t *key_lens = table->key_lens; unsigned int nbuckets = table->nbuckets; @@ -422,8 +428,6 @@ sec_merge_hash_lookup (struct sec_merge_hash *table, const char *string, return NULL; hashp->alignment = alignment; - table->size++; - BFD_ASSERT (table->size == table->table.count); if (table->first == NULL) table->first = hashp; else @@ -451,7 +455,6 @@ sec_merge_init (unsigned int entsize, bool strings) return NULL; } - table->size = 0; table->first = NULL; table->last = NULL; table->entsize = entsize; @@ -883,7 +886,7 @@ merge_strings (struct sec_merge_info *sinfo) unsigned int alignment = 0; /* Now sort the strings */ - amt = sinfo->htab->size * sizeof (struct sec_merge_hash_entry *); + amt = sinfo->htab->table.count * sizeof (struct sec_merge_hash_entry *); array = (struct sec_merge_hash_entry **) bfd_malloc (amt); if (array == NULL) return NULL; @@ -903,10 +906,10 @@ merge_strings (struct sec_merge_info *sinfo) } } - sinfo->htab->size = a - array; - if (sinfo->htab->size != 0) + size_t asize = a - array; + if (asize != 0) { - qsort (array, (size_t) sinfo->htab->size, + qsort (array, asize, sizeof (struct sec_merge_hash_entry *), (alignment != (unsigned) -1 && alignment > sinfo->htab->entsize ? strrevcmp_align : strrevcmp)); |