xref: /freebsd/usr.bin/grep/queue.c (revision c66ec88fed842fbaad62c30d510644ceb7bd2d71)
1 /*	$NetBSD: queue.c,v 1.5 2011/08/31 16:24:57 plunky Exp $	*/
2 /*	$FreeBSD$	*/
3 
4 /*-
5  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
6  *
7  * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav
8  * All rights reserved.
9  * Copyright (c) 2020 Kyle Evans <kevans@FreeBSD.org>
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  * 1. Redistributions of source code must retain the above copyright
15  *    notice, this list of conditions and the following disclaimer.
16  * 2. Redistributions in binary form must reproduce the above copyright
17  *    notice, this list of conditions and the following disclaimer in the
18  *    documentation and/or other materials provided with the distribution.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30  * SUCH DAMAGE.
31  */
32 
33 /*
34  * A really poor man's queue.  It does only what it has to and gets out of
35  * Dodge.  It is used in place of <sys/queue.h> to get a better performance.
36  */
37 
38 #include <sys/cdefs.h>
39 __FBSDID("$FreeBSD$");
40 
41 #include <sys/param.h>
42 #include <sys/queue.h>
43 
44 #include <stdlib.h>
45 #include <string.h>
46 
47 #include "grep.h"
48 
49 typedef struct str		qentry_t;
50 
51 static long long		filled;
52 static qentry_t			*qend, *qpool;
53 
54 /*
55  * qnext is the next entry to populate.  qlist is where the list actually
56  * starts, for the purposes of printing.
57  */
58 static qentry_t		*qlist, *qnext;
59 
60 void
61 initqueue(void)
62 {
63 
64 	qlist = qnext = qpool = grep_calloc(Bflag, sizeof(*qpool));
65 	qend = qpool + (Bflag - 1);
66 }
67 
68 static qentry_t *
69 advqueue(qentry_t *itemp)
70 {
71 
72 	if (itemp == qend)
73 		return (qpool);
74 	return (itemp + 1);
75 }
76 
77 /*
78  * Enqueue another line; return true if we've dequeued a line as a result
79  */
80 bool
81 enqueue(struct str *x)
82 {
83 	qentry_t *item;
84 	bool rotated;
85 
86 	item = qnext;
87 	qnext = advqueue(qnext);
88 	rotated = false;
89 
90 	if (filled < Bflag) {
91 		filled++;
92 	} else if (filled == Bflag) {
93 		/* We had already filled up coming in; just rotate. */
94 		qlist = advqueue(qlist);
95 		rotated = true;
96 		free(item->dat);
97 	}
98 	item->dat = grep_malloc(sizeof(char) * x->len);
99 	item->len = x->len;
100 	item->line_no = x->line_no;
101 	item->boff = x->boff;
102 	item->off = x->off;
103 	memcpy(item->dat, x->dat, x->len);
104 	item->file = x->file;
105 
106 	return (rotated);
107 }
108 
109 void
110 printqueue(void)
111 {
112 	qentry_t *item;
113 
114 	item = qlist;
115 	do {
116 		/* Buffer must have ended early. */
117 		if (item->dat == NULL)
118 			break;
119 
120 		grep_printline(item, '-');
121 		free(item->dat);
122 		item->dat = NULL;
123 		item = advqueue(item);
124 	} while (item != qlist);
125 
126 	qlist = qnext = qpool;
127 	filled = 0;
128 }
129 
130 void
131 clearqueue(void)
132 {
133 	qentry_t *item;
134 
135 	item = qlist;
136 	do {
137 		free(item->dat);
138 		item->dat = NULL;
139 		item = advqueue(item);
140 	} while (item != qlist);
141 
142 	qlist = qnext = qpool;
143 	filled = 0;
144 }
145