Sitemap

 

   1  #REM /* -*- Mode: C++ -*-
   2  #REM  * Author: Henrik Theiling
   3  #REM  *
   4  #REM  * @@Begin: Licencing and Copying@@
   5  #REM  * 
   6  #REM  * Copyright (c) Henrik Theiling
   7  #REM  * Licence Version 2, Special Version for Erwin.
   8  #REM  * 
   9  #REM  * The term 'this software' used in the following, additional to its
  10  #REM  * usual usage, also includes the instantiated source files generated by
  11  #REM  * tools of this package.
  12  #REM  * 
  13  #REM  * This software is provided 'as-is', without warranty of any kind,
  14  #REM  * express or implied.  In no event will the authors or copyright holders
  15  #REM  * be held liable for any damages arising from the use of this software.
  16  #REM  * 
  17  #REM  * Permission is granted to anyone to use this software for any purpose,
  18  #REM  * including commercial applications, and to alter it and redistribute it
  19  #REM  * freely, subject to the following restrictions:
  20  #REM  * 
  21  #REM  * 1. The origin of this software must not be misrepresented; you must
  22  #REM  * not claim that you wrote the original software. If you use this
  23  #REM  * software in a product, an acknowledgment in the product documentation
  24  #REM  * would be appreciated.
  25  #REM  *
  26  #REM  * 2. Altered source versions must be plainly marked as such, and must
  27  #REM  * not be misrepresented as being the original software.
  28  #REM  *
  29  #REM  * 3. You must not use any of the names of the authors or copyright
  30  #REM  * holders of the original software for advertising or publicity
  31  #REM  * pertaining to distribution without specific, written prior permission.
  32  #REM  *
  33  #REM  * 4. If you change this software and redistribute parts or all of it in
  34  #REM  * any form, you must make the source code of the altered version of this
  35  #REM  * software available.  As an exception, files that were generated by
  36  #REM  * tools of this package may be used freely, including modification.
  37  #REM  *
  38  #REM  * 5. This notice must not be removed or altered from any source
  39  #REM  * distribution.
  40  #REM  *
  41  #REM  * This licence is governed by the Laws of Germany.  Disputes shall be
  42  #REM  * settled by Saarbruecken City Court.
  43  #REM  *
  44  #REM  * @@End: Licencing and Copying@@
  45  #REM  *
  46  #REM  * TODO:
  47  #REM  *   - Re-structure the constructors to not automatically copy an
  48  #REM  *     map_t *!  (Have a look at operator = then).
  49  #REM  *
  50  #REM  *   - Fix TOOSMALL and TOOLARGE macros to handle large element counts.
  51  #REM  *
  52  #REM  */
  53  #PARAMETER(iType)
  54  #DESCRIPTION(Type of the keys. For pointers, you usual must declare Global_iType_ICOPY and Global_iType_IFREE)
  55  #PARAMETER(oType)
  56  #DESCRIPTION(Type of the values)
  57  #CHECK
  58  #REM
  59  #REM /* Contruct help types (params and results) */
  60  #REPLACE_PERHAPS_START(iT###ypeVar,iType)
  61  #REPLACE_PERHAPS_START(oT###ypeVar,oType)
  62  #REPLACE_PERHAPS_START(iT###ypeSuffix,)
  63  #REPLACE_PERHAPS_START(oT###ypeSuffix,)
  64  #REM
  65  #REM /* Function Parameters */
  66  #REPLACE_PERHAPS_START(iT###ypeParamSuffix,iTypeSuffix)
  67  #REPLACE_PERHAPS_START(oT###ypeParamSuffix,oTypeSuffix)
  68  #REPLACE_PERHAPS_START(iT###ypeParam,iType iTypeParamSuffix)
  69  #REPLACE_PERHAPS_START(oT###ypeParam,oType oTypeParamSuffix)
  70  #REPLACE_PERHAPS_START(iT###ypeVarParam,iTypeVar iTypeParamSuffix)
  71  #REPLACE_PERHAPS_START(oT###ypeVarParam,oTypeVar oTypeParamSuffix)
  72  #REPLACE_PERHAPS_START(iT###ypeTouched,iTypeParam)
  73  #REPLACE_PERHAPS_START(oT###ypeTouched,oTypeParam)
  74  #REM
  75  #REM /* Function results */
  76  #REPLACE_PERHAPS_START(iT###ypeResultSuffix,iTypeSuffix)
  77  #REPLACE_PERHAPS_START(oT###ypeResultSuffix,oTypeSuffix)
  78  #REPLACE_PERHAPS_START(iT###ypeResult,iType iTypeResultSuffix)
  79  #IF(oType == void)
  80  #REPLACE_PERHAPS_START(oT###ypeResult,Global_ERWIN_BOOL)
  81  #ELSE
  82  #REPLACE_PERHAPS_START(oT###ypeResult,oType oTypeResultSuffix)
  83  #ENDIF
  84  #REPLACE_PERHAPS_START(oT###ypeIndex,oTypeResult)
  85  #REM
  86  #REM /* Continue with normal business */
  87  #REPLACE(Map,Global_map_iType_oType)
  88  #REPLACE(NSMap,nsmap_iType_oType)
  89  #REPLACE(List,Map_hashlist)
  90  #FILES(map.cd map_i.hd map_u.hd)
  91  #GENERAL(Global_map_u.ErwinHExt Map_u.ErwinHExt)
  92  #HEADER(Map.ErwinHExt Map_i.ErwinHExt Map_d.ErwinHExt Map_f.ErwinHExt Map_ti.ErwinHExt Map_n.ErwinHExt)
  93  #CLASS_IDENTIFIER(Map_class)
  94  #CLASS_IDENTIFIER(NSMap_class)
  95  #SPLIT_TARGET(Map)
  96  #REM *****************************************************************************************
  97  #OUTPUT(Map_f.ErwinHExt)
  98  
  99  #ifndef ERWIN_Map_f_ErwinHExt
 100  #define ERWIN_Map_f_ErwinHExt
 101  
 102  struct Map_t;
 103  #TYPEDEF_GLOBAL(aggregate Map_t NSMap_t)
 104  #ifndef __cplusplus
 105  typedef struct Map_t Map_t;
 106  #endif
 107  typedef struct Map_t Map_class;
 108  #TYPEDEF_GLOBAL(aggregate Map_class NSMap_class)
 109  
 110  typedef Map_t *Map_t_p;
 111  #TYPEDEF_GLOBAL(Map_t_p NSMap_t_p)
 112  
 113  typedef Map_t const *Map_t_const_p;
 114  #TYPEDEF_GLOBAL(Map_t_const_p NSMap_t_const_p)
 115  
 116  #define Map_SIG __gen_sig__
 117  
 118  ErwinGlobalDefines
 119  
 120  #REM #DEEPDECLS(Map,HASH_RAW,CMP,ZERO,EQUAL,HAS_CONSTANT_ZERO,ICOPY,OCOPY,IFREE,OFREE,CONSTRUCTOR,DESTRUCTOR)
 121  #DEEPDECLS(Map,HASH_RAW,CMP,ZERO,EQUAL,ICOPY,OCOPY,IFREE,OFREE,CONSTRUCTOR,DESTRUCTOR)
 122  
 123  #endif /* defined ERWIN_Map_f_ErwinHExt */
 124  
 125  #REM *****************************************************************************************
 126  #OUTPUT(Map_n.ErwinHExt)
 127  
 128  #CHECKINCLUDE(Map)
 129  
 130  #ifdef Map_NEED_HEADER
 131  #include "#Map.ErwinHExt"
 132  #endif
 133  
 134  #REM *****************************************************************************************
 135  #OUTPUT(Map_ti.ErwinHExt)
 136  
 137  #ifndef ERWIN_Map_ti_ErwinHExt
 138  #define ERWIN_Map_ti_ErwinHExt
 139  
 140  #define List_t_KIND STRUCT
 141  #define List_t_TYPE_INFO  TYPE_INFO_NAME(List_t)
 142  extern  TYPE_INFO_T(List_t);
 143  
 144  #define List_t_p_KIND  POINTER
 145  #define List_t_p_TYPE_INFO  TYPE_INFO_NAME(List_t_p)
 146  extern  TYPE_INFO_T(List_t_p);
 147  
 148  #define List_t_const_p_KIND POINTER
 149  #define List_t_const_p_TYPE_INFO  TYPE_INFO_NAME(List_t_const_p)
 150  extern  TYPE_INFO_T(List_t_const_p);
 151  
 152  #define Map_internal_Iterator_KIND STRUCT
 153  #define Map_internal_Iterator_TYPE_INFO  TYPE_INFO_NAME(Map_internal_Iterator)
 154  extern  TYPE_INFO_T(Map_internal_Iterator);
 155  
 156  #define Map_t_KIND STRUCT
 157  #define Map_t_TYPE_INFO  TYPE_INFO_NAME(Map_t)
 158  extern  TYPE_INFO_T(Map_t);
 159  
 160  #define Map_t_p_KIND POINTER
 161  #define Map_t_p_TYPE_INFO  TYPE_INFO_NAME(Map_t_p)
 162  extern  TYPE_INFO_T(Map_t_p);
 163  
 164  #define Map_t_const_p_KIND POINTER
 165  #define Map_t_const_p_TYPE_INFO  TYPE_INFO_NAME(Map_t_const_p)
 166  extern  TYPE_INFO_T(Map_t_const_p);
 167  
 168  #define Map_content_KIND VECTOR
 169  #define Map_content_TYPE_INFO  TYPE_INFO_NAME(Map_content)
 170  extern  TYPE_INFO_T(Map_content);
 171  
 172  #define Map_content_p_KIND POINTER
 173  #define Map_content_p_TYPE_INFO  TYPE_INFO_NAME(Map_content_p)
 174  extern  TYPE_INFO_T(Map_content_p);
 175  
 176  #define Map_class###_TYPE_INFO          Map_t_TYPE_INFO
 177  #define Map_class_p###_TYPE_INFO        Map_t_p_TYPE_INFO
 178  #define Map_class_const_p###_TYPE_INFO  Map_t_const_p_TYPE_INFO
 179  
 180  #endif /* defined ERWIN_Map_ti_ErwinHExt */
 181  
 182  #REM *****************************************************************************************
 183  #OUTPUT(Map.ErwinHExt)
 184  /* -*- Mode: C -*- */
 185  #DATE
 186  /*
 187   * Author: Henrik Theiling
 188   * Description:
 189   *     Public header file for maps with arbitrary key and value types.
 190   *     The implementation uses dynamic hashing with lists as conflict
 191   *     resolving mechanism.
 192   *
 193   */
 194  #LICENCE
 195  
 196  #ifdef ERWIN_DEBUG_INCLUDE
 197  #warning "Including Map.h"
 198  #endif
 199  
 200  #ifndef ERWIN_Map_ErwinHExt
 201  #define ERWIN_Map_ErwinHExt
 202  
 203  #ifdef ERWIN_DEBUG_INCLUDE
 204  #warning "First inclusion of Map.h"
 205  #endif
 206  
 207  /* Include basic configuration */
 208  #ifdef Global_ERWIN_COMPILING
 209  #  include "erwin/defs.h"
 210  #else
 211  #  include <erwin/defs.h>
 212  #endif
 213  
 214  /* Include the definitions: */
 215  #include "#Map_d.ErwinHExt"
 216  
 217  /* Include basic definitions */
 218  #ifdef Global_ERWIN_COMPILING
 219  #  include "erwin/base.h"
 220  #else
 221  #  include <erwin/base.h>
 222  #endif
 223  
 224  /* Include forward declarations */
 225  #ifdef Global_ERWIN_COMPILING
 226  #  include "erwin/forwards.h"
 227  #else
 228  #  include <erwin/forwards.h>
 229  #endif
 230  
 231  #ifdef HAVE_STDIO_H
 232  #include <stdio.h>
 233  #endif
 234  
 235  #IFCPPONLY
 236  #ELSE
 237  #ifdef __cplusplus
 238  extern "C" {
 239  #endif
 240  #ENDIF
 241  
 242  #if defined(Global_ERWIN_REQUIRE_DETERMINISM) && !defined(Global_ERWIN_WEAK_DETERMINISM)
 243  #  ifndef __cplusplus
 244  /* #    error "Determinism for maps is currently only available for C++." */
 245  /*     Too many problems with mixed C/C++ projects. */
 246  /*     Actually, C projects will still be 'weakly' deterministic, in the sence
 247   *     that they are determinstic on the EQUAL and HASH_RAW level.  Only the
 248   *     special DETCMP are ignored.  This is because iteration in C still
 249   *     iterates over the internal structure deterministically, which is
 250   *     sorted by HASH_RAW mainly and the insertion order and EQUAL secondly.
 251   *     And since with enabled determinism, the internal hash table for
 252   *     distributing HASH_RAW to HASH is not randomised when using determinism,
 253   *     hash tables are still, well, weakly determistic.
 254   *     The non-determinsm usually occurs when symbols are hash, since the
 255   *     system simply produces different pointer values during different
 256   *     runs, leading to different structures inside the hash table.  This
 257   *     is then overcome in C++ by sorting the table before iteration. */
 258  #  endif
 259  #endif
 260  
 261  /* These are undef'ed first because there is only one error code for all
 262   * the maps in your program.
 263   * All the functions returing error codes will both return this error
 264   * and write it into Global_map_errno.
 265   *    == Global_MAP_OK: Ok.
 266   *               Macro: Global_MAP_IS_OK(X)
 267   *
 268   *    <  Global_MAP_OK: Error: operation did not succeed.
 269   *               Macro: Global_MAP_IS_ERROR(X)
 270   *
 271   *    >  Global_MAP_OK: Warning: operation did succeed but not perfectly. (e.g.
 272   *                        rehash failed)
 273   *               Macro: Global_MAP_IS_WARNING(X)
 274   *
 275   *  In all cases, success, errors, warnings, rehash failures, failed assertions, etc, the
 276   *  consistency of the data structure is guaranteed.
 277   */
 278  
 279  #undef  Global_map_errno
 280  
 281  #if Global_ERWIN_GLOBAL_ERRNO
 282  #  define Global_map_errno Global_erwininternalmaperrno
 283    /* The global map status code. */
 284  #endif
 285  
 286  #undef  Global_map_strerror
 287  #define Global_map_strerror Global_erwininternalmapstrerror
 288    /* Returns a textual description of a given error.  This description
 289     * starts with `Error: ' or `Warning: ' or something the like
 290     * to indicate the status level.  This is then followed by a
 291     * short description phrase.
 292     */
 293  
 294  /*! enum: Global_MAP_OK, Global_MAP_ERR_*, Global_MAP_WARN_*, Global_MAP_REHASH_* */
 295  #undef  Global_MAP_OK
 296  #define Global_MAP_OK                     Global_ERWININTERNALMAPOK
 297      /* No error occurred */
 298  
 299  #undef  Global_MAP_IS_OK
 300  #define Global_MAP_IS_OK(X)               Global_ERWININTERNALMAPISOK(X)
 301    /* Find out whether the status code map_errno indicates that everything is fine. */
 302  
 303  #undef  Global_MAP_IS_ERROR
 304  #define Global_MAP_IS_ERROR(X)            Global_ERWININTERNALMAPISERROR(X)
 305    /* Find out whether the status code map_errno indicates that an error occured. */
 306  
 307  #undef  Global_MAP_IS_WARNING
 308  #define Global_MAP_IS_WARNING(X)          Global_ERWININTERNALMAPISWARNING(X)
 309    /* Find out whether the status code map_errno indicates that an error occured. */
 310  
 311  #undef  Global_MAP_ERR_NOMEM
 312  #define Global_MAP_ERR_NOMEM              Global_ERWININTERNALMAPERRNOMEM
 313    /* Memory exhausted.  If you think this is a fatal error and should be
 314     * treated like a failed assertion, #define Global_ERWIN_NOMEM_IS_FATAL.
 315     */
 316  
 317  #undef  Global_MAP_ERR_ASSERTIONFAILED
 318  #define Global_MAP_ERR_ASSERTIONFAILED    Global_ERWININTERNALMAPERRASSERTIONFAILED
 319    /* Whenever an axiomatic assertion failed, this error is occured.
 320     *
 321     * Note: Something really went wrong in this case, so do not expect that
 322     *       every failed assertion allows normal control flow to continue.
 323     *       This error means the program is broken and would have crashed
 324     *       or done something bad if the assertion had not been checked.
 325     */
 326  
 327    /* The following are warnings only.  They are created by the iterator functions: */
 328  
 329  #undef  Global_MAP_WARN_EXISTINGKEY
 330  #define Global_MAP_WARN_EXISTINGKEY       Global_ERWININTERNALMAPWARNEXISTINGKEY
 331    /* A key could not be inserted into a map, because it already exists. */
 332  
 333  #undef  Global_MAP_ERR_EXISTINGKEY
 334  #define Global_MAP_ERR_EXISTINGKEY please_use_MAP_WARN_EXISTINGKEY_instead
 335  
 336  #undef  Global_MAP_WARN_KEYNOTFOUND
 337  #define Global_MAP_WARN_KEYNOTFOUND       Global_ERWININTERNALMAPWARNKEYNOTFOUND
 338    /* A key was not found in the map. */
 339  
 340  #undef  Global_MAP_ERR_KEYNOTFOUND
 341  #define Global_MAP_ERR_KEYNOTFOUND please_use_MAP_WARN_KEYNOTFOUND_instead
 342  
 343  #undef  Global_MAP_WARN_EMTPY
 344  #define Global_MAP_WARN_EMPTY             Global_ERWININTERNALMAPWARNEMPTY
 345  
 346  #undef  Global_MAP_WARN_NOMOREELEMS
 347  #define Global_MAP_WARN_NOMOREELEMS       Global_ERWININTERNALMAPWARNNOMOREELEMS
 348  
 349  #undef  Global_MAP_REHASH_NOMEM
 350  #define Global_MAP_REHASH_NOMEM           Global_ERWININTERNALMAPREHASHNOMEM
 351    /* This is returned if the element could be inserted but the rehash then failed. */
 352  
 353  #undef  Global_MAP_REHASH_DUPLICATEKEY
 354  #define Global_MAP_REHASH_DUPLICATEKEY    Global_ERWININTERNALMAPREHASHDUPLICATEKEY
 355    /* This is returned if a consistency error is detected during a rehash operation.
 356     * In this case there where two duplicate keys.
 357     *   This can happen if the copy function for the
 358     *   keys is missing or if the comparison and hash functions do not
 359     *   work properly. */
 360  
 361  #undef  Global_MAP_REHASH_RECURSION
 362  #define Global_MAP_REHASH_RECURSION       Global_ERWININTERNALMAPREHASHRECURSION
 363    /* This is returned if a rehash operation behaved totally unexpectedly
 364     * and triggered its own recursive call. */
 365  
 366  
 367  typedef iType Map_index_t;
 368  typedef oType Map_value_t;
 369  #TYPEDEF(Map_index_t NSMap_index_t)
 370  #TYPEDEF(Map_value_t NSMap_value_t)
 371  
 372  #REM For oType==void, 'pair' is a misnomer, but sorted operators are easier to implement.
 373  typedef struct _Map_pair_t {
 374      iType key;
 375  #IF(oType != void)
 376      oType value;
 377  #ENDIF
 378  } Map_pair_t;
 379  #TYPEDEF(aggregate Map_pair_t NSMap_pair_t)
 380  
 381  typedef Map_pair_t Map_pair_dynarray;
 382  
 383  
 384  #REM For oType==void, 'pair' is a misnomer, but sorted operators are easier to implement.
 385  typedef struct _Map_pair_ptr_t {
 386      iType key;
 387  #IF(oType != void)
 388      oTypeVar *value;
 389  #ENDIF
 390  #REM For oType==void, this type is a misnomer, but sorted operators are easier to implement.
 391  } Map_pair_ptr_t;
 392  #TYPEDEF(aggregate Map_pair_ptr_t NSMap_pair_ptr_t)
 393  
 394  
 395  typedef Map_pair_ptr_t Map_pair_ptr_dynarray;
 396  
 397  typedef int (*Map_pair_cmp_t)(Map_pair_t const *, Map_pair_t const *);
 398  #TYPEDEF(Map_pair_cmp_t NSMap_pair_cmp_t)
 399  
 400  typedef int (*Map_pair_ptr_cmp_t)(Map_pair_ptr_t const *, Map_pair_ptr_t const *);
 401  #TYPEDEF(Map_pair_ptr_cmp_t NSMap_pair_ptr_cmp_t)
 402  
 403  typedef int (*Map_void_pair_cmp_t)(void const *, void const *);
 404  #TYPEDEF(Map_void_pair_cmp_t NSMap_void_pair_cmp_t)
 405  
 406  
 407  
 408  #IF(oType == void)
 409  typedef Global_ERWIN_BOOL (*Map_feature_t)(iTypeParam);
 410  #ELSE
 411  typedef Global_ERWIN_BOOL (*Map_feature_t)(iTypeParam, oTypeParam);
 412  #ENDIF
 413  #TYPEDEF(Map_feature_t NSMap_feature_t)
 414  
 415  #IF(oType != void)
 416  
 417  #IF(oType == oTypeVar)
 418  typedef oType *Map_element_ptr_t;
 419  #ELSE
 420  typedef oType const *Map_element_ptr_t;
 421  #ENDIF
 422  #TYPEDEF(Map_element_ptr_t NSMap_element_ptr_t)
 423  
 424  #ENDIF(oType != void)
 425  
 426  
 427  #IF(iType == iTypeResult)
 428  typedef iType Map_key_result_t;
 429  #ELSE
 430  typedef iTypeVar const *Map_key_result_t;
 431  #ENDIF
 432  #TYPEDEF(Map_key_result_t NSMap_key_result_t)
 433  
 434  
 435  #ifndef Global_MAP_ITERATOR
 436  
 437  #define Global_MAP_ITERATOR
 438  #REM no: TYPEDEF(aggregate Global_map_iterator_t map_iterator_t)
 439  struct _Global_map_iterator_t;
 440  
 441  typedef void (*_Global_map_iterator_callback_t) (void const *, struct _Global_map_iterator_t *);
 442  
 443  typedef struct _Global_map_iterator_t {
 444      /* This is an iterator for maps.  You need to know about this struct
 445       * when programming in C, since you have to declare such an iterator
 446       * manually.  Map iteration looks like this:
 447       *     : Global_map_iterator_t iter;
 448       *     : ...
 449       *     : Map_forall (map, iter, key, value) {
 450       *     :     ...
 451       *     : }
 452       *
 453       * The internal structure of this class is not important to the user,
 454       * however -- you should never try to look inside an iterator structure.
 455       */
 456  
 457      /*! class-ignore */
 458      void *p;
 459      int i;
 460  #ifdef __cplusplus
 461      _Global_map_iterator_t ()
 462      {}
 463  
 464     /* This is a hack, but I did not find a good way of programming the C++ iterator. */
 465      _Global_map_iterator_t (
 466          _Global_map_iterator_callback_t callback,
 467          void const *map)
 468      {
 469           callback (map, this);
 470      }
 471  #endif /* defined(__cplusplus) */
 472  } Global_map_iterator_t;
 473  
 474  
 475  #ifdef __cplusplus
 476  /*
 477   * Only available in C++ since otherwise some easy to produce memory leaks would be
 478   * really hard to find for the user.  In C, the user must sort the array themself.
 479   */
 480  #REM no: TYPEDEF_CXX(aggregate Global_map_iterator_sorted_t map_iterator_sorted_t)
 481  struct _Global_map_iterator_sorted_t;
 482  
 483  typedef void (*_Global_map_iterator_sorted_callback_t)
 484                   (void const *, struct _Global_map_iterator_sorted_t *);
 485  
 486  typedef int  (*_Global_map_iterator_cmp_callback_t)(void const *, void const *);
 487  
 488  typedef void (*_Global_map_iterator_sorted_init_callback_t)(
 489              void const *,
 490              struct _Global_map_iterator_sorted_t *,
 491              _Global_map_iterator_cmp_callback_t);
 492  
 493  typedef struct _Global_map_iterator_sorted_t {
 494      /* You do not need any knowledge about this class, since
 495       * the C++ interface introduces iterators on the fly and
 496       * the C interface currently has no support for sorted
 497       * iteration, since allocation/deallocation of the needed
 498       * help structures is a serious problem in C.
 499       */
 500  
 501      /*! class-ignore */
 502      void *p;
 503      int l;
 504      int c;
 505      void (*free_cb)(void *);
 506  
 507      _Global_map_iterator_sorted_t ():
 508           free_cb(0)
 509      {}
 510  
 511      _Global_map_iterator_sorted_t (
 512          _Global_map_iterator_sorted_callback_t callback,
 513          void const *map)
 514      {
 515          callback (map, this);
 516      }
 517  
 518      _Global_map_iterator_sorted_t (
 519          _Global_map_iterator_sorted_init_callback_t callback,
 520          void const *map,
 521          _Global_map_iterator_cmp_callback_t u)
 522      {
 523           callback (map, this, u);
 524      }
 525  
 526      ~_Global_map_iterator_sorted_t ()
 527      {
 528           if (free_cb) free_cb ((void*)this);
 529              /* (a kind of virtual destructor)
 530               * Callback, since the operator does not know how to do it.
 531               */
 532      }
 533  } Global_map_iterator_sorted_t;
 534  #endif
 535  
 536  #endif /* defined(Global_MAP_ITERATOR) */
 537  
 538  
 539  /* ***** handling `hash' objects: ***** */
 540  
 541  
 542  /*--BEGIN-C--*/
 543  Global_ERWIN_EXPORT
 544  Map_t *Map_new (void) ATTR_MALLOC;
 545    /* Return a new map with default settings.  I.e., with the
 546     * default zero element Map_ZERO and the default initial hash table
 547     * size of Map_INITIAL_SIZE.
 548     *
 549     * \errno(OK, ERR_NOMEM)
 550     */
 551  
 552  Global_ERWIN_EXPORT
 553  Map_t *Map_new_with_initial_size (int /*initial_size*/) ATTR_MALLOC;
 554    /* Create a new map with a given initial hash table.  This is
 555     * useful whenever you know how many entries you will have.
 556     *
 557     * The number you pass is interpreted as the number of elements.
 558     * The real hash size that will be used will be computed in such
 559     * a way that no rehash will occur when inserting the number of
 560     * elements given.  Note that a single deletion of an element may
 561     * still trigger a rehash, only when only inserting the elements,
 562     * no rehash is guaranteed.
 563     *
 564     * If initial_size < 0 the default size Map_INITIAL_SIZE will be used.
 565     * If initial_size == 0 but Map_MINIMAL_SIZE > 0, a size of 1 will be
 566     * used.
 567     *
 568     * With the default value of the re-hash parameters, a re-hash
 569     * will be done when the map has more than 80% entries compared
 570     * to the hash table size.  So if you intend to insert 80 entries,
 571     * you must specify more than 100 for the initial size.  To be
 572     * precise, you must specify more than
 573     * Map_TRIGGER_NUMERATOR * 80 / Map_TRIGGER_DENOMINATOR.
 574     *
 575     * \errno(OK, ERR_NOMEM)
 576     */
 577  
 578  #if Map_DYN_ZERO
 579  Global_ERWIN_EXPORT
 580  Map_t *Map_new_with_zero (oTypeTouched /*zero*/) ATTR_MALLOC;
 581    /* zero will eventually be tried to be copied!  So if you provide
 582     * oType_OCOPY, make sure it handles the zero element appropriately.
 583     *
 584     * \errno(OK, ERR_NOMEM)
 585     */
 586  
 587  Global_ERWIN_EXPORT
 588  Map_t *Map_new_with_zero_and_initial_size (oTypeTouched /*zero*/, int /*initial_size*/) ATTR_MALLOC;
 589    /* Create a new, empty map.  The first form uses
 590     * Global_oType_zero as the zero element.
 591     *
 592     * If initial_size < 0 the default size Map_INITIAL_SIZE will be used.
 593     * If initial_size == 0 but Map_MINIMAL_SIZE > 0, a size of 1 will be
 594     * used.
 595     *
 596     * \errno(OK, ERR_NOMEM)
 597     */
 598  #endif
 599  
 600  Global_ERWIN_EXPORT
 601  int Map_init (
 602      Map_t * /*self*/) ATTR_NONNULL((1));
 603    /*
 604     * This is for initialising non-heap Map_t objects.
 605     *
 606     * Invoking this function manually is usually discouraged.  It is thought
 607     * to be for nesting data structures.  However, if you need to optimise
 608     * heap usage, it is ok to use this function.
 609     *
 610     * \errno(OK, ERR_NOMEM)
 611     */
 612  
 613  #if Map_DYN_ZERO
 614  Global_ERWIN_EXPORT
 615  int Map_init_with_zero_and_initial_size (
 616      Map_t *      /*self*/,
 617      oTypeTouched /*zero*/,
 618      int          /*initial_size*/) ATTR_NONNULL((1));
 619    /*
 620     * This is for initialising non-heap Map_t objects that are allocated
 621     * manually (thus, not via Map_new).
 622     *
 623     * Invoking this function manually is usually discouraged.  It is thought
 624     * to be for nesting data structures.  However, if you need to optimise
 625     * heap usage, it is ok to use this function.
 626     *
 627     * \errno(OK, ERR_NOMEM)
 628     */
 629  #endif
 630  
 631  Global_ERWIN_EXPORT
 632  int Map_init_with_initial_size (
 633      Map_t * /*self*/,
 634      int     /*initial_size*/) ATTR_NONNULL((1));
 635    /*
 636     * This is for initialising non-heap Map_t objects.
 637     *
 638     * Invoking this function manually is usually discouraged.  It is thought
 639     * to be for nesting data structures.  However, if you need to optimise
 640     * heap usage, it is ok to use this function.
 641     *
 642     * \errno(OK, ERR_NOMEM)
 643     */
 644  
 645  Global_ERWIN_EXPORT
 646  void Map_destroy (Map_t * /*self*/);
 647    /*
 648     * This is for deleting non-heap Map_t objects.
 649     *
 650     * Invoking this function manually is usually discouraged.  It is thought
 651     * to be for nesting data structures.  However, if you need to optimise
 652     * heap usage, it is ok to use this function.
 653     *
 654     * \errno(OK)
 655     */
 656  
 657  Global_ERWIN_EXPORT
 658  void Map_xchg (Map_t * /*self*/, Map_t * /*other*/);
 659    /*
 660     * Exchanges the two maps' contents.  No memory allocation is
 661     * performed; this is a fast O(1) operation for swapping two values.
 662     */
 663  
 664  Global_ERWIN_EXPORT
 665  void Map_destroy_flags (
 666    Map_t * /*self*/, Global_ERWIN_BOOL /* destroy_keys */, Global_ERWIN_BOOL /* destroy_values */);
 667    /*
 668     * Same as Map_destroy with the possiblity to determine what to destroy.
 669     *
 670     * Invoking this function manually is usually discouraged.  It is thought
 671     * to be for nesting data structures.  However, if you need to optimise
 672     * heap usage, it is ok to use this function.
 673     *
 674     * \errno(OK)
 675     */
 676  
 677  
 678  #if !Global_ERWIN_GLOBAL_ERRNO
 679  Global_ERWIN_EXPORT
 680  int Map_errno(Map_t const *) ATTR_PURE ATTR_NONNULL((1));
 681    /* If the library was compiled with Global_ERWIN_THREAD_SAFE, this is the
 682     * way to retrieve the status code of a map.
 683     *
 684     * If you do not
 685     * have a thread-safe Erwin library, there is a macro with the same name as
 686     * this function.
 687     *
 688     * \noerrno
 689     */
 690  
 691  Global_ERWIN_EXPORT
 692  void Map_clear_errno(Map_t const *) ATTR_NONNULL((1));
 693    /* Resets the status code to MAP_OK.
 694     *
 695     * If you do not
 696     * have a thread-safe Erwin library, there is a macro with the same name as
 697     * this function.
 698     *
 699     * \errno(OK)
 700     */
 701  
 702  #else
 703  
 704  #define Map_errno(X)          Global_map_errno
 705    /* If the library was not compiled with Global_ERWIN_THREAD_SAFE, Map_errno(X)
 706     * is just a synonym for the global variable Global_map_errno.
 707     *
 708     * If you
 709     * have a thread-safe Erwin library, there is a function with the same name as
 710     * this macro.
 711     *
 712     * \noerrno
 713     */
 714  
 715  #define Map_clear_errno(X)    ((void)(Global_map_errno= Global_MAP_OK))
 716    /* If the library was not compiled with Global_ERWIN_THREAD_SAFE, Map_clear_errno(X)
 717     * is a small macro that resets the status code to Global_MAP_OK.
 718     *
 719     * If you
 720     * have a thread-safe Erwin library, there is a function with the same name as
 721     * this macro.
 722     *
 723     * \errno(OK)
 724     */
 725  
 726  #endif
 727  
 728  Global_ERWIN_EXPORT
 729  Map_t *Map_copy (Map_t const* /*self*/);
 730    /* Copies the map with all its keys and elements
 731     *
 732     * NULL is allowed and passed through.
 733     *
 734     * Don't use as a copy function for other Erwin structures.  Use _copy_err instead.
 735     *
 736     * \errno(OK,REHASH_*,ERR_NOMEM)
 737     */
 738  
 739  Global_ERWIN_EXPORT
 740  Map_t *Map_copy_err (Map_t const* /*self*/, int *err);
 741    /* Copies the map with all its keys and elements.  *err will be set
 742     * to 1 if an error occurs.
 743     *
 744     * \errno(OK, REHASH_*, ERR_NOMEM)
 745     */
 746  
 747  
 748  Global_ERWIN_EXPORT
 749  void Map_delete (Map_t* /*self*/);
 750    /* Deletes everything in the map and the map structure itself
 751     *
 752     * \errno(OK)
 753     */
 754  
 755  Global_ERWIN_EXPORT
 756  void   Map_delete_flags (Map_t* /* self*/, Global_ERWIN_BOOL /* destroy_keys */, Global_ERWIN_BOOL /* destroy_values */);
 757    /* Deletes only the map structure, not the entries.  This is
 758     * useful if you got the entries via Map_get_{values|keys}.
 759     * Map_delete_flat (a, true, true) is the same as
 760     * Map_delete (a);
 761     *
 762     * \errno(OK)
 763     */
 764  
 765  
 766  /* *****  normal operations: ***** */
 767  
 768  
 769  /* The `iType' is used to force the caller to provide copy functions
 770   * when pointers are used for iType.  Otherwise, duplicate keys are
 771   * easily possible. */
 772  #IF(oType == void)
 773  Global_ERWIN_EXPORT
 774  int Map_insert (Map_t* /*self*/, iTypeTouched /*key*/) ATTR_NONNULL((1));
 775  #ELSE
 776  Global_ERWIN_EXPORT
 777  int Map_insert (Map_t* /*self*/, iTypeTouched /*key*/, oTypeTouched /*value*/) ATTR_NONNULL((1));
 778  #ENDIF
 779    /* Introduces a value for a given key into the map.  If the key did not
 780     * exist, errno will be OK.  If the key existed, the map will not be changed,
 781     * and errno will be WARN_EXISTINGKEY.
 782     *
 783     * Key and value are copied (if copy functions are available, as usual).
 784     *
 785     * \errno(OK, WARN_EXISTINGKEY, REHASH_*, ERR_NOMEM)
 786     */
 787  
 788  Global_ERWIN_EXPORT
 789  int Map_insert_map (Map_t* /*self*/, Map_t const * /* other */);
 790    /* Inserts all keys from other into self.  If any key is not inserted,
 791     * returns WARN_EXISTINGKEY.
 792     *
 793     * \errno(OK, WARN_EXISTINGKEY, REHASH_*, ERR_NOMEM)
 794     */
 795  
 796  Global_ERWIN_EXPORT
 797  iTypeResult Map_ensure (Map_t* /*self*/, iTypeTouched /*key*/) ATTR_NONNULL((1));
 798    /* This ensures that key is inserted in the table, i.e., it allocates a cell
 799     * for it.  The inserted value will be Global_oType_ZERO.  If you
 800     * want to change this, re-define Map_ENSURE_VALUE.
 801     * The result is the key as inserted in the hash table, so if you defined
 802     * Global_iType_ICOPY, you will get a copy of your key.
 803     *
 804     * Note: This function implements symbol tables.
 805     *
 806     * \errno(OK, WARN_EXISTINGKEY, REHASH_*, ERR_NOMEM)
 807     */
 808  
 809  Global_ERWIN_EXPORT
 810  iTypeResult Map_ensure_no_icopy (Map_t * /*self*/, iTypeVarParam /*key*/) ATTR_NONNULL((1));
 811    /* This is like Map_ensure(), but the input key will be stolen or freed, i.e.,
 812     * it will be used as a copy inside the hash table, instead of being copied
 813     * as in Map_ensure.  If the key already exists, the key passed will be freed.
 814     *
 815     * Note: This function implements symbol tables.
 816     *
 817     * This could be called Map_ensure_steal(), but we already have poke_no_icopy().
 818     *
 819     * \errno(OK, WARN_EXISTINGKEY, REHASH_*, ERR_NOMEM)
 820     */
 821  
 822  #IF(oType != void)
 823  Global_ERWIN_EXPORT
 824  oTypeResult Map_find_any (Map_t const* /*self*/)
 825    ATTR_ERRNO_PURE;
 826    /* Returns the found element or the zero element if not found.
 827     *
 828     * For maps with 0 or 1 elements and in the non-deterministic
 829     * case, this is very fast.  In the deterministic mode, this
 830     * is O(n).  In weak determinism, it is typically O(1) as in
 831     * the non-deterministic mode.  (The very unlikely worst case
 832     * is always O(n)).
 833     *
 834     * \errno(OK, WARN_KEYNOTFOUND)
 835     */
 836  #ENDIF
 837  
 838  
 839  #IF(oType == void)
 840  Global_ERWIN_EXPORT
 841  int Map_find_any_pair (Map_key_result_t *, Map_t const* /*self*/)
 842    ATTR_ERRNO_PURE;
 843  #ELSE
 844  Global_ERWIN_EXPORT
 845  int Map_find_any_pair (Map_key_result_t *, Map_element_ptr_t *, Map_t const* /*self*/)
 846    ATTR_ERRNO_PURE;
 847  #ENDIF
 848    /* Returns the number of elements in the map.  If that is > 0, the
 849     * first argument is set to any key, and the second to the pointer to
 850     * the corresponding value.
 851     *
 852     * You may pass NULL for any of the first two parameters if you do not want
 853     * the return value.
 854     *
 855     * See Map_find_any() for more documentation.
 856     *
 857     * \errno(OK, WARN_KEYNOTFOUND)
 858     */
 859  
 860  
 861  Global_ERWIN_EXPORT
 862  oTypeResult  Map_find (Map_t const* /*self*/, iTypeParam /*index*/)
 863    ATTR_ERRNO_PURE;
 864    /* Returns the found element or the zero element if not found.
 865     *
 866     * \errno(OK, WARN_KEYNOTFOUND)
 867     */
 868  
 869  #IF(oType != void)
 870  Global_ERWIN_EXPORT
 871  oTypeResult Map_find_ensure (Map_t * /*self*/, iTypeTouched /*index*/);
 872    /* Returns the found element or introduces an empty element into the
 873     * map and returns that (use Map_ENSURE_VALUE to determine the value
 874     * that is introduced).
 875     *
 876     * Also consider find_ptr_ensure if you want to modify the (newly
 877     * introduced) value.  Also see Map_ensure if you need the key, not
 878     * the value after the operation.
 879     *
 880     * \errno(OK, WARN_KEYNOTFOUND)
 881     */
 882  #ENDIF
 883  
 884  Global_ERWIN_EXPORT
 885  iTypeResult  Map_find_key (Map_t const* /*self*/, iTypeParam /*index*/) ATTR_ERRNO_PURE;
 886    /* Returns the key as stored in the table.  For copied pointer types, this
 887     * might be different from index.
 888     *
 889     * \errno(OK, WARN_KEYNOTFOUND)
 890     */
 891  
 892  Global_ERWIN_EXPORT
 893  iTypeResult  Map_find_any_key (Map_t const* /*self*/) ATTR_ERRNO_PURE;
 894    /* Returns some key that is stored in the table.
 895     *
 896     * See Map_find_any() for docu.
 897     *
 898     * \errno(OK, WARN_KEYNOTFOUND)
 899     */
 900  
 901  #IF(oType != void)
 902  
 903  Global_ERWIN_EXPORT
 904  Map_element_ptr_t Map_find_ptr (Map_t const* /*self*/, iTypeParam /*index*/) ATTR_ERRNO_PURE;
 905    /* Returns a pointer to the found element or NULL on failure.
 906     *
 907     * Note: If oType == oTypeVar, you may not use the pointer to directly
 908     * write into the hash table because this circumvents copying and that
 909     * is prohibited.  Use poke_no_ocopy for things like that to make it
 910     * explicit.
 911     *
 912     * \errno(OK, WARN_KEYNOTFOUND)
 913     */
 914  
 915  Global_ERWIN_EXPORT
 916  Map_element_ptr_t Map_find_any_ptr (Map_t const* /*self*/) ATTR_ERRNO_PURE;
 917    /* Returns a pointer to some element or NULL on failure.
 918     *
 919     * Note: If oType == oTypeVar, you may not use the pointer to directly
 920     * write into the hash table because this circumvents copying and that
 921     * is prohibited.  Use poke_no_ocopy for things like that to make it
 922     * explicit.
 923     *
 924     * \errno(OK, WARN_KEYNOTFOUND)
 925     */
 926  
 927  Global_ERWIN_EXPORT
 928  Map_element_ptr_t Map_find_ptr_ensure (Map_t * /*self*/, iTypeTouched /*index*/);
 929    /* Returns a pointer to the found element or one to a newly allocated one.
 930     * In the case when it was not possible to allocate space for a new element,
 931     * the result NULL.  Otherwise, it is not NULL.
 932     *
 933     * If a new element was introduced, errno will be set to MAP_WARN_KEYNOTFOUND,
 934     * otherwise to MAP_OK.  Note again that in both cases, the result is non-NULL!
 935     *
 936     * Note: If oType == oTypeVar, you may not use the pointer to directly
 937     * write into the hash table because this circumvents copying and that
 938     * is prohibited.  Use poke_no_ocopy for things like that to make it
 939     * explicit.
 940     *
 941     * \errno(OK, WARN_KEYNOTFOUND)
 942     */
 943  
 944  Global_ERWIN_EXPORT
 945  oTypeVar Map_modify (
 946      Map_t* /*self*/, iTypeParam /*index*/, oTypeTouched /*value*/) ATTR_NONNULL((1));
 947    /* Change an existing value for the given index (errno=OK).  If the index does
 948     * not exist, do not modify the map nothing (errno=WARN_KETNOTFOUND).
 949     *
 950     * Returns the old value or Global_oType_ZERO if it is new in which case the map is
 951     * not changed.  Nothing is freed, value is copied.
 952     *
 953     * \errno(OK, WARN_KEYNOTFOUND, REHASH_*, ERR_NOMEM)
 954     */
 955  
 956  Global_ERWIN_EXPORT
 957  int Map_modify_map (Map_t* /*self*/, Map_t const * /* other */);
 958    /* like Map_modify on all entries in other.  If any key was not found,
 959     * WARN_KEYNOTFOUND is returned.
 960     *
 961     * \errno(OK, WARN_KEYNOTFOUND, REHASH_*, ERR_NOMEM)
 962     */
 963  
 964  Global_ERWIN_EXPORT
 965  int Map_set (Map_t* /*self*/, iTypeTouched /*index*/, oTypeTouched /*value*/) ATTR_NONNULL((1));
 966    /* Insert or modify a value: introduce value for given index if it does not
 967     * exist (errno=OK) or change value if index does exist (errno=WARN_EXISTINGKEY).
 968     *
 969     * Similar to Map_modify, but value is freed and the status instead of the value
 970     * is returned.   Furthermore, of course, it is different in that if the value
 971     * does not exist, it will be inserted.
 972     *
 973     * Note: If you don't care whether to use Map_set or Map_insert, use Map_insert.
 974     *       Map_insert might be a little faster.
 975     *
 976     * Result:
 977     *    The error code, same as Global_map_errno.
 978     *
 979     * \errno(OK, WARN_EXISTINGKEY, REHASH_*, ERR_NOMEM)
 980     */
 981  
 982  Global_ERWIN_EXPORT
 983  int Map_set_map (Map_t* /*self*/, Map_t const * /* other */);
 984    /* like Map_set on all entries in other
 985     *
 986     * \errno(OK, REHASH_*, ERR_NOMEM)
 987     */
 988  
 989  #ENDIF
 990  
 991  Global_ERWIN_EXPORT
 992  int Map_intersect (Map_t* /*self*/, Map_t const * /* other */);
 993    /* Implements set intersection: this invokes Map_erase on all entries
 994     * in self that are not in other.
 995     * Returns the number of erased elements (quite like Map_erase_if).
 996     *
 997     * \errno(OK, REHASH_*, ERR_NOMEM)
 998     */
 999  
1000  Global_ERWIN_EXPORT
1001  int Map_intersect_no_resize (Map_t* /*self*/, Map_t const * /* other */);
1002    /* Like Map_intersect, but does not shrink the internal hash table.
1003     *
1004     * \errno(OK, REHASH_*, ERR_NOMEM)
1005     */
1006  
1007  #IF(oType != void)
1008  Global_ERWIN_EXPORT
1009  oTypeVar Map_remove (Map_t* /*self*/, iTypeTouched /*index*/) ATTR_NONNULL((1));
1010    /* Returns the old value or Global_oType_ZERO. Does *not* free the value (which is
1011     * returned), but only the key.   A more appropriate name for this function
1012     * might be `steal', because the value is kept.
1013     *
1014     * In error-free operation, returns errno=OK if the index was found and erased,
1015     * and WARN_KEYNOTFOUND if the index was not found.
1016     *
1017     * \errno(OK, WARN_KEYNOTFOUND, REHASH_*)
1018     */
1019  
1020  Global_ERWIN_EXPORT
1021  oTypeVar Map_remove_no_resize (Map_t* /*self*/, iTypeTouched /*index*/) ATTR_NONNULL((1));
1022    /* Like Map_remove, but does not shrink the internal hash table.
1023     *
1024     * \errno(OK, WARN_KEYNOTFOUND)
1025     */
1026  
1027  Global_ERWIN_EXPORT
1028  int Map_remove_map (Map_t* /*self*/, Map_t const * /* other */);
1029    /* like Map_remove on all entries in other.  If any key was not found,
1030     * WARN_KEYNOTFOUND is returned.
1031     *
1032     * \errno(OK, WARN_KEYNOTFOUND, REHASH_*)
1033     */
1034  
1035  Global_ERWIN_EXPORT
1036  int Map_remove_if (Map_t * /*self */, Map_feature_t /* feature */, Global_ERWIN_BOOL /* value */);
1037    /* Remove some entries from the map according to a given feature.  This
1038     * is much faster than repeated deletions and maximally requires one
1039     * rehash operation only.
1040     *
1041     * NOTE: Even if the library is compiled with determinism, the order of the
1042     *       invocations of the feature callback is non-deterministic!
1043     *
1044     * \errno (OK, REHASH_*)
1045     */
1046  
1047  #ENDIF
1048  
1049  Global_ERWIN_EXPORT
1050  int Map_erase (Map_t* /*self*/, iTypeTouched /*index*/) ATTR_NONNULL((1));
1051    /* Same as Map_remove, but value is freed.  In error-free operation, returns
1052     * errno=OK if the index was found and erased, and WARN_KEYNOTFOUND if the
1053     * index was not found.
1054     *
1055     * \errno(OK, WARN_KEYNOTFOUND, REHASH_*)
1056     */
1057  
1058  Global_ERWIN_EXPORT
1059  int Map_erase_no_resize (Map_t* /*self*/, iTypeTouched /*index*/) ATTR_NONNULL((1));
1060    /* Same as Map_erase, but does not shrink the internal hash table.
1061     *
1062     * \errno(OK, WARN_KEYNOTFOUND)
1063     */
1064  
1065  Global_ERWIN_EXPORT
1066  int Map_erase_map (Map_t* /*self*/, Map_t const * /* other */);
1067    /* like Map_erase on all entries in other.  If any key was not found,
1068     * WARN_KEYNOTFOUND is returned.
1069     *
1070     * \errno(OK, WARN_KEYNOTFOUND, REHASH_*)
1071     */
1072  
1073  Global_ERWIN_EXPORT
1074  int Map_erase_map_no_resize (Map_t* /*self*/, Map_t const * /* other */);
1075    /* Like Map_erase_map, but does not shrink the internal hash table.
1076     *
1077     * \errno(OK, WARN_KEYNOTFOUND)
1078     */
1079  
1080  Global_ERWIN_EXPORT
1081  int Map_erase_if (Map_t * /*self */, Map_feature_t /* feature */, Global_ERWIN_BOOL /* value */);
1082    /* Erase some entries from the map according to a given feature.  This
1083     * is much faster than repeated deletions and maximally requires one
1084     * rehash operation only.
1085     *
1086     * NOTE: Even if the library is compiled with determinism, the order of the
1087     *       invocations of the feature callback is non-deterministic!
1088     *
1089     * \errno (OK, REHASH_*)
1090     */
1091  
1092  
1093  #IF(oType == void)
1094  Global_ERWIN_EXPORT
1095  int Map_poke (
1096          iType *      /* key_out */,
1097          Map_t *      /* self */,
1098          iTypeTouched /* key */,
1099          Global_ERWIN_BOOL       /* introduce */) ATTR_NONNULL((2));
1100  #ELSE
1101  Global_ERWIN_EXPORT
1102  int Map_poke (
1103          iType *      /* key_out */,
1104          oTypeVar *   /* value_out */,
1105          Map_t *      /* self */,
1106          iTypeTouched /* key */,
1107          oTypeTouched /* value */,
1108          Global_ERWIN_BOOL       /* introduce */,
1109          Global_ERWIN_BOOL       /* overwrite */) ATTR_NONNULL((3));
1110  #ENDIF
1111    /* This is the generalised interface to Map_insert, Map_modify, Map_set, Map_ensure, Map_find
1112     * and Map_find_key.  This function cannot erase, however (see Map_erase).
1113     *
1114     * Input parameters:
1115     *   +--------------+----------------------------------------------------------------------+
1116     *   | \p self      | is the map as usual                                                  |
1117     *   | \p key       | defines the entry which is to be inserted or changed                 |
1118     *   | \p value     | is the value that is inserted or with which the entry is overwritten |
1119     *   | \p introduce | insert a new value if nothing exists for the key                     |
1120     *   | \p overwrite | defines whether a value will be overwritten if it already exists     |
1121     *   +--------------+----------------------------------------------------------------------+
1122     *
1123     * Output parameters:
1124     *   +--------------+----------------------------------------------------------------------+
1125     *   | return value | the error code (Global_map_errno)                                    |
1126     *   +--------------+----------------------------------------------------------------------+
1127     *   | \p key_out   | *key_out will be the key as inserted in the map.  This can be        |
1128     *   |              | different from key when the keys are copied.                         |
1129     *   |              | key_out may be NULL                                                  |
1130     *   +--------------+----------------------------------------------------------------------+
1131     *   | \p value_out | If non-NULL, the entry found in the map will be stored here. It      |
1132     *   |              | will not be freed if it is overwritten of value_out != NULL.         |
1133     *   |              | If value_out==NULL, overwritten values are freed as usual.           |
1134     *   +--------------+----------------------------------------------------------------------+
1135     *
1136     * Note: The is an important difference between key_out and value_out.  Via
1137     *       key_out, the *current* key in the map is returned, but via value_out, the
1138     *       *old* value is returned.
1139     *
1140     * The following shows the (idealised) bodies of some functions.
1141     *
1142     * Map_insert:
1143     *       : return Map_poke (NULL, NULL, self, key, value,
1144     *       :                  Global_ERWIN_TRUE, Global_ERWIN_FALSE);
1145     *
1146     * Map_set:
1147     *       : return Map_poke (NULL, NULL, self, key, value,
1148     *       :                 Global_ERWIN_TRUE, Global_ERWIN_TRUE);
1149     *
1150     * Map_modify:
1151     *       : oTypeVar *result;
1152     *       : Map_poke (NULL, &result, self, key, value,
1153     *       :           Global_ERWIN_FALSE, Global_ERWIN_TRUE);
1154     *       : return result;
1155     *
1156     * Map_find:
1157     *       : oTypeVar *result;
1158     *       : Map_poke (NULL, &result, self, key, ZERO (oType),
1159     *       :           Global_ERWIN_FALSE, Global_ERWIN_FALSE);
1160     *       : return (oType*)result;
1161     *
1162     * Map_find_key:
1163     *       : iTypeVar *result;
1164     *       : Map_poke (&result, NULL, self, key, ZERO (oType),
1165     *       :           Global_ERWIN_FALSE, Global_ERWIN_FALSE);
1166     *       : return (iType*)result;
1167     *
1168     * Almost:
1169     * Map_ensure:
1170     *       : iTypeVar *result;
1171     *       : Map_poke (&result, NULL, self, key, ZERO (oType),
1172     *       :           Global_ERWIN_TRUE, Global_ERWIN_FALSE);
1173     *       : result;
1174     * (Only Map_ensure uses Map_ENSURE_VALUE to introduce a new element, not
1175     * ZERO and without copying)
1176     *
1177     * Note that Map_find_ptr, Map_remove and Map_erase cannot be implemented with
1178     * this function.
1179     *
1180     * Return Values:
1181     *    - Global_MAP_OK:
1182     *         If an entry was not found, but could be successfully inserted
1183     *         or if an entry was found and could be successfully overwritten
1184     *         or if an entry was found and neither insertion nor overwriting was
1185     *         allowed (introduce == overwrite == Global_ERWIN_FALSE).
1186     *
1187     *     - Global_MAP_WARN_KEYNOTFOUND:
1188     *         If a key was not found, but not inserted (due to introduce ==
1189     *         Global_ERWIN_FALSE).
1190     *
1191     *     - Global_MAP_WARN_EXISTINGKEY:
1192     *         If a key was found, but not overwritten (due to overwrite == Global_ERWIN_FALSE).
1193     *
1194     *     - Global_MAP_ERR_NOMEM:
1195     *         If a structure could not be allocated, or a key or a value could not
1196     *         be copied. In this case, the map is returned unmodified.
1197     *
1198     *     - Global_MAP_ERR_ASSERTIONFAILED:
1199     *         If an assertion failed.
1200     */
1201  
1202  #IF(oType == void)
1203  Global_ERWIN_EXPORT
1204  int Map_poke_no_icopy (
1205     iType * /*key_out*/,
1206     Map_t * /*self*/,
1207     iTypeVarParam /*key*/,
1208     Global_ERWIN_BOOL /*introduce*/) ATTR_NONNULL((2));
1209  #ELSE
1210  Global_ERWIN_EXPORT
1211  int Map_poke_no_icopy (
1212     iType * /*key_out*/,
1213     oTypeVar * /*value_out*/,
1214     Map_t * /*self*/,
1215     iTypeVarParam /*key*/,
1216     oTypeParam /*value*/,
1217     Global_ERWIN_BOOL /*introduce*/,
1218     Global_ERWIN_BOOL /*overwrite*/) ATTR_NONNULL((3));
1219  #ENDIF
1220    /* Like Map_poke, but the key is not copied.  However, \p key will be freed if it is not
1221     * used for the map.  This means that you pass the responsibility for memory management
1222     * of the key to the map.  In particular, if you use this function for searching
1223     * only (i.e., \p introduce == ERWIN_FALSE, \p overwrite == ERWIN_FALSE), the key will
1224     * always be deallocated.
1225     */
1226  
1227  #IF(oType != void)
1228  Global_ERWIN_EXPORT
1229  int Map_poke_no_ocopy (
1230    iType * /*key_out*/,
1231    oTypeVar * /*value_out*/,
1232    Map_t * /*self*/,
1233    iTypeTouched /*key*/,
1234    oTypeVarParam /*value*/,
1235    Global_ERWIN_BOOL /*introduce*/,
1236    Global_ERWIN_BOOL /*overwrite*/) ATTR_NONNULL((3));
1237    /* Like Map_poke, but the value is not copied.  However, value may be freed if
1238     * value_out is NULL.  The rules for copying and freeing values are the same as
1239     * for key with Map_poke_no_icopy.
1240     */
1241  
1242  Global_ERWIN_EXPORT
1243  int Map_poke_no_icopy_no_ocopy (
1244    iType * /*key_out*/,
1245    oTypeVar * /*value_out*/,
1246    Map_t * /*self*/,
1247    iTypeVarParam /*key*/,
1248    oTypeVarParam /*value*/,
1249    Global_ERWIN_BOOL /*introduce*/,
1250    Global_ERWIN_BOOL /*overwrite*/) ATTR_NONNULL((3));
1251    /* Like Map_poke, but neither the key nor the value are copied.  Both, key and value
1252     * may be freed.  The rules for copying and freeing keys and values are the same
1253     * as for Map_poke_no_icopy and Map_poke_no_ocopy.
1254     */
1255  #ENDIF
1256  
1257  Global_ERWIN_EXPORT
1258  oTypeResult Map_zero (Map_t const* /*self*/) ATTR_PURE ATTR_NONNULL((1));
1259    /* Returns the zero element of oType
1260     *
1261     * \noerrno
1262     */
1263  
1264  Global_ERWIN_EXPORT
1265  int Map_cmp (Map_t const* /*self*/, Map_t const * /*other */) ATTR_ERRNO_PURE;
1266    /* Returns a comparison value for the two maps.  The keys must be sortable for this to
1267     * work.  Maps are invariant in the actual storage order in the hash table.
1268     *
1269     * Note: This operation is expensive and needs additional space for copying the
1270     *       keys of self for sorting!
1271     *
1272     * For equality tests, use Map_equal instead, which is faster.
1273     *
1274     * The comparison value is as follows:
1275     *    a) the map that contains most elements is assumed largest.
1276     *    b) for equally sized maps, a lexical order is used by sorting the keys and
1277     *       comparing the values of the two maps.  'Not contained' is assumed
1278     *       smallest.
1279     *
1280     * Further Note: Calling this results in a runtime error if either
1281     *    Global_iType_CMP or Global_oType_CMP is not defined.
1282     *
1283     * \errno(OK, ERR_NOMEM)
1284     */
1285  
1286  Global_ERWIN_EXPORT
1287  Global_ERWIN_BOOL Map_equal (Map_t const* /*self*/, Map_t const * /*other */) ATTR_ERRNO_PURE;
1288    /* Returns whether two maps are equal.  (Of course, maps are invariant in the
1289     * actual storage order in the hash table.)
1290     *
1291     * Note: This operation is quite expensive but *much* *less* *expensive*
1292     *       than Map_cmp!
1293     *
1294     * Further Note: Calling this results in a runtime error if
1295     * Global_oType_EQUAL is not defined.
1296     *
1297     * \errno(OK)
1298     */
1299  
1300  Global_ERWIN_EXPORT
1301  int Map_cmp_keys (Map_t const* /*self*/, Map_t const * /*other */) ATTR_ERRNO_PURE;
1302    /* Returns whether the set of keys in the map is equal.
1303     *
1304     * Note: This operation is quite expensive.  Use keys_equal
1305     *                if that is sufficient.
1306     *
1307     * Further Note: Calling this results in a runtime error if either
1308     *    Global_iType_CMP is not defined.
1309     *
1310     * \errno(OK, ERR_NOMEM)
1311     */
1312  
1313  Global_ERWIN_EXPORT
1314  Global_ERWIN_BOOL Map_equal_keys (Map_t const* /*self*/, Map_t const * /*other */) ATTR_ERRNO_PURE;
1315    /* Returns whether the set of keys in the map is equal.
1316     *
1317     * Note: This operation is quite expensive but less expensive than
1318     *                Map_keys_cmp
1319     *
1320     * \errno(OK)
1321     */
1322  
1323  Global_ERWIN_EXPORT
1324  Global_hashval_t Map_hash_raw (Map_t const * /*self*/) ATTR_ERRNO_PURE;
1325    /* Calculates a hash value for this hash table.  In earlier versions of Erwin,
1326     * the result was inferior to that of Map_hash, but they are now the same
1327     * and no additional hashing of the result needs to be done.
1328     *
1329     * Note: Calling this results in a runtime error if Global_oType_HASH is not defined.
1330     *
1331     * \errno(OK)
1332     */
1333  
1334  ERWIN_WRAPPER Global_hashval_t Map_hash (Map_t const *) ATTR_ERRNO_PURE;
1335      /* Same as Map_hash_raw() now that hash_raw() is good enough. */
1336  
1337  ERWIN_WRAPPER Global_hashval_t Map_hash (Map_t const *x)
1338  {
1339      return Map_hash_raw(x);
1340  }
1341  
1342  
1343  /* ***** access to all entries: ***** */
1344  Global_ERWIN_EXPORT
1345  void Map_clear (Map_t* /*self*/);
1346     /* Like Map_erase for all elements
1347      *
1348      * \errno(OK)
1349      */
1350  
1351  Global_ERWIN_EXPORT
1352  void Map_clear_no_resize (Map_t* /*self*/);
1353     /* Like Map_erase for all elements, but does not shrink the internal hash table.
1354      *
1355      * \errno(OK)
1356      */
1357  
1358  Global_ERWIN_EXPORT
1359  void Map_clear_flags (
1360      Map_t* /*self*/,
1361      Global_ERWIN_BOOL     /*destroy_keys*/,
1362      Global_ERWIN_BOOL     /*destroy_values*/);
1363     /* Clear and selectively free the map
1364      *
1365      * \errno(OK)
1366      */
1367  
1368  Global_ERWIN_EXPORT
1369  void Map_clear_flags_no_resize (
1370      Map_t* /*self*/,
1371      Global_ERWIN_BOOL     /*destroy_keys*/,
1372      Global_ERWIN_BOOL     /*destroy_values*/);
1373     /* Like Map_clear_flags, but does not shrink the internal hash table.
1374      *
1375      * \errno(OK)
1376      */
1377  
1378  Global_ERWIN_EXPORT
1379  int Map_nentries (Map_t const* /*self*/) ATTR_PURE;
1380     /* Returns the number of entries (pairs of keys and values)
1381      *
1382      * \noerrno
1383      */
1384  
1385  Global_ERWIN_EXPORT
1386  Global_ERWIN_BOOL Map_empty (Map_t const* /*self*/) ATTR_PURE;
1387     /* Returns whether map has 0 entries
1388      *
1389      * \noerrno
1390      */
1391  
1392  Global_ERWIN_EXPORT
1393  Map_pair_t *Map_get_entries (Map_t const* /*self*/) ATTR_MALLOC;
1394     /* Use Map_delete_entries to deallocate the returned array.
1395      *
1396      * \errno(OK, ERR_NOMEM)
1397      */
1398  
1399  Global_ERWIN_EXPORT
1400  void Map_delete_entries (Map_pair_t * /*entries*/);
1401     /* Deallocate keys obtained by Map_get_entries(). */
1402  
1403  
1404  #IF(oType != void)
1405  Global_ERWIN_EXPORT
1406  Map_pair_ptr_t *Map_get_entries_ptr (Map_t const* /*self*/) ATTR_MALLOC;
1407     /* Usp Map_delete_entries_ptr to deallocate the returned array.
1408      *
1409      * \errno(OK, ERR_NOMEM) */
1410  
1411  Global_ERWIN_EXPORT
1412  void Map_delete_entries_ptr (Map_pair_ptr_t * /*entries_ptr*/);
1413     /* Deallocate keys obtained by Map_get_entries_ptr(). */
1414  
1415  Global_ERWIN_EXPORT
1416  oType *Map_get_values (Map_t const* /*self*/) ATTR_MALLOC;
1417     /* \errno(OK, ERR_NOMEM) */
1418  
1419  Global_ERWIN_EXPORT
1420  void Map_delete_values (oType * /*values*/);
1421     /* Deallocate keys obtained by Map_get_values(). */
1422  #ENDIF(oType==void)
1423  
1424  Global_ERWIN_EXPORT
1425  iType *Map_get_keys   (Map_t const* /*self*/) ATTR_MALLOC;
1426     /* Get all keys, values, or key/value pairs as a normal standard C array.
1427      * The elements and keys are *not* copied.   The array will be terminated
1428      * with the zero value.
1429      *
1430      * Note: The returned maps are newly allocated and must eventually be
1431      *       freed by the user using Map_delete_keys().  In earlier versions
1432      *       of Erwin, free() was recommended for freeing, but due to more
1433      *       sophisticated memory management, Map_delete_keys() is the
1434      *       primary choice now.  It old code, no adjustment should be
1435      *       necessary, since this is only different if you
1436      *       customise Global_ERWIN_TMALLOC etc.
1437      *
1438      * \errno(OK, ERR_NOMEM)
1439      */
1440  
1441  Global_ERWIN_EXPORT
1442  void Map_delete_keys (iType * /*keys*/);
1443     /* Deallocate keys obtained by Map_get_keys(). */
1444  
1445  
1446  /* ***** debugging and special purposes (use rarely!): ***** */
1447  Global_ERWIN_EXPORT
1448  int Map_hash_size (Map_t const* /*self*/) ATTR_PURE;
1449     /* Returns the size of the internal array of list pointers used to implement
1450      * the hash table.
1451      *
1452      * \noerrno
1453      */
1454  
1455  Global_ERWIN_EXPORT
1456  void Map_rehash (Map_t* /*self*/, int /*newsize*/);
1457     /* Do a manual rehash.   If Global_map_errno holds anything other than MAP_OK,
1458      * the map operation did not succeed.  However, the map is guaranteed to be
1459      * usable after the function call; either rehashed or original.
1460      * The return type is set to void because the function should not be
1461      * considered failed if anything bad has happened.
1462      *
1463      * \errno(OK, REHASH_*)
1464      */
1465  
1466  Global_ERWIN_EXPORT
1467  Global_ERWIN_BOOL Map_expect_size (Map_t* /*self*/, int /*newsize*/);
1468     /* Declare that the immediately following action will
1469      * insert or delete elements so that the new number of
1470      * elements will be newsize.  This will possibly rehash
1471      * to a hash size that requires no rehashes during the
1472      * following operation.  Note: this only works if you
1473      * consistently insert or consistently delete elements.
1474      * If you mix the operations, further rehashes might
1475      * occur.
1476      *
1477      * Returns whether a rehash was performed.
1478      *
1479      * \errno(OK, REHASH_*)
1480      */
1481  
1482  Global_ERWIN_EXPORT
1483  double Map_average_line_length (Map_t const* /*self*/) ATTR_PURE;
1484  
1485  Global_ERWIN_EXPORT
1486  double Map_variance_line_length (Map_t const* /*self*/) ATTR_PURE;
1487  
1488  #ifdef HAVE_SQRT
1489  Global_ERWIN_EXPORT
1490  double Map_deviation_line_length (Map_t const* /*self*/) ATTR_PURE;
1491  #endif
1492  
1493  Global_ERWIN_EXPORT
1494  int Map_max_line_length (Map_t const* /*self*/) ATTR_PURE;
1495  
1496  Global_ERWIN_EXPORT
1497  int Map_min_line_length (Map_t const* /*self*/) ATTR_PURE;
1498  
1499  Global_ERWIN_EXPORT
1500  void Map_dump (FILE *, Map_t const * /*self*/);
1501    /* Dumps the internal structure of the map to the given file. */
1502  
1503  /* ***** iteration: ***** */
1504  /* New approach: */
1505  #define Map_forall_nondet(h,i,k,v) \
1506          for(Map_init_iterator ((h),&i); \
1507              Map_next_iteration ((h),&i,&k,&v);)
1508  /* Operator for non-deterministic hash iteration.  This is non-deterministic even if
1509   * Global_ERWIN_REQUIRE_DETERMINISM is #defined.
1510   *
1511   * This iterates over keys and values.  You need a map_iterator_t as a temporary for
1512   * using this.  See Map_forall for details.
1513   */
1514  
1515  #define Map_forall_ptr_nondet(h,i,k,v) \
1516          for(Map_init_iterator ((h),&i); \
1517              Map_next_iteration_ptr ((h),&i,&k,&v);)
1518  /* Operator for non-deterministic hash iteration.  This is non-deterministic even if
1519   * Global_ERWIN_REQUIRE_DETERMINISM is #defined.
1520   *
1521   * This iterates over keys and pointers to values.  You need a map_iterator_t as a
1522   * temporary for using this.  See Map_forall for details.  Iterating over pointers
1523   * allows you to change entries in the table on the fly.
1524   */
1525  
1526  #define Map_forall_values_nondet(h,i,v) \
1527          for(Map_init_iterator ((h),&i); \
1528              Map_next_iteration_values ((h),&i,&v);)
1529  /* Operator for non-deterministic hash iteration.  This is non-deterministic even if
1530   * Global_ERWIN_REQUIRE_DETERMINISM is #defined.
1531   *
1532   * This iterates over values only.  You need a map_iterator_t as a temporary for
1533   * using this.  See Map_forall for details.
1534   */
1535  
1536  #define Map_forall_values_ptr_nondet(h,i,v) \
1537          for(Map_init_iterator ((h),&i); \
1538              Map_next_iteration_values_ptr ((h),&i,&v);)
1539  /* Operator for non-deterministic hash iteration.  This is non-deterministic even if
1540   * Global_ERWIN_REQUIRE_DETERMINISM is #defined.
1541   *
1542   * This iterates over values only.  You need a map_iterator_t as a temporary for
1543   * using this.  See Map_forall for details.  Iterating over pointers
1544   * allows you to change entries in the table on the fly.
1545   */
1546  
1547  #define Map_forall_keys_nondet(h,i,k) \
1548          for(Map_init_iterator ((h),&i); \
1549              Map_next_iteration_keys ((h),&i,&k);)
1550  /* Operator for non-deterministic hash iteration.  This is non-deterministic even if
1551   * Global_ERWIN_REQUIRE_DETERMINISM is #defined.
1552   *
1553   * This iterates over keys only.  You need a map_iterator_t as a temporary for
1554   * using this.  See Map_forall for details.
1555   */
1556  
1557  #define Map_forall_pairs_nondet(h,i,p) \
1558          for(Map_init_iterator ((h),&i); \
1559              Map_next_iteration_pairs ((h),&i,&p);)
1560  /* Operator for non-deterministic hash iteration.  This is non-deterministic even if
1561   * Global_ERWIN_REQUIRE_DETERMINISM is #defined.
1562   *
1563   * This iterates over key/value pairs.  You need a map_iterator_t as a temporary for
1564   * using this.  See Map_forall for details.
1565   */
1566  
1567  #define Map_forall_pairs_ptr_nondet(h,i,p) \
1568          for(Map_init_iterator ((h),&i); \
1569              Map_next_iteration_pairs_ptr ((h),&i,&p);)
1570  /* Operator for non-deterministic hash iteration.  This is non-deterministic even if
1571   * Global_ERWIN_REQUIRE_DETERMINISM is #defined.
1572   *
1573   * This iterates over key/value pairs.  You need a map_iterator_t as a temporary for
1574   * using this.  See Map_forall for details.  Iterating over pointers
1575   * allows you to change entries in the table on the fly.
1576   */
1577  
1578  #if !defined (Global_ERWIN_REQUIRE_DETERMINISM) || defined (Global_ERWIN_WEAK_DETERMINISM)
1579     /* Only have these implementations if the user does not require
1580      * non-determinism. */
1581  
1582  #  define Map_forall(h,i,k,v) Map_forall_nondet(h,i,k,v)
1583  /* Operator for hash iteration.  This iterates over keys and values.  To use it,
1584   * declare an additional map_iterator_t.  Example:
1585   *    : map_int_char_p_t *m= map_int_char_p_new ();
1586   *    : ...
1587   *    : int i;
1588   *    : char *s;
1589   *    : map_iterator_t iter;
1590   *    : map_int_char_p_forall (m, iter, i, s) {
1591   *    :     printf ("key=%d, value=%s\n", i, s);
1592   *    : }
1593   */
1594  
1595  #  define Map_forall_ptr(h,i,k,v) Map_forall_ptr_nondet(h,i,k,v)
1596  /* Works similar to map_forall.
1597   *
1598   * This iterates over keys and pointers to values.  You need a map_iterator_t as a
1599   * temporary for using this.  See Map_forall for details.  Iterating over pointers
1600   * allows you to change entries in the table on the fly.
1601   */
1602  
1603  #  define Map_forall_values(h,i,v) Map_forall_values_nondet(h,i,v)
1604  /* Works similar to map_forall.
1605   *
1606   * This iterates over values only.  You need a map_iterator_t as a temporary for
1607   * using this.  See Map_forall for details.
1608   */
1609  
1610  #  define Map_forall_values_ptr(h,i,v) Map_forall_values_ptr_nondet(h,i,v)
1611  /* Works similar to map_forall.
1612   *
1613   * This iterates over values only.  You need a map_iterator_t as a temporary for
1614   * using this.  See Map_forall for details.  Iterating over pointers
1615   * allows you to change entries in the table on the fly.
1616   */
1617  
1618  #  define Map_forall_keys(h,i,k)   Map_forall_keys_nondet(h,i,k)
1619  /* Works similar to map_forall.
1620   *
1621   * This iterates over keys only.  You need a map_iterator_t as a temporary for
1622   * using this.  See Map_forall for details.
1623   */
1624  
1625  #  define Map_forall_pairs(h,i,p)  Map_forall_pairs_nondet(h,i,p)
1626  /* Works similar to map_forall.
1627   *
1628   * This iterates over key/value pairs.  You need a map_iterator_t as a temporary for
1629   * using this.  See Map_forall for details.
1630   */
1631  
1632  #  define Map_forall_pairs_ptr(h,i,p)  Map_forall_pairs_ptr_nondet(h,i,p)
1633  /* Works similar to map_forall.
1634   *
1635   * This iterates over key/value pairs.  You need a map_iterator_t as a temporary for
1636   * using this.  See Map_forall for details.  Iterating over pointers
1637   * allows you to change entries in the table on the fly.
1638   */
1639  
1640  #endif
1641  
1642  /* The following function should not be invoked by the user! */
1643  /* BEGIN: Generated automatically by makeforall.pl (part of Erwin2) */
1644  
1645  Global_ERWIN_EXPORT
1646  void Map_init_iterator (Map_t const *, Global_map_iterator_t *);
1647  /*private*/
1648  
1649  #ifdef __cplusplus
1650  Global_ERWIN_EXPORT
1651  void Map_init_iterator_sorted_by_key (Map_t const *, Global_map_iterator_sorted_t *);
1652  /*private*/
1653  
1654  #IF(oType != void)
1655  Global_ERWIN_EXPORT
1656  void Map_init_iterator_sorted_by_value (Map_t const *, Global_map_iterator_sorted_t *);
1657  /*private*/
1658  
1659  Global_ERWIN_EXPORT
1660  void Map_init_iterator_sorted_by_key_and_value (Map_t const *, Global_map_iterator_sorted_t *);
1661  /*private*/
1662  
1663  Global_ERWIN_EXPORT
1664  void Map_init_iterator_sorted_by_value_and_key (Map_t const *, Global_map_iterator_sorted_t *);
1665  /*private*/
1666  #ENDIF
1667  
1668  Global_ERWIN_EXPORT
1669  void Map_init_iterator_sorted_by_user (Map_t const *, Global_map_iterator_sorted_t *,
1670      Map_pair_cmp_t);
1671  /*private*/
1672  
1673  #IF(oType != void)
1674  Global_ERWIN_EXPORT                       
1675  void Map_init_iterator_ptr_sorted_by_key (Map_t const *, Global_map_iterator_sorted_t *);
1676  /*private*/
1677  
1678  Global_ERWIN_EXPORT
1679  void Map_init_iterator_ptr_sorted_by_value (Map_t const *, Global_map_iterator_sorted_t *);
1680  /*private*/
1681  
1682  Global_ERWIN_EXPORT
1683  void Map_init_iterator_ptr_sorted_by_key_and_value (Map_t const *, Global_map_iterator_sorted_t *);
1684  /*private*/
1685  
1686  Global_ERWIN_EXPORT
1687  void Map_init_iterator_ptr_sorted_by_value_and_key (Map_t const *, Global_map_iterator_sorted_t *);
1688  /*private*/
1689  
1690  Global_ERWIN_EXPORT
1691  void Map_init_iterator_ptr_sorted_by_user (Map_t const *, Global_map_iterator_sorted_t *,
1692      Map_pair_ptr_cmp_t);
1693  /*private*/
1694  #ENDIF(oType != void)
1695  
1696  Global_ERWIN_EXPORT
1697  void Map_init_iterator_sorted_by_key_reverse (Map_t const *, Global_map_iterator_sorted_t *);
1698  /*private*/
1699  
1700  #IF(oType != void)
1701  Global_ERWIN_EXPORT
1702  void Map_init_iterator_sorted_by_value_reverse (Map_t const *, Global_map_iterator_sorted_t *);
1703  /*private*/
1704  
1705  Global_ERWIN_EXPORT
1706  void Map_init_iterator_sorted_by_key_and_value_reverse (
1707      Map_t const *, Global_map_iterator_sorted_t *);
1708  /*private*/
1709  
1710  Global_ERWIN_EXPORT
1711  void Map_init_iterator_sorted_by_value_and_key_reverse (
1712     Map_t const *, Global_map_iterator_sorted_t *);
1713  /*private*/
1714  #ENDIF
1715  
1716  Global_ERWIN_EXPORT
1717  void Map_init_iterator_sorted_by_user_reverse (
1718      Map_t const *, Global_map_iterator_sorted_t *, Map_pair_cmp_t);
1719  /*private*/
1720  
1721  #IF(oType != void)
1722  Global_ERWIN_EXPORT
1723  void Map_init_iterator_ptr_sorted_by_key_reverse (Map_t const *, Global_map_iterator_sorted_t *);
1724  /*private*/
1725  
1726  Global_ERWIN_EXPORT
1727  void Map_init_iterator_ptr_sorted_by_value_reverse (Map_t const *, Global_map_iterator_sorted_t *);
1728  /*private*/
1729  
1730  Global_ERWIN_EXPORT
1731  void Map_init_iterator_ptr_sorted_by_key_and_value_reverse (
1732      Map_t const *, Global_map_iterator_sorted_t *);
1733  /*private*/
1734  
1735  Global_ERWIN_EXPORT
1736  void Map_init_iterator_ptr_sorted_by_value_and_key_reverse (
1737      Map_t const *, Global_map_iterator_sorted_t *);
1738  /*private*/
1739  
1740  Global_ERWIN_EXPORT
1741  void Map_init_iterator_ptr_sorted_by_user_reverse (
1742      Map_t const *, Global_map_iterator_sorted_t *, Map_pair_ptr_cmp_t);
1743  /*private*/
1744  
1745  Global_ERWIN_EXPORT
1746  Global_ERWIN_BOOL Map_next_iteration_sorted (Map_t const *, Global_map_iterator_sorted_t *,
1747      iType *, oType *);
1748  /*private*/
1749  
1750  Global_ERWIN_EXPORT
1751  Global_ERWIN_BOOL Map_next_iteration_sorted_ptr (Map_t const *, Global_map_iterator_sorted_t *,
1752      iType *, Map_element_ptr_t *);
1753  /*private*/
1754  #ENDIF
1755  
1756  Global_ERWIN_EXPORT
1757  Global_ERWIN_BOOL Map_next_iteration_sorted_keys (Map_t const *,
1758      Global_map_iterator_sorted_t *, iType *);
1759  /*private*/
1760  
1761  #IF(oType != void)
1762  Global_ERWIN_EXPORT
1763  Global_ERWIN_BOOL Map_next_iteration_sorted_values (Map_t const *,
1764      Global_map_iterator_sorted_t *, oType *);
1765  /*private*/
1766  
1767  Global_ERWIN_EXPORT
1768  Global_ERWIN_BOOL Map_next_iteration_sorted_values_ptr (Map_t const *,
1769      Global_map_iterator_sorted_t *, Map_element_ptr_t *);
1770  /*private*/
1771  #ENDIF
1772  
1773  Global_ERWIN_EXPORT
1774  Global_ERWIN_BOOL Map_next_iteration_sorted_pairs (Map_t const *,
1775      Global_map_iterator_sorted_t *, Map_pair_t *);
1776  /*private*/
1777  
1778  #IF(oType != void)
1779  Global_ERWIN_EXPORT
1780  Global_ERWIN_BOOL Map_next_iteration_sorted_pairs_ptr (Map_t const *,
1781      Global_map_iterator_sorted_t *, Map_pair_ptr_t *);
1782  /*private*/
1783  #ENDIF
1784  
1785  #IF(oType != void)
1786  Global_ERWIN_EXPORT
1787  Global_ERWIN_BOOL Map_next_iteration_sorted_reverse (
1788      Map_t const *, Global_map_iterator_sorted_t *, iType *, oType *);
1789  /*private*/
1790  
1791  Global_ERWIN_EXPORT
1792  Global_ERWIN_BOOL Map_next_iteration_sorted_ptr_reverse (
1793      Map_t const *, Global_map_iterator_sorted_t *, iType *, Map_element_ptr_t *);
1794  /*private*/
1795  #ENDIF
1796  
1797  Global_ERWIN_EXPORT
1798  Global_ERWIN_BOOL Map_next_iteration_sorted_keys_reverse (Map_t const *,
1799      Global_map_iterator_sorted_t *, iType *);
1800  /*private*/
1801  
1802  #IF(oType != void)
1803  Global_ERWIN_EXPORT
1804  Global_ERWIN_BOOL Map_next_iteration_sorted_values_reverse (Map_t const *,
1805      Global_map_iterator_sorted_t *, oType *);
1806  /*private*/
1807  
1808  Global_ERWIN_EXPORT
1809  Global_ERWIN_BOOL Map_next_iteration_sorted_values_ptr_reverse (Map_t const *,
1810      Global_map_iterator_sorted_t *, Map_element_ptr_t *);
1811  /*private*/
1812  #ENDIF
1813  
1814  Global_ERWIN_EXPORT
1815  Global_ERWIN_BOOL Map_next_iteration_sorted_pairs_reverse (Map_t const *,
1816      Global_map_iterator_sorted_t *, Map_pair_t *);
1817  /*private*/
1818  
1819  #IF(oType != void)
1820  Global_ERWIN_EXPORT
1821  Global_ERWIN_BOOL Map_next_iteration_sorted_pairs_ptr_reverse (Map_t const *,
1822      Global_map_iterator_sorted_t *, Map_pair_ptr_t *);
1823  /*private*/
1824  #ENDIF
1825  
1826  #endif /* defined(__cplusplus) */
1827  
1828  #IF(oType != void)
1829  Global_ERWIN_EXPORT
1830  Global_ERWIN_BOOL Map_next_iteration  (Map_t const* /*self*/,
1831      Global_map_iterator_t *, iType * /*key*/, oType * /*value*/);
1832  /*private*/
1833  
1834  Global_ERWIN_EXPORT
1835  Global_ERWIN_BOOL Map_next_iteration_ptr  (Map_t const* /*self*/,
1836      Global_map_iterator_t *, iType * /*key*/, Map_element_ptr_t * /*value_ptr*/);
1837  /*private*/
1838  
1839  Global_ERWIN_EXPORT
1840  Global_ERWIN_BOOL Map_next_iteration_values  (Map_t const * /*self*/,
1841      Global_map_iterator_t *, oType * /* value */);
1842  /*private*/
1843  
1844  Global_ERWIN_EXPORT
1845  Global_ERWIN_BOOL Map_next_iteration_values_ptr  (Map_t const * /*self*/,
1846      Global_map_iterator_t *, Map_element_ptr_t * /* value_ptr */);
1847  /*private*/
1848  #ENDIF
1849  
1850  Global_ERWIN_EXPORT
1851  Global_ERWIN_BOOL Map_next_iteration_keys  (Map_t const* /*self*/,
1852      Global_map_iterator_t *, iType * /* key */);
1853  /*private*/
1854  
1855  Global_ERWIN_EXPORT
1856  Global_ERWIN_BOOL Map_next_iteration_pairs (Map_t const* /*self*/,
1857      Global_map_iterator_t *, Map_pair_t * /*pair*/);
1858  /*private*/
1859  
1860  #IF(oType != void)
1861  Global_ERWIN_EXPORT
1862  Global_ERWIN_BOOL Map_next_iteration_pairs_ptr (Map_t const* /*self*/,
1863      Global_map_iterator_t *, Map_pair_ptr_t * /*pair*/);
1864  /*private*/
1865  #ENDIF
1866  
1867  #ifdef Global_ERWIN_PROFILE
1868  
1869  Global_ERWIN_EXPORT
1870  int Map_nrehash_ops (Map_t const* /*self*/) ATTR_PURE;
1871  
1872  Global_ERWIN_EXPORT
1873  int Map_nrehash (Map_t const* /*self*/) ATTR_PURE;
1874    /* rehash_ops is the number of pure rehash operations and rehash
1875     * is the number of elements moved around during rehashes */
1876  
1877  Global_ERWIN_EXPORT
1878  int Map_ninsert (Map_t const* /*self*/) ATTR_PURE;
1879  
1880  Global_ERWIN_EXPORT
1881  int Map_nremove (Map_t const* /*self*/) ATTR_PURE;
1882  
1883  Global_ERWIN_EXPORT
1884  int Map_nfind (Map_t const* /*self*/) ATTR_PURE;
1885  
1886  Global_ERWIN_EXPORT
1887  int Map_nops (Map_t const* /*self*/) ATTR_PURE;
1888    /* Sum of inserts, deletions, and searches */
1889  
1890    /* Most interesting are Map_nops / Map_nrehash. */
1891  #endif
1892  
1893  /*--END-C--*/
1894  
1895  /*
1896   * Unfortunately, for a good implementation of the C++ class, we need to
1897   * include the file showing the internal structure of an map.  This
1898   * is only to give the compiler information about the size of the
1899   * structure.  I don't like an #ifdef'd include, so always include this:
1900   */
1901  #include "#Map_i.ErwinHExt"
1902  
1903  #IFCPPONLY
1904  #ELSE
1905  #ifdef __cplusplus
1906  } /* extern "C" */
1907  #endif
1908  #ENDIF
1909  
1910  struct Map_t
1911  #ifdef Map_SUPER_CLASS
1912     : Map_SUPER_CLASS_ACCESS Map_SUPER_CLASS
1913  #endif
1914  {
1915      /* The Map Class
1916       * =============
1917       * This class implements hash tables.
1918       *
1919       * Throughout the documentation, the following prefixes will be used:
1920       *   - Global_:
1921       *       The library prefix: for applications, this is typically
1922       *       empty, for an xyz-Library, this is either \tt(XYZ_), \tt(xyz_) or
1923       *       \tt(Xyz), depending on the identifier in occurs in.
1924       *       +------------------+-----------------+
1925       *       |! Template        |! Instantiation  |
1926       *       | Global_MAP_OK    | XYZ_MAP_OK      |
1927       *       | Global_map_new   | xyz_map_new     |
1928       *       +------------------+-----------------+
1929       *
1930       *   - Map_:
1931       *       This is equivalent to Global_map_iType_oType, or the name
1932       *       that was set with \tt(-name=...) for this data structure.
1933       *       The case and underbar convention is adjusted, too.
1934       *
1935       *       Assuming a library prefix \tt(xyz) and iType=int *,
1936       *       oType == int, you get:
1937       *       +-------------------+------------------------------+
1938       *       |! Template         |! Instantiation               |
1939       *       | Map_t             | xyz_map_int_p_int_t          |
1940       *       | Map_ALLOW_NULL    | XYZ_MAP_INT_P_INT_ALLOW_NULL |
1941       *       +-------------------+------------------------------+
1942       *   - Map_class:
1943       *       This is the name of the data structure type in C++: capitalised
1944       *       and with underbars removed:
1945       *       +-------------------+-----------------+
1946       *       |! Map_t            |! Map_class      |
1947       *       | map_int_p_int_t   | MapIntPInt      |
1948       *       +-------------------+-----------------+
1949       *
1950       * In the following, for many functions, the error code values are given.  There are
1951       * two kinds, those for success and those for failure.  The error codes (if set at all)
1952       * are  always stored in the global variable Global_map_errno, no mattern whether the function
1953       * returns its success or not.  Note that the error value MAP_ERR_ASSERTIONFAILED
1954       * is never explicitly given, because it
1955       *
1956       *   - can happen virtually always
1957       *
1958       *   - is considered a fatal error and should therefore lead to program
1959       *     abortion immediately.
1960       *
1961       * Successful operation is indicated by Global_MAP_OK, Global_MAP_WARN_*, and
1962       * Global_MAP_REHASH*.
1963       *
1964       * Failure is indicated by Global_MAP_ERR_*.  If a functions does not return the error code,
1965       * its result value in case of an error is _always_ the zero element of the result type.
1966       * I.e. NULL for pointers, 0 for integers, the user specified zero element for iType or oType,
1967       * Global_ERWIN_FALSE for Global_ERWIN_BOOL, etc.
1968       *
1969       * Functions that only set map_errno to Global_MAP_REHASH_* or Global_MAP_OK will return
1970       * void if they do not have a natural result.
1971       *
1972       * Note: The term `success' means that the function could perform its operation
1973       *       according to the specification.  E.g. if you call _insert and the
1974       *       key exists, the functions does not insert it.  However, this is no
1975       *       error.  It is defined that it should not be inserted in this case.
1976       *       Accordingly, you get a warning, not an error.
1977       */
1978  
1979      Map_STD_MEMBERS(Map_t)
1980  
1981  #ifdef __cplusplus
1982  public:
1983  #endif
1984  
1985      Map_record
1986  
1987  #ifdef __cplusplus
1988  
1989      /*! doc-ignore */
1990      Map_t *it()             { return this; }
1991  
1992      /*! doc-ignore */
1993      Map_t const *it() const { return this; }
1994  
1995  protected:
1996  #ifndef NDEBUG
1997      void cn() const;
1998      void cn(void const *) const;
1999  #else
2000      /* Hopefully optimised away: */
2001      static void cn() {}
2002      static void cn(void const *) {}
2003  #endif
2004      static void nocn() {}             /* makes explicit that functions might handle NULL well. */
2005      static void nocn(void const *) {} /* makes explicit that functions might handle NULL well. */
2006  
2007  /*--BEGIN-CLASS--*/
2008  public:
2009  #ifdef __cplusplus
2010  #if !Global_ERWIN_DEFAULT_NEW_DELETE
2011      static void *operator new(size_t);
2012      static void operator delete(void *, size_t);
2013      static void *operator new[](size_t);
2014      static void operator delete[](void *, size_t);
2015  #endif
2016  #endif
2017  
2018      /* Creation */
2019  
2020      Map_t (void);
2021  
2022      static Map_t const &static_zero();
2023  
2024  #if Map_HAVE_INT_CONSTRUCTOR
2025      Global_ERWIN_EXPLICIT Map_t (int initial_size);
2026  #endif
2027  #if Map_DYN_ZERO
2028      Global_ERWIN_EXPLICIT Map_t (oTypeTouched zero_element);
2029      Map_t (oTypeTouched zero_element, int initial_size);
2030  #endif
2031  
2032      /* status code */
2033  #if !Global_ERWIN_GLOBAL_ERRNO
2034      int get_errno(void) const        { cn(); return it()->m_errno; }
2035      void clear_errno(void) const     { cn(); Map_clear_errno (it()); }
2036  #else
2037      static int get_errno(void)       { return Global_map_errno; }
2038      static void clear_errno(void)    { Global_map_errno= Global_MAP_OK; }
2039  #endif
2040  
2041      /* Copying */
2042  
2043      Global_ERWIN_EXPLICIT Map_t (Map_t const *a);
2044  
2045      Map_t (Map_t const &a);
2046  
2047      Map_t *copy (void) const
2048      {
2049          cn();
2050          return new Map_t (it());
2051      }
2052  
2053      Map_t *copy_err (int *err) const
2054      {
2055          cn();
2056          Map_t *result= new Map_t (it());
2057          if (err != NULL && Global_MAP_IS_ERROR (get_errno ()))
2058              *err= 1;
2059          return result;
2060      }
2061  
2062      Map_t &xchg(Map_t *other)
2063      {
2064          Map_xchg (it(), other);
2065          return *this;
2066      }
2067  
2068      Map_t &xchg(Map_t &other)
2069      {
2070          Map_xchg (this, &other);
2071          return *this;
2072      }
2073  
2074      /* Assignment */
2075  
2076      Map_t &operator= (Map_t const &);
2077  
2078      Map_t &operator= (Map_t const *);
2079          /* without this, it would be copied twice */
2080  
2081      void _constructor (void);
2082          /* Quite private: do not use unless you know what you're doing:
2083           *
2084           * This constructs the map for a given preallocated memory location.
2085           *
2086           * FIXME: There should be an operator new() for this. */
2087  
2088      void _destructor  (void);
2089          /* Quite private: do not use unless you know what you're doing:
2090           *
2091           * Needed if you want to use maps without a pointer in vectors.  vectors use
2092           * C-style memory allocation because they need realloc.  The constructor/destructors
2093           * are invoked via these two functions.
2094           */
2095  
2096      /* Destruction */
2097  
2098      ~Map_t ();
2099          /* There is no delete_flags here in C++, but you can clear_flags() before
2100           * deletion. */
2101  
2102  
2103      /* Conversion to C type.
2104       * DO NOT CALL Map_delete or Map_delete_flags ON THE RETURNED VALUE!
2105       * All other things you do are ok. */
2106  
2107      operator Map_t *(void)             { cn(); return it(); }
2108      operator Map_t const *(void) const { cn(); return it(); }
2109  
2110      /* More operators for easy use: */
2111  
2112  #IF(oTypeIndex == oTypeResult)
2113      /* oTypeIndex == oTypeResult */
2114  
2115      oTypeResult operator[] (iTypeParam i) const
2116      {
2117          nocn();
2118          return Map_find (it(), i);
2119      }
2120  
2121      /* operator int () const { return get_errno(); }
2122       * FIXME: maybe add this one day.  It produces invisible semantics changes with
2123       * old versions when 'explicit' is used as well. */
2124  #IF(oType != void)
2125  #IF(oType == oTypeVar)
2126      oType &operator[] (iTypeTouched i) {
2127          cn();
2128          return *Map_find_ptr_ensure (it(), i);
2129      }
2130  #ENDIF
2131  #ENDIF
2132  
2133  #ELSE
2134      /* oTypeIndex != oTypeResult */
2135  
2136      /* We have an index type, so the user wants an additional dereferencing of
2137       * the result of the operator[].  Note that we cannot provide a non-const
2138       * version of the operator[] here in this setting.  Use find() explicitly
2139       * in this case. */
2140  
2141      oTypeIndex &operator[] (iTypeTouched i) {
2142          cn();
2143          return *Map_find_ensure (it(), i);
2144      }
2145  
2146  #ENDIF
2147  
2148  #IF(oType != void)
2149  #IF(oType == oTypeVar)
2150      oType *find_ptr (iTypeParam i) const
2151          { nocn(); return Map_find_ptr (it(), i); }
2152  
2153      oType *find_ptr_ensure (iTypeTouched i)
2154          { cn(); return Map_find_ptr_ensure (it(), i); }
2155  #ELSE
2156      oType const *find_ptr (iTypeParam i) const
2157          { nocn(); return Map_find_ptr (it(), i); }
2158  
2159      oType const *find_ptr_ensure (iTypeTouched i)
2160          { cn(); return Map_find_ptr_ensure (it(), i); }
2161  #ENDIF
2162  #ENDIF
2163  
2164      /* All other members map to the C equivalent directly. */
2165      oTypeResult find (iTypeParam i) const
2166          { nocn(); return Map_find (it(), i); }
2167        
2168  #IF(oType != void)
2169      oTypeResult find_ensure (iTypeTouched i)
2170          { cn(); return Map_find_ensure (it(), i); }
2171  #ENDIF
2172  
2173      iTypeResult find_any_key() const
2174          { nocn(); return Map_find_any_key (it()); }
2175  
2176  #IF(oType != void)
2177      oTypeResult find_any() const
2178          { nocn(); return Map_find_any (it()); }
2179  
2180      Map_element_ptr_t find_any_ptr() const
2181          { nocn(); return Map_find_any_ptr (it()); }
2182  
2183      int find_any_pair(Map_key_result_t &kp, Map_element_ptr_t &vp) const
2184          { nocn(); return Map_find_any_pair (&kp, &vp, it()); }
2185  #ENDIF
2186  
2187  
2188      /* insert */
2189  #IF(oType == void)
2190      Map_t  &insert (iTypeTouched k)
2191          { cn(); Map_insert (it(), k); return *this; }
2192  #ELSE
2193      Map_t  &insert (iTypeTouched k, oTypeTouched v)
2194          { cn(); Map_insert (it(), k, v); return *this; }
2195  #ENDIF
2196  
2197      Map_t  &insert_map (Map_t const &other)
2198          { cn(&other); Map_insert_map (it(), other.it()); return *this; }
2199  
2200      Map_t  &insert_map (Map_t const *other)
2201          { cn(other); Map_insert_map (it(), other->it()); return *this; }
2202  
2203  #if Map_DIRECT_RECURSION == 0
2204      Map_t  &insert (Map_t const &other)
2205          { cn(&other); Map_insert_map (it(), other.it()); return *this; }
2206  
2207      Map_t  &insert (Map_t const *other)
2208          { cn(other); Map_insert_map (it(), other->it()); return *this; }
2209  
2210  #endif
2211  
2212  #IF(oType != void)
2213      /* modify */
2214      oTypeVar modify (iTypeParam i, oTypeTouched v)
2215          { cn(); return Map_modify (it(), i, v); }
2216  
2217      Map_t  &modify_map (Map_t const &other)
2218          { cn(&other);  Map_modify_map (it(), other.it()); return *this; }
2219  
2220      Map_t  &modify_map (Map_t const *other)
2221          { cn(other); Map_modify_map (it(), other->it()); return *this; }
2222  
2223  #if Map_DIRECT_RECURSION == 0
2224      Map_t  &modify (Map_t const &other)
2225          { cn(&other); Map_modify_map (it(), other.it()); return *this; }
2226  
2227      Map_t  &modify (Map_t const *other)
2228          { cn(other); Map_modify_map (it(), other->it()); return *this; }
2229  
2230  #endif
2231  
2232      /* set */
2233  
2234      Map_t  &set (iTypeTouched i, oTypeTouched v)
2235          { cn(); Map_set (it(), i, v); return *this; }
2236  
2237      Map_t  &set_map (Map_t const &other)
2238          { cn(&other); Map_set_map (it(), other.it()); return *this; }
2239  
2240      Map_t  &set_map (Map_t const *other)
2241          { cn(other); Map_set_map (it(), other->it()); return *this; }
2242  
2243  
2244  #if Map_DIRECT_RECURSION == 0
2245      Map_t  &set (Map_t const &other)
2246          { cn(&other); Map_set_map (it(), other.it()); return *this; }
2247  
2248      Map_t  &set (Map_t const *other)
2249          { cn(other); Map_set_map (it(), other->it()); return *this; }
2250  
2251  #endif
2252  
2253      /* remove */
2254      oTypeVar remove (iTypeTouched i)
2255          { nocn(); return Map_remove (it(), i); }
2256  
2257      Map_t &remove_map (Map_t const &other)
2258          { nocn(&other); Map_remove_map (it(), other.it()); return *this; }
2259  
2260      Map_t &remove_map (Map_t const *other)
2261          { nocn(other); Map_remove_map (it(), other->it()); return *this; }
2262  
2263      int remove_if (Map_feature_t f, bool value = true)
2264      {
2265          nocn();
2266          return Map_remove_if (it(), f, value);
2267      }
2268  #ENDIF
2269  #REM oType=void
2270  
2271      /* erase */
2272      Map_t  &erase (iTypeTouched i)
2273          { nocn(); Map_erase (it(), i); return *this; }
2274  
2275      Map_t  &erase_map (Map_t const &other)
2276          { nocn(&other); Map_erase_map (it(), other.it()); return *this; }
2277  
2278      Map_t  &erase_map (Map_t const *other)
2279          { nocn(other); Map_erase_map (it(), other->it()); return *this; }
2280  
2281  #if Map_DIRECT_RECURSION == 0
2282      Map_t  &erase (Map_t const &other)
2283          { nocn(other); Map_erase_map (it(), other.it()); return *this; }
2284  
2285      Map_t  &erase (Map_t const *other)
2286          { nocn(other); Map_erase_map (it(), other->it()); return *this; }
2287  
2288  #endif
2289  
2290      int erase_if (Map_feature_t f, bool value = true)
2291      {
2292          nocn();
2293          return Map_erase_if (it(), f, value);
2294      }
2295  
2296      Map_t &intersect (Map_t const &other)
2297          { nocn(&other); Map_intersect (it(), other.it()); return *this; }
2298  
2299      Map_t &intersect (Map_t const *other)
2300          { nocn(other); Map_intersect (it(), other->it()); return *this; }
2301  
2302      Map_t &intersect_no_resize (Map_t const &other)
2303          { nocn(&other); Map_intersect_no_resize (it(), other.it()); return *this; }
2304  
2305      Map_t &intersect_no_resize (Map_t const *other)
2306          { nocn(other); Map_intersect_no_resize (it(), other->it()); return *this; }
2307  
2308  
2309      /* others */
2310      iTypeResult find_key (iTypeParam i) const { nocn(); return Map_find_key (it(), i); }
2311  
2312      oTypeResult zero(void) const { nocn(); return Map_zero (it()); }
2313  
2314      iTypeResult ensure (iTypeTouched k)
2315          { cn(); return Map_ensure (it(), k); }
2316  
2317      iTypeResult ensure_no_icopy (iTypeVarParam k)
2318          { cn(); return Map_ensure_no_icopy (it(), k); }
2319  
2320      iTypeResult operator() (iTypeTouched k)
2321          { cn(); return Map_ensure (it(), k); }
2322  
2323  #IF(oType == void)
2324      Map_t &poke (
2325          iType *kp,
2326          iTypeTouched k,
2327          bool aintroduce Map_DEFAULT_ARG(true))
2328      {
2329          cn();
2330          Map_poke (kp, it(), k, aintroduce);
2331          return *this;
2332      }
2333  #ELSE
2334      Map_t &poke (
2335          iType *kp, oTypeVar *vo,
2336          iTypeTouched k, oTypeTouched v,
2337          bool aintroduce Map_DEFAULT_ARG(true),
2338          bool aoverwrite Map_DEFAULT_ARG(true))
2339      {
2340          cn();
2341          Map_poke (kp,vo, it(), k,v, aintroduce, aoverwrite);
2342          return *this;
2343      }
2344  #ENDIF
2345  
2346  #IF(oType == void)
2347      Map_t &poke_no_icopy (
2348          iType *kp,
2349          iTypeVarParam k,
2350          bool aintroduce Map_DEFAULT_ARG(true))
2351      {
2352          cn();
2353          Map_poke_no_icopy (kp, it(), k, aintroduce);
2354          return *this;
2355      }
2356  #ELSE
2357      Map_t &poke_no_icopy (
2358          iType *kp, oTypeVar *vo,
2359          iTypeVarParam k, oTypeTouched v,
2360          bool aintroduce Map_DEFAULT_ARG(true),
2361          bool aoverwrite Map_DEFAULT_ARG(true))
2362      {
2363          cn();
2364          Map_poke_no_icopy (kp,vo, it(), k,v, aintroduce, aoverwrite);
2365          return *this;
2366      }
2367  #ENDIF
2368  
2369  #IF(oType != void)
2370      Map_t &poke_no_ocopy (
2371          iType *kp, oTypeVar *vo,
2372          iTypeTouched k, oTypeVarParam v,
2373          bool aintroduce Map_DEFAULT_ARG(true),
2374          bool aoverwrite Map_DEFAULT_ARG(true))
2375      {
2376          cn();
2377          Map_poke_no_ocopy (kp,vo, it(), k,v, aintroduce, aoverwrite);
2378          return *this;
2379      }
2380  
2381      Map_t &poke_no_icopy_no_ocopy (
2382          iType *kp, oTypeVar *vo,
2383          iTypeVarParam k, oTypeVarParam v,
2384          bool aintroduce Map_DEFAULT_ARG(true),
2385          bool aoverwrite Map_DEFAULT_ARG(true))
2386      {
2387          cn();
2388          Map_poke_no_icopy_no_ocopy (kp,vo, it(), k,v, aintroduce, aoverwrite);
2389          return *this;
2390      }
2391  #ENDIF
2392  
2393      /* clear */
2394      Map_t &clear (void)
2395      {
2396          nocn();
2397          Map_clear (it());
2398          return *this;
2399      }
2400  
2401      Map_t &clear_no_resize (void)
2402      {
2403          nocn();
2404          Map_clear_no_resize (it());
2405          return *this;
2406      }
2407  
2408      Map_t &clear (bool k, bool v)
2409      {
2410          nocn();
2411          Map_clear_flags (it(), k, v);
2412          return *this;
2413      }
2414  
2415      int   nentries (void) const                  { nocn(); return Map_nentries (it()); }
2416      bool  empty (void) const                     { nocn(); return Global_ERWIN_TO_BOOL(Map_empty (it())); }
2417      bool  non_empty (void) const                 { nocn(); return !Map_empty (it()); }
2418  
2419      iType          *get_keys   (void) const      { nocn(); return Map_get_keys (it()); }
2420      static void delete_keys        (iType          *k) { Map_delete_keys (k); }
2421  
2422  #IF(oType != void)
2423      Map_pair_t     *get_entries (void) const     { nocn(); return Map_get_entries (it()); }
2424      Map_pair_ptr_t *get_entries_ptr (void) const { nocn(); return Map_get_entries_ptr (it()); }
2425      oType          *get_values (void) const      { nocn(); return Map_get_values (it()); }
2426  
2427      static void delete_entries_ptr (Map_pair_ptr_t *k) { Map_delete_entries_ptr (k); }
2428      static void delete_entries     (Map_pair_t     *k) { Map_delete_entries (k); }
2429      static void delete_values      (oType          *k) { Map_delete_values (k); }
2430  #ENDIF
2431  
2432      int     hash_size (void) const            { nocn(); return Map_hash_size (it()); }
2433      Map_t &rehash (int n)                     { nocn(); Map_rehash (it(), n); return *this;}
2434      double  average_line_length (void) const  { nocn(); return Map_average_line_length (it()); }
2435      double  variance_line_length (void) const { nocn(); return Map_variance_line_length (it()); }
2436  #ifdef HAVE_SQRT
2437      double  deviation_line_length (void) const { nocn(); return Map_deviation_line_length (it()); }
2438  #endif
2439      int     max_line_length (void) const      { nocn(); return Map_max_line_length (it()); }
2440      int     min_line_length (void) const      { nocn(); return Map_min_line_length (it()); }
2441  
2442      void    dump (FILE *f) const              { nocn(); Map_dump (f, it()); }
2443  
2444  #ifdef Global_ERWIN_PROFILE
2445      int     nrehash_ops (void) const          { nocn(); return Map_nrehash_ops (it()); }
2446      int     nrehash (void) const              { nocn(); return Map_nrehash (it()); }
2447      int     ninsert (void) const              { nocn(); return Map_ninsert (it()); }
2448      int     nremove (void) const              { nocn(); return Map_nremove (it()); }
2449      int     nfind (void) const                { nocn(); return Map_nfind (it()); }
2450      int     nops(void) const                  { nocn(); return Map_nops (it()); }
2451  #endif
2452  
2453      Global_hashval_t hash_raw(void) const { nocn(); return Map_hash_raw (it()); }
2454      Global_hashval_t hash(void) const     { nocn(); return Map_hash     (it()); }
2455  
2456      bool equal(Map_t const *other) const
2457      {
2458          if (this == NULL || other == NULL) /* must be NULL-safe */
2459              return this == other;
2460          return Global_ERWIN_TO_BOOL(Map_equal (it(), other->it()));
2461      }
2462  
2463      bool equal(Map_t const &other) const
2464      {
2465          return equal (&other);
2466      }
2467  
2468      int cmp (Map_t const *other) const
2469      {
2470          if (this == NULL)
2471              return other == NULL ? 0 : -1;
2472          if (other == NULL)
2473              return +1;
2474          return Map_cmp (it(), other->it());
2475      }
2476  
2477      int cmp (Map_t const &other) const { nocn(); return cmp (&other); }
2478  
2479      bool operator== (Map_t const &b) const { nocn(); return equal(b); }    /* see equal() */
2480      bool operator== (Map_t const *b) const { nocn(); return equal(b); }    /* see equal() */
2481  
2482      bool operator!= (Map_t const &b) const { nocn(); return !equal(b); }   /* see equal() */
2483      bool operator!= (Map_t const *b) const { nocn(); return !equal(b); }   /* see equal() */
2484  
2485      bool operator<= (Map_t const &b) const { nocn(); return cmp(b) <= 0; } /* see cmp() */
2486      bool operator<= (Map_t const *b) const { nocn(); return cmp(b) <= 0; } /* see cmp() */
2487  
2488      bool operator>= (Map_t const &b) const { nocn(); return cmp(b) >= 0; } /* see cmp() */
2489      bool operator>= (Map_t const *b) const { nocn(); return cmp(b) >= 0; } /* see cmp() */
2490  
2491      bool operator<  (Map_t const &b) const { nocn(); return cmp(b) < 0; }  /* see cmp() */
2492      bool operator<  (Map_t const *b) const { nocn(); return cmp(b) < 0; }  /* see cmp() */
2493  
2494      bool operator>  (Map_t const &b) const { nocn(); return cmp(b) > 0; }  /* see cmp() */
2495      bool operator>  (Map_t const *b) const { nocn(); return cmp(b) > 0; }  /* see cmp() */
2496  
2497      /* Type defs */
2498  #IF(oType != void)
2499      typedef oType ValueType;
2500  #ENDIF
2501  
2502      typedef iType KeyType;
2503  
2504  #INCLUDE <generated/map_forall_cpp_members.hd>
2505  
2506  /*--END-CLASS--*/
2507  #endif /* __cplusplus */
2508  };
2509  
2510  #ifdef __cplusplus
2511  
2512  #IF(1)
2513  
2514  /* some nasty global functions that are useful e.g. for forall.  Note that these
2515   * are not local to one vector but will be overloaded by all different vector
2516   * instantiations. */
2517  extern "C++" {
2518  ERWIN_WRAPPER
2519  Map_t *Global_erwin_ptr_of(Map_t *x) { return x;  }
2520  
2521  ERWIN_WRAPPER
2522  Map_t *Global_erwin_ptr_of(Map_t &x) { return &x; }
2523  
2524  ERWIN_WRAPPER
2525  Map_t const *Global_erwin_ptr_const_of (Map_t const *x) { return x;  }
2526  
2527  ERWIN_WRAPPER
2528  Map_t const *Global_erwin_ptr_const_of (Map_t const &x) { return &x; }
2529  } /* extern "C++" */
2530  
2531  #ELSE
2532  
2533  #ifndef Global_erwin_ptr_of
2534  #define Global_erwin_ptr_of(x) x
2535  #endif
2536  
2537  #ifndef Global_erwin_ptr_const_of
2538  #define Global_erwin_ptr_const_of(x) x
2539  #endif
2540  
2541  #ENDIF
2542  
2543  /*
2544   * For the sorted iteration you must provide Global_iType_CMP and Global_oType_CMP resp.  Otherwise, you
2545   * will get run-time errors when using these macros.
2546   */
2547  #if defined (Global_ERWIN_REQUIRE_DETERMINISM) && !defined (Global_ERWIN_WEAK_DETERMINISM)
2548  /* Force forall macros that allow deterministic sort order if user required determinism.
2549   * When _sorted_by_user functions are given the NULL function, they will still
2550   * sort the map if that is required.
2551   */
2552  #  ifndef Global_map_forall
2553  #    define Global_map_forall(h,k,v) Global_map_forall_copy(h,k,v)
2554  /* Operator for hash iteration in C++.  This iterates over keys and values.  You do not
2555   * need any additional structure when using C++ since this is declared automatically.
2556   * Use it as follows.
2557   *    : MapIntCharP m;
2558   *    : ...
2559   *    : int i;
2560   *    : char *s;
2561   *    : map_forall (m, i, s) {
2562   *    :     printf ("key=%d, value=%s\n", i, s);
2563   *    : }
2564   *
2565   *
2566   * The macro also accepts pointers to maps.  So you could also have used:
2567   *    : ...
2568   *    : map_forall (&m, i, s)
2569   *    : ...
2570   *
2571   * It might be interesting to compare this to the C version Map_forall.
2572   *
2573   * Other variants for C++ are available.  In addition to the C macros, the
2574   * C++ macros allow sorted iteration (..._sorted_by_... variants).
2575   *
2576   * All C++ macros support determinism by possibly pre-sorting the map.
2577   *
2578   * For convenience, the non-deterministic iterators are available for C++, too.
2579   * These are the ..._nondet variants.
2580   *
2581   * Further, all sorted versions and the copied versions (..._copy) allow you
2582   * to arbitrarily modify (Map_erase, Map_insert, Map_modify) the map while you
2583   * iterate it.  These changes are not reflected during that loop, however.
2584   *
2585   * Iteration is allowed on points to values, too.  These are the ...ptr
2586   * variants.  This way, you can modify values on the fly.  You need not use
2587   * the copied functions for this to work.  There is no way of modifying keys
2588   * on the fly, since this needs restructuring of the internal hash table.
2589   * Use Map_erase and Map_insert for this.
2590   *
2591   * The following is the complete list of C++ iteration macros, which should be
2592   * self-explained, since naming is completely regular.
2593   *
2594   *    : Global_map_forall(h,k,v)
2595   *    : Global_map_forall_copy(h,k,v)
2596   *    : Global_map_forall_nondet(h,k,v)
2597   *    : Global_map_forall_sorted_by_key(h,k,v)
2598   *    : Global_map_forall_sorted_by_value(h,k,v)
2599   *    : Global_map_forall_sorted_by_key_and_value(h,k,v)
2600   *    : Global_map_forall_sorted_by_value_and_key(h,k,v)
2601   *    : Global_map_forall_sorted_by_user(h,u,k,v)
2602   *    : Global_map_forall_ptr(h,k,V)
2603   *    : Global_map_forall_ptr_copy(h,k,V)
2604   *    : Global_map_forall_ptr_nondet(h,k,V)
2605   *    : Global_map_forall_ptr_sorted_by_key(h,k,V)
2606   *    : Global_map_forall_ptr_sorted_by_value(h,k,V)
2607   *    : Global_map_forall_ptr_sorted_by_key_and_value(h,k,V)
2608   *    : Global_map_forall_ptr_sorted_by_value_and_key(h,k,V)
2609   *    : Global_map_forall_ptr_sorted_by_user(h,U,k,V)
2610   *    : Global_map_forall_keys(h,k)
2611   *    : Global_map_forall_keys_copy(h,k)
2612   *    : Global_map_forall_keys_nondet(h,k)
2613   *    : Global_map_forall_keys_sorted_by_key(h,k)
2614   *    : Global_map_forall_keys_sorted_by_value(h,k)
2615   *    : Global_map_forall_keys_sorted_by_key_and_value(h,k)
2616   *    : Global_map_forall_keys_sorted_by_value_and_key(h,k)
2617   *    : Global_map_forall_keys_sorted_by_user(h,u,k)
2618   *    : Global_map_forall_values(h,v)
2619   *    : Global_map_forall_values_copy(h,v)
2620   *    : Global_map_forall_values_nondet(h,v)
2621   *    : Global_map_forall_values_sorted_by_key(h,v)
2622   *    : Global_map_forall_values_sorted_by_value(h,v)
2623   *    : Global_map_forall_values_sorted_by_key_and_value(h,v)
2624   *    : Global_map_forall_values_sorted_by_value_and_key(h,v)
2625   *    : Global_map_forall_values_sorted_by_user(h,u,v)
2626   *    : Global_map_forall_values_ptr(h,V)
2627   *    : Global_map_forall_values_ptr_copy(h,V)
2628   *    : Global_map_forall_values_ptr_nondet(h,V)
2629   *    : Global_map_forall_values_ptr_sorted_by_key(h,V)
2630   *    : Global_map_forall_values_ptr_sorted_by_value(h,V)
2631   *    : Global_map_forall_values_ptr_sorted_by_key_and_value(h,V)
2632   *    : Global_map_forall_values_ptr_sorted_by_value_and_key(h,V)
2633   *    : Global_map_forall_values_ptr_sorted_by_user(h,U,V)
2634   *    : Global_map_forall_pairs(h,p)
2635   *    : Global_map_forall_pairs_copy(h,p)
2636   *    : Global_map_forall_pairs_nondet(h,p)
2637   *    : Global_map_forall_pairs_sorted_by_key(h,p)
2638   *    : Global_map_forall_pairs_sorted_by_value(h,p)
2639   *    : Global_map_forall_pairs_sorted_by_key_and_value(h,p)
2640   *    : Global_map_forall_pairs_sorted_by_value_and_key(h,p)
2641   *    : Global_map_forall_pairs_sorted_by_user(h,u,p)
2642   *    : Global_map_forall_pairs_ptr(h,P)
2643   *    : Global_map_forall_pairs_ptr_copy(h,P)
2644   *    : Global_map_forall_pairs_ptr_nondet(h,P)
2645   *    : Global_map_forall_pairs_ptr_sorted_by_key(h,P)
2646   *    : Global_map_forall_pairs_ptr_sorted_by_value(h,P)
2647   *    : Global_map_forall_pairs_ptr_sorted_by_key_and_value(h,P)
2648   *    : Global_map_forall_pairs_ptr_sorted_by_value_and_key(h,P)
2649   *    : Global_map_forall_pairs_ptr_sorted_by_user(h,U,P)
2650   *
2651   */
2652  #  endif
2653  
2654  #  ifndef Global_map_forall_ptr
2655  #    define Global_map_forall_ptr(h,k,v) Global_map_forall_ptr_copy(h,k,v)
2656  #  endif
2657  
2658  #  ifndef Global_map_forall_keys
2659  #    define Global_map_forall_keys(h,k) Global_map_forall_keys_copy(h,k)
2660  #  endif
2661  
2662  #  ifndef Global_map_forall_values
2663  #    define Global_map_forall_values(h,v) Global_map_forall_values_copy(h,v)
2664  #  endif
2665  
2666  #  ifndef Global_map_forall_values_ptr
2667  #    define Global_map_forall_values_ptr(h,v) Global_map_forall_values_ptr_copy(h,v)
2668  #  endif
2669  
2670  #  ifndef Global_map_forall_pairs
2671  #    define Global_map_forall_pairs(h,p) Global_map_forall_pairs_copy(h,p)
2672  #  endif
2673  
2674  #  ifndef Global_map_forall_pairs_ptr
2675  #    define Global_map_forall_pairs_ptr(h,p) Global_map_forall_pairs_ptr_copy(h,p)
2676  #  endif
2677  
2678  #else
2679  
2680  #  ifndef Global_map_forall
2681  #    define Global_map_forall(h,k,v) Global_map_forall_nondet(h,k,v)
2682  #  endif
2683  
2684  #  ifndef Global_map_forall_ptr
2685  #    define Global_map_forall_ptr(h,k,v) Global_map_forall_ptr_nondet(h,k,v)
2686  #  endif
2687  
2688  #  ifndef Global_map_forall_keys
2689  #    define Global_map_forall_keys(h,k) Global_map_forall_keys_nondet(h,k)
2690  #  endif
2691  
2692  #  ifndef Global_map_forall_values
2693  #    define Global_map_forall_values(h,v) Global_map_forall_values_nondet(h,v)
2694  #  endif
2695  
2696  #  ifndef Global_map_forall_values_ptr
2697  #    define Global_map_forall_values_ptr(h,v) Global_map_forall_values_ptr_nondet(h,v)
2698  #  endif
2699  
2700  #  ifndef Global_map_forall_pairs
2701  #    define Global_map_forall_pairs(h,p) Global_map_forall_pairs_nondet(h,p)
2702  #  endif
2703  
2704  #  ifndef Global_map_forall_pairs_ptr
2705  #    define Global_map_forall_pairs_ptr(h,p) Global_map_forall_pairs_ptr_nondet(h,p)
2706  #  endif
2707  
2708  #endif
2709  
2710  /*
2711   * The following are convenience macros for iterating over a copy of the map
2712   * in order to allow modification during iteration. */
2713  #ifndef Global_map_forall_copy
2714  #  define Global_map_forall_copy(h,k,v) Global_map_forall_sorted_by_user(h,NULL,k,v)
2715  #endif
2716  
2717  #ifndef Global_map_forall_ptr_copy
2718  #  define Global_map_forall_ptr_copy(h,k,v) Global_map_forall_ptr_sorted_by_user(h,NULL,k,v)
2719  #endif
2720  
2721  #ifndef Global_map_forall_keys_copy
2722  #  define Global_map_forall_keys_copy(h,k) Global_map_forall_keys_sorted_by_user(h,NULL,k)
2723  #endif
2724  
2725  #ifndef Global_map_forall_values_copy
2726  #  define Global_map_forall_values_copy(h,v) Global_map_forall_values_sorted_by_user(h,NULL,v)
2727  #endif
2728  
2729  #ifndef Global_map_forall_values_ptr_copy
2730  #  define Global_map_forall_values_ptr_copy(h,v) Global_map_forall_values_ptr_sorted_by_user(h,NULL,v)
2731  #endif
2732  
2733  #ifndef Global_map_forall_pairs_copy
2734  #  define Global_map_forall_pairs_copy(h,p) Global_map_forall_pairs_sorted_by_user(h,NULL,p)
2735  #endif
2736  
2737  #ifndef Global_map_forall_pairs_ptr_copy
2738  #  define Global_map_forall_pairs_ptr_copy(h,p) Global_map_forall_pairs_ptr_sorted_by_user(h,NULL,p)
2739  #endif
2740  
2741  #INCLUDE <generated/map_forall_macros.hd>
2742  
2743  #endif /* defined(__cplusplus) */
2744  
2745  #endif /* !defined(ERWIN_Map_ErwinHExt) */
2746