PL_DHashTableEnumerate should be stable unless PL_DHASH_REMOVE

RESOLVED FIXED in mozilla1.3alpha

Status

()

P1
enhancement
RESOLVED FIXED
16 years ago
16 years ago

People

(Reporter: beard, Assigned: brendan)

Tracking

({js1.5})

Trunk
mozilla1.3alpha
js1.5
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(2 attachments)

(Reporter)

Description

16 years ago
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.
(Assignee)

Comment 1

16 years ago
Patch in a moment.

/be
Status: NEW → ASSIGNED
Keywords: js1.5
Target Milestone: --- → mozilla1.2beta
(Assignee)

Comment 2

16 years ago
Created attachment 103108 [details] [diff] [review]
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
(Reporter)

Comment 3

16 years ago
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
Attachment #103108 - Flags: superreview+
Comment on attachment 103108 [details] [diff] [review]
proposed fix

One! Two! Least surprise!

r=shaver.
Attachment #103108 - Flags: review+
(Assignee)

Comment 5

16 years ago
Created attachment 103145 [details] [diff] [review]
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
(Assignee)

Updated

16 years ago
Priority: -- → P1
(Assignee)

Comment 6

16 years ago
> 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
(Reporter)

Comment 7

16 years ago
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
Attachment #103145 - Flags: superreview+

Comment 8

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

r=waterson
Attachment #103145 - Flags: review+
(Assignee)

Updated

16 years ago
Summary: [RFE] |PLDHashTable| should have a primitive enumeration API → PL_DHashTableEnumerate should be stable unless PL_DHASH_REMOVE
(Assignee)

Updated

16 years ago
Blocks: 163188
(Assignee)

Comment 9

16 years ago
Fixed on the trunk.

/be
Status: ASSIGNED → RESOLVED
Last Resolved: 16 years ago
Resolution: --- → FIXED
Target Milestone: mozilla1.2beta → mozilla1.3alpha
You need to log in before you can comment on or make changes to this bug.