Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

delete() can orphan keys and make them inaccessible due to how chaining is implemented #17

Open
binki opened this issue Dec 28, 2016 · 0 comments

Comments

@binki
Copy link

binki commented Dec 28, 2016

Adding this to to test/basic.js after the akey section makes it fail:

var ckey = {}
var dkey = {}
m.set(ckey, { some: 'additional data' })
m.set(dkey, { some: 'more data' })
m.delete(ckey)
t.equal(m.has(ckey), false)
t.same(m.get(dkey), { some: 'more data' })
m.delete(dkey)
t.equal(m.get(dkey), undefined)

Deleting ckey should not make dkey inaccessible, but it does with the current implementation:

test/basic.js ....................................... 55/60
  not ok should be equivalent
    +++ found
    --- wanted
    -{
    -  "some": "more data"
    -}
    +[null]
    at:
      file: test\basic.js
      line: 52
      column: 5
      function: runTests
    source: |
      t.same(m.get(dkey), { some: 'more data' })
    stack: |
      runTests (test\basic.js:52:5)
      Object.<anonymous> (test\basic.js:6:1)
      run (bootstrap_node.js:394:7)
      startup (bootstrap_node.js:149:9)
      bootstrap_node.js:509:3

(further results trimmed because the failure causes the rest of the test to break).

Fixing it naively doesn’t work because if you shift the chain down you might orphan a chain from another key with a string representation of [object Object]0, especially if objects are interleaved in the chain (e.g., inserting {} then {toString: () => '[object Object]0'} then another {}). The least mind-bending way to fix this would be to just use buckets at each slot instead of chaining. To preserve memory perhaps the bucket could use a linked-list style or store a single value in itself and only allocate an array to push additional values if necessary.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant