xref: /minix3/minix/usr.bin/grep/queue.c (revision d794ecc9efbcfa044947fd20468ba1f184b357e7)
1*d794ecc9SDavid van Moolenbroek /*	$OpenBSD: queue.c,v 1.6 2011/07/08 01:20:24 tedu Exp $	*/
2*d794ecc9SDavid van Moolenbroek 
3*d794ecc9SDavid van Moolenbroek /*-
4*d794ecc9SDavid van Moolenbroek  * Copyright (c) 1999 James Howard and Dag-Erling Co�dan Sm�rgrav
5*d794ecc9SDavid van Moolenbroek  * All rights reserved.
6*d794ecc9SDavid van Moolenbroek  *
7*d794ecc9SDavid van Moolenbroek  * Redistribution and use in source and binary forms, with or without
8*d794ecc9SDavid van Moolenbroek  * modification, are permitted provided that the following conditions
9*d794ecc9SDavid van Moolenbroek  * are met:
10*d794ecc9SDavid van Moolenbroek  * 1. Redistributions of source code must retain the above copyright
11*d794ecc9SDavid van Moolenbroek  *    notice, this list of conditions and the following disclaimer.
12*d794ecc9SDavid van Moolenbroek  * 2. Redistributions in binary form must reproduce the above copyright
13*d794ecc9SDavid van Moolenbroek  *    notice, this list of conditions and the following disclaimer in the
14*d794ecc9SDavid van Moolenbroek  *    documentation and/or other materials provided with the distribution.
15*d794ecc9SDavid van Moolenbroek  *
16*d794ecc9SDavid van Moolenbroek  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17*d794ecc9SDavid van Moolenbroek  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18*d794ecc9SDavid van Moolenbroek  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19*d794ecc9SDavid van Moolenbroek  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20*d794ecc9SDavid van Moolenbroek  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21*d794ecc9SDavid van Moolenbroek  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22*d794ecc9SDavid van Moolenbroek  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23*d794ecc9SDavid van Moolenbroek  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24*d794ecc9SDavid van Moolenbroek  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25*d794ecc9SDavid van Moolenbroek  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26*d794ecc9SDavid van Moolenbroek  * SUCH DAMAGE.
27*d794ecc9SDavid van Moolenbroek  */
28*d794ecc9SDavid van Moolenbroek 
29*d794ecc9SDavid van Moolenbroek /*
30*d794ecc9SDavid van Moolenbroek  * A really poor man's queue.  It does only what it has to and gets out of
31*d794ecc9SDavid van Moolenbroek  * Dodge.
32*d794ecc9SDavid van Moolenbroek  */
33*d794ecc9SDavid van Moolenbroek 
34*d794ecc9SDavid van Moolenbroek #include <sys/param.h>
35*d794ecc9SDavid van Moolenbroek 
36*d794ecc9SDavid van Moolenbroek #include <stdlib.h>
37*d794ecc9SDavid van Moolenbroek #include <string.h>
38*d794ecc9SDavid van Moolenbroek 
39*d794ecc9SDavid van Moolenbroek #include "grep.h"
40*d794ecc9SDavid van Moolenbroek 
41*d794ecc9SDavid van Moolenbroek typedef struct queue {
42*d794ecc9SDavid van Moolenbroek 	struct queue   *next;
43*d794ecc9SDavid van Moolenbroek 	str_t		data;
44*d794ecc9SDavid van Moolenbroek } queue_t;
45*d794ecc9SDavid van Moolenbroek 
46*d794ecc9SDavid van Moolenbroek static queue_t	*q_head, *q_tail;
47*d794ecc9SDavid van Moolenbroek static int	 count;
48*d794ecc9SDavid van Moolenbroek 
49*d794ecc9SDavid van Moolenbroek static queue_t	*dequeue(void);
50*d794ecc9SDavid van Moolenbroek 
51*d794ecc9SDavid van Moolenbroek void
initqueue(void)52*d794ecc9SDavid van Moolenbroek initqueue(void)
53*d794ecc9SDavid van Moolenbroek {
54*d794ecc9SDavid van Moolenbroek 	q_head = q_tail = NULL;
55*d794ecc9SDavid van Moolenbroek }
56*d794ecc9SDavid van Moolenbroek 
57*d794ecc9SDavid van Moolenbroek static void
free_item(queue_t * item)58*d794ecc9SDavid van Moolenbroek free_item(queue_t *item)
59*d794ecc9SDavid van Moolenbroek {
60*d794ecc9SDavid van Moolenbroek 	free(item);
61*d794ecc9SDavid van Moolenbroek }
62*d794ecc9SDavid van Moolenbroek 
63*d794ecc9SDavid van Moolenbroek void
enqueue(str_t * x)64*d794ecc9SDavid van Moolenbroek enqueue(str_t *x)
65*d794ecc9SDavid van Moolenbroek {
66*d794ecc9SDavid van Moolenbroek 	queue_t	*item;
67*d794ecc9SDavid van Moolenbroek 
68*d794ecc9SDavid van Moolenbroek 	item = grep_malloc(sizeof *item + x->len);
69*d794ecc9SDavid van Moolenbroek 	item->data.len = x->len;
70*d794ecc9SDavid van Moolenbroek 	item->data.line_no = x->line_no;
71*d794ecc9SDavid van Moolenbroek 	item->data.off = x->off;
72*d794ecc9SDavid van Moolenbroek 	item->data.dat = (char *)item + sizeof *item;
73*d794ecc9SDavid van Moolenbroek 	memcpy(item->data.dat, x->dat, x->len);
74*d794ecc9SDavid van Moolenbroek 	item->data.file = x->file;
75*d794ecc9SDavid van Moolenbroek 	item->next = NULL;
76*d794ecc9SDavid van Moolenbroek 
77*d794ecc9SDavid van Moolenbroek 	if (!q_head) {
78*d794ecc9SDavid van Moolenbroek 		q_head = q_tail = item;
79*d794ecc9SDavid van Moolenbroek 	} else {
80*d794ecc9SDavid van Moolenbroek 		q_tail->next = item;
81*d794ecc9SDavid van Moolenbroek 		q_tail = item;
82*d794ecc9SDavid van Moolenbroek 	}
83*d794ecc9SDavid van Moolenbroek 
84*d794ecc9SDavid van Moolenbroek 	if (++count > Bflag)
85*d794ecc9SDavid van Moolenbroek 		free_item(dequeue());
86*d794ecc9SDavid van Moolenbroek }
87*d794ecc9SDavid van Moolenbroek 
88*d794ecc9SDavid van Moolenbroek static queue_t *
dequeue(void)89*d794ecc9SDavid van Moolenbroek dequeue(void)
90*d794ecc9SDavid van Moolenbroek {
91*d794ecc9SDavid van Moolenbroek 	queue_t	*item;
92*d794ecc9SDavid van Moolenbroek 
93*d794ecc9SDavid van Moolenbroek 	if (q_head == NULL)
94*d794ecc9SDavid van Moolenbroek 		return NULL;
95*d794ecc9SDavid van Moolenbroek 
96*d794ecc9SDavid van Moolenbroek 	--count;
97*d794ecc9SDavid van Moolenbroek 	item = q_head;
98*d794ecc9SDavid van Moolenbroek 	q_head = item->next;
99*d794ecc9SDavid van Moolenbroek 	if (q_head == NULL)
100*d794ecc9SDavid van Moolenbroek 		q_tail = NULL;
101*d794ecc9SDavid van Moolenbroek 	return item;
102*d794ecc9SDavid van Moolenbroek }
103*d794ecc9SDavid van Moolenbroek 
104*d794ecc9SDavid van Moolenbroek void
printqueue(void)105*d794ecc9SDavid van Moolenbroek printqueue(void)
106*d794ecc9SDavid van Moolenbroek {
107*d794ecc9SDavid van Moolenbroek 	queue_t *item;
108*d794ecc9SDavid van Moolenbroek 
109*d794ecc9SDavid van Moolenbroek 	while ((item = dequeue()) != NULL) {
110*d794ecc9SDavid van Moolenbroek 		printline(&item->data, '-', NULL);
111*d794ecc9SDavid van Moolenbroek 		free_item(item);
112*d794ecc9SDavid van Moolenbroek 	}
113*d794ecc9SDavid van Moolenbroek }
114*d794ecc9SDavid van Moolenbroek 
115*d794ecc9SDavid van Moolenbroek void
clearqueue(void)116*d794ecc9SDavid van Moolenbroek clearqueue(void)
117*d794ecc9SDavid van Moolenbroek {
118*d794ecc9SDavid van Moolenbroek 	queue_t	*item;
119*d794ecc9SDavid van Moolenbroek 
120*d794ecc9SDavid van Moolenbroek 	while ((item = dequeue()) != NULL)
121*d794ecc9SDavid van Moolenbroek 		free_item(item);
122*d794ecc9SDavid van Moolenbroek }
123