1236769Sobrien/* $NetBSD: lst.h,v 1.18 2009/01/23 21:58:27 dsl Exp $ */ 2236769Sobrien 3236769Sobrien/* 4236769Sobrien * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. 5236769Sobrien * All rights reserved. 6236769Sobrien * 7236769Sobrien * This code is derived from software contributed to Berkeley by 8236769Sobrien * Adam de Boor. 9236769Sobrien * 10236769Sobrien * Redistribution and use in source and binary forms, with or without 11236769Sobrien * modification, are permitted provided that the following conditions 12236769Sobrien * are met: 13236769Sobrien * 1. Redistributions of source code must retain the above copyright 14236769Sobrien * notice, this list of conditions and the following disclaimer. 15236769Sobrien * 2. Redistributions in binary form must reproduce the above copyright 16236769Sobrien * notice, this list of conditions and the following disclaimer in the 17236769Sobrien * documentation and/or other materials provided with the distribution. 18236769Sobrien * 3. Neither the name of the University nor the names of its contributors 19236769Sobrien * may be used to endorse or promote products derived from this software 20236769Sobrien * without specific prior written permission. 21236769Sobrien * 22236769Sobrien * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23236769Sobrien * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24236769Sobrien * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25236769Sobrien * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26236769Sobrien * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27236769Sobrien * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28236769Sobrien * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29236769Sobrien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30236769Sobrien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31236769Sobrien * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32236769Sobrien * SUCH DAMAGE. 33236769Sobrien * 34236769Sobrien * from: @(#)lst.h 8.1 (Berkeley) 6/6/93 35236769Sobrien */ 36236769Sobrien 37236769Sobrien/* 38236769Sobrien * Copyright (c) 1988, 1989 by Adam de Boor 39236769Sobrien * Copyright (c) 1989 by Berkeley Softworks 40236769Sobrien * All rights reserved. 41236769Sobrien * 42236769Sobrien * This code is derived from software contributed to Berkeley by 43236769Sobrien * Adam de Boor. 44236769Sobrien * 45236769Sobrien * Redistribution and use in source and binary forms, with or without 46236769Sobrien * modification, are permitted provided that the following conditions 47236769Sobrien * are met: 48236769Sobrien * 1. Redistributions of source code must retain the above copyright 49236769Sobrien * notice, this list of conditions and the following disclaimer. 50236769Sobrien * 2. Redistributions in binary form must reproduce the above copyright 51236769Sobrien * notice, this list of conditions and the following disclaimer in the 52236769Sobrien * documentation and/or other materials provided with the distribution. 53236769Sobrien * 3. All advertising materials mentioning features or use of this software 54236769Sobrien * must display the following acknowledgement: 55236769Sobrien * This product includes software developed by the University of 56236769Sobrien * California, Berkeley and its contributors. 57236769Sobrien * 4. Neither the name of the University nor the names of its contributors 58236769Sobrien * may be used to endorse or promote products derived from this software 59236769Sobrien * without specific prior written permission. 60236769Sobrien * 61236769Sobrien * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 62236769Sobrien * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 63236769Sobrien * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 64236769Sobrien * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 65236769Sobrien * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 66236769Sobrien * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 67236769Sobrien * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 68236769Sobrien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 69236769Sobrien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 70236769Sobrien * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 71236769Sobrien * SUCH DAMAGE. 72236769Sobrien * 73236769Sobrien * from: @(#)lst.h 8.1 (Berkeley) 6/6/93 74236769Sobrien */ 75236769Sobrien 76236769Sobrien/*- 77236769Sobrien * lst.h -- 78236769Sobrien * Header for using the list library 79236769Sobrien */ 80236769Sobrien#ifndef _LST_H_ 81236769Sobrien#define _LST_H_ 82236769Sobrien 83236769Sobrien#include <sys/param.h> 84236769Sobrien#include <stdlib.h> 85236769Sobrien 86236769Sobrien#include "sprite.h" 87236769Sobrien 88236769Sobrien/* 89236769Sobrien * basic typedef. This is what the Lst_ functions handle 90236769Sobrien */ 91236769Sobrien 92236769Sobrientypedef struct List *Lst; 93236769Sobrientypedef struct ListNode *LstNode; 94236769Sobrien 95236769Sobrientypedef void *DuplicateProc(void *); 96236769Sobrientypedef void FreeProc(void *); 97236769Sobrien 98236769Sobrien#define LST_CONCNEW 0 /* create new LstNode's when using Lst_Concat */ 99236769Sobrien#define LST_CONCLINK 1 /* relink LstNode's when using Lst_Concat */ 100236769Sobrien 101236769Sobrien/* 102236769Sobrien * Creation/destruction functions 103236769Sobrien */ 104236769Sobrien/* Create a new list */ 105236769SobrienLst Lst_Init(Boolean); 106236769Sobrien/* Duplicate an existing list */ 107236769SobrienLst Lst_Duplicate(Lst, DuplicateProc *); 108236769Sobrien/* Destroy an old one */ 109236769Sobrienvoid Lst_Destroy(Lst, FreeProc *); 110236769Sobrien/* True if list is empty */ 111236769SobrienBoolean Lst_IsEmpty(Lst); 112236769Sobrien 113236769Sobrien/* 114236769Sobrien * Functions to modify a list 115236769Sobrien */ 116236769Sobrien/* Insert an element before another */ 117236769SobrienReturnStatus Lst_InsertBefore(Lst, LstNode, void *); 118236769Sobrien/* Insert an element after another */ 119236769SobrienReturnStatus Lst_InsertAfter(Lst, LstNode, void *); 120236769Sobrien/* Place an element at the front of a lst. */ 121236769SobrienReturnStatus Lst_AtFront(Lst, void *); 122236769Sobrien/* Place an element at the end of a lst. */ 123236769SobrienReturnStatus Lst_AtEnd(Lst, void *); 124236769Sobrien/* Remove an element */ 125236769SobrienReturnStatus Lst_Remove(Lst, LstNode); 126236769Sobrien/* Replace a node with a new value */ 127236769SobrienReturnStatus Lst_Replace(LstNode, void *); 128236769Sobrien/* Concatenate two lists */ 129236769SobrienReturnStatus Lst_Concat(Lst, Lst, int); 130236769Sobrien 131236769Sobrien/* 132236769Sobrien * Node-specific functions 133236769Sobrien */ 134236769Sobrien/* Return first element in list */ 135236769SobrienLstNode Lst_First(Lst); 136236769Sobrien/* Return last element in list */ 137236769SobrienLstNode Lst_Last(Lst); 138236769Sobrien/* Return successor to given element */ 139236769SobrienLstNode Lst_Succ(LstNode); 140236769Sobrien/* Return predecessor to given element */ 141236769SobrienLstNode Lst_Prev(LstNode); 142236769Sobrien/* Get datum from LstNode */ 143236769Sobrienvoid *Lst_Datum(LstNode); 144236769Sobrien 145236769Sobrien/* 146236769Sobrien * Functions for entire lists 147236769Sobrien */ 148236769Sobrien/* Find an element in a list */ 149236769SobrienLstNode Lst_Find(Lst, const void *, int (*)(const void *, const void *)); 150236769Sobrien/* Find an element starting from somewhere */ 151236769SobrienLstNode Lst_FindFrom(Lst, LstNode, const void *, 152236769Sobrien int (*cProc)(const void *, const void *)); 153236769Sobrien/* 154236769Sobrien * See if the given datum is on the list. Returns the LstNode containing 155236769Sobrien * the datum 156236769Sobrien */ 157236769SobrienLstNode Lst_Member(Lst, void *); 158236769Sobrien/* Apply a function to all elements of a lst */ 159236769Sobrienint Lst_ForEach(Lst, int (*)(void *, void *), void *); 160236769Sobrien/* 161236769Sobrien * Apply a function to all elements of a lst starting from a certain point. 162236769Sobrien * If the list is circular, the application will wrap around to the 163236769Sobrien * beginning of the list again. 164236769Sobrien */ 165236769Sobrienint Lst_ForEachFrom(Lst, LstNode, int (*)(void *, void *), 166236769Sobrien void *); 167236769Sobrien/* 168236769Sobrien * these functions are for dealing with a list as a table, of sorts. 169236769Sobrien * An idea of the "current element" is kept and used by all the functions 170236769Sobrien * between Lst_Open() and Lst_Close(). 171236769Sobrien */ 172236769Sobrien/* Open the list */ 173236769SobrienReturnStatus Lst_Open(Lst); 174236769Sobrien/* Next element please */ 175236769SobrienLstNode Lst_Next(Lst); 176236769Sobrien/* Done yet? */ 177236769SobrienBoolean Lst_IsAtEnd(Lst); 178236769Sobrien/* Finish table access */ 179236769Sobrienvoid Lst_Close(Lst); 180236769Sobrien 181236769Sobrien/* 182236769Sobrien * for using the list as a queue 183236769Sobrien */ 184236769Sobrien/* Place an element at tail of queue */ 185236769SobrienReturnStatus Lst_EnQueue(Lst, void *); 186236769Sobrien/* Remove an element from head of queue */ 187236769Sobrienvoid *Lst_DeQueue(Lst); 188236769Sobrien 189236769Sobrien#endif /* _LST_H_ */ 190