michaelrsweet / mxml

Tiny XML library.
https://www.msweet.org/mxml
Apache License 2.0
426 stars 157 forks source link

_mxml_entity_cb: simplify binary search a bit #302

Closed loskutov closed 2 months ago

loskutov commented 1 year ago

The loop invariant is that last is at least first + 2, which means that neither entities[first] nor entities[last] are ever accessed, so it's safe to have them outside the array bounds. Another invariant is that entities[first].name < name < entities[last].name, so once first + 1 == last, it means there's no occurrence.

Also, bsearch could be used, which might be a more straightforward approach.

michaelrsweet commented 1 year ago

Hmm, there was a reason I didn't use bsearch, will see if I can dig up any notes on that.

Considering this change...

michaelrsweet commented 2 months ago

OK, so using bsearch requires a using separate comparison function... The new code also uses size_t (unsigned) so I can't start left negative...

That said, I'll look at simplifying this code since it isn't performance-critical...