| 588 | } |
| 589 | |
| 590 | static const char *find_reference_location_1(struct snapshot *snapshot, |
| 591 | const char *refname, int mustexist, |
| 592 | int start) |
| 593 | { |
| 594 | /* |
| 595 | * This is not *quite* a garden-variety binary search, because |
| 596 | * the data we're searching is made up of records, and we |
| 597 | * always need to find the beginning of a record to do a |
| 598 | * comparison. A "record" here is one line for the reference |
| 599 | * itself and zero or one peel lines that start with '^'. Our |
| 600 | * loop invariant is described in the next two comments. |
| 601 | */ |
| 602 | |
| 603 | /* |
| 604 | * A pointer to the character at the start of a record whose |
| 605 | * preceding records all have reference names that come |
| 606 | * *before* `refname`. |
| 607 | */ |
| 608 | const char *lo = snapshot->start; |
| 609 | |
| 610 | /* |
| 611 | * A pointer to a the first character of a record whose |
| 612 | * reference name comes *after* `refname`. |
| 613 | */ |
| 614 | const char *hi = snapshot->eof; |
| 615 | |
| 616 | while (lo != hi) { |
| 617 | const char *mid, *rec; |
| 618 | int cmp; |
| 619 | |
| 620 | mid = lo + (hi - lo) / 2; |
| 621 | rec = find_start_of_record(lo, mid); |
| 622 | cmp = cmp_record_to_refname(rec, refname, start, snapshot); |
| 623 | if (cmp < 0) { |
| 624 | lo = find_end_of_record(mid, hi); |
| 625 | } else if (cmp > 0) { |
| 626 | hi = rec; |
| 627 | } else { |
| 628 | return rec; |
| 629 | } |
| 630 | } |
| 631 | |
| 632 | if (mustexist) |
| 633 | return NULL; |
| 634 | else |
| 635 | return lo; |
| 636 | } |
| 637 | |
| 638 | /* |
| 639 | * Find the place in `snapshot->buf` where the start of the record for |
no test coverage detected