head	1.128;access	david	neto;symbols	zero-five-zero:1.128	zero-four-seventeen:1.128	zero-four-ten:1.127	zero-four-nine:1.127	zero-four-eight:1.127	zero-four-five:1.127	zero-four-zero:1.127;locks	neto:1.128;1.128date	98.10.16.20.43.58;	author neto;	state Exp;branches;next	1.127;1.127date	98.07.16.21.58.55;	author neto;	state Exp;branches;next	1.126;1.126date	98.06.12.22.48.21;	author neto;	state Exp;branches;next	1.125;1.125date	98.05.23.16.36.37;	author neto;	state Exp;branches;next	1.124;1.124date	98.05.21.20.28.29;	author neto;	state Exp;branches;next	1.123;1.123date	97.09.27.18.05.36;	author neto;	state Exp;branches;next	1.122;1.122date	97.08.15.20.18.25;	author neto;	state Exp;branches;next	1.121;1.121date	97.05.16.22.39.33;	author neto;	state Exp;branches;next	1.120;1.120date	97.05.16.21.30.19;	author neto;	state Exp;branches;next	1.119;1.119date	97.05.16.18.11.41;	author neto;	state Exp;branches;next	1.118;1.118date	97.05.16.18.09.40;	author neto;	state Exp;branches;next	1.117;1.117date	97.05.16.16.45.31;	author neto;	state Exp;branches;next	1.116;1.116date	97.05.16.16.34.16;	author neto;	state Exp;branches;next	1.115;1.115date	97.05.16.16.21.31;	author neto;	state Exp;branches;next	1.114;1.114date	97.05.16.16.20.20;	author neto;	state Exp;branches;next	1.113;1.113date	97.05.14.20.23.29;	author neto;	state Exp;branches;next	1.112;1.112date	97.01.27.16.35.30;	author neto;	state Exp;branches;next	1.111;1.111date	97.01.21.21.55.55;	author david;	state Exp;branches;next	1.110;1.110date	96.12.17.10.58.36;	author neto;	state Exp;branches;next	1.109;1.109date	96.08.20.11.30.14;	author neto;	state Exp;branches;next	1.108;1.108date	96.08.16.13.04.40;	author neto;	state Exp;branches;next	1.107;1.107date	96.08.15.14.14.53;	author neto;	state Exp;branches;next	1.106;1.106date	96.08.15.13.14.35;	author neto;	state Exp;branches;next	1.105;1.105date	96.08.02.14.20.24;	author neto;	state Exp;branches;next	1.104;1.104date	96.08.01.15.50.44;	author neto;	state Exp;branches;next	1.103;1.103date	96.07.29.17.09.58;	author neto;	state Exp;branches;next	1.102;1.102date	96.07.29.16.19.45;	author neto;	state Exp;branches;next	1.101;1.101date	96.06.19.14.14.57;	author neto;	state Exp;branches;next	1.100;1.100date	96.05.29.11.13.07;	author neto;	state Exp;branches;next	1.5;1.5date	96.05.24.16.44.12;	author neto;	state Exp;branches;next	1.4;1.4date	96.03.15.15.59.27;	author neto;	state Exp;branches;next	1.3;1.3date	96.03.04.14.40.18;	author neto;	state Exp;branches;next	1.2;1.2date	96.03.04.14.01.38;	author neto;	state Exp;branches;next	1.1;1.1date	96.03.04.13.53.34;	author neto;	state Exp;branches;next	;desc@Dictionary ADT.@1.128log@Fixed typo@text@\noindent Copyright \copyright 1994, 1995, 1996, 1997, 1998 David Neto\smallskip\noindent    This library is free software; you can redistribute it and/or   modify it under the terms of the GNU Library General Public   License as published by the Free Software Foundation; either   version 2 of the License, or (at your option) any later version.\smallskip\noindent    This library is distributed in the hope that it will be useful,   but WITHOUT ANY WARRANTY; without even the implied warranty of   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU   Library General Public License for more details.\smallskip\noindent      You should have received a copy of the GNU Library General Public   License along with this library; if not, write to the   Free Software Foundation, Inc., 59 Temple Place - Suite 330,   Boston, MA  02111-1307, USA.\smallskip\noindent      You may contact David Neto via email at {\tt netod@@@@acm.org}, or with   greater latency at\smallskip\noindent{\obeylines     Department of Computer Science     University of Toronto     10 King's College Rd.     Toronto, Ontario     M5S 3G4     Canada}\medskip\noindent\hbox{}\hrule\hbox{}\penalty-1000\vskip0.5cm\relax@@i webdefs.w@@i types.w{\obeylines$Log: dict.w,v $Revision 1.127  1998/07/16 21:58:55  netoAdded the LGPL notice in each file.Revision 1.126  1998/06/12 22:48:21  netoFixed a bug.  delete min and delete max weren't returning the rightthink.  (That's ok, LK wasn't using that stuff anyway...)Revision 1.125  1998/05/23 16:36:37  netoGet rid of unused l in delete min and delete max.Give a value to variable here so GCC's dataflow analysis is satisfied.Revision 1.124  1998/05/21 20:28:29  netoAdded dict size, dict delete min, dict delete max.Revision 1.123  1997/09/27 18:05:36  netoFixed RCS log behaviour.Revision 1.122  1997/08/15  20:18:25  netoAdded Index major section.Revision 1.121  1997/05/16  22:39:33  netoFix the pointer print spec.Revision 1.120  1997/05/16  21:30:19  netoFixed a printf spec: from integer to pointer.(This is in dicttest).Revision 1.119  1997/05/16  18:11:41  netoBreak locks by david and neto.Include <config.h> and "lkconfig.h"Revision 1.118  1997/05/16  18:09:40  netoInclude <config.h> and lkconfig.hRevision 1.117  1997/05/16  16:45:31  netoMake dicttest's main conform to ANSI standard by making it takeint, char ** arguments.Revision 1.116  1997/05/16  16:34:16  netoRemoved dumb conditional in dicttest.Revision 1.115  1997/05/16  16:21:31  netoDont discard const.Revision 1.114  1997/05/16  16:20:20  netoAdd prototypes for functions in dicttest.Revision 1.113  1997/05/14  20:23:29  netodicttest.w doesn't actually use resource measurement. removed.Revision 1.112  97/01/27  16:35:30  netoFixed the function definition for dict\_ createRevision 1.111  1997/01/21  21:55:55  davidAdded standard copyright notice by including copyrt.wRevision 1.110  96/12/17  10:58:36  netoFixed some dataflow analysis warnings.Revision 1.109  96/08/20  11:30:14  netoFixed uninitialized variable l.  That was a bug.Also fixed ggpl.  Not a bug, but a dataflow analysis warning.Revision 1.108  96/08/16  13:04:40  netoAdded fixincludes.Revision 1.107  96/08/15  14:14:53  netoAdde prototype to satisfy all the warning options of GCC.Revision 1.106  96/08/15  13:14:35  netoMake it pass -WallRevision 1.105  96/08/02  14:20:24  netoAllow others to get dict without first getting pool.Revision 1.104  96/08/01  15:50:44  netoMaked dict\_delete return the item it just deleted.Revision 1.103  96/07/29  17:09:58  netoFixed to compile.Revision 1.102  96/07/29  16:19:45  netoAdded *\_rcs\_id.Made sure RCS log is activated within this file.}@@*Dictionaries.This module is implements the dictionary abstract data type overany totally ordered domain.% Format |dict_t| as an int.@@s dict_t int@@ The outline of this module is as follows:@@c#include <config.h>#include "lkconfig.h"@@<System headers@@>@@;@@<Module headers@@>@@;@@<Module macros@@>@@;@@<Subroutines@@>@@;const char *dict_rcs_id = "$Id: dict.w,v 1.127 1998/07/16 21:58:55 neto Exp neto $";@@ We will be using many routines from external libraries.  The interfacesto those routines are described in the following headers.@@<System headers@@>=#include <stdio.h>#include <stdlib.h>#include <stddef.h>#include <assert.h>#include "fixincludes.h"@@ The exported interface is contained in the \file{dict.h} header file,which has the following form.@@(dict.h@@>=#if !defined(_DICT_H_)#define _DICT_H_@@<Headers required for the interface@@>@@;extern const char *dict_rcs_id;@@<Exported type definitions@@>@@;@@<Exported subroutines@@>@@;#endif@@ To ensure consistency between the interface and the implementation,we include our own header.@@<Module headers@@>=#include "dict.h"@@ The interface is as follows:|dict_t *dict_create(int (*cmp_fnc)(const void *, const void*),void (*prn_fnc)(void *))| takes a comparison functionand returns a new dictionary for items that may be compared with thatfunction.  The comparison function is the same kind as required forthe |qsort| library function.  That is, given pointers to two objects,it should return an integer that is less than, equal to, or greater thanzero if the first object compares less than, equal to, or greater thanthe second object, respectively.For debugging purposes, we also take a node printing function.|void dict_destroy(dict_t *d, void (*action)(void *))| destroys a previously created dictionary.  If |action != NULL|, then|action| is called on every item in the dictionary.|int dict_insert(dict_t *d,void *e)| inserts item |e| into the given dictionary.This function returns a non-zero value if and only if the item was already in the dictionary.  If the item was already present, then a newcopy is {\it not} added.  You can always get around this no-duplicateslimitationby modifying the comparison function to return the difference of the twopointers if the pointed-to items would otherwise compare as equal.|void *dict_find(dict_t *d,void *e)| finds any previously inserted itemwhich tests as equal to the given item.  If the item is found, itreturns the previously stored pointer (not necessarily the pointerprovided in this call); otherwise, NULL is returned.|void *dict_delete(dict_t *d, void *e, void (*action)(void *))| deletes the item which compares equalto the given item.  If it isn't present, then nothing happens.If |action| is non-NULL, then it is called with the item found equal to |e|.(This is useful for deallocation of space, for example.)The procedure returns the entry that it deleted, if any.  Note that thisis not necessarily the same pointer value passed to it as |e|, but isthe pointer value that compared as equal to |e|.  If no entry wasdeleted, then this procedure returns |NULL|.|void dict_delete_all(dict_t *, void (*action)(void *))| empties the dictionary.  If |action != NULL|, then it is called on everydeleted element.|void *dict_delete_any(dict_t *)| deletes and returns an arbitrary element of the dictionary.If the dictionary is empty, then it returns |NULL|.|void *dict_min(dict_t *)| returns the minimum element of the dictionary.If the dictionary is empty, then it returns |NULL|.|void *dict_delete_min(dict_t *)| returns the minimum element of thedictionary,removing it from the dictionary.If the dictionary is empty, then it returns |NULL|.|void *dict_max(dict_t *)| returns the maximum element of the dictionary.If the dictionary is empty, then it returns |NULL|.|void *dict_delete_max(dict_t *)| returns the maximum element of the dictionary,removing it from the dictionary.If the dictionary is empty, then it returns |NULL|.|void dict_update_all(dict_t *,void (*proc)(void *env2,void **payload_p),void *env1)|,for each item in the dictionary, calls |proc| on |env1| and a pointer to that item's payload pointer.  This allows update in place of all theitems in the dictionary.   Procedure |proc| must not call any of the otherdictionary routines on this dictionary.It also must not change the relative ordering of any of the nodes.The results are undefined if |proc| breaks either of these rules.|size_t dict_size(dict_t *)| returns the number of elements in thedictionary.This is accounting is ok if the routines aren't used re-entrantly onthe same dictionary.  That is, if the destruction routine for adictionaryentry calls a routine modifying the entry, then this count could be wrong.Heck all hell might break loose.@@<Exported subroutines@@>=dict_t *dict_create(int (*cmp_fnc)(const void *, const void*), 		void (*prn_fnc)(void *));void dict_destroy(dict_t *d,void (*action)(void *));int dict_insert(dict_t *d,void *e);void *dict_find(dict_t *d,void *e);void *dict_delete(dict_t *d, void *e, void (*action)(void *));void dict_delete_all(dict_t *d, void (*action)(void *));void *dict_delete_any(dict_t *d, void (*action)(void *));void *dict_min(dict_t *d);void *dict_max(dict_t *d);void *dict_delete_min(dict_t *d);void *dict_delete_max(dict_t *d);void dict_update_all(dict_t *d,void (*proc)(void *env2,void **payload_p),void *env1);size_t dict_size(dict_t *d);@@ Up front, we know we'll need interfaces tothe error checking and memory allocationmodules.@@<Module headers@@>=#include "error.h"#include "memory.h"@@*The dictionary implementation.I'll use splay trees.  They have linear worst-case storage, and logarithmicamortized worst-case time per operation.  Splay trees have the addedfeature thatperform very well when there is a lot of locality present in thesequence of operations.  They adjust well to a shifting distribution ofaccesses.% Format |pool_t| as if it were an |int|.@@s pool_t int@@ Each dictionary consists of just a pointer to the root node, a pointer to the comparison function, and an optional pointer to a payload printing function.Each node has pointers to its parent, its left and right children,and the payload.Each dictionary allocates from its own pool of memory.  We keep a pointerto that pool.@@<Exported type definitions@@>=typedef struct dict_node_s {	void *payload;	struct dict_node_s *link[3];} dict_node_t;typedef struct {	dict_node_t *root;	int (*cmp)(const void *a, const void *b);	void (*prn)(void *a);	pool_t *pool;	size_t size;} dict_t;@@ We need the interface for the pool-oriented allocator.  Sincepart of our own interface includes a pool type, we must include thepool interface within our own interface.@@<Headers required for the interface@@>=#include "pool.h"@@ We've allocated space for three links per node.  It will be convenientto give them the following standard names.  I've allocated an an array instead of using the names themselves becauseit will compact the code later on.@@<Module macros@@>=#define NILLINK (-2)	/* A nonsense value, for debugging purposes. */#define SELF (-1)#define PARENT (0)#define LEFT (1)#define RIGHT (2)#define parent link[PARENT]#define left link[LEFT]#define right link[RIGHT]@@ Creating the dictionary just means allocating and initializing a |dict_t| structure.@@<Subroutines@@>=dict_t *dict_create(int (*the_cmp)(const void *a, const void *b),void (*the_prn)(void *a)) {	dict_t *d = new_of(dict_t);	d->root = NULL;	errorif(the_cmp == NULL,"Need a non-null comparison function");	d->cmp = the_cmp;	d->prn = the_prn;	d->pool = pool_create(sizeof(dict_node_t),1000);	d->size = 0;	return d;}@@ Destroying the dictionary involves freeing all the nodes int the tree,and freeing the |dict_t| structure as well.@@<Subroutines@@>=voiddict_destroy(dict_t *d, void (*action)(void *)) {	if ( d != NULL ) {		@@<Deallocate the subtree rooted at |d->root|, calling |action| on each item@@>@@;		d->cmp = NULL;		d->prn = NULL;		d->root = NULL;		pool_destroy(d->pool);		d->pool = NULL;		d->size = 0;		free_mem(d);	}}@@ We can traverse the entire tree non-recursively because we have parentpointers.  This is a darn clever bit of code.  It does a post-ordertraversal.Note that this bit of code requires only constant space.  A recursivetraversal would take linear space in the worst case.  Remember thatsplay trees have bad operation sequences which sometimes force them to into degenerate trees.@@<Deallocate the subtree rooted at |d->root|, calling |action| on each item@@>={dict_node_t *here, *prev;here = d->root;prev = NULL;while ( here != NULL ) {	if ( here->left != NULL && prev == here->parent ) {		prev = here;		here = here->left;	} else if ( here->right != NULL && prev != here->right ) {		prev = here;		here = here->right;	} else { /* Deallocate the |here| node. */		if ( action ) action(here->payload);		prev = here;		here = here->parent;		pool_free(d->pool,prev);	}}}@@ We've just coded most of what is needed for |dict_delete_all|.  It doesa subset of |dict_destroy|.@@<Subroutines@@>=voiddict_delete_all(dict_t *d,void (*action)(void *)) {	@@<Deallocate the subtree rooted at |d->root|, calling |action| on each item@@>@@;	d->root = NULL;	d->size = 0;}@@ We will take some care in coding  the insertion routine so that we canreuse parts of it later.To insert a node, we find where it should go, add it there, and then splay it to the root.If there already was an item that compared equal to |e|, then we don'tadd anything.@@<Subroutines@@>=intdict_insert(dict_t *d, void *e) {	dict_node_t *here, *next;	int l;	/* The link where |e| goes. */	int was_absent;	next = d->root;	@@<Find |e| in the subtree rooted at |next|@@>@@;	if ( 0!=(was_absent = (l!=SELF)) )  {		@@<Add |e|, and make |here| to point its node@@>@@;		d->size++;	}	@@<Splay |here| to the root@@>@@;	return !was_absent;}@@ To find a node, we do the usual binary search down from the root.We do the test for equality last because it is the most likely testto fail.  Make the common code fast, and make the fast code common.If |e| exists in the subtree, then this code will make both |next| and |here|point to its node, and set |l| to |SELF|.  The otherwise casesplits into two cases.  If |e| isn't in the tree because the treeis empty, then |l| is set to something other than |SELF| and |here| isset to |NULL|.  If |e| isn't in the tree and the tree is non-empty,then we make|next==NULL|, and |here->link[l]| is the null pointer that should point to a new node for |e|.@@<Find |e| in the subtree rooted at |next|@@>=l=PARENT;	/* Something other than |SELF|. */for ( here = NULL; next && next != here ; ) {	int compared_as = d->cmp(e,next->payload);	here = next;	if ( compared_as < 0 ) {