diff options
Diffstat (limited to 'contrib/less/search.c')
| -rw-r--r-- | contrib/less/search.c | 665 |
1 files changed, 576 insertions, 89 deletions
diff --git a/contrib/less/search.c b/contrib/less/search.c index 24d4210a0135..e824acb4a3fc 100644 --- a/contrib/less/search.c +++ b/contrib/less/search.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1984-2012 Mark Nudelman + * Copyright (C) 1984-2015 Mark Nudelman * * You may distribute under the terms of either the GNU General Public * License or the Less License, as specified in the README file. @@ -45,15 +45,57 @@ static POSITION prep_endpos; static int is_caseless; static int is_ucase_pattern; +/* + * Structures for maintaining a set of ranges for hilites and filtered-out + * lines. Each range is stored as a node within a red-black tree, and we + * try to extend existing ranges (without creating overlaps) rather than + * create new nodes if possible. We remember the last node found by a + * search for constant-time lookup if the next search is near enough to + * the previous. To aid that, we overlay a secondary doubly-linked list + * on top of the red-black tree so we can find the preceding/succeeding + * nodes also in constant time. + * + * Each node is allocated from a series of pools, each pool double the size + * of the previous (for amortised constant time allocation). Since our only + * tree operations are clear and node insertion, not node removal, we don't + * need to maintain a usage bitmap or freelist and can just return nodes + * from the pool in-order until capacity is reached. + */ struct hilite { - struct hilite *hl_next; POSITION hl_startpos; POSITION hl_endpos; }; -static struct hilite hilite_anchor = { NULL, NULL_POSITION, NULL_POSITION }; -static struct hilite filter_anchor = { NULL, NULL_POSITION, NULL_POSITION }; -#define hl_first hl_next +struct hilite_node +{ + struct hilite_node *parent; + struct hilite_node *left; + struct hilite_node *right; + struct hilite_node *prev; + struct hilite_node *next; + int red; + struct hilite r; +}; +struct hilite_storage +{ + int capacity; + int used; + struct hilite_storage *next; + struct hilite_node *nodes; +}; +struct hilite_tree +{ + struct hilite_storage *first; + struct hilite_storage *current; + struct hilite_node *root; + struct hilite_node *lookaside; +}; +#define HILITE_INITIALIZER() { NULL, NULL, NULL, NULL } +#define HILITE_LOOKASIDE_STEPS 2 + +static struct hilite_tree hilite_anchor = HILITE_INITIALIZER(); +static struct hilite_tree filter_anchor = HILITE_INITIALIZER(); + #endif /* @@ -219,7 +261,6 @@ repaint_hilite(on) { int slinenum; POSITION pos; - POSITION epos; int save_hide_hilite; if (squished) @@ -245,7 +286,6 @@ repaint_hilite(on) pos = position(slinenum); if (pos == NULL_POSITION) continue; - epos = position(slinenum+1); (void) forw_line(pos); goto_line(slinenum); put_line(); @@ -324,17 +364,23 @@ undo_search() */ public void clr_hlist(anchor) - struct hilite *anchor; + struct hilite_tree *anchor; { - struct hilite *hl; - struct hilite *nexthl; + struct hilite_storage *hls; + struct hilite_storage *nexthls; - for (hl = anchor->hl_first; hl != NULL; hl = nexthl) + for (hls = anchor->first; hls != NULL; hls = nexthls) { - nexthl = hl->hl_next; - free((void*)hl); + nexthls = hls->next; + free((void*)hls->nodes); + free((void*)hls); } - anchor->hl_first = NULL; + anchor->first = NULL; + anchor->current = NULL; + anchor->root = NULL; + + anchor->lookaside = NULL; + prep_startpos = prep_endpos = NULL_POSITION; } @@ -350,6 +396,126 @@ clr_filter() clr_hlist(&filter_anchor); } + struct hilite_node* +hlist_last(anchor) + struct hilite_tree *anchor; +{ + struct hilite_node *n = anchor->root; + while (n != NULL && n->right != NULL) + n = n->right; + return n; +} + + struct hilite_node* +hlist_next(n) + struct hilite_node *n; +{ + return n->next; +} + + struct hilite_node* +hlist_prev(n) + struct hilite_node *n; +{ + return n->prev; +} + +/* + * Find the node covering pos, or the node after it if no node covers it, + * or return NULL if pos is after the last range. Remember the found node, + * to speed up subsequent searches for the same or similar positions (if + * we return NULL, remember the last node.) + */ + struct hilite_node* +hlist_find(anchor, pos) + struct hilite_tree *anchor; + POSITION pos; +{ + struct hilite_node *n, *m; + + if (anchor->lookaside) + { + int steps = 0; + int hit = 0; + + n = anchor->lookaside; + + for (;;) + { + if (pos < n->r.hl_endpos) + { + if (n->prev == NULL || pos >= n->prev->r.hl_endpos) + { + hit = 1; + break; + } + } else if (n->next == NULL) + { + n = NULL; + hit = 1; + break; + } + + /* + * If we don't find the right node within a small + * distance, don't keep doing a linear search! + */ + if (steps >= HILITE_LOOKASIDE_STEPS) + break; + steps++; + + if (pos < n->r.hl_endpos) + anchor->lookaside = n = n->prev; + else + anchor->lookaside = n = n->next; + } + + if (hit) + return n; + } + + n = anchor->root; + m = NULL; + + while (n != NULL) + { + if (pos < n->r.hl_startpos) + { + if (n->left != NULL) + { + m = n; + n = n->left; + continue; + } + break; + } + if (pos >= n->r.hl_endpos) + { + if (n->right != NULL) + { + n = n->right; + continue; + } + if (m != NULL) + { + n = m; + } else + { + m = n; + n = NULL; + } + } + break; + } + + if (n != NULL) + anchor->lookaside = n; + else if (m != NULL) + anchor->lookaside = m; + + return n; +} + /* * Should any characters in a specified range be highlighted? */ @@ -358,18 +524,8 @@ is_hilited_range(pos, epos) POSITION pos; POSITION epos; { - struct hilite *hl; - - /* - * Look at each highlight and see if any part of it falls in the range. - */ - for (hl = hilite_anchor.hl_first; hl != NULL; hl = hl->hl_next) - { - if (hl->hl_endpos > pos && - (epos == NULL_POSITION || epos > hl->hl_startpos)) - return (1); - } - return (0); + struct hilite_node *n = hlist_find(&hilite_anchor, pos); + return (n != NULL && (epos == NULL_POSITION || epos > n->r.hl_startpos)); } /* @@ -379,24 +535,64 @@ is_hilited_range(pos, epos) is_filtered(pos) POSITION pos; { - struct hilite *hl; + struct hilite_node *n; if (ch_getflags() & CH_HELPFILE) return (0); - /* - * Look at each filter and see if the start position - * equals the start position of the line. - */ - for (hl = filter_anchor.hl_first; hl != NULL; hl = hl->hl_next) + n = hlist_find(&filter_anchor, pos); + return (n != NULL && pos >= n->r.hl_startpos); +} + +/* + * If pos is hidden, return the next position which isn't, otherwise + * just return pos. + */ + public POSITION +next_unfiltered(pos) + POSITION pos; +{ + struct hilite_node *n; + + if (ch_getflags() & CH_HELPFILE) + return (pos); + + n = hlist_find(&filter_anchor, pos); + while (n != NULL && pos >= n->r.hl_startpos) { - if (hl->hl_startpos == pos) - return (1); + pos = n->r.hl_endpos; + n = n->next; } - return (0); + return (pos); } /* + * If pos is hidden, return the previous position which isn't or 0 if + * we're filtered right to the beginning, otherwise just return pos. + */ + public POSITION +prev_unfiltered(pos) + POSITION pos; +{ + struct hilite_node *n; + + if (ch_getflags() & CH_HELPFILE) + return (pos); + + n = hlist_find(&filter_anchor, pos); + while (n != NULL && pos >= n->r.hl_startpos) + { + pos = n->r.hl_startpos; + if (pos == 0) + break; + pos--; + n = n->prev; + } + return (pos); +} + + +/* * Should any characters in a specified range be highlighted? * If nohide is nonzero, don't consider hide_hilite. */ @@ -447,43 +643,288 @@ is_hilited(pos, epos, nohide, p_matches) } /* + * Tree node storage: get the current block of nodes if it has spare + * capacity, or create a new one if not. + */ + static struct hilite_storage* +hlist_getstorage(anchor) + struct hilite_tree *anchor; +{ + int capacity = 1; + struct hilite_storage *s; + + if (anchor->current) + { + if (anchor->current->used < anchor->current->capacity) + return anchor->current; + capacity = anchor->current->capacity * 2; + } + + s = (struct hilite_storage *) ecalloc(1, sizeof(struct hilite_storage)); + s->nodes = (struct hilite_node *) ecalloc(capacity, sizeof(struct hilite_node)); + s->capacity = capacity; + s->used = 0; + s->next = NULL; + if (anchor->current) + anchor->current->next = s; + else + anchor->first = s; + anchor->current = s; + return s; +} + +/* + * Tree node storage: retrieve a new empty node to be inserted into the + * tree. + */ + static struct hilite_node* +hlist_getnode(anchor) + struct hilite_tree *anchor; +{ + struct hilite_storage *s = hlist_getstorage(anchor); + return &s->nodes[s->used++]; +} + +/* + * Rotate the tree left around a pivot node. + */ + static void +hlist_rotate_left(anchor, n) + struct hilite_tree *anchor; + struct hilite_node *n; +{ + struct hilite_node *np = n->parent; + struct hilite_node *nr = n->right; + struct hilite_node *nrl = n->right->left; + + if (np != NULL) + { + if (n == np->left) + np->left = nr; + else + np->right = nr; + } else + { + anchor->root = nr; + } + nr->left = n; + n->right = nrl; + + nr->parent = np; + n->parent = nr; + if (nrl != NULL) + nrl->parent = n; +} + +/* + * Rotate the tree right around a pivot node. + */ + static void +hlist_rotate_right(anchor, n) + struct hilite_tree *anchor; + struct hilite_node *n; +{ + struct hilite_node *np = n->parent; + struct hilite_node *nl = n->left; + struct hilite_node *nlr = n->left->right; + + if (np != NULL) + { + if (n == np->right) + np->right = nl; + else + np->left = nl; + } else + { + anchor->root = nl; + } + nl->right = n; + n->left = nlr; + + nl->parent = np; + n->parent = nl; + if (nlr != NULL) + nlr->parent = n; +} + + +/* * Add a new hilite to a hilite list. */ static void add_hilite(anchor, hl) - struct hilite *anchor; + struct hilite_tree *anchor; struct hilite *hl; { - struct hilite *ihl; + struct hilite_node *p, *n, *u; + + /* Ignore empty ranges. */ + if (hl->hl_startpos >= hl->hl_endpos) + return; + + p = anchor->root; + + /* Inserting the very first node is trivial. */ + if (p == NULL) + { + n = hlist_getnode(anchor); + n->r = *hl; + anchor->root = n; + anchor->lookaside = n; + return; + } /* - * Hilites are sorted in the list; find where new one belongs. - * Insert new one after ihl. + * Find our insertion point. If we come across any overlapping + * or adjoining existing ranges, shrink our range and discard + * if it become empty. */ - for (ihl = anchor; ihl->hl_next != NULL; ihl = ihl->hl_next) + for (;;) { - if (ihl->hl_next->hl_startpos > hl->hl_startpos) + if (hl->hl_startpos < p->r.hl_startpos) + { + if (hl->hl_endpos > p->r.hl_startpos) + hl->hl_endpos = p->r.hl_startpos; + if (p->left != NULL) + { + p = p->left; + continue; + } break; + } + if (hl->hl_startpos < p->r.hl_endpos) { + hl->hl_startpos = p->r.hl_endpos; + if (hl->hl_startpos >= hl->hl_endpos) + return; + } + if (p->right != NULL) + { + p = p->right; + continue; + } + break; } /* - * Truncate hilite so it doesn't overlap any existing ones - * above and below it. + * Now we're at the right leaf, again check for contiguous ranges + * and extend the existing node if possible to avoid the + * insertion. Otherwise insert a new node at the leaf. */ - if (ihl != anchor) - hl->hl_startpos = MAXPOS(hl->hl_startpos, ihl->hl_endpos); - if (ihl->hl_next != NULL) - hl->hl_endpos = MINPOS(hl->hl_endpos, ihl->hl_next->hl_startpos); - if (hl->hl_startpos >= hl->hl_endpos) + if (hl->hl_startpos < p->r.hl_startpos) { + if (hl->hl_endpos == p->r.hl_startpos) + { + p->r.hl_startpos = hl->hl_startpos; + return; + } + if (p->prev != NULL && p->prev->r.hl_endpos == hl->hl_startpos) + { + p->prev->r.hl_endpos = hl->hl_endpos; + return; + } + + p->left = n = hlist_getnode(anchor); + n->next = p; + if (p->prev != NULL) + { + n->prev = p->prev; + p->prev->next = n; + } + p->prev = n; + } else { + if (p->r.hl_endpos == hl->hl_startpos) + { + p->r.hl_endpos = hl->hl_endpos; + return; + } + if (p->next != NULL && hl->hl_endpos == p->next->r.hl_startpos) { + p->next->r.hl_startpos = hl->hl_startpos; + return; + } + + p->right = n = hlist_getnode(anchor); + n->prev = p; + if (p->next != NULL) + { + n->next = p->next; + p->next->prev = n; + } + p->next = n; + } + n->parent = p; + n->red = 1; + n->r = *hl; + + /* + * The tree is in the correct order and covers the right ranges + * now, but may have become unbalanced. Rebalance it using the + * standard red-black tree constraints and operations. + */ + for (;;) { + /* case 1 - current is root, root is always black */ + if (n->parent == NULL) + { + n->red = 0; + break; + } + + /* case 2 - parent is black, we can always be red */ + if (!n->parent->red) + break; + /* - * Hilite was truncated out of existence. + * constraint: because the root must be black, if our + * parent is red it cannot be the root therefore we must + * have a grandparent */ - free(hl); - return; + + /* + * case 3 - parent and uncle are red, repaint them black, + * the grandparent red, and start again at the grandparent. + */ + u = n->parent->parent->left; + if (n->parent == u) + u = n->parent->parent->right; + if (u != NULL && u->red) + { + n->parent->red = 0; + u->red = 0; + n = n->parent->parent; + n->red = 1; + continue; + } + + /* + * case 4 - parent is red but uncle is black, parent and + * grandparent on opposite sides. We need to start + * changing the structure now. This and case 5 will shorten + * our branch and lengthen the sibling, between them + * restoring balance. + */ + if (n == n->parent->right && + n->parent == n->parent->parent->left) + { + hlist_rotate_left(anchor, n->parent); + n = n->left; + } else if (n == n->parent->left && + n->parent == n->parent->parent->right) + { + hlist_rotate_right(anchor, n->parent); + n = n->right; + } + + /* + * case 5 - parent is red but uncle is black, parent and + * grandparent on same side + */ + n->parent->red = 0; + n->parent->parent->red = 1; + if (n == n->parent->left) + hlist_rotate_right(anchor, n->parent->parent); + else + hlist_rotate_left(anchor, n->parent->parent); + break; } - hl->hl_next = ihl->hl_next; - ihl->hl_next = hl; } /* @@ -496,12 +937,11 @@ create_hilites(linepos, start_index, end_index, chpos) int end_index; int *chpos; { - struct hilite *hl; + struct hilite hl; int i; /* Start the first hilite. */ - hl = (struct hilite *) ecalloc(1, sizeof(struct hilite)); - hl->hl_startpos = linepos + chpos[start_index]; + hl.hl_startpos = linepos + chpos[start_index]; /* * Step through the displayed chars. @@ -515,13 +955,12 @@ create_hilites(linepos, start_index, end_index, chpos) { if (chpos[i] != chpos[i-1] + 1 || i == end_index) { - hl->hl_endpos = linepos + chpos[i-1] + 1; - add_hilite(&hilite_anchor, hl); + hl.hl_endpos = linepos + chpos[i-1] + 1; + add_hilite(&hilite_anchor, &hl); /* Start new hilite unless this is the last char. */ if (i < end_index) { - hl = (struct hilite *) ecalloc(1, sizeof(struct hilite)); - hl->hl_startpos = linepos + chpos[i]; + hl.hl_startpos = linepos + chpos[i]; } } } @@ -545,8 +984,6 @@ hilite_line(linepos, line, line_len, chpos, sp, ep, cvt_ops) char *searchp; char *line_end = line + line_len; - if (sp == NULL || ep == NULL) - return; /* * sp and ep delimit the first match in the line. * Mark the corresponding file positions, then @@ -559,6 +996,8 @@ hilite_line(linepos, line, line_len, chpos, sp, ep, cvt_ops) */ searchp = line; do { + if (sp == NULL || ep == NULL) + return; create_hilites(linepos, sp-line, ep-line, chpos); /* * If we matched more than zero characters, @@ -694,11 +1133,10 @@ search_pos(search_type) * It starts at the jump target (if searching backwards), * or at the jump target plus one (if forwards). */ - linenum = jump_sline; + linenum = adjsline(jump_sline); if (search_type & SRCH_FORW) - add_one = 1; + add_one = 1; } - linenum = adjsline(linenum); pos = position(linenum); if (add_one) pos = forw_raw_line(pos, (char **)NULL, (int *)NULL); @@ -709,20 +1147,20 @@ search_pos(search_type) */ if (search_type & SRCH_FORW) { - while (pos == NULL_POSITION) - { - if (++linenum >= sc_height) - break; - pos = position(linenum); - } + while (pos == NULL_POSITION) + { + if (++linenum >= sc_height) + break; + pos = position(linenum); + } } else { - while (pos == NULL_POSITION) - { - if (--linenum < 0) - break; - pos = position(linenum); - } + while (pos == NULL_POSITION) + { + if (--linenum < 0) + break; + pos = position(linenum); + } } return (pos); } @@ -842,16 +1280,19 @@ search_range(pos, endpos, search_type, matches, maxlines, plinepos, pendpos) * Check to see if the line matches the filter pattern. * If so, add an entry to the filter list. */ - if ((search_type & SRCH_FIND_ALL) && prev_pattern(&filter_info)) { + if (((search_type & SRCH_FIND_ALL) || + prep_startpos == NULL_POSITION || + linepos < prep_startpos || linepos >= prep_endpos) && + prev_pattern(&filter_info)) { int line_filter = match_pattern(info_compiled(&filter_info), filter_info.text, cline, line_len, &sp, &ep, 0, filter_info.search_type); if (line_filter) { - struct hilite *hl = (struct hilite *) - ecalloc(1, sizeof(struct hilite)); - hl->hl_startpos = linepos; - hl->hl_endpos = pos; - add_hilite(&filter_anchor, hl); + struct hilite hl; + hl.hl_startpos = linepos; + hl.hl_endpos = pos; + add_hilite(&filter_anchor, &hl); + continue; } } #endif @@ -1108,6 +1549,12 @@ prep_hilite(spos, epos, maxlines) return; /* + * Make sure our prep region always starts at the beginning of + * a line. (search_range takes care of the end boundary below.) + */ + spos = back_raw_line(spos+1, (char **)NULL, (int *)NULL); + + /* * If we're limited to a max number of lines, figure out the * file position we should stop at. */ @@ -1199,12 +1646,48 @@ prep_hilite(spos, epos, maxlines) { int search_type = SRCH_FORW | SRCH_FIND_ALL; search_type |= (search_info.search_type & SRCH_NO_REGEX); - result = search_range(spos, epos, search_type, 0, - maxlines, (POSITION*)NULL, &new_epos); - if (result < 0) - return; - if (prep_endpos == NULL_POSITION || new_epos > prep_endpos) - nprep_endpos = new_epos; + for (;;) + { + result = search_range(spos, epos, search_type, 0, maxlines, (POSITION*)NULL, &new_epos); + if (result < 0) + return; + if (prep_endpos == NULL_POSITION || new_epos > prep_endpos) + nprep_endpos = new_epos; + + /* + * Check both ends of the resulting prep region to + * make sure they're not filtered. If they are, + * keep going at least one more line until we find + * something that isn't filtered, or hit the end. + */ + if (prep_endpos == NULL_POSITION || nprep_endpos > prep_endpos) + { + if (new_epos >= nprep_endpos && is_filtered(new_epos-1)) + { + spos = nprep_endpos; + epos = forw_raw_line(nprep_endpos, (char **)NULL, (int *)NULL); + if (epos == NULL_POSITION) + break; + maxlines = 1; + continue; + } + } + + if (prep_startpos == NULL_POSITION || nprep_startpos < prep_startpos) + { + if (nprep_startpos > 0 && is_filtered(nprep_startpos)) + { + epos = nprep_startpos; + spos = back_raw_line(nprep_startpos, (char **)NULL, (int *)NULL); + if (spos == NULL_POSITION) + break; + nprep_startpos = spos; + maxlines = 1; + continue; + } + } + break; + } } prep_startpos = nprep_startpos; prep_endpos = nprep_endpos; @@ -1243,12 +1726,16 @@ is_filtering() * This function is called by the V8 regcomp to report * errors in regular expressions. */ +public int reg_show_error = 1; + void regerror(s) char *s; { PARG parg; + if (!reg_show_error) + return; parg.p_string = s; error("%s", &parg); } |