range seems not work correctly.

[al8n]

Hi folks, I found that range does not work expectedly.

In the example, range only contains one element, key = 1, val = "1". But, I think the correct range should return two elements key = 1 and key = 2.

fn main() {
    let db = jammdb::Db::open("foo").unwrap();
    let tx = db.tx(true).unwrap();
    let b = tx.get_or_create_bucket("foo").unwrap();
    b.put(1u64.to_be_bytes(), "1").unwrap();
    b.put(2u64.to_be_bytes(), "2").unwrap();
    b.put(3u64.to_be_bytes(), "3").unwrap();
    tx.commit().unwrap();

    let tx = db.tx(true).unwrap();
    let b = tx.get_bucket("foo").unwrap();
    for i in b.range(1u64.to_be_bytes().as_slice()..=2u64.to_be_bytes().as_slice()) {
      println!("remove key {}", i.key());
      b.delete(i.key()).unwrap();
    }
    tx.commit().unwrap();

    let tx = db.tx(false).unwrap();
    let b = tx.get_bucket("foo").unwrap();

    // panic unexpectedly, as the code should remove key in range 1..=2
    assert!(b.get(2u64.to_be_bytes().as_slice()).is_none()); 
 }

[pjtatlow]

Hey @al8n sorry for the silence on my end. I looked at this the day you filed the issue but forgot to fill you in on what's going on. The issue is you're deleting things from the bucket that you're iterating over. The cursor remembers the index of the item you were on last, but when an item is deleted the indices for each key shift by one to the left. So on the next iteration of the loop the index increments by one, but that skips the element that you were expecting to be next.

You would run into a similar issue if you were to delete items from a vector in a for loop using an incrementing index.

This is definitely something that should be fixed, but no obvious solution is jumping out at me. I'm open to any ideas if you have some!

[tokahuke]

Well, the rust-y "zero runtime cost" solution would be to have a mutable reference to the bucket inside range. However, this would not work here afaik because the user could instantiate another Bucket instance pointing to the same bucket and then delete keys with.

The second would be runtime locks. This is what Python does, for example:

x = {"a": 1, "b": 2}

for key in x.keys():
    del x[key]

Traceback (most recent call last):
  File "<python-input-0>", line 3, in <module>
    for key in x.keys():
               ~~~~~~^^
RuntimeError: dictionary changed size during iteration