search

hraban / cl-containers

Containers Library for Common Lisp
http://common-lisp.net/project/cl-containers/
Other
63 stars 13 forks source link

Deleting elements from a red-black-tree removes the wrong nodes #8

Open lokedhs opened 8 years ago

lokedhs commented 8 years ago

I have a test case which repeatedly inserts and removes elements from a red-black tree. After a certain number of operations, the DELETE-ITEM function starts removing the wrong elements. The test case has over 20000 operations, but the error can be seen after 45 operations, at which point I try to delete (720255619835071/500000 . 122) but (720255619835069/500000 . 121) gets deleted instead.

The test case is here. It can be run with Fiveam using the call (fiveam:run!). https://gist.github.com/lokedhs/e781cc273a2e53a18d00

fare commented 8 years ago

If it fails after 45 operations, can you reduce the test case further?

I've adapted your test case into a test case for LIL, and it works there.

lokedhs commented 8 years ago

I have implemented a failing test case using lift and integrated it in the cl-containers test cases. Please have a look at this commit:

https://github.com/lokedhs/cl-containers/commit/4b577c8f8ebd1c379dc02f62c38ac30f5bd6c6fa

lokedhs commented 8 years ago

I gave up on trying to fix the implementation in cl-containers, and implemented a new one based on this reference implementation in C: http://web.mit.edu/~emin/Desktop/ref_to_emin/www.old/source_code/red_black_tree/index.html

The code is here: https://github.com/lokedhs/containers/blob/master/src/rbtree.lisp

It should be easy to adapt this code to replace the existing implementation in cl-containers. Would you be willing to do this?

I've tested this version extensively, although I can't of course guarantee that it's 100% correct. I have found, and fixed, at least two bugs in it that took quite some time to reveal themselves. That said, it's in production as part of https://github.com/cicakhq/potato for a long time now, with no problems.

lokedhs commented 8 years ago

@fare did you have a look at my red-black implementation?

fare commented 8 years ago

Sorry, I didn't give an extensive look. It seems to be generally good, however at this point I'm not involved in cl-containers enough to port other people's code to it, I only accept, reject or rewrite patches to it. Same thing with lisp-interface-library, my main data structure library, though I may extend that one if I do serious work with Common Lisp again.

fare commented 8 years ago

So, if you adapt your code to cl-container, I will be glad to review and accept your pull request, but I am not willing to do that at this time.