/*############################################################################## FUNNNELWEB COPYRIGHT ==================== FunnelWeb is a literate-programming macro preprocessor. The FunnelWeb web is at http://www.ross.net/funnelweb/ Copyright (c) Ross N. Williams 1992. All rights reserved. This program is free software; you can redistribute it and/or modify it under the terms of Version 2 of the GNU General Public License as published by the Free Software Foundation (http://www.gnu.org/). This program is distributed WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See Version 2 of the GNU General Public License for more details. You should have received a copy of Version 2 of the GNU General Public License along with this program. If not, you can obtain a copy as follows: ftp://prep.ai.mit.edu/pub/gnu/COPYING-2.0 or write to: Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA Section 2a of the license requires that all changes to this file be recorded prominently in this file. Please record all changes here. Programmers: RNW Ross N. Williams (ross@ross.net) Changes: 07-May-1992 RNW Program prepared for release under GNU GPL V2. ##############################################################################*/ /******************************************************************************/ /* TABLE.H */ /******************************************************************************/ /* */ /* Introduction */ /* ------------ */ /* This table package (table.h and table.c) implements a table abstraction. */ /* */ /* Facts about Tables */ /* ------------------ */ /* - A TABLE stores zero or more (KEY,VALUE) PAIRS. */ /* - The user decides the types of keys and values and provides a */ /* COMPARISON FUNCTION providing a complete ordering of the set of keys. */ /* - The comparison function must be consistent between calls. */ /* - Tables store pairs in key order. */ /* - A table cannot store more than one pair with the same key. */ /* - Pairs can be added, but not deleted. */ /* - A table can return the value corresponding to a given key. */ /* - The pairs in a table can be read sequentially in key order. At all */ /* times, the table has an imaginary MARKER positioned on one of its pairs */ /* (or after the last pair). You can move the marker to the first pair and */ /* you can move the marker to the next pair, reading the pair as you go. */ /* Upon table creation, a table's marker is at the end-of-table position. */ /* - If you try to perform an illegal operation on a table, the table package */ /* will call "error" to write out an error message and bomb the program. */ /* - Tables store copies of (key,value) pairs. They do not hold pointers to */ /* outside data (unless your keys or values are pointers themselves). */ /* - If the keys are pointers themselves and point to other data which is */ /* used by the comparison function, then that data must not be modified */ /* in a way that will change the order of pairs in the table. */ /* - A table can hold from zero to about 2^31 pairs. */ /* - The identifier "tb" is used as an abbreviation for "table". */ /* - The identifier "ky" is used as an abbreviation for "key". */ /* - The identifier "vl" is used as an abbreviation for "value". */ /* - The author would like to use longer names, but has chosen to use the */ /* abbreviations so as to enhance the portability of the code. */ /* - IMPORTANT: Tables get all their memory using mm_temp calls. */ /* */ /* How To Use This Table Package */ /* ----------------------------- */ /* 1. Include this .H file in your program file. */ /* 2. Identify the key and value types that you are going to use. */ /* 3. Define a function (having two parameters being pointers to keys) */ /* that compares two keys and returns [-1,0,1] accordingly. */ /* 4. Define a variable of type p_tb as a view to a table. */ /* 5. Use the tb_* functions to perform the desired operations. */ /* Start with a call to tb_cre and (optionally) end with a call to tb_des. */ /* */ /******************************************************************************/ /* Ensure that the body of this header file is included at most once. */ #ifndef DONE_TABLE #define DONE_TABLE /******************************************************************************/ #include #include "style.h" /******************************************************************************/ /* Hide the exported abstract definition of a table from the table.c package. */ /* Table.c defines INTABLEC so as to prevent itself from seeing the following */ /* definitions. It defines its own more concrete definitions. */ #ifndef INTABLEC /* The functions of the table abstraction pass keys and values exclusively */ /* using pointers. These two definitions define types for these pointers. */ /* Although the two types are both 'p_void', the different types are useful */ /* to indicate what is expected in each position of the parameter lists. */ typedef p_void p_tbky_t; typedef p_void p_tbvl_t; /* Define a type for a function to compare two keys. Such functions are */ /* needed to organize the storage of (key,value) pairs inside the table. */ /* Given the arguments are (a,b), the function should return: */ /* -1 if ab */ /* The user must create such a function and hand it to the 'tb_create' */ /* function when creating new a new table. */ typedef sign (*p_kycm_t) P_((p_tbky_t,p_tbky_t)); /* Users manipulate tables through pointers to tables. Here the actual table */ /* internals are hidden from the user. */ typedef struct {word NEVER_USE_THIS_FIELD_UQJTKC;} tb_t; typedef tb_t *p_tb_t; #endif /******************************************************************************/ /* General Notes About These Functions */ /* ----------------------------------- */ /* - All tables, keys, and values are passed by pointer. Whether a parameter */ /* is read or written is determined by it's functions description. */ /* - Each function (except tb_cre) accepts a single pointer to a table and */ /* each function's description is assumed to be referring to the table. */ /* - "Raising an error" means calling the external function "error" to */ /* write out a message and bomb the program. */ /* - You must create a table using tb_cre before performing any operations */ /* upon it. The table operations will usually raise an error if they are */ /* handed a pointer that does not point to a properly CREated table. */ /* The Functions */ /* ------------- */ EXPORT p_tb_t tb_cre P_((size_t,size_t,p_kycm_t)); /* CREate. This function creates a new table and returns a pointer to the */ /* table. The user must supply 1) the size in bytes of keys, 2) the size in */ /* bytes of values, 3) a pointer to a function that compares two keys. */ EXPORT bool tb_itb P_((p_tb_t,p_tbky_t)); /* InTaBle. Returns TRUE iff the given key is in the table. */ EXPORT void tb_loo P_((p_tb_t,p_tbky_t,p_tbvl_t)); /* LOOkup. Feed this function a table and a key and it will return (in the */ /* p_tbvl_t parameter) the value corresponding to the key. The function */ /* raises an error if the table does not contain the key. */ EXPORT void tb_ins P_((p_tb_t,p_tbky_t,p_tbvl_t)); /* INSert. Inserts the (key,value) pair into the table. Raises an error if */ /* the key is already in the table. */ EXPORT ulong tb_len P_((p_tb_t)); /* LENgth. Returns the number of pairs in the table. */ EXPORT void tb_fir P_((p_tb_t)); /* FIRst. Set's the table's marker to the first pair in the table (or the end */ /* of table position if the table is empty. */ EXPORT bool tb_rea P_((p_tb_t,p_tbky_t,p_tbvl_t)); /* REAd. Returns in (p_tbky_t,p_tbvl_t) the (key,value) pair corresponding to */ /* the marker and them moves the marker onto the next pair. */ /* Returns TRUE => Returned a pair. */ /* Returns FALSE => Did not return a pair. No more pairs left. */ /* of key) to be read from the table. Returns TRUE if it returns a pair */ /* This function will not raise an error if it is called more than once with */ /* the marker at the end of the table (it just keeps returning FALSE). */ #if FALSE void tb_des P_((p_tb_t)); /* DEStroy. Destroys a table, deallocating all its memory. */ #endif /******************************************************************************/ /* For #ifndef preventing multiple inclusion of the body of this header file. */ #endif /******************************************************************************/ /* End of TABLE.H */ /******************************************************************************/