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