MapPolicy

Documentation

API Reference

MapPolicy

Description

Policy object controlling probe-table behavior of Map.

MapPolicy is intentionally narrower than a full backend interface. The map runtime still owns allocation, rollback, copying, and slot writes. The policy answers strategy questions:

when probing pressure is unhealthy
what capacity should be chosen next
where probing starts
how probing advances after collisions

This keeps policies powerful enough to tune behavior for different workloads without letting them redefine container ownership or memory semantics.

Fields

Name	Description
`name`	Human-readable identifier used in diagnostics and validation errors.
`should_rehash`	Callback deciding whether current occupancy, tombstones, pending inserts, and recent probe pressure require a rebuild.
`next_capacity`	Callback choosing the next table capacity. It must return enough capacity to hold at least `min_entries`.
`first_index`	Callback mapping a key hash to the first slot to probe in a table of the given capacity.
`next_index`	Callback choosing the next slot after a collision, using the previous index and probe count.
`max_probe_count`	Hard limit on probe attempts before the map forces a rebuild or fails validation.

Usage example (from documentation)

  MapPolicy policy = {
      .name            = "dense-linear",
      .should_rehash   = my_should_rehash,
      .next_capacity   = my_next_capacity,
      .first_index     = my_first_index,
      .next_index      = my_next_index,
      .max_probe_count = 64,
  };

  typedef Map(Str, Str) StrMap;
  StrMap map = MapInitWithPolicy(KvConfigHash, KvConfigCompare, policy);

Usage example (Cross-references)

Usage examples (Cross-references)

In Map.c:86:

    }
    
    void validate_map_policy(const MapPolicy *policy) {
        static const struct {
            u64 length;

In Map.c:102:

    
        if (!policy) {
            LOG_FATAL("Expected a valid MapPolicy pointer");
        }

In Map.c:106:

    
        if (!policy->name || !policy->name[0]) {
            LOG_FATAL("MapPolicy must have a non-empty name");
        }

In Map.c:110:

    
        if (!policy->should_rehash || !policy->next_capacity || !policy->first_index || !policy->next_index) {
            LOG_FATAL("MapPolicy '{}' must provide all required callbacks", policy->name);
        }

In Map.c:114:

    
        if (policy->max_probe_count == 0) {
            LOG_FATAL("MapPolicy '{}' must provide a non-zero max_probe_count", policy->name);
        }

In Map.c:128:

    
            if ((next0 == 0) && ((length != 0) || (capacity != 0) || (tombstones != 0))) {
                LOG_FATAL("MapPolicy '{}' returned zero capacity for a non-empty snapshot", policy->name);
            }

In Map.c:132:

    
            if ((next_same != 0) && (next_same < length)) {
                LOG_FATAL("MapPolicy '{}' returned capacity smaller than current length", policy->name);
            }

In Map.c:136:

    
            if (next_more < ((size)length + 1)) {
                LOG_FATAL("MapPolicy '{}' returned capacity smaller than requested minimum entries", policy->name);
            }
        }

In Map.c:151:

    
                if (next == first) {
                    LOG_FATAL("MapPolicy '{}' produced a stuck probe sequence for capacity {}", policy->name, capacity);
                }
            }

In Map.c:157:

    }
    
    MapPolicy validate_map_policy_copy(MapPolicy policy) {
        validate_map_policy(&policy);
        return policy;

In Map.c:162:

    }
    
    const MapPolicy MisraMapPolicyLinear = {
        .name            = "linear",
        .should_rehash   = default_should_rehash,

In Map.c:171:

    };
    
    const MapPolicy MisraMapPolicyQuadratic = {
        .name            = "quadratic",
        .should_rehash   = default_should_rehash,

In Map.c:480:

        size        hash_offset,
        size        n,
        MapPolicy   policy
    ) {
        char *old_entries;

In Map.Type.c:75:

    static bool test_map_policy_copy(void) {
        typedef Map(int, int) IntIntMap;
        MapPolicy custom_policy = {
            .name            = "custom-linear",
            .should_rehash   = custom_should_rehash_snapshot,

In Map.Type.c:99:

    
    static bool test_validate_map_policy(void) {
        MapPolicy custom_policy = {
            .name            = "custom-linear",
            .should_rehash   = custom_should_rehash_snapshot,

In Map.Init.c:93:

    static bool test_map_custom_policy_growth(void) {
        typedef Map(int, int) IntIntMap;
        MapPolicy custom_policy = {
            .name            = "five-step",
            .should_rehash   = custom_should_rehash,

In Type.h:80:

        MapPolicyNextIndexFn    next_index;
        size                    max_probe_count;
    } MapPolicy;
    
    ///

In Type.h:87:

    /// INFO: This is the best general-purpose starting point when you do not have a workload-specific reason to choose something else.
    ///
    extern const MapPolicy MisraMapPolicyLinear;
    
    ///

In Type.h:94:

    /// INFO: This is useful when you want to reduce clustering pressure while keeping the same `Map` API and runtime ownership model.
    ///
    extern const MapPolicy MisraMapPolicyQuadratic;
    
    typedef struct {

In Type.h:113:

        char             *entries;
        u8               *states;
        MapPolicy         policy;
        u64               __magic;
    };

In Type.h:176:

            MapEntry(K, V) * entries;                                                                                      \
            u8       *states;                                                                                              \
            MapPolicy policy;                                                                                              \
            u64       __magic;                                                                                             \
        }

Last updated on April 20, 2026

MapPairCount MapRehashWithPolicy