doc/containers.texi

   1 @node Container data types
   2 @section Container data types
   3
   4 @c Copyright (C) 2019--2024 Free Software Foundation, Inc.
   5
   6 @c Permission is granted to copy, distribute and/or modify this document
   7 @c under the terms of the GNU Free Documentation License, Version 1.3 or
   8 @c any later version published by the Free Software Foundation; with no
   9 @c Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.  A
  10 @c copy of the license is at <https://www.gnu.org/licenses/fdl-1.3.en.html>.
  11
  12 @c Written by Bruno Haible.
  13
  14 @c This macro expands to \log in TeX mode, but just 'log' in HTML and info
  15 @c modes.
  16 @ifnottex
  17 @macro log
  18 log
  19 @end macro
  20 @end ifnottex
  21
  22 @c This macro expands to \mathopsup in TeX mode, to a superscript in HTML
  23 @c mode, and to ^ without braces in info mode.
  24 @ifhtml
  25 @macro mathopsup {EXP}
  26 @sup{\EXP\}
  27 @end macro
  28 @end ifhtml
  29 @ifinfo
  30 @macro mathopsup {EXP}
  31 ^\EXP\
  32 @end macro
  33 @end ifinfo
  34
  35 Gnulib provides several generic container data types.  They can be used
  36 to organize collections of application-defined objects.
  37
  38 @node Ordinary containers
  39 @subsection Ordinary container data types
  40
  41 @multitable @columnfractions .15 .5 .1 .1 .15
  42 @headitem Data type
  43 @tab Details
  44 @tab Module
  45 @tab Main include file
  46 @tab Include file for operations with out-of-memory checking
  47 @item Sequential list
  48 @tab Can contain any number of objects in any given order.
  49      Duplicates are allowed, but can optionally be forbidden.
  50 @tab @code{list}
  51 @tab @code{"gl_list.h"}
  52 @tab @code{"gl_xlist.h"}
  53 @item Set
  54 @tab Can contain any number of objects; the order does not matter.
  55      Duplicates (in the sense of the comparator) are forbidden.
  56 @tab @code{set}
  57 @tab @code{"gl_set.h"}
  58 @tab @code{"gl_xset.h"}
  59 @item Ordered set
  60 @tab Can contain any number of objects in the order of a given comparator
  61      function.
  62      Duplicates (in the sense of the comparator) are forbidden.
  63 @tab @code{oset}
  64 @tab @code{"gl_oset.h"}
  65 @tab @code{"gl_xoset.h"}
  66 @item Map
  67 @tab Can contain any number of (key, value) pairs, where keys and values
  68      are objects;
  69      there are no (key, value1) and (key, value2) pairs with the same key
  70      (in the sense of a given comparator function).
  71 @tab @code{map}
  72 @tab @code{"gl_map.h"}
  73 @tab @code{"gl_xmap.h"}
  74 @item Ordered map
  75 @tab Can contain any number of (key, value) pairs, where keys and values
  76      are objects;
  77      the (key, value) pairs are ordered by the key, in the order of a given
  78      comparator function;
  79      there are no (key, value1) and (key, value2) pairs with the same key
  80      (in the sense of the comparator function).
  81 @tab @code{omap}
  82 @tab @code{"gl_omap.h"}
  83 @tab @code{"gl_xomap.h"}
  84 @end multitable
  85
  86 Operations without out-of-memory checking (suitable for use in libraries) are
  87 declared in the ``main include file''.  Whereas operations with out-of-memory
  88 checking (suitable only in programs) are declared in the ``include file for
  89 operations with out-of-memory checking''.
  90
  91 For each of the data types, several implementations are available, with
  92 different performance profiles with respect to the available operations.
  93 This enables you to start with the simplest implementation (ARRAY) initially,
  94 and switch to a more suitable implementation after profiling your application.
  95 The implementation of each container instance is specified in a single place
  96 only: in the invocation of the function @code{gl_*_create_empty} that creates
  97 the instance.
  98
  99 The implementations and the guaranteed average performance for the operations
 100 for the ``sequential list'' data type are:
 101
 102 @multitable @columnfractions 0.2 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
 103 @headitem Operation
 104 @tab ARRAY
 105 @tab CARRAY
 106 @tab LINKED
 107 @tab TREE
 108 @tab LINKEDHASH with duplicates
 109 @tab LINKEDHASH without duplicates
 110 @tab TREEHASH with duplicates
 111 @tab TREEHASH without duplicates
 112 @item @code{gl_list_size}
 113 @tab @math{O(1)}
 114 @tab @math{O(1)}
 115 @tab @math{O(1)}
 116 @tab @math{O(1)}
 117 @tab @math{O(1)}
 118 @tab @math{O(1)}
 119 @tab @math{O(1)}
 120 @tab @math{O(1)}
 121 @item @code{gl_list_node_value}
 122 @tab @math{O(1)}
 123 @tab @math{O(1)}
 124 @tab @math{O(1)}
 125 @tab @math{O(1)}
 126 @tab @math{O(1)}
 127 @tab @math{O(1)}
 128 @tab @math{O(1)}
 129 @tab @math{O(1)}
 130 @item @code{gl_list_node_set_value}
 131 @tab @math{O(1)}
 132 @tab @math{O(1)}
 133 @tab @math{O(1)}
 134 @tab @math{O(1)}
 135 @tab @math{O(1)}
 136 @tab @math{O(1)}
 137 @tab @math{O((@log n)@mathopsup{2})}
 138 @tab @math{O(1)}
 139 @item @code{gl_list_next_node}
 140 @tab @math{O(1)}
 141 @tab @math{O(1)}
 142 @tab @math{O(1)}
 143 @tab @math{O(@log n)}
 144 @tab @math{O(1)}
 145 @tab @math{O(1)}
 146 @tab @math{O(@log n)}
 147 @tab @math{O(@log n)}
 148 @item @code{gl_list_previous_node}
 149 @tab @math{O(1)}
 150 @tab @math{O(1)}
 151 @tab @math{O(1)}
 152 @tab @math{O(@log n)}
 153 @tab @math{O(1)}
 154 @tab @math{O(1)}
 155 @tab @math{O(@log n)}
 156 @tab @math{O(@log n)}
 157 @item @code{gl_list_first_node}
 158 @tab @math{O(1)}
 159 @tab @math{O(1)}
 160 @tab @math{O(1)}
 161 @tab @math{O(@log n)}
 162 @tab @math{O(1)}
 163 @tab @math{O(1)}
 164 @tab @math{O(@log n)}
 165 @tab @math{O(@log n)}
 166 @item @code{gl_list_last_node}
 167 @tab @math{O(1)}
 168 @tab @math{O(1)}
 169 @tab @math{O(1)}
 170 @tab @math{O(@log n)}
 171 @tab @math{O(1)}
 172 @tab @math{O(1)}
 173 @tab @math{O(@log n)}
 174 @tab @math{O(@log n)}
 175 @item @code{gl_list_get_at}
 176 @tab @math{O(1)}
 177 @tab @math{O(1)}
 178 @tab @math{O(n)}
 179 @tab @math{O(@log n)}
 180 @tab @math{O(n)}
 181 @tab @math{O(n)}
 182 @tab @math{O(@log n)}
 183 @tab @math{O(@log n)}
 184 @item @code{gl_list_get_first}
 185 @tab @math{O(1)}
 186 @tab @math{O(1)}
 187 @tab @math{O(1)}
 188 @tab @math{O(@log n)}
 189 @tab @math{O(1)}
 190 @tab @math{O(1)}
 191 @tab @math{O(@log n)}
 192 @tab @math{O(@log n)}
 193 @item @code{gl_list_get_last}
 194 @tab @math{O(1)}
 195 @tab @math{O(1)}
 196 @tab @math{O(1)}
 197 @tab @math{O(@log n)}
 198 @tab @math{O(1)}
 199 @tab @math{O(1)}
 200 @tab @math{O(@log n)}
 201 @tab @math{O(@log n)}
 202 @item @code{gl_list_set_at}
 203 @tab @math{O(1)}
 204 @tab @math{O(1)}
 205 @tab @math{O(n)}
 206 @tab @math{O(@log n)}
 207 @tab @math{O(n)}
 208 @tab @math{O(n)}
 209 @tab @math{O((@log n)@mathopsup{2})}
 210 @tab @math{O(@log n)}
 211 @item @code{gl_list_set_first}
 212 @tab @math{O(1)}
 213 @tab @math{O(1)}
 214 @tab @math{O(1)}
 215 @tab @math{O(@log n)}
 216 @tab @math{O(n)}
 217 @tab @math{O(1)}
 218 @tab @math{O((@log n)@mathopsup{2})}
 219 @tab @math{O(@log n)}
 220 @item @code{gl_list_set_last}
 221 @tab @math{O(1)}
 222 @tab @math{O(1)}
 223 @tab @math{O(1)}
 224 @tab @math{O(@log n)}
 225 @tab @math{O(n)}
 226 @tab @math{O(1)}
 227 @tab @math{O((@log n)@mathopsup{2})}
 228 @tab @math{O(@log n)}
 229 @item @code{gl_list_search}
 230 @tab @math{O(n)}
 231 @tab @math{O(n)}
 232 @tab @math{O(n)}
 233 @tab @math{O(n)}
 234 @tab @math{O(n)}
 235 @tab @math{O(1)}
 236 @tab @math{O(@log n)}
 237 @tab @math{O(1)}
 238 @item @code{gl_list_search_from}
 239 @tab @math{O(n)}
 240 @tab @math{O(n)}
 241 @tab @math{O(n)}
 242 @tab @math{O(n)}
 243 @tab @math{O(n)}
 244 @tab @math{O(1)}
 245 @tab @math{O((@log n)@mathopsup{2})}
 246 @tab @math{O(@log n)}
 247 @item @code{gl_list_search_from_to}
 248 @tab @math{O(n)}
 249 @tab @math{O(n)}
 250 @tab @math{O(n)}
 251 @tab @math{O(n)}
 252 @tab @math{O(n)}
 253 @tab @math{O(1)}
 254 @tab @math{O((@log n)@mathopsup{2})}
 255 @tab @math{O(@log n)}
 256 @item @code{gl_list_indexof}
 257 @tab @math{O(n)}
 258 @tab @math{O(n)}
 259 @tab @math{O(n)}
 260 @tab @math{O(n)}
 261 @tab @math{O(n)}
 262 @tab @math{O(n)}
 263 @tab @math{O(@log n)}
 264 @tab @math{O(@log n)}
 265 @item @code{gl_list_indexof_from}
 266 @tab @math{O(n)}
 267 @tab @math{O(n)}
 268 @tab @math{O(n)}
 269 @tab @math{O(n)}
 270 @tab @math{O(n)}
 271 @tab @math{O(n)}
 272 @tab @math{O((@log n)@mathopsup{2})}
 273 @tab @math{O(@log n)}
 274 @item @code{gl_list_indexof_from_to}
 275 @tab @math{O(n)}
 276 @tab @math{O(n)}
 277 @tab @math{O(n)}
 278 @tab @math{O(n)}
 279 @tab @math{O(n)}
 280 @tab @math{O(n)}
 281 @tab @math{O((@log n)@mathopsup{2})}
 282 @tab @math{O(@log n)}
 283 @item @code{gl_list_add_first}
 284 @tab @math{O(n)}
 285 @tab @math{O(1)}
 286 @tab @math{O(1)}
 287 @tab @math{O(@log n)}
 288 @tab @math{O(1)}
 289 @tab @math{O(1)}
 290 @tab @math{O((@log n)@mathopsup{2})}
 291 @tab @math{O(@log n)}
 292 @item @code{gl_list_add_last}
 293 @tab @math{O(1)}
 294 @tab @math{O(1)}
 295 @tab @math{O(1)}
 296 @tab @math{O(@log n)}
 297 @tab @math{O(1)}
 298 @tab @math{O(1)}
 299 @tab @math{O((@log n)@mathopsup{2})}
 300 @tab @math{O(@log n)}
 301 @item @code{gl_list_add_before}
 302 @tab @math{O(n)}
 303 @tab @math{O(n)}
 304 @tab @math{O(1)}
 305 @tab @math{O(@log n)}
 306 @tab @math{O(1)}
 307 @tab @math{O(1)}
 308 @tab @math{O((@log n)@mathopsup{2})}
 309 @tab @math{O(@log n)}
 310 @item @code{gl_list_add_after}
 311 @tab @math{O(n)}
 312 @tab @math{O(n)}
 313 @tab @math{O(1)}
 314 @tab @math{O(@log n)}
 315 @tab @math{O(1)}
 316 @tab @math{O(1)}
 317 @tab @math{O((@log n)@mathopsup{2})}
 318 @tab @math{O(@log n)}
 319 @item @code{gl_list_add_at}
 320 @tab @math{O(n)}
 321 @tab @math{O(n)}
 322 @tab @math{O(n)}
 323 @tab @math{O(@log n)}
 324 @tab @math{O(n)}
 325 @tab @math{O(n)}
 326 @tab @math{O((@log n)@mathopsup{2})}
 327 @tab @math{O(@log n)}
 328 @item @code{gl_list_remove_node}
 329 @tab @math{O(n)}
 330 @tab @math{O(n)}
 331 @tab @math{O(1)}
 332 @tab @math{O(@log n)}
 333 @tab @math{O(n)}
 334 @tab @math{O(1)}
 335 @tab @math{O((@log n)@mathopsup{2})}
 336 @tab @math{O(@log n)}
 337 @item @code{gl_list_remove_at}
 338 @tab @math{O(n)}
 339 @tab @math{O(n)}
 340 @tab @math{O(n)}
 341 @tab @math{O(@log n)}
 342 @tab @math{O(n)}
 343 @tab @math{O(n)}
 344 @tab @math{O((@log n)@mathopsup{2})}
 345 @tab @math{O(@log n)}
 346 @item @code{gl_list_remove_first}
 347 @tab @math{O(n)}
 348 @tab @math{O(1)}
 349 @tab @math{O(1)}
 350 @tab @math{O(@log n)}
 351 @tab @math{O(n)}
 352 @tab @math{O(1)}
 353 @tab @math{O((@log n)@mathopsup{2})}
 354 @tab @math{O(@log n)}
 355 @item @code{gl_list_remove_last}
 356 @tab @math{O(1)}
 357 @tab @math{O(1)}
 358 @tab @math{O(1)}
 359 @tab @math{O(@log n)}
 360 @tab @math{O(n)}
 361 @tab @math{O(1)}
 362 @tab @math{O((@log n)@mathopsup{2})}
 363 @tab @math{O(@log n)}
 364 @item @code{gl_list_remove}
 365 @tab @math{O(n)}
 366 @tab @math{O(n)}
 367 @tab @math{O(n)}
 368 @tab @math{O(n)}
 369 @tab @math{O(n)}
 370 @tab @math{O(1)}
 371 @tab @math{O((@log n)@mathopsup{2})}
 372 @tab @math{O(@log n)}
 373 @item @code{gl_list_iterator}
 374 @tab @math{O(1)}
 375 @tab @math{O(1)}
 376 @tab @math{O(1)}
 377 @tab @math{O(@log n)}
 378 @tab @math{O(1)}
 379 @tab @math{O(1)}
 380 @tab @math{O(@log n)}
 381 @tab @math{O(@log n)}
 382 @item @code{gl_list_iterator_from_to}
 383 @tab @math{O(1)}
 384 @tab @math{O(1)}
 385 @tab @math{O(n)}
 386 @tab @math{O(@log n)}
 387 @tab @math{O(n)}
 388 @tab @math{O(n)}
 389 @tab @math{O(@log n)}
 390 @tab @math{O(@log n)}
 391 @item @code{gl_list_iterator_next}
 392 @tab @math{O(1)}
 393 @tab @math{O(1)}
 394 @tab @math{O(1)}
 395 @tab @math{O(@log n)}
 396 @tab @math{O(1)}
 397 @tab @math{O(1)}
 398 @tab @math{O(@log n)}
 399 @tab @math{O(@log n)}
 400 @item @code{gl_sortedlist_search}
 401 @tab @math{O(@log n)}
 402 @tab @math{O(@log n)}
 403 @tab @math{O(n)}
 404 @tab @math{O(@log n)}
 405 @tab @math{O(n)}
 406 @tab @math{O(n)}
 407 @tab @math{O(@log n)}
 408 @tab @math{O(@log n)}
 409 @item @code{gl_sortedlist_search_from}
 410 @tab @math{O(@log n)}
 411 @tab @math{O(@log n)}
 412 @tab @math{O(n)}
 413 @tab @math{O(@log n)}
 414 @tab @math{O(n)}
 415 @tab @math{O(n)}
 416 @tab @math{O(@log n)}
 417 @tab @math{O(@log n)}
 418 @item @code{gl_sortedlist_indexof}
 419 @tab @math{O(@log n)}
 420 @tab @math{O(@log n)}
 421 @tab @math{O(n)}
 422 @tab @math{O(@log n)}
 423 @tab @math{O(n)}
 424 @tab @math{O(n)}
 425 @tab @math{O(@log n)}
 426 @tab @math{O(@log n)}
 427 @item @code{gl_sortedlist_indexof_from}
 428 @tab @math{O(@log n)}
 429 @tab @math{O(@log n)}
 430 @tab @math{O(n)}
 431 @tab @math{O(@log n)}
 432 @tab @math{O(n)}
 433 @tab @math{O(n)}
 434 @tab @math{O(@log n)}
 435 @tab @math{O(@log n)}
 436 @item @code{gl_sortedlist_add}
 437 @tab @math{O(n)}
 438 @tab @math{O(n)}
 439 @tab @math{O(n)}
 440 @tab @math{O(@log n)}
 441 @tab @math{O(n)}
 442 @tab @math{O(n)}
 443 @tab @math{O((@log n)@mathopsup{2})}
 444 @tab @math{O(@log n)}
 445 @item @code{gl_sortedlist_remove}
 446 @tab @math{O(n)}
 447 @tab @math{O(n)}
 448 @tab @math{O(n)}
 449 @tab @math{O(@log n)}
 450 @tab @math{O(n)}
 451 @tab @math{O(n)}
 452 @tab @math{O((@log n)@mathopsup{2})}
 453 @tab @math{O(@log n)}
 454 @end multitable
 455
 456 The implementations and the guaranteed average performance for the operations
 457 for the ``set'' data type are:
 458
 459 @multitable @columnfractions 0.4 0.2 0.4
 460 @headitem Operation
 461 @tab ARRAY
 462 @tab LINKEDHASH, HASH
 463 @item @code{gl_set_size}
 464 @tab @math{O(1)}
 465 @tab @math{O(1)}
 466 @item @code{gl_set_add}
 467 @tab @math{O(n)}
 468 @tab @math{O(1)}
 469 @item @code{gl_set_remove}
 470 @tab @math{O(n)}
 471 @tab @math{O(1)}
 472 @item @code{gl_set_search}
 473 @tab @math{O(n)}
 474 @tab @math{O(1)}
 475 @item @code{gl_set_iterator}
 476 @tab @math{O(1)}
 477 @tab @math{O(1)}
 478 @item @code{gl_set_iterator_next}
 479 @tab @math{O(1)}
 480 @tab @math{O(1)}
 481 @end multitable
 482
 483 The implementations and the guaranteed average performance for the operations
 484 for the ``ordered set'' data type are:
 485
 486 @multitable @columnfractions 0.5 0.25 0.25
 487 @headitem Operation
 488 @tab ARRAY
 489 @tab TREE
 490 @item @code{gl_oset_size}
 491 @tab @math{O(1)}
 492 @tab @math{O(1)}
 493 @item @code{gl_oset_add}
 494 @tab @math{O(n)}
 495 @tab @math{O(@log n)}
 496 @item @code{gl_oset_remove}
 497 @tab @math{O(n)}
 498 @tab @math{O(@log n)}
 499 @item @code{gl_oset_search}
 500 @tab @math{O(@log n)}
 501 @tab @math{O(@log n)}
 502 @item @code{gl_oset_search_atleast}
 503 @tab @math{O(@log n)}
 504 @tab @math{O(@log n)}
 505 @item @code{gl_oset_iterator}
 506 @tab @math{O(1)}
 507 @tab @math{O(@log n)}
 508 @item @code{gl_oset_iterator_next}
 509 @tab @math{O(1)}
 510 @tab @math{O(@log n)}
 511 @end multitable
 512
 513 The implementations and the guaranteed average performance for the operations
 514 for the ``map'' data type are:
 515
 516 @multitable @columnfractions 0.4 0.2 0.4
 517 @headitem Operation
 518 @tab ARRAY
 519 @tab LINKEDHASH, HASH
 520 @item @code{gl_map_size}
 521 @tab @math{O(1)}
 522 @tab @math{O(1)}
 523 @item @code{gl_map_get}
 524 @tab @math{O(n)}
 525 @tab @math{O(1)}
 526 @item @code{gl_map_put}
 527 @tab @math{O(n)}
 528 @tab @math{O(1)}
 529 @item @code{gl_map_remove}
 530 @tab @math{O(n)}
 531 @tab @math{O(1)}
 532 @item @code{gl_map_search}
 533 @tab @math{O(n)}
 534 @tab @math{O(1)}
 535 @item @code{gl_map_iterator}
 536 @tab @math{O(1)}
 537 @tab @math{O(1)}
 538 @item @code{gl_map_iterator_next}
 539 @tab @math{O(1)}
 540 @tab @math{O(1)}
 541 @end multitable
 542
 543 The implementations and the guaranteed average performance for the operations
 544 for the ``ordered map'' data type are:
 545
 546 @multitable @columnfractions 0.5 0.25 0.25
 547 @headitem Operation
 548 @tab ARRAY
 549 @tab TREE
 550 @item @code{gl_omap_size}
 551 @tab @math{O(1)}
 552 @tab @math{O(1)}
 553 @item @code{gl_omap_get}
 554 @tab @math{O(@log n)}
 555 @tab @math{O(@log n)}
 556 @item @code{gl_omap_put}
 557 @tab @math{O(n)}
 558 @tab @math{O(@log n)}
 559 @item @code{gl_omap_remove}
 560 @tab @math{O(n)}
 561 @tab @math{O(@log n)}
 562 @item @code{gl_omap_search}
 563 @tab @math{O(@log n)}
 564 @tab @math{O(@log n)}
 565 @item @code{gl_omap_search_atleast}
 566 @tab @math{O(@log n)}
 567 @tab @math{O(@log n)}
 568 @item @code{gl_omap_iterator}
 569 @tab @math{O(1)}
 570 @tab @math{O(@log n)}
 571 @item @code{gl_omap_iterator_next}
 572 @tab @math{O(1)}
 573 @tab @math{O(@log n)}
 574 @end multitable
 575
 576 For C++, Gnulib provides a C++ template class for each of these container data types.
 577
 578 @multitable @columnfractions .30 .20 .25 .25
 579 @headitem Data type
 580 @tab C++ class
 581 @tab Module
 582 @tab Include file
 583 @item Sequential list
 584 @tab @code{gl_List}
 585 @tab @code{list-c++}
 586 @tab @code{"gl_list.hh"}
 587 @item Set
 588 @tab @code{gl_Set}
 589 @tab @code{set-c++}
 590 @tab @code{"gl_set.hh"}
 591 @item Ordered set
 592 @tab @code{gl_OSet}
 593 @tab @code{oset-c++}
 594 @tab @code{"gl_oset.hh"}
 595 @item Map
 596 @tab @code{gl_Map}
 597 @tab @code{map-c++}
 598 @tab @code{"gl_map.hh"}
 599 @item Ordered map
 600 @tab @code{gl_OMap}
 601 @tab @code{omap-c++}
 602 @tab @code{"gl_omap.hh"}
 603 @end multitable
 604
 605 @node Specialized containers
 606 @subsection Specialized container data types
 607
 608 The @code{hamt} module implements the hash array mapped trie (HAMT) data
 609 structure.  This is a data structure that contains (key, value) pairs.
 610 Lookup of a (key, value) pair given the key is on average an @math{O(1)}
 611 operation, assuming a good hash function for the keys is employed.
 612
 613 The HAMT data structure is useful when you want modifications (additions
 614 of pairs, removal, value changes) to be visible only to some part of
 615 your program, whereas other parts of the program continue to use the
 616 unmodified HAMT.  The HAMT makes this possible in a space-efficient
 617 manner: the modified and the unmodified HAMT share most of their
 618 allocated memory.  It is also time-efficient: Every such modification
 619 is @math{O(1)} on average, again assuming a good hash function for the keys.
 620
 621 A HAMT can be used whenever an ordinary hash table would be used.  It
 622 does however, provide non-destructive updating operations without the
 623 need to copy the whole container. On the other hand, a hash table is
 624 simpler so that its performance may be better when non-destructive
 625 update operations are not needed.
 626
 627 For example, a HAMT can be used to model the dynamic environment in a
 628 LISP interpreter.  Updating a value in the dynamic environment of one
 629 continuation frame would not modify values in earlier frames.
 630
 631 To use the module, include @code{hamt.h} in your code.  The public
 632 interface is documented in that header file.  You have to provide a hash
 633 function and an equivalence relation, which defines key equality.  The
 634 module includes a test file @code{test-hamt.c}, which demonstrates how
 635 the API can be used.
 636
 637 In the current implementation, each inner node of the HAMT can store up
 638 to @math{32 = 2^5} entries and subtries.  Whenever a collision between
 639 the initial bits of the hash values of two entries would happen, the
 640 next @math{5} bits of the hash values are examined and the two entries
 641 pushed down one level in the trie.
 642
 643 HAMTs have the same average access times as hash tables but grow and
 644 shrink dynamically, so they use memory more economically and do not have
 645 to be periodically resized.
 646
 647 They were described and analyzed in @cite{Phil Bagwell (2000). Ideal
 648 Hash Trees (Report). Infoscience Department, École Polytechnique
 649 Fédérale de Lausanne.}
 650
 651 The persistence aspect of the HAMT data structure, which means that each
 652 updating operation (like inserting, replacing, or removing an entry)
 653 returns a new HAMT while leaving the original one intact, is achieved
 654 through structure sharing, which is even safe in the presence of
 655 multiple threads when the used C compiler supports atomics.
 656
 657 @ifnottex
 658 @unmacro log
 659 @end ifnottex
 660 @ifhtml
 661 @unmacro mathopsup
 662 @end ifhtml
 663 @ifinfo
 664 @unmacro mathopsup
 665 @end ifinfo