Hi Juergen,
On 13/12/2022 16:00, Juergen Gross wrote:
@@ -115,47 +117,32 @@ hashtable_expand(struct hashtable *h)
if (h->primeindex == (prime_table_length - 1)) return 0;
newsize = primes[++(h->primeindex)];
- newtable = (struct entry **)calloc(newsize, sizeof(struct entry*));
- if (NULL != newtable)
+ newtable = talloc_realloc(h, h->table, struct entry *, newsize);
+ if (!newtable)
{
- /* This algorithm is not 'stable'. ie. it reverses the list
- * when it transfers entries between the tables */
- for (i = 0; i < h->tablelength; i++) {
- while (NULL != (e = h->table[i])) {
- h->table[i] = e->next;
- index = indexFor(newsize,e->h);
+ h->primeindex--;
+ return 0;
+ }
+
+ h->table = newtable;
+ memset(newtable + h->tablelength, 0,
+ (newsize - h->tablelength) * sizeof(*newtable));
+ for (i = 0; i < h->tablelength; i++) {
I understand this code is taken from the realloc path. However, isn't
this algorithm also not stable? If so, then I think we move the comment
here.
+ for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) {
+ index = indexFor(newsize,e->h);
Missing space after ",".
+ if (index == i)
+ {
+ pE = &(e->next);
+ }
+ else
+ {
+ *pE = e->next;
e->next = newtable[index];
newtable[index] = e;
}
}
- free(h->table);
- h->table = newtable;
- }
- /* Plan B: realloc instead */
- else
- {
- newtable = (struct entry **)
- realloc(h->table, newsize * sizeof(struct entry *));
- if (NULL == newtable) { (h->primeindex)--; return 0; }
- h->table = newtable;
- memset(newtable + h->tablelength, 0,
- (newsize - h->tablelength) * sizeof(*newtable));
- for (i = 0; i < h->tablelength; i++) {
- for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) {
- index = indexFor(newsize,e->h);
- if (index == i)
- {
- pE = &(e->next);
- }
- else
- {
- *pE = e->next;
- e->next = newtable[index];
- newtable[index] = e;
- }
- }
- }
}
+
h->tablelength = newsize;
h->loadlimit = (unsigned int)
(((uint64_t)newsize * max_load_factor) / 100);
@@ -184,7 +171,7 @@ hashtable_insert(struct hashtable *h, void *k, void *v)
* element may be ok. Next time we insert, we'll try expanding
again.*/
hashtable_expand(h);
}
- e = (struct entry *)calloc(1, sizeof(struct entry));
+ e = talloc_zero(h, struct entry);
if (NULL == e) { --(h->entrycount); return 0; } /*oom*/
e->h = hash(h,k);
index = indexFor(h->tablelength,e->h);
@@ -238,8 +225,8 @@ hashtable_remove(struct hashtable *h, void *k)
h->entrycount--;
v = e->v;
if (h->flags & HASHTABLE_FREE_KEY)
- free(e->k);
- free(e);
+ talloc_free(e->k);
+ talloc_free(e);
return v;
}
pE = &(e->next);
@@ -280,25 +267,20 @@ void
hashtable_destroy(struct hashtable *h)
{
unsigned int i;
- struct entry *e, *f;
+ struct entry *e;
struct entry **table = h->table;
for (i = 0; i < h->tablelength; i++)
{
- e = table[i];
- while (NULL != e)
+ for (e = table[i]; e; e = e->next)
{
- f = e;
- e = e->next;
if (h->flags & HASHTABLE_FREE_KEY)
- free(f->k);
+ talloc_free(e->k);
if (h->flags & HASHTABLE_FREE_VALUE)
- free(f->v);
- free(f);
AFAIU, the loop is reworked so you let talloc to free each element with
the parent. Using a while loop is definitely cleaner, but now you will
end up to have two separate loop for the elements.
There is a risk that the overall performance of hashtable_destroy() will
be worse as the data accessed in one loop may not fit in the cache. So
you will have to reload it on the second loop.
Therefore, I think it would be better to keep the loop as-is.
Cheers,
--
Julien Grall