13e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey/* $NetBSD: queue.c,v 1.5 2011/08/31 16:24:57 plunky Exp $ */ 23e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey/* $FreeBSD: head/usr.bin/grep/queue.c 211496 2010-08-19 09:28:59Z des $ */ 33e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey/*- 43e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav 53e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * All rights reserved. 63e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * 73e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * Redistribution and use in source and binary forms, with or without 83e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * modification, are permitted provided that the following conditions 93e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * are met: 103e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * 1. Redistributions of source code must retain the above copyright 113e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * notice, this list of conditions and the following disclaimer. 123e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * 2. Redistributions in binary form must reproduce the above copyright 133e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * notice, this list of conditions and the following disclaimer in the 143e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * documentation and/or other materials provided with the distribution. 153e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * 163e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 173e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 183e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 193e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 203e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 213e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 223e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 233e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 243e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 253e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 263e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * SUCH DAMAGE. 273e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey */ 283e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 293e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey/* 303e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * A really poor man's queue. It does only what it has to and gets out of 313e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey * Dodge. It is used in place of <sys/queue.h> to get a better performance. 323e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey */ 333e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 343e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey#if HAVE_NBTOOL_CONFIG_H 353e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey#include "nbtool_config.h" 363e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey#endif 373e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 383e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey#include <sys/cdefs.h> 393e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey__RCSID("$NetBSD: queue.c,v 1.5 2011/08/31 16:24:57 plunky Exp $"); 403e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 413e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey#include <sys/param.h> 423e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey#include <sys/queue.h> 433e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 443e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey#include <stdlib.h> 453e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey#include <string.h> 463e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 473e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey#include "grep.h" 483e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 493e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkeystruct qentry { 503e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey STAILQ_ENTRY(qentry) list; 513e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey struct str data; 523e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey}; 533e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 543e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkeystatic STAILQ_HEAD(, qentry) queue = STAILQ_HEAD_INITIALIZER(queue); 553e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkeystatic unsigned long long count; 563e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 573e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkeystatic struct qentry *dequeue(void); 583e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 593e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkeyvoid 603e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkeyenqueue(struct str *x) 613e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey{ 623e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey struct qentry *item; 633e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 643e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey item = grep_malloc(sizeof(struct qentry)); 653e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey item->data.dat = grep_malloc(sizeof(char) * x->len); 663e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey item->data.len = x->len; 673e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey item->data.line_no = x->line_no; 683e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey item->data.off = x->off; 693e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey memcpy(item->data.dat, x->dat, x->len); 703e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey item->data.file = x->file; 713e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 723e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey STAILQ_INSERT_TAIL(&queue, item, list); 733e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 743e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey if (++count > Bflag) { 753e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey item = dequeue(); 763e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey free(item->data.dat); 773e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey free(item); 783e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey } 793e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey} 803e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 813e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkeystatic struct qentry * 823e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkeydequeue(void) 833e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey{ 843e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey struct qentry *item; 853e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 863e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey item = STAILQ_FIRST(&queue); 873e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey if (item == NULL) 883e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey return (NULL); 893e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 903e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey STAILQ_REMOVE_HEAD(&queue, list); 913e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey --count; 923e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey return (item); 933e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey} 943e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 953e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkeyvoid 963e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkeyprintqueue(void) 973e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey{ 983e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey struct qentry *item; 993e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 1003e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey while ((item = dequeue()) != NULL) { 1013e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey printline(&item->data, '-', NULL, 0); 1023e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey free(item->data.dat); 1033e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey free(item); 1043e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey } 1053e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey} 1063e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 1073e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkeyvoid 1083e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkeyclearqueue(void) 1093e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey{ 1103e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey struct qentry *item; 1113e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey 1123e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey while ((item = dequeue()) != NULL) { 1133e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey free(item->data.dat); 1143e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey free(item); 1153e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey } 1163e8b1581ff0f2daa934eb9d6362dfe4e2b4fa8c9Jeff Sharkey} 117