xref: /freebsd/usr.bin/grep/queue.c (revision e738085b94631f90e21a49852538ac95974baf44)
1f3f50de6SPedro F. Giffuni /*	$NetBSD: queue.c,v 1.5 2011/08/31 16:24:57 plunky Exp $	*/
2b66a823bSGabor Kovesdan 
34dc88ebeSGabor Kovesdan /*-
44d846d26SWarner Losh  * SPDX-License-Identifier: BSD-2-Clause
51de7b4b8SPedro F. Giffuni  *
6*e738085bSDag-Erling Smørgrav  * Copyright (c) 1999 James Howard and Dag-Erling Smørgrav
74dc88ebeSGabor Kovesdan  * All rights reserved.
8df546c3bSKyle Evans  * Copyright (c) 2020 Kyle Evans <kevans@FreeBSD.org>
94dc88ebeSGabor Kovesdan  *
104dc88ebeSGabor Kovesdan  * Redistribution and use in source and binary forms, with or without
114dc88ebeSGabor Kovesdan  * modification, are permitted provided that the following conditions
124dc88ebeSGabor Kovesdan  * are met:
134dc88ebeSGabor Kovesdan  * 1. Redistributions of source code must retain the above copyright
144dc88ebeSGabor Kovesdan  *    notice, this list of conditions and the following disclaimer.
154dc88ebeSGabor Kovesdan  * 2. Redistributions in binary form must reproduce the above copyright
164dc88ebeSGabor Kovesdan  *    notice, this list of conditions and the following disclaimer in the
174dc88ebeSGabor Kovesdan  *    documentation and/or other materials provided with the distribution.
184dc88ebeSGabor Kovesdan  *
194dc88ebeSGabor Kovesdan  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
204dc88ebeSGabor Kovesdan  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
214dc88ebeSGabor Kovesdan  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
224dc88ebeSGabor Kovesdan  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
234dc88ebeSGabor Kovesdan  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
244dc88ebeSGabor Kovesdan  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
254dc88ebeSGabor Kovesdan  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
264dc88ebeSGabor Kovesdan  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
274dc88ebeSGabor Kovesdan  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
284dc88ebeSGabor Kovesdan  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
294dc88ebeSGabor Kovesdan  * SUCH DAMAGE.
304dc88ebeSGabor Kovesdan  */
314dc88ebeSGabor Kovesdan 
324dc88ebeSGabor Kovesdan /*
334dc88ebeSGabor Kovesdan  * A really poor man's queue.  It does only what it has to and gets out of
344dc88ebeSGabor Kovesdan  * Dodge.  It is used in place of <sys/queue.h> to get a better performance.
354dc88ebeSGabor Kovesdan  */
364dc88ebeSGabor Kovesdan 
374dc88ebeSGabor Kovesdan #include <sys/cdefs.h>
384dc88ebeSGabor Kovesdan #include <sys/param.h>
394dc88ebeSGabor Kovesdan #include <sys/queue.h>
404dc88ebeSGabor Kovesdan 
414dc88ebeSGabor Kovesdan #include <stdlib.h>
424dc88ebeSGabor Kovesdan #include <string.h>
434dc88ebeSGabor Kovesdan 
444dc88ebeSGabor Kovesdan #include "grep.h"
454dc88ebeSGabor Kovesdan 
46df546c3bSKyle Evans typedef struct str		qentry_t;
474dc88ebeSGabor Kovesdan 
48df546c3bSKyle Evans static long long		filled;
49df546c3bSKyle Evans static qentry_t			*qend, *qpool;
504dc88ebeSGabor Kovesdan 
51df546c3bSKyle Evans /*
52df546c3bSKyle Evans  * qnext is the next entry to populate.  qlist is where the list actually
53df546c3bSKyle Evans  * starts, for the purposes of printing.
54df546c3bSKyle Evans  */
55df546c3bSKyle Evans static qentry_t		*qlist, *qnext;
56df546c3bSKyle Evans 
57df546c3bSKyle Evans void
58df546c3bSKyle Evans initqueue(void)
59df546c3bSKyle Evans {
60df546c3bSKyle Evans 
61df546c3bSKyle Evans 	qlist = qnext = qpool = grep_calloc(Bflag, sizeof(*qpool));
62df546c3bSKyle Evans 	qend = qpool + (Bflag - 1);
63df546c3bSKyle Evans }
64df546c3bSKyle Evans 
65df546c3bSKyle Evans static qentry_t *
66df546c3bSKyle Evans advqueue(qentry_t *itemp)
67df546c3bSKyle Evans {
68df546c3bSKyle Evans 
69df546c3bSKyle Evans 	if (itemp == qend)
70df546c3bSKyle Evans 		return (qpool);
71df546c3bSKyle Evans 	return (itemp + 1);
72df546c3bSKyle Evans }
734dc88ebeSGabor Kovesdan 
74a4f3f02bSEd Maste /*
75a4f3f02bSEd Maste  * Enqueue another line; return true if we've dequeued a line as a result
76a4f3f02bSEd Maste  */
77a4f3f02bSEd Maste bool
784dc88ebeSGabor Kovesdan enqueue(struct str *x)
794dc88ebeSGabor Kovesdan {
80df546c3bSKyle Evans 	qentry_t *item;
81df546c3bSKyle Evans 	bool rotated;
824dc88ebeSGabor Kovesdan 
83df546c3bSKyle Evans 	item = qnext;
84df546c3bSKyle Evans 	qnext = advqueue(qnext);
85df546c3bSKyle Evans 	rotated = false;
864dc88ebeSGabor Kovesdan 
87df546c3bSKyle Evans 	if (filled < Bflag) {
88df546c3bSKyle Evans 		filled++;
89df546c3bSKyle Evans 	} else if (filled == Bflag) {
90df546c3bSKyle Evans 		/* We had already filled up coming in; just rotate. */
91df546c3bSKyle Evans 		qlist = advqueue(qlist);
92df546c3bSKyle Evans 		rotated = true;
93df546c3bSKyle Evans 		free(item->dat);
94f3f50de6SPedro F. Giffuni 	}
9581c3f641SAlex Richardson 	/* len + 1 for NUL-terminator */
9681c3f641SAlex Richardson 	item->dat = grep_malloc(sizeof(char) * x->len + 1);
97df546c3bSKyle Evans 	item->len = x->len;
98df546c3bSKyle Evans 	item->line_no = x->line_no;
99df546c3bSKyle Evans 	item->boff = x->boff;
100df546c3bSKyle Evans 	item->off = x->off;
101df546c3bSKyle Evans 	memcpy(item->dat, x->dat, x->len);
10281c3f641SAlex Richardson 	item->dat[x->len] = '\0';
103df546c3bSKyle Evans 	item->file = x->file;
1044dc88ebeSGabor Kovesdan 
105df546c3bSKyle Evans 	return (rotated);
1064dc88ebeSGabor Kovesdan }
1074dc88ebeSGabor Kovesdan 
1084dc88ebeSGabor Kovesdan void
1094dc88ebeSGabor Kovesdan printqueue(void)
1104dc88ebeSGabor Kovesdan {
111df546c3bSKyle Evans 	qentry_t *item;
1124dc88ebeSGabor Kovesdan 
113df546c3bSKyle Evans 	item = qlist;
114df546c3bSKyle Evans 	do {
115df546c3bSKyle Evans 		/* Buffer must have ended early. */
116df546c3bSKyle Evans 		if (item->dat == NULL)
117df546c3bSKyle Evans 			break;
118df546c3bSKyle Evans 
119df546c3bSKyle Evans 		grep_printline(item, '-');
120df546c3bSKyle Evans 		free(item->dat);
121df546c3bSKyle Evans 		item->dat = NULL;
122df546c3bSKyle Evans 		item = advqueue(item);
123df546c3bSKyle Evans 	} while (item != qlist);
124df546c3bSKyle Evans 
125df546c3bSKyle Evans 	qlist = qnext = qpool;
126df546c3bSKyle Evans 	filled = 0;
1274dc88ebeSGabor Kovesdan }
1284dc88ebeSGabor Kovesdan 
1294dc88ebeSGabor Kovesdan void
1304dc88ebeSGabor Kovesdan clearqueue(void)
1314dc88ebeSGabor Kovesdan {
132df546c3bSKyle Evans 	qentry_t *item;
1334dc88ebeSGabor Kovesdan 
134df546c3bSKyle Evans 	item = qlist;
135df546c3bSKyle Evans 	do {
136df546c3bSKyle Evans 		free(item->dat);
137df546c3bSKyle Evans 		item->dat = NULL;
138df546c3bSKyle Evans 		item = advqueue(item);
139df546c3bSKyle Evans 	} while (item != qlist);
140df546c3bSKyle Evans 
141df546c3bSKyle Evans 	qlist = qnext = qpool;
142df546c3bSKyle Evans 	filled = 0;
143f3f50de6SPedro F. Giffuni }
144