Map – MisraStdC

Documentation

API Reference

Map

Description

Typesafe multimap definition.

This behaves like the other generic containers in the project: each use of Map(K, V) creates a distinct anonymous type, so reusable aliases should be defined with typedef. Multiple values may be stored for the same key.

Fields

Name	Description
`length`	Number of stored key/value pairs, including duplicate keys.
`capacity`	Total number of probe slots currently allocated.
`tombstones`	Number of deleted slots currently retained for probing.
`key_copy_init`	Optional deep-copy callback for keys.
`key_copy_deinit`	Optional deinit callback for keys held by the map.
`value_copy_init`	Optional deep-copy callback for values.
`value_copy_deinit`	Optional deinit callback for values held by the map.
`key_compare`	Required comparator for keys. Equality is `compare == 0`.
`value_compare`	Optional comparator for values. Required for pair-level APIs.
`key_hash`	Required hash callback for keys.
`entries`	Pointer to entry storage. Do not index directly.
`states`	Slot-state storage used internally by the probing policy.
`policy`	Copy of the probing policy used by this map.

Usage example (from documentation)

  typedef Map(int, Str) IntStrMap;
  typedef Map(T(Pair(i32, i32)), float) PairFloatMap;

Usage example (Cross-references)

Usage examples (Cross-references)

In Debug.c:14:

    
    #include <Misra/Std.h>
    #include <Misra/Std/Container/Map.h>
    #include <Misra/Std/Log.h>
    #include <Misra/Std/Memory.h>

In Map.c:7:

    /// Generic map implementation
    
    #include <Misra/Std/Container/Map.h>
    #include <Misra/Std/Log.h>
    #include <Misra/Std/Memory.h>

In Map.c:300:

        limit = map->policy.max_probe_count;
        if (limit == 0) {
            LOG_FATAL("Map policy '{}' has invalid max_probe_count", map->policy.name);
        }

In Map.c:400:

    static void validate_map_structural(const GenericMap *map) {
        if (!map->key_compare || !map->key_hash) {
            LOG_FATAL("Map must have valid key compare and key hash callbacks");
        }
        if (!map->allocator) {

In Map.c:403:

        }
        if (!map->allocator) {
            LOG_FATAL("Map allocator pointer is NULL");
        }
        if (!map->allocator->allocate || !map->allocator->resize || !map->allocator->remap || !map->allocator->deallocate) {

In Map.c:406:

        }
        if (!map->allocator->allocate || !map->allocator->resize || !map->allocator->remap || !map->allocator->deallocate) {
            LOG_FATAL("Map allocator is invalid");
        }
        validate_map_policy(&map->policy);

In Map.c:410:

        validate_map_policy(&map->policy);
        if (map->length > map->capacity) {
            LOG_FATAL("Map length cannot exceed capacity");
        }
        if ((map->length + map->tombstones) > map->capacity) {

In Map.c:413:

        }
        if ((map->length + map->tombstones) > map->capacity) {
            LOG_FATAL("Map occupied slots and tombstones cannot exceed capacity");
        }
        if (!map->capacity) {

In Map.c:417:

        if (!map->capacity) {
            if (map->entries || map->states) {
                LOG_FATAL("Map with zero capacity must not have allocated storage");
            }
            return;

In Map.c:422:

        }
        if (!map->entries || !map->states) {
            LOG_FATAL("Map storage is corrupted");
        }
    }

In Map.c:428:

    void validate_map(const GenericMap *map) {
        if (!map) {
            LOG_FATAL("Expected a valid Map pointer");
        }
        if (!MAGIC_MATCHES(map->__magic, MAP_MAGIC)) {

In Map.c:431:

        }
        if (!MAGIC_MATCHES(map->__magic, MAP_MAGIC)) {
            LOG_FATAL("Map is uninitialized or corrupted");
        }
        if (!(map->__magic & MAGIC_VALIDATED_BIT)) {

In Map.c:526:

    
        if (new_capacity < (n > map->length ? n : (size)map->length)) {
            LOG_FATAL("Map policy '{}' returned insufficient capacity {}", policy.name, new_capacity);
        }

In Map.Insert.c:2:

    #include <Misra/Std/Allocator/Default.h>
    #include <Misra/Std/Container/Map.h>
    #include <Misra/Std/Log.h>
    #include "../Util/TestRunner.h"

In Map.Insert.c:22:

    
    static bool test_map_insert_and_set(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Map.Insert.c:46:

    
    static bool test_map_set_first(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInitWithValueCompare(i32_hash, i32_compare, i32_compare, &alloc);

In Map.Insert.c:68:

    
    static bool test_map_lvalue_zeroing(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Map.Insert.c:91:

    // would re-probe the same cluster and loop forever).
    static bool test_map_churn_does_not_loop(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc  = DefaultAllocatorInit();
        IntIntMap        map    = MapInit(i32_hash, i32_compare, &alloc);

In Map.Insert.c:118:

    
    static bool test_map_ensure_ptr(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Map.Insert.c:148:

        };
    
        WriteFmt("[INFO] Starting Map.Insert tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Map.Insert");
    }

In Map.Insert.c:149:

    
        WriteFmt("[INFO] Starting Map.Insert tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Map.Insert");
    }

In Float.Compare.c:4:

    #include <Misra/Std/Container/Float.h>
    #include <Misra/Std/Container/Int.h>
    #include <Misra/Std/Container/Map.h>
    #include <Misra/Std/Log.h>

In Float.Compare.c:195:

    // the GenericHash / GenericCompare-shaped helpers wire in directly.
    bool test_float_hash_as_map_key(void) {
        WriteFmt("Testing float_hash as Map<Float, u64> key\n");
    
        DefaultAllocator alloc = DefaultAllocatorInit();

In Float.Compare.c:199:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        Map(Float, u64) counts = MapInit(float_hash, float_compare, &alloc);
    
        Float k1 = FloatFromStr("3.14", &alloc.base);

In Map.Foreach.c:2:

    #include <Misra/Std/Allocator/Default.h>
    #include <Misra/Std/Container/Map.h>
    #include <Misra/Std/Log.h>
    #include "../Util/TestRunner.h"

In Map.Foreach.c:22:

    
    static bool test_map_foreach_ptr(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc     = DefaultAllocatorInit();
        IntIntMap        map       = MapInit(i32_hash, i32_compare, &alloc);

In Map.Foreach.c:46:

    
    static bool test_map_foreach_multimap_iterators(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc          = DefaultAllocatorInit();
        IntIntMap        map            = MapInit(i32_hash, i32_compare, &alloc);

In Map.Foreach.c:90:

        };
    
        WriteFmt("[INFO] Starting Map.Foreach tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Map.Foreach");
    }

In Map.Foreach.c:91:

    
        WriteFmt("[INFO] Starting Map.Foreach tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Map.Foreach");
    }

In Map.Deadend.c:2:

    #include <Misra/Std/Allocator/Default.h>
    #include <Misra/Std/Container/Map.h>
    #include <Misra/Std/Log.h>

In Map.Deadend.c:25:

        WriteFmt("Testing ValidateMap on uninitialized map\n");
    
        Map(int, int) map = {0};
        ValidateMap(&map);

In Map.Deadend.c:34:

        WriteFmt("Testing MapContainsPair without value comparator\n");
    
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Map.Deadend.c:48:

        WriteFmt("Testing MapRemovePair without value comparator\n");
    
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Map.Deadend.c:62:

        WriteFmt("Testing MapRemoveIf without predicate\n");
    
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Map.Deadend.c:76:

        WriteFmt("Testing MapRetainIf without predicate\n");
    
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Map.Deadend.c:157:

        };
    
        WriteFmt("[INFO] Starting Map.Deadend tests\n\n");
        return run_test_suite(
            NULL,

In Map.Deadend.c:163:

            deadend_tests,
            (int)(sizeof(deadend_tests) / sizeof(deadend_tests[0])),
            "Map.Deadend"
        );
    }

In Map.Remove.c:2:

    #include <Misra/Std/Allocator/Default.h>
    #include <Misra/Std/Container/Map.h>
    #include <Misra/Std/Log.h>
    #include "../Util/TestRunner.h"

In Map.Remove.c:22:

    
    static bool test_map_remove_value(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Map.Remove.c:42:

    
    static bool test_map_remove_pair(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInitWithValueCompare(i32_hash, i32_compare, i32_compare, &alloc);

In Map.Remove.c:68:

    
    static bool test_map_remove_if(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Map.Remove.c:90:

    
    static bool test_map_remove_all(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Map.Remove.c:111:

    
    static bool test_map_tombstone_reuse(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Map.Remove.c:140:

        };
    
        WriteFmt("[INFO] Starting Map.Remove tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Map.Remove");
    }

In Map.Remove.c:141:

    
        WriteFmt("[INFO] Starting Map.Remove tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Map.Remove");
    }

In Int.Compare.c:3:

    #include <Misra/Std/Allocator/Default.h>
    #include <Misra/Std/Container/Int.h>
    #include <Misra/Std/Container/Map.h>
    #include <Misra/Std/Log.h>
    #include <Misra/Types.h>

In Int.Compare.c:152:

    // GenericHash / GenericCompare-shaped helpers wire in directly.
    bool test_int_hash_as_map_key(void) {
        WriteFmt("Testing int_hash as Map<Int,u64> key\n");
    
        DefaultAllocator alloc = DefaultAllocatorInit();

In Int.Compare.c:156:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        Map(Int, u64) counts = MapInit(int_hash, int_compare, &alloc);
    
        Int k1 = IntFrom(100u, &alloc.base);

In Map.Access.c:2:

    #include <Misra/Std/Allocator/Default.h>
    #include <Misra/Std/Container/Map.h>
    #include <Misra/Std/Log.h>
    #include "../Util/TestRunner.h"

In Map.Access.c:22:

    
    static bool test_map_contains_and_find(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInitWithValueCompare(i32_hash, i32_compare, i32_compare, &alloc);

In Map.Access.c:47:

    
    static bool test_map_get_ptr(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Map.Access.c:64:

    
    static bool test_map_try_get_ptr(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Map.Access.c:81:

    
    static bool test_map_get_or_default(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Map.Access.c:100:

    
    static bool test_map_value_cursor_query(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc     = DefaultAllocatorInit();
        IntIntMap        map       = MapInit(i32_hash, i32_compare, &alloc);

In Map.Access.c:136:

    
    static bool test_map_cursor_invalidated_after_removal(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc  = DefaultAllocatorInit();
        IntIntMap        map    = MapInit(i32_hash, i32_compare, &alloc);

In Map.Access.c:172:

        };
    
        WriteFmt("[INFO] Starting Map.Access tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Map.Access");
    }

In Map.Access.c:173:

    
        WriteFmt("[INFO] Starting Map.Access tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Map.Access");
    }

In Map.Init.c:2:

    #include <Misra/Std/Allocator/Default.h>
    #include <Misra/Std/Container/Map.h>
    #include <Misra/Std/Log.h>
    #include "../Util/TestRunner.h"

In Map.Init.c:54:

    
    static bool test_map_reserve_and_clear(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Map.Init.c:81:

    
    static bool test_map_rehash_policy_switch(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Map.Init.c:107:

    
    static bool test_map_custom_policy_growth(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc         = DefaultAllocatorInit();
        MapPolicy        custom_policy = {

In Map.Init.c:144:

        };
    
        WriteFmt("[INFO] Starting Map.Init tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Map.Init");
    }

In Map.Init.c:145:

    
        WriteFmt("[INFO] Starting Map.Init tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Map.Init");
    }

In Graph.Foreach.c:4:

    #include <Misra/Std/Zstr.h>
    #include <Misra/Std/Container/Graph.h>
    #include <Misra/Std/Container/Map.h>
    #include <Misra/Std/Container/Str.h>
    #include <Misra/Std/Log.h>

In Graph.Foreach.c:30:

    
    typedef Graph(Str) CityGraph;
    typedef Map(Str, GraphNodeId) CityIndex;
    
    static GraphNodeId city_add_intersection(CityGraph *graph, CityIndex *index, const Str *name, DefaultAllocator *alloc) {

In Graph.Foreach.c:136:

    
        typedef Graph(int) IntGraph;
        typedef Map(GraphNodeId, u64) CountMap;
    
        IntGraph graph  = GraphInit(&alloc);

In BitVec.Compare.c:2:

    #include <Misra/Std/Container/BitVec.h>
    #include <Misra/Std/Container/Map.h>
    #include <Misra/Std/Allocator/Default.h>
    #include <Misra/Std/Log.h>

In BitVec.Compare.c:1023:

    // shaped helpers wired in directly -- no per-callsite cast needed.
    bool test_bitvec_hash_as_map_key(void) {
        WriteFmt("Testing bitvec_hash as Map<BitVec, u64> key\n");
    
        DefaultAllocator alloc = DefaultAllocatorInit();

In BitVec.Compare.c:1028:

        Allocator       *base  = ALLOCATOR_OF(&alloc);
    
        Map(BitVec, u64) counts = MapInit(bitvec_hash, bitvec_compare, &alloc);
    
        BitVec k1 = BitVecInit(base);

In Map.Ops.c:3:

    #include <Misra/Std/Allocator/Default.h>
    #include <Misra/Std/Zstr.h>
    #include <Misra/Std/Container/Map.h>
    #include <Misra/Std/Container/Str.h>
    #include <Misra/Std/Memory.h>

In Map.Ops.c:25:

    
    static bool test_map_deep_copy_zstrs(void) {
        typedef Map(Zstr, Zstr) ZstrMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        ZstrMap          map   = MapInitWithDeepCopy(

In Map.Ops.c:71:

    
    static bool test_map_policy_switch_preserves_entries(void) {
        typedef Map(Zstr, Zstr) ZstrMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        ZstrMap          map   = MapInitWithDeepCopy(

In Map.Ops.c:112:

    
    static bool test_map_compact_and_swap(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc  = DefaultAllocatorInit();
        IntIntMap        first  = MapInitWithValueCompare(i32_hash, i32_compare, i32_compare, &alloc);

In Map.Ops.c:157:

    
    static bool test_map_retain_if(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc     = DefaultAllocatorInit();
        IntIntMap        map       = MapInit(i32_hash, i32_compare, &alloc);

In Map.Ops.c:187:

        };
    
        WriteFmt("[INFO] Starting Map.Ops tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Map.Ops");
    }

In Map.Ops.c:188:

    
        WriteFmt("[INFO] Starting Map.Ops tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Map.Ops");
    }

In Map.Type.c:3:

    #include <Misra/Std/Allocator/Default.h>
    #include <Misra/Std/Zstr.h>
    #include <Misra/Std/Container/Map.h>
    #include <Misra/Std/Log.h>
    #include "../Util/TestRunner.h"

In Map.Type.c:56:

    
    static bool test_map_type_defaults(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Map.Type.c:75:

    
    static bool test_map_type_with_value_compare(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInitWithValueCompare(i32_hash, i32_compare, i32_compare, &alloc);

In Map.Type.c:88:

    
    static bool test_map_policy_copy(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc         = DefaultAllocatorInit();
        MapPolicy        custom_policy = {

In Map.Type.c:141:

        };
    
        WriteFmt("[INFO] Starting Map.Type tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Map.Type");
    }

In Map.Type.c:142:

    
        WriteFmt("[INFO] Starting Map.Type tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Map.Type");
    }

In Container.h:25:

    #endif
    #if FEATURE_MAP
    #    include <Misra/Std/Container/Map.h>
    #endif
    #if FEATURE_GRAPH

In Debug.h:58:

    #include <Misra/Std/Allocator/Heap.h>
    #include <Misra/Std/Allocator/Page.h>
    #include <Misra/Std/Container/Map.h>
    #include <Misra/Std/Container/Str.h>
    #include <Misra/Std/Container/Vec.h>

In Debug.h:85:

        } DebugRecord;
    
        typedef Map(void *, DebugRecord) DebugRecordMap;
    
        ///

In Map.h:11:

    
    // clang-format off
    #include "Map/Type.h"
    #include "Map/Init.h"
    #include "Map/Insert.h"

In Map.h:12:

    // clang-format off
    #include "Map/Type.h"
    #include "Map/Init.h"
    #include "Map/Insert.h"
    #include "Map/Remove.h"

In Map.h:13:

    #include "Map/Type.h"
    #include "Map/Init.h"
    #include "Map/Insert.h"
    #include "Map/Remove.h"
    #include "Map/Access.h"

In Map.h:14:

    #include "Map/Init.h"
    #include "Map/Insert.h"
    #include "Map/Remove.h"
    #include "Map/Access.h"
    #include "Map/Memory.h"

In Map.h:15:

    #include "Map/Insert.h"
    #include "Map/Remove.h"
    #include "Map/Access.h"
    #include "Map/Memory.h"
    #include "Map/Foreach.h"

In Map.h:16:

    #include "Map/Remove.h"
    #include "Map/Access.h"
    #include "Map/Memory.h"
    #include "Map/Foreach.h"
    #include "Map/Ops.h"

In Map.h:17:

    #include "Map/Access.h"
    #include "Map/Memory.h"
    #include "Map/Foreach.h"
    #include "Map/Ops.h"
    #include "Map/Private.h"

In Map.h:18:

    #include "Map/Memory.h"
    #include "Map/Foreach.h"
    #include "Map/Ops.h"
    #include "Map/Private.h"
    // clang-format on

In Map.h:19:

    #include "Map/Foreach.h"
    #include "Map/Ops.h"
    #include "Map/Private.h"
    // clang-format on

In KvConfig.h:33:

    #define MISRA_PARSERS_KVCONFIG_H
    
    #include <Misra/Std/Container/Map.h>
    #include <Misra/Std/Container/Str.h>
    #include <Misra/Std/Utility/StrIter.h>

In KvConfig.h:43:

    // translation-unit-visible spot so the public header and the
    // implementation agree on the layout.
    typedef Map(Str, Str) KvConfig;
    
    // Private backends. Included AFTER the KvConfig typedef so the

Last updated on June 4, 2026

MachoUuid MapAllocator