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 Container.h:25:

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

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 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 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

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 Debug.c:14:

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

In 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 Foreach.c:31:

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

In Foreach.c:137:

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

In Compare.c:5:

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

In Compare.c:217:

    // 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 Compare.c:221:

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

In 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 Compare.c:1032:

    // 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 Compare.c:1037:

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

In 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 Compare.c:157:

    // 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 Compare.c:161:

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

In 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 Ops.c:32:

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

In Ops.c:78:

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

In Ops.c:119:

    
    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 Ops.c:167:

    // pair is removed/cleared.
    static bool test_map_empty_true_and_false(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Ops.c:204:

    // preserved, length exact) happened and control returned to the caller.
    static bool test_map_must_compact_success(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInitWithValueCompare(i32_hash, i32_compare, i32_compare, &alloc);

In Ops.c:233:

    // live entry survives the rehash, tombstones gone, and control returned.
    static bool test_map_must_rehash_with_policy_success(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInitWithValueCompare(i32_hash, i32_compare, i32_compare, &alloc);

In Ops.c:268:

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

In Ops.c:295:

    // the stale zeroed slot ahead of the real entry.
    static bool test_clear_resets_slots_to_empty(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInitWithValueCompare(const_hash, i32_compare, i32_compare, &alloc);

In Ops.c:328:

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

In Ops.c:329:

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

In Init.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/Log.h>

In Init.c:56:

    
    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 Init.c:83:

    
    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 Init.c:109:

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

In Init.c:140:

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

In Init.c:159:

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

In Init.c:185:

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

In Init.c:203:

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

In Init.c:220:

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

In Init.c:251:

    // to force several growths.
    static bool test_map_grows_to_fit_many_inserts(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Init.c:285:

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

In Init.c:286:

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

In 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 Insert.c:340:

    
    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 Insert.c:364:

    
    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 Insert.c:391:

    // miss (or the header claiming it does) turns this RED.
    static bool test_map_set_first_miss_returns_false(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Insert.c:419:

    // map_remove_all step would leave the old duplicates behind.
    static bool test_map_set_only_collapses_multi(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInitWithValueCompare(i32_hash, i32_compare, i32_compare, &alloc);

In Insert.c:444:

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

In Insert.c:466:

    // never through map_zero_insert_sources_on_success.
    static bool test_map_rvalue_does_not_zero_sources(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Insert.c:488:

    // the set_only_l form.
    static bool test_map_set_only_lvalue_zeroing(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Insert.c:511:

    // set_first_l form (zero only on success).
    static bool test_map_set_first_lvalue_zeroing(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Insert.c:542:

    // 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 Insert.c:571:

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

In Insert.c:596:

    // that map_ensure_value_ptr returns the in-table slot, not a copy.
    static bool test_map_ensure_ptr_mutation_persists(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Insert.c:620:

    // replace semantics). Guards the aliasing #defines in Insert.h.
    static bool test_map_default_aliases(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Insert.c:650:

    // assert each MapMust* applies the same effect as its fallible form.
    static bool test_map_must_family_success(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInitWithValueCompare(i32_hash, i32_compare, i32_compare, &alloc);

In Insert.c:712:

        WriteFmt("Testing MapRehashWithPolicy validates the new policy up front\n");
    
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Insert.c:731:

    // breaks MapCompact on a fresh/empty map.
    static bool test_compact_empty_map_succeeds(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Insert.c:749:

    // empty MapCompact must leave the map valid for further use.
    static bool test_compact_empty_then_insert_length(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Insert.c:763:

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

In Insert.c:779:

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

In Insert.c:796:

    // valid and must be accepted.
    static bool test_rehash_tight_capacity_accepted(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Insert.c:823:

        WriteFmt("Testing MapRehashWithPolicy rejects under-sized capacity for n<length\n");
    
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Insert.c:841:

    // so the map stays consistent (FAILURE contract: map unchanged).
    static bool test_rehash_alloc_failure_keeps_map_usable(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator inner = DefaultAllocatorInit();
        FailAlloc        fa    = fail_alloc_init(&inner);

In Insert.c:867:

    // exhausts the 4-probe budget; one doubling (to 16) splits them and succeeds.
    static bool run_doubling_retry_compact(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc  = DefaultAllocatorInit();
        MapPolicy        policy = make_small_probe_policy();

In Insert.c:926:

    // crosses the 3/4 load threshold and must grow.
    static bool test_map_preemptive_grow_succeeds(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc  = DefaultAllocatorInit();
        IntIntMap        map    = MapInit(i32_hash, i32_compare, &alloc);

In Insert.c:949:

    // succeed by taking the forced-grow recovery path.
    static bool test_map_probe_exhaustion_recovers(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc  = DefaultAllocatorInit();
        MapPolicy        policy = fill_then_grow_policy();

In Insert.c:973:

    // Mutant 1008 (`tombstones -= 1` -> `+= 1` when reusing a tombstone slot).
    static bool test_map_tombstone_reuse_decrements(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Insert.c:993:

    // fails to copy must restore the tombstone count to its pre-insert value.
    static bool test_map_tombstone_rollback_on_copy_fail(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap map = MapInitWithDeepCopy(i32_hash, i32_compare, NULL, NULL, toggled_value_copy_init, NULL, &alloc);

In Insert.c:1023:

    // and retries. The mutant lets it slip into an out-of-bounds write.
    static bool test_insert_raw_entry_grows_on_budget_exhaustion(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc  = DefaultAllocatorInit();
        MapPolicy        policy = {

In Insert.c:1057:

    // current capacity.
    static bool test_reserve_grows_when_target_exceeds_capacity(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc  = DefaultAllocatorInit();
        MapPolicy        policy = make_policy42();

In Insert.c:1087:

    // Real code is at capacity 16 by the 7th insert.
    static bool test_default_grow_uses_multiply_not_divide(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Insert.c:1107:

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

In Insert.c:1132:

    // mutant doubles once more to 16.
    static bool test_next_capacity_doubling_strict_less(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Insert.c:1152:

    // decrements the tombstone count back to 0; the mutant inflates it.
    static bool test_setonly_raw_reinsert_decrements_tombstones(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInitWithValueCompare(i32_hash, i32_compare, i32_compare, &alloc);

In Insert.c:1179:

    // not the resulting capacity.
    static bool test_probe_recovery_forced_n_is_capacity_plus_one(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc  = DefaultAllocatorInit();
        MapPolicy        policy = fill_then_grow_policy();

In Insert.c:1244:

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

In Insert.c:1250:

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

In Type.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/Log.h>

In Type.c:57:

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

In Type.c:76:

    
    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 Type.c:89:

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

In Type.c:135:

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

In Type.c:160:

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

In Type.c:194:

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

In Type.c:195:

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

In Deadend.c:2:

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

In Deadend.c:67:

    // as length + tombstones <= capacity. Real code validates cleanly.
    static bool test_validate_more_tombstones_than_live_is_valid(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Deadend.c:121:

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

In Deadend.c:134:

        WriteFmt("Testing ValidateMap with corrupted magic\n");
    
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Deadend.c:153:

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

In Deadend.c:167:

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

In Deadend.c:181:

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

In Deadend.c:195:

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

In Deadend.c:463:

        WriteFmt("Testing MapInitWithPolicy with an invalid policy\n");
    
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc  = DefaultAllocatorInit();
        MapPolicy        policy = valid_baseline_policy();

In Deadend.c:479:

        WriteFmt("Testing ValidateMap with corrupted policy name\n");
    
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Deadend.c:499:

        WriteFmt("Testing ValidateMap with length exceeding capacity\n");
    
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Deadend.c:509:

        g->__magic    |= MAGIC_VALIDATED_BIT;
    
        ValidateMap(&map);                // must abort: "Map length cannot exceed capacity"
    
        return false;

In Deadend.c:622:

    // -> a normal test that aborts = mutant killed.
    static bool test_self_check_accepts_policy_sufficient_for_real_snapshots(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc  = DefaultAllocatorInit();
        MapPolicy        policy = {

In Deadend.c:650:

    
    static bool deadend_self_check_stuck_at_cap8(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc  = DefaultAllocatorInit();
        MapPolicy        policy = make_probe_policy(poly_next_index_stuck_at_cap8);

In Deadend.c:660:

    
    static bool deadend_self_check_stuck_at_golden_hash(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc  = DefaultAllocatorInit();
        MapPolicy        policy = make_probe_policy(poly_next_index_stuck_at_golden);

In Deadend.c:670:

    
    static bool deadend_self_check_first_index_compare(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc  = DefaultAllocatorInit();
        MapPolicy        policy = make_probe_policy(poly_next_index_returns_first);

In Deadend.c:694:

    // harness counts the abort as a failure of this normal test -> mutant killed.
    static bool test_validate_skips_structural_after_first_op(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Deadend.c:757:

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

In Deadend.c:763:

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

In Remove.c:3:

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

In Remove.c:35:

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

In Remove.c:63:

    // the map completely unchanged (no spurious tombstone, no length change).
    static bool test_map_remove_first_missing_returns_false(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Remove.c:85:

    
    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 Remove.c:108:

    // absent) and the missing-key case.
    static bool test_map_remove_pair_no_match_returns_false(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInitWithValueCompare(i32_hash, i32_compare, i32_compare, &alloc);

In Remove.c:157:

    // the same key reclaims it, restoring the tombstone count to zero.
    static bool test_remove_then_reinsert_reclaims_tombstone(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Remove.c:183:

    // iterations and return 0; the mutant dereferences the NULL states array.
    static bool test_retain_if_on_empty_map_returns_zero(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Remove.c:199:

    // 0; the mutant dereferences states[0] through a NULL pointer.
    static bool test_remove_if_on_empty_map_returns_zero(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Remove.c:212:

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

In Remove.c:234:

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

In Remove.c:257:

    // unchanged. Guards the FAILURE contract of map_remove_all.
    static bool test_map_remove_all_missing_returns_zero(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Remove.c:291:

    // deletion-strategy details rather than contract.
    static bool test_map_remove_then_reinsert_same_key(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Remove.c:325:

    // callbacks, the clones would leak and the live count would be non-zero.
    static bool test_map_deep_copy_deinit_on_remove(void) {
        typedef Map(Zstr, Zstr) ZstrMap;
        DebugAllocator dbg = DebugAllocatorInit();
        // Deep-copy callbacks for both key and value, plus a value comparator

In Remove.c:376:

    // equally correct).
    static bool test_map_collision_chain_survives_deletion(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(const_hash, i32_compare, &alloc);

In Remove.c:421:

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

In Remove.c:422:

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

In 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 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 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 Foreach.c:88:

    // must NOT write back into the map.
    static bool test_map_foreach_pair_by_value(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc     = DefaultAllocatorInit();
        IntIntMap        map       = MapInit(i32_hash, i32_compare, &alloc);

In Foreach.c:125:

    // address. Writing through it must persist into the map.
    static bool test_map_foreach_value_ptr(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Foreach.c:157:

    // Each counter must stay 0.
    static bool test_map_foreach_empty_skips_body(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInit(i32_hash, i32_compare, &alloc);

In Foreach.c:210:

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

In Foreach.c:211:

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

In 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 Access.c:82:

    // ---------------------------------------------------------------------------
    static bool test_find_next_index_honours_full_probe_budget(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc  = DefaultAllocatorInit();
        MapPolicy        policy = {

In Access.c:114:

    // ---------------------------------------------------------------------------
    static bool test_value_ptr_from_cursor_rejects_index_equal_capacity(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc  = DefaultAllocatorInit();
        MapPolicy        policy = {

In Access.c:144:

    
    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 Access.c:169:

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

In Access.c:189:

    // value, and the first stored value is the duplicate inserted first.
    static bool test_map_get_first_ptr_is_live(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInitWithValueCompare(i32_hash, i32_compare, i32_compare, &alloc);

In Access.c:218:

    // branch in Map.c. Guards `if (!map->capacity) return ...;` lines.
    static bool test_map_empty_queries(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInitWithValueCompare(i32_hash, i32_compare, i32_compare, &alloc);

In Access.c:246:

    
    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 Access.c:265:

    
    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 Access.c:312:

    
    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 Access.c:344:

    // neighbour's value and turns this RED.
    static bool test_map_collision_chain_lookup(void) {
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInitWithValueCompare(const_hash, i32_compare, i32_compare, &alloc);

In Access.c:391:

            KEY_COUNT = 24
        };
        typedef Map(int, int) IntIntMap;
        DefaultAllocator alloc = DefaultAllocatorInit();
        IntIntMap        map   = MapInitWithValueCompareAndPolicy(const_hash, i32_compare, i32_compare, policy, &alloc);

In Access.c:462:

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

In Access.c:463:

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

Last updated on July 1, 2026

ListTail MapClear