The states' collection of the C version was implemented as a
sorted array of whole state structs
(i.e: state_t * prev_states
)
. At the end of that array a sort margin
was kept with unsorted states. After the sort margin grew
to a fixed size, the entire array, including the sort margin
was sorted using the qsort()
function.
This yielded a bigger sorted array and an empty margin.
When a new state had to be added it was first added to the
end of the sort margin. Then, when the sort margin grew to
a certain size, it was merged with the main array. When
the size of prev_states
was exceeded,
it was realloced.
To lookup a state, I performed a binary search on the sorted
part of prev_states
and then went over
all the elements of the sort margin and checked them one by
one.