174859 - PL_DHashTableEnumerate should be stable unless PL_DHASH_REMOVE

Status: RESOLVED FIXED

(Core :: XPCOM, enhancement, P1)

Description

[Patrick C. Beard]

Having just been bitten by the fact that the current implementation of
|PL_DHashTableEnumerate| will actually shrink the table if it has too few live
entries in it, I believe that a new API should be added to perform enumeration
w/o side-effects. In this new API, the |PLDHashEnumerator| would be restricted
having only two legal return values:

    PL_DHASH_NEXT = 0,          /* enumerator says continue */
    PL_DHASH_STOP = 1           /* enumerator says stop */

In addition, perhaps a new data type for doing inline enumeration should be
added. Something like this:

struct PLDHashTableEnumeration {
  PRUint32 mEntrySize;
  char *mEntryAddr, *mEntryLimit;
};

#define PL_DHASHENUM_INIT(table, etion) \
do {\
etion->mEntrySize = table->entrySize;\
etion->mEntryAddr = table->entryStore;\
etion->mEntryLimit = table->entryStore +\
                     PL_DHASH_TABLE_SIZE(table) *\
                     table->entrySize;\
} while (0)

#define PL_DHASHENUM_MORE(etion) \
(etion->mEntryAddr < etion->mEntryLimit)

#define PL_DHASHENUM_NEXT(type, entry, etion) \
do {
  PLDHashEntryHdr *entryHdr = (PLDHashEntryHdr*) etion->mEntryAddr;\
  if (ENTRY_IS_LIVE(*entryHdr)) { \
    entry = (type*) entryHdr; \
    break; \
  } \
  etion->mEntryAddr += etion->mEntrySize;
} while (PL_DHASHENUM_MORE(etion))

You get the idea.

Comment 1

[Brendan Eich [:brendan]]

Patch in a moment.

/be

Comment 2

[Brendan Eich [:brendan]]

Attachment: proposed fix

I don't want to add to the API, so I'm making Enumerate stable unless your etor
removes entries.  Comments?

I think the enumeration data structure and macro in comment #0 are overkill
compared to a couple of local variables of the right type for your entry.

/be

Comment 3

[Patrick C. Beard]

Comment on attachment 103108 [details] [diff] [review]
proposed fix

Good answer. It was what I'd tacitly (bogusly) assumed. Memory usage will be a
little higher, but will probably thrash less.
sr=beard

Comment 4

[Mike Shaver (:shaver emeritus)]

Comment on attachment 103108 [details] [diff] [review]
proposed fix

One! Two! Least surprise!

r=shaver.

Comment 5

[Brendan Eich [:brendan]]

Attachment: jsdhash.h/pldhash.h comments to match the code change

It seems worth pointing out why JS_DHASH_REMOVE exists (to save slightly on
code space in enumerators -- they need not all call JS_DHashTableRawRemove, but
can instead return a flag), while allowing for enumerators that want entry
storage stability after enumeration to call JS_DHashTableRawRemove and simply
return JS_DHASH_NEXT.

/be

Comment 6

[Brendan Eich [:brendan]]

> It seems worth pointing out why JS_DHASH_REMOVE exists (to save slightly on
> code space in enumerators -- they need not all call JS_DHashTableRawRemove, but
> can instead return a flag),

...and to shrink or compress after an enumeration that returns JS_DHASH_REMOVE a
lot, or otherwise ends with an underloaded table.  RawRemove was always kosher,
but now its use from enumerators doesn't trigger reallocation of live entries.

/be

Comment 7

[Patrick C. Beard]

Comment on attachment 103145 [details] [diff] [review]
jsdhash.h/pldhash.h comments to match the code change

I love comments that refer to something I've had to do in my own code.
sr=beard

Comment 8

[Chris Waterson]

Comment on attachment 103145 [details] [diff] [review]
jsdhash.h/pldhash.h comments to match the code change

r=waterson

Comment 9

[Brendan Eich [:brendan]]

Fixed on the trunk.

/be