chiark - git - mdw - mLib/blob - struct/assoc.3.in

   1 .\" -*-nroff-*-
   2 .\"
   3 .\" Manual for association tables based on atoms
   4 .\"
   5 .\" (c) 2001, 2005, 2009, 2023, 2024 Straylight/Edgeware
   6 .\"
   7 .
   8 .\"----- Licensing notice ---------------------------------------------------
   9 .\"
  10 .\" This file is part of the mLib utilities library.
  11 .\"
  12 .\" mLib is free software: you can redistribute it and/or modify it under
  13 .\" the terms of the GNU Library General Public License as published by
  14 .\" the Free Software Foundation; either version 2 of the License, or (at
  15 .\" your option) any later version.
  16 .\"
  17 .\" mLib is distributed in the hope that it will be useful, but WITHOUT
  18 .\" ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  19 .\" FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Library General Public
  20 .\" License for more details.
  21 .\"
  22 .\" You should have received a copy of the GNU Library General Public
  23 .\" License along with mLib.  If not, write to the Free Software
  24 .\" Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  25 .\" USA.
  26 .
  27 .\"--------------------------------------------------------------------------
  28 .so ../defs.man \" @@@PRE@@@
  29 .
  30 .\"--------------------------------------------------------------------------
  31 .TH assoc 3mLib "23 January 2001" "Straylight/Edgeware" "mLib utilities library"
  32 .\" @assoc_create
  33 .\" @assoc_destroy
  34 .\" @assoc_find
  35 .\" @assoc_remove
  36 .\" @assoc_mkiter
  37 .\" @assoc_next
  38 .
  39 .\" @ASSOC_ATOM
  40 .
  41 .\"--------------------------------------------------------------------------
  42 .SH NAME
  43 assoc \- tables indexed by atoms
  44 .
  45 .\"--------------------------------------------------------------------------
  46 .SH SYNOPSIS
  47 .
  48 .nf
  49 .B "#include <mLib/assoc.h>"
  50 .PP
  51 .B "typedef struct { ...\& } assoc_table;"
  52 .B "typedef struct { ...\& } assoc_base;"
  53 .PP
  54 .BI "void assoc_create(assoc_table *" t );
  55 .BI "void assoc_destroy(assoc_table *" t );
  56 .PP
  57 .BI "void *assoc_find(assoc_table *" t ", atom *" a ", size_t " sz ", unsigned *" f );
  58 .BI "void assoc_remove(assoc_table *" t ", void *" b );
  59 .PP
  60 .BI "atom *ASSOC_ATOM(const void *" p );
  61 .PP
  62 .BI "void assoc_mkiter(assoc_iter *" i ", assoc_table *" t );
  63 .BI "void *assoc_next(assoc_iter *" i );
  64 .fi
  65 .
  66 .\"--------------------------------------------------------------------------
  67 .SH DESCRIPTION
  68 .
  69 An
  70 .I "association table"
  71 is a data structure which maps atoms (see
  72 .BR atom (3))
  73 to arbitrary values.  It works in a similar way to the symbol tables
  74 implemented by
  75 .BR sym (3),
  76 except that it uses atoms rather than blocks of data as keys.
  77 .PP
  78 Like
  79 .BR sym (3),
  80 it implements an
  81 .I intrusive
  82 table: the value structures must include an
  83 .B assoc_base
  84 structure.
  85 .PP
  86 There are three main data structures:
  87 .TP
  88 .B assoc_table
  89 Keeps track of the information associated with a particular table.
  90 .TP
  91 .B assoc_base
  92 The header which must be attached to the front of all the value objects.
  93 .TP
  94 .B assoc_iter
  95 An iterator object, used for enumerating all of the associations stored
  96 in the table
  97 .PP
  98 All of the above structures should be considered
  99 .IR opaque :
 100 don't try looking inside.
 101 .
 102 .SS "Creation and destruction"
 103 The
 104 .B assoc_table
 105 object itself needs to be allocated by the caller.  It is initialized by
 106 passing it to the function
 107 .BR assoc_create .
 108 After initialization, the table contains no entries.
 109 .PP
 110 Initializing an association table involves allocating some memory.  If
 111 this allocation fails, an
 112 .B EXC_NOMEM
 113 exception is raised.
 114 .PP
 115 When an association table is no longer needed, the memory occupied by
 116 the values and other maintenance structures can be reclaimed by calling
 117 .BR assoc_destroy .
 118 Any bits of user data attached to values should previously have been
 119 destroyed.
 120 .
 121 .SS "Adding, searching and removing"
 122 Most of the actual work is done by the function
 123 .BR assoc_find .
 124 It does both lookup and creation, depending on its arguments.  To do its
 125 job, it needs to know the following bits of information:
 126 .TP
 127 .BI "assoc_table *" t
 128 A pointer to an association table to manipulate.
 129 .TP
 130 .BI "atom *" a
 131 The address of the atom to use as a key.
 132 .TP
 133 .BI "size_t " sz
 134 The size of the value block to allocate if the key could not be found.
 135 If this is zero, no value is allocated, and a null pointer is returned
 136 to indicate an unsuccessful lookup.
 137 .TP
 138 .BI "unsigned *" f
 139 The address of a `found' flag to set.  This is an output parameter.  On
 140 exit,
 141 .B assoc_find
 142 will set the value of
 143 .BI * f
 144 to zero if the key could not be found, or nonzero if it was found.  This
 145 can be used to tell whether the value returned has been newly allocated,
 146 or whether it was already in the table.
 147 .PP
 148 A symbol can be removed from the table by calling
 149 .BR assoc_remove ,
 150 passing the association table itself, and the value block that needs
 151 removing.
 152 .
 153 .SS "Enquiries about associations"
 154 Given a pointer
 155 .I a
 156 to an association, the expression
 157 .BI ASSOC_ATOM( a )
 158 has as its value a poinetr to the atom which is that association's key.
 159 .
 160 .SS "Enumerating associations"
 161 Enumerating the values in an association table is fairly simple.
 162 Allocate an
 163 .B assoc_iter
 164 object from somewhere.  Attach it to an association table by calling
 165 .BR assoc_mkiter ,
 166 and passing in the addresses of the iterator and the symbol table.
 167 Then, each call to
 168 .B assoc_next
 169 will return a different value from the association table, until all of
 170 them have been enumerated, at which point,
 171 .B assoc_next
 172 returns a null pointer.
 173 .PP
 174 It's safe to remove the symbol you've just been returned by
 175 .BR assoc_next .
 176 However, it's not safe to remove any other symbol.  So don't do that.
 177 .PP
 178 When you've finished with an iterator, it's safe to just throw it away.
 179 You don't need to call any functions beforehand.
 180 .
 181 .\"--------------------------------------------------------------------------
 182 .SH SEE ALSO
 183 .
 184 .BR atom (3),
 185 .BR hash (3),
 186 .BR sym (3),
 187 .BR mLib (3).
 188 .
 189 .\"--------------------------------------------------------------------------
 190 .SH AUTHOR
 191 .
 192 Mark Wooding, <mdw@distorted.org.uk>
 193 .
 194 .\"----- That's all, folks --------------------------------------------------