doc/containers.texi

   1 @node Container data types
   2 @section Container data types
   3
   4 @c Copyright (C) 2019--2025 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 @mindex list
  42 @mindex set
  43 @mindex oset
  44 @mindex map
  45 @mindex omap
  46
  47 @ifinfo
  48 @multitable @columnfractions .15 .45 .09 .15 .16
  49 @end ifinfo
  50 @ifnotinfo
  51 @multitable @columnfractions .15 .5 .1 .1 .15
  52 @end ifnotinfo
  53 @headitem Data type
  54 @tab Details
  55 @tab Module
  56 @tab Main include file
  57 @tab Include file for operations with out-of-memory checking
  58 @item Sequential list
  59 @tab Can contain any number of objects in any given order.
  60      Duplicates are allowed, but can optionally be forbidden.
  61 @tab @code{list}
  62 @tab @code{"gl_list.h"}
  63 @tab @code{"gl_xlist.h"}
  64 @item Set
  65 @tab Can contain any number of objects; the order does not matter.
  66      Duplicates (in the sense of the comparator) are forbidden.
  67 @tab @code{set}
  68 @tab @code{"gl_set.h"}
  69 @tab @code{"gl_xset.h"}
  70 @item Ordered set
  71 @tab Can contain any number of objects in the order of a given comparator
  72      function.
  73      Duplicates (in the sense of the comparator) are forbidden.
  74 @tab @code{oset}
  75 @tab @code{"gl_oset.h"}
  76 @tab @code{"gl_xoset.h"}
  77 @item Map
  78 @tab Can contain any number of (key, value) pairs, where keys and values
  79      are objects;
  80      there are no (key, value1) and (key, value2) pairs with the same key
  81      (in the sense of a given comparator function).
  82 @tab @code{map}
  83 @tab @code{"gl_map.h"}
  84 @tab @code{"gl_xmap.h"}
  85 @item Ordered map
  86 @tab Can contain any number of (key, value) pairs, where keys and values
  87      are objects;
  88      the (key, value) pairs are ordered by the key, in the order of a given
  89      comparator function;
  90      there are no (key, value1) and (key, value2) pairs with the same key
  91      (in the sense of the comparator function).
  92 @tab @code{omap}
  93 @tab @code{"gl_omap.h"}
  94 @tab @code{"gl_xomap.h"}
  95 @end multitable
  96
  97 Operations without out-of-memory checking (suitable for use in libraries) are
  98 declared in the ``main include file''.  Whereas operations with out-of-memory
  99 checking (suitable only in programs) are declared in the ``include file for
 100 operations with out-of-memory checking''.
 101
 102 For each of the data types, several implementations are available, with
 103 different performance profiles with respect to the available operations.
 104 This enables you to start with the simplest implementation (ARRAY) initially,
 105 and switch to a more suitable implementation after profiling your application.
 106 The implementation of each container instance is specified in a single place
 107 only: in the invocation of the function @code{gl_*_create_empty} that creates
 108 the instance.
 109
 110 @subsubsection Sequential lists
 111
 112 The implementations and the guaranteed average performance for the operations
 113 for the ``sequential list'' data type are:
 114
 115 @ifinfo
 116 @noindent
 117 Note: This table is overloaded in the @command{info}-formatted documentation.
 118 It is better viewable in the HTML-formatted documentation.
 119 @end ifinfo
 120
 121 @multitable @columnfractions 0.2 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
 122 @headitem Operation
 123 @tab ARRAY
 124 @tab CARRAY
 125 @tab LINKED
 126 @tab TREE
 127 @tab LINKEDHASH with duplicates
 128 @tab LINKEDHASH without duplicates
 129 @tab TREEHASH with duplicates
 130 @tab TREEHASH without duplicates
 131 @item @code{gl_list_size}
 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(1)}
 138 @tab @math{O(1)}
 139 @tab @math{O(1)}
 140 @item @code{gl_list_node_value}
 141 @tab @math{O(1)}
 142 @tab @math{O(1)}
 143 @tab @math{O(1)}
 144 @tab @math{O(1)}
 145 @tab @math{O(1)}
 146 @tab @math{O(1)}
 147 @tab @math{O(1)}
 148 @tab @math{O(1)}
 149 @item @code{gl_list_node_set_value}
 150 @tab @math{O(1)}
 151 @tab @math{O(1)}
 152 @tab @math{O(1)}
 153 @tab @math{O(1)}
 154 @tab @math{O(1)}
 155 @tab @math{O(1)}
 156 @tab @math{O((@log n)@mathopsup{2})}
 157 @tab @math{O(1)}
 158 @item @code{gl_list_next_node}
 159 @tab @math{O(1)}
 160 @tab @math{O(1)}
 161 @tab @math{O(1)}
 162 @tab @math{O(@log n)}
 163 @tab @math{O(1)}
 164 @tab @math{O(1)}
 165 @tab @math{O(@log n)}
 166 @tab @math{O(@log n)}
 167 @item @code{gl_list_previous_node}
 168 @tab @math{O(1)}
 169 @tab @math{O(1)}
 170 @tab @math{O(1)}
 171 @tab @math{O(@log n)}
 172 @tab @math{O(1)}
 173 @tab @math{O(1)}
 174 @tab @math{O(@log n)}
 175 @tab @math{O(@log n)}
 176 @item @code{gl_list_first_node}
 177 @tab @math{O(1)}
 178 @tab @math{O(1)}
 179 @tab @math{O(1)}
 180 @tab @math{O(@log n)}
 181 @tab @math{O(1)}
 182 @tab @math{O(1)}
 183 @tab @math{O(@log n)}
 184 @tab @math{O(@log n)}
 185 @item @code{gl_list_last_node}
 186 @tab @math{O(1)}
 187 @tab @math{O(1)}
 188 @tab @math{O(1)}
 189 @tab @math{O(@log n)}
 190 @tab @math{O(1)}
 191 @tab @math{O(1)}
 192 @tab @math{O(@log n)}
 193 @tab @math{O(@log n)}
 194 @item @code{gl_list_get_at}
 195 @tab @math{O(1)}
 196 @tab @math{O(1)}
 197 @tab @math{O(n)}
 198 @tab @math{O(@log n)}
 199 @tab @math{O(n)}
 200 @tab @math{O(n)}
 201 @tab @math{O(@log n)}
 202 @tab @math{O(@log n)}
 203 @item @code{gl_list_get_first}
 204 @tab @math{O(1)}
 205 @tab @math{O(1)}
 206 @tab @math{O(1)}
 207 @tab @math{O(@log n)}
 208 @tab @math{O(1)}
 209 @tab @math{O(1)}
 210 @tab @math{O(@log n)}
 211 @tab @math{O(@log n)}
 212 @item @code{gl_list_get_last}
 213 @tab @math{O(1)}
 214 @tab @math{O(1)}
 215 @tab @math{O(1)}
 216 @tab @math{O(@log n)}
 217 @tab @math{O(1)}
 218 @tab @math{O(1)}
 219 @tab @math{O(@log n)}
 220 @tab @math{O(@log n)}
 221 @item @code{gl_list_set_at}
 222 @tab @math{O(1)}
 223 @tab @math{O(1)}
 224 @tab @math{O(n)}
 225 @tab @math{O(@log n)}
 226 @tab @math{O(n)}
 227 @tab @math{O(n)}
 228 @tab @math{O((@log n)@mathopsup{2})}
 229 @tab @math{O(@log n)}
 230 @item @code{gl_list_set_first}
 231 @tab @math{O(1)}
 232 @tab @math{O(1)}
 233 @tab @math{O(1)}
 234 @tab @math{O(@log n)}
 235 @tab @math{O(n)}
 236 @tab @math{O(1)}
 237 @tab @math{O((@log n)@mathopsup{2})}
 238 @tab @math{O(@log n)}
 239 @item @code{gl_list_set_last}
 240 @tab @math{O(1)}
 241 @tab @math{O(1)}
 242 @tab @math{O(1)}
 243 @tab @math{O(@log n)}
 244 @tab @math{O(n)}
 245 @tab @math{O(1)}
 246 @tab @math{O((@log n)@mathopsup{2})}
 247 @tab @math{O(@log n)}
 248 @item @code{gl_list_search}
 249 @tab @math{O(n)}
 250 @tab @math{O(n)}
 251 @tab @math{O(n)}
 252 @tab @math{O(n)}
 253 @tab @math{O(n)}
 254 @tab @math{O(1)}
 255 @tab @math{O(@log n)}
 256 @tab @math{O(1)}
 257 @item @code{gl_list_search_from}
 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(1)}
 264 @tab @math{O((@log n)@mathopsup{2})}
 265 @tab @math{O(@log n)}
 266 @item @code{gl_list_search_from_to}
 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(1)}
 273 @tab @math{O((@log n)@mathopsup{2})}
 274 @tab @math{O(@log n)}
 275 @item @code{gl_list_indexof}
 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(n)}
 282 @tab @math{O(@log n)}
 283 @tab @math{O(@log n)}
 284 @item @code{gl_list_indexof_from}
 285 @tab @math{O(n)}
 286 @tab @math{O(n)}
 287 @tab @math{O(n)}
 288 @tab @math{O(n)}
 289 @tab @math{O(n)}
 290 @tab @math{O(n)}
 291 @tab @math{O((@log n)@mathopsup{2})}
 292 @tab @math{O(@log n)}
 293 @item @code{gl_list_indexof_from_to}
 294 @tab @math{O(n)}
 295 @tab @math{O(n)}
 296 @tab @math{O(n)}
 297 @tab @math{O(n)}
 298 @tab @math{O(n)}
 299 @tab @math{O(n)}
 300 @tab @math{O((@log n)@mathopsup{2})}
 301 @tab @math{O(@log n)}
 302 @item @code{gl_list_add_first}
 303 @tab @math{O(n)}
 304 @tab @math{O(1)}
 305 @tab @math{O(1)}
 306 @tab @math{O(@log n)}
 307 @tab @math{O(1)}
 308 @tab @math{O(1)}
 309 @tab @math{O((@log n)@mathopsup{2})}
 310 @tab @math{O(@log n)}
 311 @item @code{gl_list_add_last}
 312 @tab @math{O(1)}
 313 @tab @math{O(1)}
 314 @tab @math{O(1)}
 315 @tab @math{O(@log n)}
 316 @tab @math{O(1)}
 317 @tab @math{O(1)}
 318 @tab @math{O((@log n)@mathopsup{2})}
 319 @tab @math{O(@log n)}
 320 @item @code{gl_list_add_before}
 321 @tab @math{O(n)}
 322 @tab @math{O(n)}
 323 @tab @math{O(1)}
 324 @tab @math{O(@log n)}
 325 @tab @math{O(1)}
 326 @tab @math{O(1)}
 327 @tab @math{O((@log n)@mathopsup{2})}
 328 @tab @math{O(@log n)}
 329 @item @code{gl_list_add_after}
 330 @tab @math{O(n)}
 331 @tab @math{O(n)}
 332 @tab @math{O(1)}
 333 @tab @math{O(@log n)}
 334 @tab @math{O(1)}
 335 @tab @math{O(1)}
 336 @tab @math{O((@log n)@mathopsup{2})}
 337 @tab @math{O(@log n)}
 338 @item @code{gl_list_add_at}
 339 @tab @math{O(n)}
 340 @tab @math{O(n)}
 341 @tab @math{O(n)}
 342 @tab @math{O(@log n)}
 343 @tab @math{O(n)}
 344 @tab @math{O(n)}
 345 @tab @math{O((@log n)@mathopsup{2})}
 346 @tab @math{O(@log n)}
 347 @item @code{gl_list_remove_node}
 348 @tab @math{O(n)}
 349 @tab @math{O(n)}
 350 @tab @math{O(1)}
 351 @tab @math{O(@log n)}
 352 @tab @math{O(n)}
 353 @tab @math{O(1)}
 354 @tab @math{O((@log n)@mathopsup{2})}
 355 @tab @math{O(@log n)}
 356 @item @code{gl_list_remove_at}
 357 @tab @math{O(n)}
 358 @tab @math{O(n)}
 359 @tab @math{O(n)}
 360 @tab @math{O(@log n)}
 361 @tab @math{O(n)}
 362 @tab @math{O(n)}
 363 @tab @math{O((@log n)@mathopsup{2})}
 364 @tab @math{O(@log n)}
 365 @item @code{gl_list_remove_first}
 366 @tab @math{O(n)}
 367 @tab @math{O(1)}
 368 @tab @math{O(1)}
 369 @tab @math{O(@log n)}
 370 @tab @math{O(n)}
 371 @tab @math{O(1)}
 372 @tab @math{O((@log n)@mathopsup{2})}
 373 @tab @math{O(@log n)}
 374 @item @code{gl_list_remove_last}
 375 @tab @math{O(1)}
 376 @tab @math{O(1)}
 377 @tab @math{O(1)}
 378 @tab @math{O(@log n)}
 379 @tab @math{O(n)}
 380 @tab @math{O(1)}
 381 @tab @math{O((@log n)@mathopsup{2})}
 382 @tab @math{O(@log n)}
 383 @item @code{gl_list_remove}
 384 @tab @math{O(n)}
 385 @tab @math{O(n)}
 386 @tab @math{O(n)}
 387 @tab @math{O(n)}
 388 @tab @math{O(n)}
 389 @tab @math{O(1)}
 390 @tab @math{O((@log n)@mathopsup{2})}
 391 @tab @math{O(@log n)}
 392 @item @code{gl_list_iterator}
 393 @tab @math{O(1)}
 394 @tab @math{O(1)}
 395 @tab @math{O(1)}
 396 @tab @math{O(@log n)}
 397 @tab @math{O(1)}
 398 @tab @math{O(1)}
 399 @tab @math{O(@log n)}
 400 @tab @math{O(@log n)}
 401 @item @code{gl_list_iterator_from_to}
 402 @tab @math{O(1)}
 403 @tab @math{O(1)}
 404 @tab @math{O(n)}
 405 @tab @math{O(@log n)}
 406 @tab @math{O(n)}
 407 @tab @math{O(n)}
 408 @tab @math{O(@log n)}
 409 @tab @math{O(@log n)}
 410 @item @code{gl_list_iterator_next}
 411 @tab @math{O(1)}
 412 @tab @math{O(1)}
 413 @tab @math{O(1)}
 414 @tab @math{O(@log n)}
 415 @tab @math{O(1)}
 416 @tab @math{O(1)}
 417 @tab @math{O(@log n)}
 418 @tab @math{O(@log n)}
 419 @item @code{gl_sortedlist_search}
 420 @tab @math{O(@log n)}
 421 @tab @math{O(@log n)}
 422 @tab @math{O(n)}
 423 @tab @math{O(@log n)}
 424 @tab @math{O(n)}
 425 @tab @math{O(n)}
 426 @tab @math{O(@log n)}
 427 @tab @math{O(@log n)}
 428 @item @code{gl_sortedlist_search_from}
 429 @tab @math{O(@log n)}
 430 @tab @math{O(@log n)}
 431 @tab @math{O(n)}
 432 @tab @math{O(@log n)}
 433 @tab @math{O(n)}
 434 @tab @math{O(n)}
 435 @tab @math{O(@log n)}
 436 @tab @math{O(@log n)}
 437 @item @code{gl_sortedlist_indexof}
 438 @tab @math{O(@log n)}
 439 @tab @math{O(@log n)}
 440 @tab @math{O(n)}
 441 @tab @math{O(@log n)}
 442 @tab @math{O(n)}
 443 @tab @math{O(n)}
 444 @tab @math{O(@log n)}
 445 @tab @math{O(@log n)}
 446 @item @code{gl_sortedlist_indexof_from}
 447 @tab @math{O(@log n)}
 448 @tab @math{O(@log n)}
 449 @tab @math{O(n)}
 450 @tab @math{O(@log n)}
 451 @tab @math{O(n)}
 452 @tab @math{O(n)}
 453 @tab @math{O(@log n)}
 454 @tab @math{O(@log n)}
 455 @item @code{gl_sortedlist_add}
 456 @tab @math{O(n)}
 457 @tab @math{O(n)}
 458 @tab @math{O(n)}
 459 @tab @math{O(@log n)}
 460 @tab @math{O(n)}
 461 @tab @math{O(n)}
 462 @tab @math{O((@log n)@mathopsup{2})}
 463 @tab @math{O(@log n)}
 464 @item @code{gl_sortedlist_remove}
 465 @tab @math{O(n)}
 466 @tab @math{O(n)}
 467 @tab @math{O(n)}
 468 @tab @math{O(@log n)}
 469 @tab @math{O(n)}
 470 @tab @math{O(n)}
 471 @tab @math{O((@log n)@mathopsup{2})}
 472 @tab @math{O(@log n)}
 473 @end multitable
 474
 475 The Gnulib modules for sequential lists are:
 476
 477 @mindex list
 478 @mindex xlist
 479 @mindex array-list
 480 @mindex carray-list
 481 @mindex linked-list
 482 @mindex avltree-list
 483 @mindex rbtree-list
 484 @mindex linkedhash-list
 485 @mindex avltreehash-list
 486 @mindex rbtreehash-list
 487 @mindex sublist
 488 @mindex xsublist
 489 @multitable @columnfractions 0.3 0.7
 490 @headitem Implementation @tab Modules
 491 @item Abstract @tab @code{list}, @code{xlist}
 492 @item ARRAY @tab @code{array-list}
 493 @item CARRAY @tab @code{carray-list}
 494 @item LINKED @tab @code{linked-list}
 495 @item TREE @tab @code{avltree-list}, @code{rbtree-list}
 496 @item LINKEDHASH @tab @code{linkedhash-list}
 497 @item TREEHASH @tab @code{avltreehash-list}, @code{rbtreehash-list}
 498 @item Portion of a list @tab @code{sublist}, @code{xsublist}
 499 @end multitable
 500
 501 @subsubsection Sets
 502
 503 The implementations and the guaranteed average performance for the operations
 504 for the ``set'' data type are:
 505
 506 @multitable @columnfractions 0.4 0.2 0.4
 507 @headitem Operation
 508 @tab ARRAY
 509 @tab LINKEDHASH, HASH
 510 @item @code{gl_set_size}
 511 @tab @math{O(1)}
 512 @tab @math{O(1)}
 513 @item @code{gl_set_add}
 514 @tab @math{O(n)}
 515 @tab @math{O(1)}
 516 @item @code{gl_set_remove}
 517 @tab @math{O(n)}
 518 @tab @math{O(1)}
 519 @item @code{gl_set_search}
 520 @tab @math{O(n)}
 521 @tab @math{O(1)}
 522 @item @code{gl_set_iterator}
 523 @tab @math{O(1)}
 524 @tab @math{O(1)}
 525 @item @code{gl_set_iterator_next}
 526 @tab @math{O(1)}
 527 @tab @math{O(1)}
 528 @end multitable
 529
 530 The Gnulib modules for sets are:
 531
 532 @mindex set
 533 @mindex xset
 534 @mindex array-set
 535 @mindex linkedhash-set
 536 @mindex hash-set
 537 @multitable @columnfractions 0.3 0.7
 538 @headitem Implementation @tab Modules
 539 @item Abstract @tab @code{set}, @code{xset}
 540 @item ARRAY @tab @code{array-set}
 541 @item LINKEDHASH @tab @code{linkedhash-set}
 542 @item HASH @tab @code{hash-set}
 543 @end multitable
 544
 545 @subsubsection Ordered sets
 546
 547 The implementations and the guaranteed average performance for the operations
 548 for the ``ordered set'' data type are:
 549
 550 @multitable @columnfractions 0.5 0.25 0.25
 551 @headitem Operation
 552 @tab ARRAY
 553 @tab TREE
 554 @item @code{gl_oset_size}
 555 @tab @math{O(1)}
 556 @tab @math{O(1)}
 557 @item @code{gl_oset_add}
 558 @tab @math{O(n)}
 559 @tab @math{O(@log n)}
 560 @item @code{gl_oset_remove}
 561 @tab @math{O(n)}
 562 @tab @math{O(@log n)}
 563 @item @code{gl_oset_search}
 564 @tab @math{O(@log n)}
 565 @tab @math{O(@log n)}
 566 @item @code{gl_oset_search_atleast}
 567 @tab @math{O(@log n)}
 568 @tab @math{O(@log n)}
 569 @item @code{gl_oset_iterator}
 570 @tab @math{O(1)}
 571 @tab @math{O(@log n)}
 572 @item @code{gl_oset_iterator_next}
 573 @tab @math{O(1)}
 574 @tab @math{O(@log n)}
 575 @end multitable
 576
 577 The Gnulib modules for ordered sets are:
 578
 579 @mindex oset
 580 @mindex xoset
 581 @mindex array-oset
 582 @mindex avltree-oset
 583 @mindex rbtree-oset
 584 @multitable @columnfractions 0.3 0.7
 585 @headitem Implementation @tab Modules
 586 @item Abstract @tab @code{oset}, @code{xoset}
 587 @item ARRAY @tab @code{array-oset}
 588 @item TREE @tab @code{avltree-oset}, @code{rbtree-oset}
 589 @end multitable
 590
 591 @subsubsection Maps
 592
 593 The implementations and the guaranteed average performance for the operations
 594 for the ``map'' data type are:
 595
 596 @multitable @columnfractions 0.4 0.2 0.4
 597 @headitem Operation
 598 @tab ARRAY
 599 @tab LINKEDHASH, HASH
 600 @item @code{gl_map_size}
 601 @tab @math{O(1)}
 602 @tab @math{O(1)}
 603 @item @code{gl_map_get}
 604 @tab @math{O(n)}
 605 @tab @math{O(1)}
 606 @item @code{gl_map_put}
 607 @tab @math{O(n)}
 608 @tab @math{O(1)}
 609 @item @code{gl_map_remove}
 610 @tab @math{O(n)}
 611 @tab @math{O(1)}
 612 @item @code{gl_map_search}
 613 @tab @math{O(n)}
 614 @tab @math{O(1)}
 615 @item @code{gl_map_iterator}
 616 @tab @math{O(1)}
 617 @tab @math{O(1)}
 618 @item @code{gl_map_iterator_next}
 619 @tab @math{O(1)}
 620 @tab @math{O(1)}
 621 @end multitable
 622
 623 The Gnulib modules for maps are:
 624
 625 @mindex map
 626 @mindex xmap
 627 @mindex array-map
 628 @mindex linkedhash-map
 629 @mindex hash-map
 630 @multitable @columnfractions 0.3 0.7
 631 @headitem Implementation @tab Modules
 632 @item Abstract @tab @code{map}, @code{xmap}
 633 @item ARRAY @tab @code{array-map}
 634 @item LINKEDHASH @tab @code{linkedhash-map}
 635 @item HASH @tab @code{hash-map}
 636 @end multitable
 637
 638 @subsubsection Ordered maps
 639
 640 The implementations and the guaranteed average performance for the operations
 641 for the ``ordered map'' data type are:
 642
 643 @multitable @columnfractions 0.5 0.25 0.25
 644 @headitem Operation
 645 @tab ARRAY
 646 @tab TREE
 647 @item @code{gl_omap_size}
 648 @tab @math{O(1)}
 649 @tab @math{O(1)}
 650 @item @code{gl_omap_get}
 651 @tab @math{O(@log n)}
 652 @tab @math{O(@log n)}
 653 @item @code{gl_omap_put}
 654 @tab @math{O(n)}
 655 @tab @math{O(@log n)}
 656 @item @code{gl_omap_remove}
 657 @tab @math{O(n)}
 658 @tab @math{O(@log n)}
 659 @item @code{gl_omap_search}
 660 @tab @math{O(@log n)}
 661 @tab @math{O(@log n)}
 662 @item @code{gl_omap_search_atleast}
 663 @tab @math{O(@log n)}
 664 @tab @math{O(@log n)}
 665 @item @code{gl_omap_iterator}
 666 @tab @math{O(1)}
 667 @tab @math{O(@log n)}
 668 @item @code{gl_omap_iterator_next}
 669 @tab @math{O(1)}
 670 @tab @math{O(@log n)}
 671 @end multitable
 672
 673 The Gnulib modules for ordered maps are:
 674
 675 @mindex omap
 676 @mindex xomap
 677 @mindex array-omap
 678 @mindex avltree-omap
 679 @mindex rbtree-omap
 680 @multitable @columnfractions 0.3 0.7
 681 @headitem Implementation @tab Modules
 682 @item Abstract @tab @code{omap}, @code{xomap}
 683 @item ARRAY @tab @code{array-omap}
 684 @item TREE @tab @code{avltree-omap}, @code{rbtree-omap}
 685 @end multitable
 686
 687 @subsubsection C++ classes for container data types
 688
 689 For C++, Gnulib provides a C++ template class for each of these container data types.
 690
 691 @mindex list-c++
 692 @mindex set-c++
 693 @mindex oset-c++
 694 @mindex map-c++
 695 @mindex omap-c++
 696 @multitable @columnfractions .30 .20 .25 .25
 697 @headitem Data type
 698 @tab C++ class
 699 @tab Module
 700 @tab Include file
 701 @item Sequential list
 702 @tab @code{gl_List}
 703 @tab @code{list-c++}
 704 @tab @code{"gl_list.hh"}
 705 @item Set
 706 @tab @code{gl_Set}
 707 @tab @code{set-c++}
 708 @tab @code{"gl_set.hh"}
 709 @item Ordered set
 710 @tab @code{gl_OSet}
 711 @tab @code{oset-c++}
 712 @tab @code{"gl_oset.hh"}
 713 @item Map
 714 @tab @code{gl_Map}
 715 @tab @code{map-c++}
 716 @tab @code{"gl_map.hh"}
 717 @item Ordered map
 718 @tab @code{gl_OMap}
 719 @tab @code{omap-c++}
 720 @tab @code{"gl_omap.hh"}
 721 @end multitable
 722
 723 @node Specialized containers
 724 @subsection Specialized container data types
 725
 726 @mindex hamt
 727 The @code{hamt} module implements the hash array mapped trie (HAMT) data
 728 structure.  This is a data structure that contains (key, value) pairs.
 729 Lookup of a (key, value) pair given the key is on average an @math{O(1)}
 730 operation, assuming a good hash function for the keys is employed.
 731
 732 The HAMT data structure is useful when you want modifications (additions
 733 of pairs, removal, value changes) to be visible only to some part of
 734 your program, whereas other parts of the program continue to use the
 735 unmodified HAMT.  The HAMT makes this possible in a space-efficient
 736 manner: the modified and the unmodified HAMT share most of their
 737 allocated memory.  It is also time-efficient: Every such modification
 738 is @math{O(1)} on average, again assuming a good hash function for the keys.
 739
 740 A HAMT can be used whenever an ordinary hash table would be used.  It
 741 does however, provide non-destructive updating operations without the
 742 need to copy the whole container. On the other hand, a hash table is
 743 simpler so that its performance may be better when non-destructive
 744 update operations are not needed.
 745
 746 For example, a HAMT can be used to model the dynamic environment in a
 747 LISP interpreter.  Updating a value in the dynamic environment of one
 748 continuation frame would not modify values in earlier frames.
 749
 750 To use the module, include @code{hamt.h} in your code.  The public
 751 interface is documented in that header file.  You have to provide a hash
 752 function and an equivalence relation, which defines key equality.  The
 753 module includes a test file @code{test-hamt.c}, which demonstrates how
 754 the API can be used.
 755
 756 In the current implementation, each inner node of the HAMT can store up
 757 to @math{32 = 2^5} entries and subtries.  Whenever a collision between
 758 the initial bits of the hash values of two entries would happen, the
 759 next @math{5} bits of the hash values are examined and the two entries
 760 pushed down one level in the trie.
 761
 762 HAMTs have the same average access times as hash tables but grow and
 763 shrink dynamically, so they use memory more economically and do not have
 764 to be periodically resized.
 765
 766 They were described and analyzed in @cite{Phil Bagwell (2000). Ideal
 767 Hash Trees (Report). Infoscience Department, École Polytechnique
 768 Fédérale de Lausanne.}
 769
 770 The persistence aspect of the HAMT data structure, which means that each
 771 updating operation (like inserting, replacing, or removing an entry)
 772 returns a new HAMT while leaving the original one intact, is achieved
 773 through structure sharing, which is even safe in the presence of
 774 multiple threads when the used C compiler supports atomics.
 775
 776 @ifnottex
 777 @unmacro log
 778 @end ifnottex
 779 @ifhtml
 780 @unmacro mathopsup
 781 @end ifhtml
 782 @ifinfo
 783 @unmacro mathopsup
 784 @end ifinfo