lst.h revision 8874
11590Srgrimes/* 25814Sjkh * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. 35814Sjkh * Copyright (c) 1988, 1989 by Adam de Boor 41590Srgrimes * Copyright (c) 1989 by Berkeley Softworks 51590Srgrimes * All rights reserved. 61590Srgrimes * 71590Srgrimes * This code is derived from software contributed to Berkeley by 81590Srgrimes * Adam de Boor. 91590Srgrimes * 101590Srgrimes * Redistribution and use in source and binary forms, with or without 111590Srgrimes * modification, are permitted provided that the following conditions 121590Srgrimes * are met: 131590Srgrimes * 1. Redistributions of source code must retain the above copyright 141590Srgrimes * notice, this list of conditions and the following disclaimer. 151590Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 161590Srgrimes * notice, this list of conditions and the following disclaimer in the 171590Srgrimes * documentation and/or other materials provided with the distribution. 181590Srgrimes * 3. All advertising materials mentioning features or use of this software 191590Srgrimes * must display the following acknowledgement: 201590Srgrimes * This product includes software developed by the University of 211590Srgrimes * California, Berkeley and its contributors. 221590Srgrimes * 4. Neither the name of the University nor the names of its contributors 231590Srgrimes * may be used to endorse or promote products derived from this software 241590Srgrimes * without specific prior written permission. 251590Srgrimes * 261590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 271590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 281590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 291590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 301590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 311590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 321590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 331590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 341590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 351590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 361590Srgrimes * SUCH DAMAGE. 371590Srgrimes * 381590Srgrimes * @(#)lst.h 8.1 (Berkeley) 6/6/93 391590Srgrimes */ 401590Srgrimes 411590Srgrimes/*- 421590Srgrimes * lst.h -- 431590Srgrimes * Header for using the list library 441590Srgrimes */ 451590Srgrimes#ifndef _LST_H_ 461590Srgrimes#define _LST_H_ 471590Srgrimes 481590Srgrimes#include <sprite.h> 495814Sjkh#include <sys/cdefs.h> 501590Srgrimes#if __STDC__ 511590Srgrimes#include <stdlib.h> 521590Srgrimes#endif 531590Srgrimes 541590Srgrimes/* 551590Srgrimes * basic typedef. This is what the Lst_ functions handle 561590Srgrimes */ 571590Srgrimes 581590Srgrimestypedef struct Lst *Lst; 591590Srgrimestypedef struct LstNode *LstNode; 601590Srgrimes 611590Srgrimes#define NILLST ((Lst) NIL) 621590Srgrimes#define NILLNODE ((LstNode) NIL) 631590Srgrimes 641590Srgrimes/* 651590Srgrimes * NOFREE can be used as the freeProc to Lst_Destroy when the elements are 661590Srgrimes * not to be freed. 671590Srgrimes * NOCOPY performs similarly when given as the copyProc to Lst_Duplicate. 681590Srgrimes */ 695814Sjkh#define NOFREE ((void (*) __P((ClientData))) 0) 705814Sjkh#define NOCOPY ((ClientData (*) __P((ClientData))) 0) 711590Srgrimes 721590Srgrimes#define LST_CONCNEW 0 /* create new LstNode's when using Lst_Concat */ 731590Srgrimes#define LST_CONCLINK 1 /* relink LstNode's when using Lst_Concat */ 741590Srgrimes 751590Srgrimes/* 761590Srgrimes * Creation/destruction functions 771590Srgrimes */ 785814Sjkh/* Create a new list */ 795814SjkhLst Lst_Init __P((Boolean)); 805814Sjkh/* Duplicate an existing list */ 815814SjkhLst Lst_Duplicate __P((Lst, ClientData (*)(ClientData))); 825814Sjkh/* Destroy an old one */ 835814Sjkhvoid Lst_Destroy __P((Lst, void (*)(ClientData))); 845814Sjkh/* True if list is empty */ 855814SjkhBoolean Lst_IsEmpty __P((Lst)); 861590Srgrimes 871590Srgrimes/* 881590Srgrimes * Functions to modify a list 891590Srgrimes */ 905814Sjkh/* Insert an element before another */ 915814SjkhReturnStatus Lst_Insert __P((Lst, LstNode, ClientData)); 925814Sjkh/* Insert an element after another */ 935814SjkhReturnStatus Lst_Append __P((Lst, LstNode, ClientData)); 945814Sjkh/* Place an element at the front of a lst. */ 955814SjkhReturnStatus Lst_AtFront __P((Lst, ClientData)); 965814Sjkh/* Place an element at the end of a lst. */ 975814SjkhReturnStatus Lst_AtEnd __P((Lst, ClientData)); 985814Sjkh/* Remove an element */ 995814SjkhReturnStatus Lst_Remove __P((Lst, LstNode)); 1005814Sjkh/* Replace a node with a new value */ 1015814SjkhReturnStatus Lst_Replace __P((LstNode, ClientData)); 1025814Sjkh/* Concatenate two lists */ 1035814SjkhReturnStatus Lst_Concat __P((Lst, Lst, int)); 1041590Srgrimes 1051590Srgrimes/* 1061590Srgrimes * Node-specific functions 1071590Srgrimes */ 1085814Sjkh/* Return first element in list */ 1095814SjkhLstNode Lst_First __P((Lst)); 1105814Sjkh/* Return last element in list */ 1115814SjkhLstNode Lst_Last __P((Lst)); 1125814Sjkh/* Return successor to given element */ 1135814SjkhLstNode Lst_Succ __P((LstNode)); 1145814Sjkh/* Get datum from LstNode */ 1155814SjkhClientData Lst_Datum __P((LstNode)); 1161590Srgrimes 1171590Srgrimes/* 1181590Srgrimes * Functions for entire lists 1191590Srgrimes */ 1205814Sjkh/* Find an element in a list */ 1218874SrgrimesLstNode Lst_Find __P((Lst, ClientData, 1225814Sjkh int (*)(ClientData, ClientData))); 1235814Sjkh/* Find an element starting from somewhere */ 1245814SjkhLstNode Lst_FindFrom __P((Lst, LstNode, ClientData, 1255814Sjkh int (*cProc)(ClientData, ClientData))); 1268874Srgrimes/* 1275814Sjkh * See if the given datum is on the list. Returns the LstNode containing 1285814Sjkh * the datum 1295814Sjkh */ 1305814SjkhLstNode Lst_Member __P((Lst, ClientData)); 1315814Sjkh/* Apply a function to all elements of a lst */ 1325814Sjkhvoid Lst_ForEach __P((Lst, int (*)(ClientData, ClientData), 1335814Sjkh ClientData)); 1341590Srgrimes/* 1355814Sjkh * Apply a function to all elements of a lst starting from a certain point. 1365814Sjkh * If the list is circular, the application will wrap around to the 1375814Sjkh * beginning of the list again. 1385814Sjkh */ 1395814Sjkhvoid Lst_ForEachFrom __P((Lst, LstNode, 1405814Sjkh int (*)(ClientData, ClientData), 1415814Sjkh ClientData)); 1425814Sjkh/* 1431590Srgrimes * these functions are for dealing with a list as a table, of sorts. 1441590Srgrimes * An idea of the "current element" is kept and used by all the functions 1451590Srgrimes * between Lst_Open() and Lst_Close(). 1461590Srgrimes */ 1475814Sjkh/* Open the list */ 1485814SjkhReturnStatus Lst_Open __P((Lst)); 1495814Sjkh/* Next element please */ 1505814SjkhLstNode Lst_Next __P((Lst)); 1515814Sjkh/* Done yet? */ 1525814SjkhBoolean Lst_IsAtEnd __P((Lst)); 1535814Sjkh/* Finish table access */ 1545814Sjkhvoid Lst_Close __P((Lst)); 1551590Srgrimes 1561590Srgrimes/* 1571590Srgrimes * for using the list as a queue 1581590Srgrimes */ 1595814Sjkh/* Place an element at tail of queue */ 1605814SjkhReturnStatus Lst_EnQueue __P((Lst, ClientData)); 1615814Sjkh/* Remove an element from head of queue */ 1625814SjkhClientData Lst_DeQueue __P((Lst)); 1631590Srgrimes 1645814Sjkh#endif /* _LST_H_ */ 165