2  * Copyright (C) 1984-2025  Mark Nudelman
12  * Code to handle displaying line numbers.
15  * We don't want to just start at the beginning of the file and
17  * wouldn't work if we couldn't get to the start of the file; e.g.
20  * So we use the function add_lnum to cache line numbers.
21  * We try to be very clever and keep only the more interesting
27  * 200 is more expensive to derive from 100.
31  * to cache the line number.  Therefore currline is occasionally
32  * called to make sure we cache line numbers often enough.
38  * Structure to keep track of a line number and the associated file position.
39  * A doubly-linked circular list of line numbers is kept ordered by line number.
43 	struct linenum_info *next;      /* Link to next in the list */
44 	struct linenum_info *prev;      /* Line to previous in the list */
51  * is the distance between the previous one and the next one in the list.
54  * line number were deleted.  It is used to decide which one to replace
55  * when we have a new one to insert and the table is full.
63 static struct linenum_info *spare;      /* We always keep one spare entry */
82 	 * Leave one for the "spare".  in clr_linenum()
84 	for (p = pool;  p < &pool[LINENUM_POOL-2];  p++)  in clr_linenum()
85 		p->next = p+1;  in clr_linenum()
86 	pool[LINENUM_POOL-2].next = NULL;  in clr_linenum()
89 	spare = &pool[LINENUM_POOL-1];  in clr_linenum()
106 	 * Don't bother to compute a gap for the anchor.  in calcgap()
107 	 * Also don't compute a gap for the last one in the list.  in calcgap()
108 	 * The gap for that last one should be considered infinite,  in calcgap()
111 	if (p == &anchor || p->next == &anchor)  in calcgap()
113 	p->gap = p->next->pos - p->prev->pos;  in calcgap()
117  * Add a new line number to the cache.
130 	 * Find the proper place in the list for the new one.  in add_lnum()
133 	for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)  in add_lnum()
134 		if (p->line == linenum)  in add_lnum()
135 			/* We already have this one. */  in add_lnum()
138 	prevp = p->prev;  in add_lnum()
144 		 * Use one of them.  in add_lnum()
147 		freelist = freelist->next;  in add_lnum()
162 	new->next = nextp;  in add_lnum()
163 	new->prev = prevp;  in add_lnum()
164 	new->pos = pos;  in add_lnum()
165 	new->line = linenum;  in add_lnum()
167 	nextp->prev = new;  in add_lnum()
168 	prevp->next = new;  in add_lnum()
181 		 * Scan the list to find the one with the smallest  in add_lnum()
183 		 * We should never remove the last one, so stop when  in add_lnum()
184 		 * we get to p->next == &anchor.  This also avoids  in add_lnum()
185 		 * looking at the gap of the last one, which is  in add_lnum()
188 		mingap = anchor.next->gap;  in add_lnum()
189 		for (p = anchor.next;  p->next != &anchor;  p = p->next)  in add_lnum()
191 			if (p->gap <= mingap)  in add_lnum()
194 				mingap = p->gap;  in add_lnum()
197 		spare->next->prev = spare->prev;  in add_lnum()
198 		spare->prev->next = spare->next;  in add_lnum()
203  * If we get stuck in a long loop trying to figure out the
204  * line number, print a message to tell the user what we're doing.
222 	dmsg->loopcount = 0;  in start_delayed_msg()
223 	dmsg->message = message;  in start_delayed_msg()
225 	dmsg->startime = get_time();  in start_delayed_msg()
232 	if (dmsg->loopcount >= 0 && ++(dmsg->loopcount) > 100)  in delayed_msg()
234 		dmsg->loopcount = 0;  in delayed_msg()
235 		if (get_time() >= dmsg->startime + LONGTIME)  in delayed_msg()
237 			dmsg->message();  in delayed_msg()
238 			dmsg->loopcount = -1;  in delayed_msg()
242 	if (dmsg->loopcount >= 0 && ++(dmsg->loopcount) > LONGLOOP)  in delayed_msg()
244 		dmsg->message();  in delayed_msg()
245 		dmsg->loopcount = -1;  in delayed_msg()
256 	if (dmsg->loopcount >= 0)  in abort_delayed_msg()
260 		 * We were displaying line numbers, so need to repaint.  in abort_delayed_msg()
295 	 * Find the entry nearest to the position we want.  in find_linenum()
297 	for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)  in find_linenum()
299 	if (p->pos == pos)  in find_linenum()
301 		return (p->line);  in find_linenum()
304 	 * This is the (possibly) time-consuming part.  in find_linenum()
307 	 * get to the place we want.  in find_linenum()
310 	 * previous one or backwards from the next one.  in find_linenum()
315 	if (p == &anchor || pos - p->prev->pos < p->pos - pos)  in find_linenum()
320 		p = p->prev;  in find_linenum()
321 		if (ch_seek(p->pos))  in find_linenum()
323 		for (linenum = p->line, cpos = p->pos;  cpos < pos;  linenum++)  in find_linenum()
326 			 * Allow a signal to abort this loop.  in find_linenum()
346 			linenum--;  in find_linenum()
352 		if (ch_seek(p->pos))  in find_linenum()
354 		for (linenum = p->line, cpos = p->pos;  cpos > pos;  linenum--)  in find_linenum()
357 			 * Allow a signal to abort this loop.  in find_linenum()
393 	 * Find the entry nearest to the line number we want.  in find_pos()
395 	for (p = anchor.next;  p != &anchor && p->line < linenum;  p = p->next)  in find_pos()
397 	if (p->line == linenum)  in find_pos()
399 		return (p->pos);  in find_pos()
401 	if (p == &anchor || linenum - p->prev->line < p->line - linenum)  in find_pos()
406 		p = p->prev;  in find_pos()
407 		if (ch_seek(p->pos))  in find_pos()
409 		for (clinenum = p->line, cpos = p->pos;  clinenum < linenum;  clinenum++)  in find_pos()
412 			 * Allow a signal to abort this loop.  in find_pos()
425 		if (ch_seek(p->pos))  in find_pos()
427 		for (clinenum = p->line, cpos = p->pos;  clinenum > linenum;  clinenum--)  in find_pos()
430 			 * Allow a signal to abort this loop.  in find_pos()
448  * The argument "where" tells which line is to be considered
465 		linenum--;  in currline()
493 		/* For efficiency, only add one every 256 line numbers. */  in scan_eof()
509  * (handles the --no-number-headers option).
519 			linenum = (linenum < header_end_line) ? 0 : linenum - header_end_line + 1;  in vlinenum()