╭ hash_map.zig ─────────────────────────────────────────────────╮ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ╰───────────────────────────────────────────────────────────────╯
🬂🬂🬒 🬂🬰🬂 🬑🬂🬀 ╭master╮ master xeubie: 🬋 🬋 🬃🬇🬋 │files │ commits refs discuss issues patches new login 🬯🬭🬭 🬭🬰🬭 🬟🬭🬑 ╰──────╯ (15882) user
╭ find file ─ ─ ─ ─ ─ ─ ─ ─ ─ ─╮ ╭────╮ ╭ clone ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ╮ │ │ │http│ ssh │ │ ╰ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─╯ ╰────╯ ╰ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ╯
.. Build/ Io/ Random/ Target/ c/ compress/ crypto/ debug/ dwarf/ fmt/ fs/ hash/ heap/ http/ json/ lang/ math/ mem/ meta/ os/ posix/ process/ sort/ tar/ testing/ time/ tz/ unicode/ valgrind/ zig/ zip/ zon/ BitStack.zig Build.zig DoublyLinkedList.zig Io.zig Progress.zig Random.zig SemanticVersion.zig SinglyLinkedList.zig Target.zig Thread.zig Uri.zig array_hash_map.zig array_list.zig ascii.zig atomic.zig base64.zig bit_set.zig buf_map.zig buf_set.zig c.zig coff.zig compress.zig crypto.zig debug.zig deque.zig dwarf.zig dynamic_library.zig elf.zig enums.zig fmt.zig fs.zig hash.zig ╭─────────────────────────────────╮ │hash_map.zig │ ╰─────────────────────────────────╯ heap.zig http.zig json.zig lang.zig leb128.zig log.zig macho.zig math.zig mem.zig meta.zig multi_array_list.zig os.zig pdb.zig pie.zig posix.zig priority_dequeue.zig priority_queue.zig process.zig simd.zig sort.zig spirv.zig start.zig static_string_map.zig std.zig tar.zig testing.zig time.zig treap.zig tz.zig unicode.zig valgrind.zig wasm.zig zig.zig zip.zig zon.zig
1 const std = @import("std.zig"); 2 const builtin = @import("builtin"); 3 const assert = std.debug.assert; 4 const autoHash = std.hash.autoHash; 5 const math = std.math; 6 const mem = std.mem; 7 const Allocator = mem.Allocator; 8 const Wyhash = std.hash.Wyhash; 9 const Alignment = std.mem.Alignment; 10 11 pub fn getAutoHashFn(comptime K: type, comptime Context: type) (fn (Context, K) u64) { 12 comptime { 13 assert(@hasDecl(std, "StringHashMap")); // detect when the following message needs updated 14 if (K == []const u8) { 15 @compileError("std.hash.autoHash does not allow slices here (" ++ 16 @typeName(K) ++ 17 ") because the intent is unclear. " ++ 18 "Consider using std.StringHashMap for hashing the contents of []const u8. " ++ 19 "Alternatively, consider using std.hash.autoHashStrat or providing your own hash function instead."); 20 } 21 } 22 23 return struct { 24 fn hash(ctx: Context, key: K) u64 { 25 _ = ctx; 26 if (std.meta.hasUniqueRepresentation(K)) { 27 return Wyhash.hash(0, std.mem.asBytes(&key)); 28 } else { 29 var hasher = Wyhash.init(0); 30 autoHash(&hasher, key); 31 return hasher.final(); 32 } 33 } 34 }.hash; 35 } 36 37 pub fn getAutoEqlFn(comptime K: type, comptime Context: type) (fn (Context, K, K) bool) { 38 return struct { 39 fn eql(ctx: Context, a: K, b: K) bool { 40 _ = ctx; 41 return std.meta.eql(a, b); 42 } 43 }.eql; 44 } 45 46 pub fn AutoHashMap(comptime K: type, comptime V: type) type { 47 return HashMap(K, V, AutoContext(K), default_max_load_percentage); 48 } 49 50 pub fn AutoHashMapUnmanaged(comptime K: type, comptime V: type) type { 51 return HashMapUnmanaged(K, V, AutoContext(K), default_max_load_percentage); 52 } 53 54 pub fn AutoContext(comptime K: type) type { 55 return struct { 56 pub const hash = getAutoHashFn(K, @This()); 57 pub const eql = getAutoEqlFn(K, @This()); 58 }; 59 } 60 61 /// Builtin hashmap for strings as keys. 62 /// Key memory is managed by the caller. Keys and values 63 /// will not automatically be freed. 64 pub fn StringHashMap(comptime V: type) type { 65 return HashMap([]const u8, V, StringContext, default_max_load_percentage); 66 } 67 68 /// Key memory is managed by the caller. Keys and values 69 /// will not automatically be freed. 70 pub fn StringHashMapUnmanaged(comptime V: type) type { 71 return HashMapUnmanaged([]const u8, V, StringContext, default_max_load_percentage); 72 } 73 74 pub const StringContext = struct { 75 pub fn hash(self: @This(), s: []const u8) u64 { 76 _ = self; 77 return hashString(s); 78 } 79 pub fn eql(self: @This(), a: []const u8, b: []const u8) bool { 80 _ = self; 81 return eqlString(a, b); 82 } 83 }; 84 85 pub fn eqlString(a: []const u8, b: []const u8) bool { 86 return mem.eql(u8, a, b); 87 } 88 89 pub fn hashString(s: []const u8) u64 { 90 return std.hash.Wyhash.hash(0, s); 91 } 92 93 pub const StringIndexContext = struct { 94 bytes: *const std.ArrayList(u8), 95 96 pub fn eql(_: @This(), a: u32, b: u32) bool { 97 return a == b; 98 } 99 100 pub fn hash(ctx: @This(), key: u32) u64 { 101 return hashString(mem.sliceTo(ctx.bytes.items[key..], 0)); 102 } 103 }; 104 105 pub const StringIndexAdapter = struct { 106 bytes: *const std.ArrayList(u8), 107 108 pub fn eql(ctx: @This(), a: []const u8, b: u32) bool { 109 return mem.eql(u8, a, mem.sliceTo(ctx.bytes.items[b..], 0)); 110 } 111 112 pub fn hash(_: @This(), adapted_key: []const u8) u64 { 113 assert(mem.findScalar(u8, adapted_key, 0) == null); 114 return hashString(adapted_key); 115 } 116 }; 117 118 pub const default_max_load_percentage = 80; 119 120 /// General purpose hash table. 121 /// No order is guaranteed and any modification invalidates live iterators. 122 /// It provides fast operations (lookup, insertion, deletion) with quite high 123 /// load factors (up to 80% by default) for low memory usage. 124 /// For a hash map that can be initialized directly that does not store an Allocator 125 /// field, see `HashMapUnmanaged`. 126 /// If iterating over the table entries is a strong usecase and needs to be fast, 127 /// prefer the alternative `std.ArrayHashMap`. 128 /// Context must be a struct type with two member functions: 129 /// hash(self, K) u64 130 /// eql(self, K, K) bool 131 /// Adapted variants of many functions are provided. These variants 132 /// take a pseudo key instead of a key. Their context must have the functions: 133 /// hash(self, PseudoKey) u64 134 /// eql(self, PseudoKey, K) bool 135 pub fn HashMap( 136 comptime K: type, 137 comptime V: type, 138 comptime Context: type, 139 comptime max_load_percentage: u64, 140 ) type { 141 return struct { 142 unmanaged: Unmanaged, 143 allocator: Allocator, 144 ctx: Context, 145 146 /// The type of the unmanaged hash map underlying this wrapper 147 pub const Unmanaged = HashMapUnmanaged(K, V, Context, max_load_percentage); 148 /// An entry, containing pointers to a key and value stored in the map 149 pub const Entry = Unmanaged.Entry; 150 /// A copy of a key and value which are no longer in the map 151 pub const KV = Unmanaged.KV; 152 /// The integer type that is the result of hashing 153 pub const Hash = Unmanaged.Hash; 154 /// The iterator type returned by iterator() 155 pub const Iterator = Unmanaged.Iterator; 156 157 pub const KeyIterator = Unmanaged.KeyIterator; 158 pub const ValueIterator = Unmanaged.ValueIterator; 159 160 /// The integer type used to store the size of the map 161 pub const Size = Unmanaged.Size; 162 /// The type returned from getOrPut and variants 163 pub const GetOrPutResult = Unmanaged.GetOrPutResult; 164 165 const Self = @This(); 166 167 /// Create a managed hash map with an empty context. 168 /// If the context is not zero-sized, you must use 169 /// initContext(allocator, ctx) instead. 170 pub fn init(allocator: Allocator) Self { 171 if (@sizeOf(Context) != 0) { 172 @compileError("Context must be specified! Call initContext(allocator, ctx) instead."); 173 } 174 return .{ 175 .unmanaged = .empty, 176 .allocator = allocator, 177 .ctx = undefined, // ctx is zero-sized so this is safe. 178 }; 179 } 180 181 /// Create a managed hash map with a context 182 pub fn initContext(allocator: Allocator, ctx: Context) Self { 183 return .{ 184 .unmanaged = .empty, 185 .allocator = allocator, 186 .ctx = ctx, 187 }; 188 } 189 190 /// Puts the hash map into a state where any method call that would 191 /// cause an existing key or value pointer to become invalidated will 192 /// instead trigger an assertion. 193 /// 194 /// `lockPointers` may be called multiple times. This allows multiple 195 /// independent users of the hash map to keep it locked simultaneously. 196 /// 197 /// `unlockPointers` restores the hash map to its previous state when 198 /// called the same number of times as `lockPointers`. 199 pub fn lockPointers(self: *Self) void { 200 self.unmanaged.lockPointers(); 201 } 202 203 /// Undoes one call to `lockPointers`. 204 pub fn unlockPointers(self: *Self) void { 205 self.unmanaged.unlockPointers(); 206 } 207 208 /// Release the backing array and invalidate this map. 209 /// This does *not* deinit keys, values, or the context! 210 /// If your keys or values need to be released, ensure 211 /// that that is done before calling this function. 212 pub fn deinit(self: *Self) void { 213 self.unmanaged.deinit(self.allocator); 214 self.* = undefined; 215 } 216 217 /// Empty the map, but keep the backing allocation for future use. 218 /// This does *not* free keys or values! Be sure to 219 /// release them if they need deinitialization before 220 /// calling this function. 221 pub fn clearRetainingCapacity(self: *Self) void { 222 return self.unmanaged.clearRetainingCapacity(); 223 } 224 225 /// Empty the map and release the backing allocation. 226 /// This does *not* free keys or values! Be sure to 227 /// release them if they need deinitialization before 228 /// calling this function. 229 pub fn clearAndFree(self: *Self) void { 230 return self.unmanaged.clearAndFree(self.allocator); 231 } 232 233 /// Return the number of items in the map. 234 pub fn count(self: Self) Size { 235 return self.unmanaged.count(); 236 } 237 238 /// Create an iterator over the entries in the map. 239 /// The iterator is invalidated if the map is modified. 240 pub fn iterator(self: *const Self) Iterator { 241 return self.unmanaged.iterator(); 242 } 243 244 /// Create an iterator over the keys in the map. 245 /// The iterator is invalidated if the map is modified. 246 pub fn keyIterator(self: Self) KeyIterator { 247 return self.unmanaged.keyIterator(); 248 } 249 250 /// Create an iterator over the values in the map. 251 /// The iterator is invalidated if the map is modified. 252 pub fn valueIterator(self: Self) ValueIterator { 253 return self.unmanaged.valueIterator(); 254 } 255 256 /// If key exists this function cannot fail. 257 /// If there is an existing item with `key`, then the result's 258 /// `Entry` pointers point to it, and found_existing is true. 259 /// Otherwise, puts a new item with undefined value, and 260 /// the `Entry` pointers point to it. Caller should then initialize 261 /// the value (but not the key). 262 pub fn getOrPut(self: *Self, key: K) Allocator.Error!GetOrPutResult { 263 return self.unmanaged.getOrPutContext(self.allocator, key, self.ctx); 264 } 265 266 /// If key exists this function cannot fail. 267 /// If there is an existing item with `key`, then the result's 268 /// `Entry` pointers point to it, and found_existing is true. 269 /// Otherwise, puts a new item with undefined key and value, and 270 /// the `Entry` pointers point to it. Caller must then initialize 271 /// the key and value. 272 pub fn getOrPutAdapted(self: *Self, key: anytype, ctx: anytype) Allocator.Error!GetOrPutResult { 273 return self.unmanaged.getOrPutContextAdapted(self.allocator, key, ctx, self.ctx); 274 } 275 276 /// If there is an existing item with `key`, then the result's 277 /// `Entry` pointers point to it, and found_existing is true. 278 /// Otherwise, puts a new item with undefined value, and 279 /// the `Entry` pointers point to it. Caller should then initialize 280 /// the value (but not the key). 281 /// If a new entry needs to be stored, this function asserts there 282 /// is enough capacity to store it. 283 pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult { 284 return self.unmanaged.getOrPutAssumeCapacityContext(key, self.ctx); 285 } 286 287 /// If there is an existing item with `key`, then the result's 288 /// `Entry` pointers point to it, and found_existing is true. 289 /// Otherwise, puts a new item with undefined value, and 290 /// the `Entry` pointers point to it. Caller must then initialize 291 /// the key and value. 292 /// If a new entry needs to be stored, this function asserts there 293 /// is enough capacity to store it. 294 pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult { 295 return self.unmanaged.getOrPutAssumeCapacityAdapted(key, ctx); 296 } 297 298 pub fn getOrPutValue(self: *Self, key: K, value: V) Allocator.Error!Entry { 299 return self.unmanaged.getOrPutValueContext(self.allocator, key, value, self.ctx); 300 } 301 302 /// Increases capacity, guaranteeing that insertions up until the 303 /// `expected_count` will not cause an allocation, and therefore cannot fail. 304 pub fn ensureTotalCapacity(self: *Self, expected_count: Size) Allocator.Error!void { 305 return self.unmanaged.ensureTotalCapacityContext(self.allocator, expected_count, self.ctx); 306 } 307 308 /// Increases capacity, guaranteeing that insertions up until 309 /// `additional_count` **more** items will not cause an allocation, and 310 /// therefore cannot fail. 311 pub fn ensureUnusedCapacity(self: *Self, additional_count: Size) Allocator.Error!void { 312 return self.unmanaged.ensureUnusedCapacityContext(self.allocator, additional_count, self.ctx); 313 } 314 315 /// Returns the number of total elements which may be present before it is 316 /// no longer guaranteed that no allocations will be performed. 317 pub fn capacity(self: Self) Size { 318 return self.unmanaged.capacity(); 319 } 320 321 /// Clobbers any existing data. To detect if a put would clobber 322 /// existing data, see `getOrPut`. 323 pub fn put(self: *Self, key: K, value: V) Allocator.Error!void { 324 return self.unmanaged.putContext(self.allocator, key, value, self.ctx); 325 } 326 327 /// Inserts a key-value pair into the hash map, asserting that no previous 328 /// entry with the same key is already present 329 pub fn putNoClobber(self: *Self, key: K, value: V) Allocator.Error!void { 330 return self.unmanaged.putNoClobberContext(self.allocator, key, value, self.ctx); 331 } 332 333 /// Asserts there is enough capacity to store the new key-value pair. 334 /// Clobbers any existing data. To detect if a put would clobber 335 /// existing data, see `getOrPutAssumeCapacity`. 336 pub fn putAssumeCapacity(self: *Self, key: K, value: V) void { 337 return self.unmanaged.putAssumeCapacityContext(key, value, self.ctx); 338 } 339 340 /// Asserts there is enough capacity to store the new key-value pair. 341 /// Asserts that it does not clobber any existing data. 342 /// To detect if a put would clobber existing data, see `getOrPutAssumeCapacity`. 343 pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void { 344 return self.unmanaged.putAssumeCapacityNoClobberContext(key, value, self.ctx); 345 } 346 347 /// Inserts a new `Entry` into the hash map, returning the previous one, if any. 348 pub fn fetchPut(self: *Self, key: K, value: V) Allocator.Error!?KV { 349 return self.unmanaged.fetchPutContext(self.allocator, key, value, self.ctx); 350 } 351 352 /// Inserts a new `Entry` into the hash map, returning the previous one, if any. 353 /// If insertion happens, asserts there is enough capacity without allocating. 354 pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV { 355 return self.unmanaged.fetchPutAssumeCapacityContext(key, value, self.ctx); 356 } 357 358 /// Removes a value from the map and returns the removed kv pair. 359 pub fn fetchRemove(self: *Self, key: K) ?KV { 360 return self.unmanaged.fetchRemoveContext(key, self.ctx); 361 } 362 363 pub fn fetchRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV { 364 return self.unmanaged.fetchRemoveAdapted(key, ctx); 365 } 366 367 /// Finds the value associated with a key in the map 368 pub fn get(self: Self, key: K) ?V { 369 return self.unmanaged.getContext(key, self.ctx); 370 } 371 pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V { 372 return self.unmanaged.getAdapted(key, ctx); 373 } 374 375 pub fn getPtr(self: Self, key: K) ?*V { 376 return self.unmanaged.getPtrContext(key, self.ctx); 377 } 378 pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V { 379 return self.unmanaged.getPtrAdapted(key, ctx); 380 } 381 382 /// Finds the actual key associated with an adapted key in the map 383 pub fn getKey(self: Self, key: K) ?K { 384 return self.unmanaged.getKeyContext(key, self.ctx); 385 } 386 pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K { 387 return self.unmanaged.getKeyAdapted(key, ctx); 388 } 389 390 pub fn getKeyPtr(self: Self, key: K) ?*K { 391 return self.unmanaged.getKeyPtrContext(key, self.ctx); 392 } 393 pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K { 394 return self.unmanaged.getKeyPtrAdapted(key, ctx); 395 } 396 397 /// Finds the key and value associated with a key in the map 398 pub fn getEntry(self: Self, key: K) ?Entry { 399 return self.unmanaged.getEntryContext(key, self.ctx); 400 } 401 402 pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry { 403 return self.unmanaged.getEntryAdapted(key, ctx); 404 } 405 406 /// Check if the map contains a key 407 pub fn contains(self: Self, key: K) bool { 408 return self.unmanaged.containsContext(key, self.ctx); 409 } 410 411 pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool { 412 return self.unmanaged.containsAdapted(key, ctx); 413 } 414 415 /// If there is an `Entry` with a matching key, it is deleted from 416 /// the hash map, and this function returns true. Otherwise this 417 /// function returns false. 418 /// 419 /// TODO: answer the question in these doc comments, does this 420 /// increase the unused capacity by one? 421 pub fn remove(self: *Self, key: K) bool { 422 return self.unmanaged.removeContext(key, self.ctx); 423 } 424 425 /// TODO: answer the question in these doc comments, does this 426 /// increase the unused capacity by one? 427 pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool { 428 return self.unmanaged.removeAdapted(key, ctx); 429 } 430 431 /// Delete the entry with key pointed to by key_ptr from the hash map. 432 /// key_ptr is assumed to be a valid pointer to a key that is present 433 /// in the hash map. 434 /// 435 /// TODO: answer the question in these doc comments, does this 436 /// increase the unused capacity by one? 437 pub fn removeByPtr(self: *Self, key_ptr: *K) void { 438 self.unmanaged.removeByPtr(key_ptr); 439 } 440 441 /// Creates a copy of this map, using the same allocator 442 pub fn clone(self: Self) Allocator.Error!Self { 443 var other = try self.unmanaged.cloneContext(self.allocator, self.ctx); 444 return other.promoteContext(self.allocator, self.ctx); 445 } 446 447 /// Creates a copy of this map, using a specified allocator 448 pub fn cloneWithAllocator(self: Self, new_allocator: Allocator) Allocator.Error!Self { 449 var other = try self.unmanaged.cloneContext(new_allocator, self.ctx); 450 return other.promoteContext(new_allocator, self.ctx); 451 } 452 453 /// Creates a copy of this map, using a specified context 454 pub fn cloneWithContext(self: Self, new_ctx: anytype) Allocator.Error!HashMap(K, V, @TypeOf(new_ctx), max_load_percentage) { 455 var other = try self.unmanaged.cloneContext(self.allocator, new_ctx); 456 return other.promoteContext(self.allocator, new_ctx); 457 } 458 459 /// Creates a copy of this map, using a specified allocator and context. 460 pub fn cloneWithAllocatorAndContext( 461 self: Self, 462 new_allocator: Allocator, 463 new_ctx: anytype, 464 ) Allocator.Error!HashMap(K, V, @TypeOf(new_ctx), max_load_percentage) { 465 var other = try self.unmanaged.cloneContext(new_allocator, new_ctx); 466 return other.promoteContext(new_allocator, new_ctx); 467 } 468 469 /// Set the map to an empty state, making deinitialization a no-op, and 470 /// returning a copy of the original. 471 pub fn move(self: *Self) Self { 472 self.unmanaged.pointer_stability.assertUnlocked(); 473 const result = self.*; 474 self.unmanaged = .empty; 475 return result; 476 } 477 478 /// Rehash the map, in-place. 479 /// 480 /// Over time, due to the current tombstone-based implementation, a 481 /// HashMap could become fragmented due to the buildup of tombstone 482 /// entries that causes a performance degradation due to excessive 483 /// probing. The kind of pattern that might cause this is a long-lived 484 /// HashMap with repeated inserts and deletes. 485 /// 486 /// After this function is called, there will be no tombstones in 487 /// the HashMap, each of the entries is rehashed and any existing 488 /// key/value pointers into the HashMap are invalidated. 489 pub fn rehash(self: *Self) void { 490 self.unmanaged.rehash(self.ctx); 491 } 492 }; 493 } 494 495 /// A HashMap based on open addressing and linear probing. 496 /// A lookup or modification typically incurs only 2 cache misses. 497 /// No order is guaranteed and any modification invalidates live iterators. 498 /// It achieves good performance with quite high load factors (by default, 499 /// grow is triggered at 80% full) and only one byte of overhead per element. 500 /// The struct itself is only 16 bytes for a small footprint. This comes at 501 /// the price of handling size with u32, which should be reasonable enough 502 /// for almost all uses. 503 /// Deletions are achieved with tombstones. 504 /// 505 /// Default initialization of this struct is deprecated; use `.empty` instead. 506 pub const HashMapUnmanaged = Custom; 507 fn Custom( 508 comptime K: type, 509 comptime V: type, 510 comptime Context: type, 511 comptime max_load_percentage: u64, 512 ) type { 513 if (max_load_percentage <= 0 or max_load_percentage >= 100) 514 @compileError("max_load_percentage must be between 0 and 100."); 515 return struct { 516 const Self = @This(); 517 518 // This is actually a midway pointer to the single buffer containing 519 // a `Header` field, the `Metadata`s and `Entry`s. 520 // At `-@sizeOf(Header)` is the Header field. 521 // At `sizeOf(Metadata) * capacity + offset`, which is pointed to by 522 // self.header().entries, is the array of entries. 523 // This means that the hashmap only holds one live allocation, to 524 // reduce memory fragmentation and struct size. 525 /// Pointer to the metadata. 526 metadata: ?[*]Metadata = null, 527 528 /// Current number of elements in the hashmap. 529 size: Size = 0, 530 531 // Having a countdown to grow reduces the number of instructions to 532 // execute when determining if the hashmap has enough capacity already. 533 /// Number of available slots before a grow is needed to satisfy the 534 /// `max_load_percentage`. 535 available: Size = 0, 536 537 /// Used to detect memory safety violations. 538 pointer_stability: std.debug.SafetyLock = .{}, 539 540 // This is purely empirical and not a /very smart magic constant™/. 541 /// Capacity of the first grow when bootstrapping the hashmap. 542 const minimal_capacity = 8; 543 544 /// A map containing no keys or values. 545 pub const empty: Self = .{ 546 .metadata = null, 547 .size = 0, 548 .available = 0, 549 }; 550 551 // This hashmap is specially designed for sizes that fit in a u32. 552 pub const Size = u32; 553 554 // u64 hashes guarantee us that the fingerprint bits will never be used 555 // to compute the index of a slot, maximizing the use of entropy. 556 pub const Hash = u64; 557 558 pub const Entry = struct { 559 key_ptr: *K, 560 value_ptr: *V, 561 }; 562 563 pub const KV = struct { 564 key: K, 565 value: V, 566 }; 567 568 const Header = struct { 569 values: [*]V, 570 keys: [*]K, 571 capacity: Size, 572 }; 573 574 /// Metadata for a slot. It can be in three states: empty, used or 575 /// tombstone. Tombstones indicate that an entry was previously used, 576 /// they are a simple way to handle removal. 577 /// To this state, we add 7 bits from the slot's key hash. These are 578 /// used as a fast way to disambiguate between entries without 579 /// having to use the equality function. If two fingerprints are 580 /// different, we know that we don't have to compare the keys at all. 581 /// The 7 bits are the highest ones from a 64 bit hash. This way, not 582 /// only we use the `log2(capacity)` lowest bits from the hash to determine 583 /// a slot index, but we use 7 more bits to quickly resolve collisions 584 /// when multiple elements with different hashes end up wanting to be in the same slot. 585 /// Not using the equality function means we don't have to read into 586 /// the entries array, likely avoiding a cache miss and a potentially 587 /// costly function call. 588 const Metadata = packed struct { 589 const FingerPrint = u7; 590 591 const free: FingerPrint = 0; 592 const tombstone: FingerPrint = 1; 593 594 fingerprint: FingerPrint = free, 595 used: u1 = 0, 596 597 const slot_free: u8 = @bitCast(Metadata{ .fingerprint = free }); 598 const slot_tombstone: u8 = @bitCast(Metadata{ .fingerprint = tombstone }); 599 600 pub fn isUsed(self: Metadata) bool { 601 return self.used == 1; 602 } 603 604 pub fn isTombstone(self: Metadata) bool { 605 return @as(u8, @bitCast(self)) == slot_tombstone; 606 } 607 608 pub fn isFree(self: Metadata) bool { 609 return @as(u8, @bitCast(self)) == slot_free; 610 } 611 612 pub fn takeFingerprint(hash: Hash) FingerPrint { 613 const hash_bits = @typeInfo(Hash).int.bits; 614 const fp_bits = @typeInfo(FingerPrint).int.bits; 615 return @as(FingerPrint, @truncate(hash >> (hash_bits - fp_bits))); 616 } 617 618 pub fn fill(self: *Metadata, fp: FingerPrint) void { 619 self.used = 1; 620 self.fingerprint = fp; 621 } 622 623 pub fn remove(self: *Metadata) void { 624 self.used = 0; 625 self.fingerprint = tombstone; 626 } 627 }; 628 629 comptime { 630 assert(@sizeOf(Metadata) == 1); 631 assert(@alignOf(Metadata) == 1); 632 } 633 634 pub const Iterator = struct { 635 hm: *const Self, 636 index: Size = 0, 637 638 pub fn next(it: *Iterator) ?Entry { 639 assert(it.index <= it.hm.capacity()); 640 if (it.hm.size == 0) return null; 641 642 const cap = it.hm.capacity(); 643 const end = it.hm.metadata.? + cap; 644 var metadata = it.hm.metadata.? + it.index; 645 646 while (metadata != end) : ({ 647 metadata += 1; 648 it.index += 1; 649 }) { 650 if (metadata[0].isUsed()) { 651 const key = &it.hm.keys()[it.index]; 652 const value = &it.hm.values()[it.index]; 653 it.index += 1; 654 return Entry{ .key_ptr = key, .value_ptr = value }; 655 } 656 } 657 658 return null; 659 } 660 }; 661 662 pub const KeyIterator = FieldIterator(K); 663 pub const ValueIterator = FieldIterator(V); 664 665 fn FieldIterator(comptime T: type) type { 666 return struct { 667 len: usize, 668 metadata: [*]const Metadata, 669 items: [*]T, 670 671 pub fn next(self: *@This()) ?*T { 672 while (self.len > 0) { 673 self.len -= 1; 674 const used = self.metadata[0].isUsed(); 675 const item = &self.items[0]; 676 self.metadata += 1; 677 self.items += 1; 678 if (used) { 679 return item; 680 } 681 } 682 return null; 683 } 684 }; 685 } 686 687 pub const GetOrPutResult = struct { 688 key_ptr: *K, 689 value_ptr: *V, 690 found_existing: bool, 691 }; 692 693 pub const Managed = HashMap(K, V, Context, max_load_percentage); 694 695 pub fn promote(self: Self, allocator: Allocator) Managed { 696 if (@sizeOf(Context) != 0) 697 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call promoteContext instead."); 698 return promoteContext(self, allocator, undefined); 699 } 700 701 pub fn promoteContext(self: Self, allocator: Allocator, ctx: Context) Managed { 702 return .{ 703 .unmanaged = self, 704 .allocator = allocator, 705 .ctx = ctx, 706 }; 707 } 708 709 /// Puts the hash map into a state where any method call that would 710 /// cause an existing key or value pointer to become invalidated will 711 /// instead trigger an assertion. 712 /// 713 /// `lockPointers` may be called multiple times. This allows multiple 714 /// independent users of the hash map to keep it locked simultaneously. 715 /// 716 /// `unlockPointers` restores the hash map to its previous state when 717 /// called the same number of times as `lockPointers`. 718 pub fn lockPointers(self: *Self) void { 719 self.pointer_stability.lockShared(); 720 } 721 722 /// Undoes one call to `lockPointers`. 723 pub fn unlockPointers(self: *Self) void { 724 self.pointer_stability.unlockShared(); 725 } 726 727 fn isUnderMaxLoadPercentage(size: Size, cap: Size) bool { 728 return size * 100 < max_load_percentage * cap; 729 } 730 731 pub fn deinit(self: *Self, allocator: Allocator) void { 732 self.pointer_stability.assertUnlocked(); 733 self.deallocate(allocator); 734 self.* = undefined; 735 } 736 737 fn capacityForSize(size: Size) Size { 738 var new_cap: u32 = @intCast((@as(u64, size) * 100) / max_load_percentage + 1); 739 new_cap = math.ceilPowerOfTwo(u32, new_cap) catch unreachable; 740 return new_cap; 741 } 742 743 pub fn ensureTotalCapacity(self: *Self, allocator: Allocator, new_size: Size) Allocator.Error!void { 744 if (@sizeOf(Context) != 0) 745 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call ensureTotalCapacityContext instead."); 746 return ensureTotalCapacityContext(self, allocator, new_size, undefined); 747 } 748 pub fn ensureTotalCapacityContext(self: *Self, allocator: Allocator, new_size: Size, ctx: Context) Allocator.Error!void { 749 self.pointer_stability.lock(); 750 defer self.pointer_stability.unlock(); 751 if (new_size > self.size) 752 try self.growIfNeeded(allocator, new_size - self.size, ctx); 753 } 754 755 pub fn ensureUnusedCapacity(self: *Self, allocator: Allocator, additional_size: Size) Allocator.Error!void { 756 if (@sizeOf(Context) != 0) 757 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call ensureUnusedCapacityContext instead."); 758 return ensureUnusedCapacityContext(self, allocator, additional_size, undefined); 759 } 760 pub fn ensureUnusedCapacityContext(self: *Self, allocator: Allocator, additional_size: Size, ctx: Context) Allocator.Error!void { 761 return ensureTotalCapacityContext(self, allocator, self.count() + additional_size, ctx); 762 } 763 764 pub fn clearRetainingCapacity(self: *Self) void { 765 self.pointer_stability.lock(); 766 defer self.pointer_stability.unlock(); 767 if (self.metadata) |_| { 768 self.initMetadatas(); 769 self.size = 0; 770 self.available = @truncate((self.capacity() * max_load_percentage) / 100); 771 } 772 } 773 774 pub fn clearAndFree(self: *Self, allocator: Allocator) void { 775 self.pointer_stability.lock(); 776 defer self.pointer_stability.unlock(); 777 self.deallocate(allocator); 778 self.size = 0; 779 self.available = 0; 780 } 781 782 pub fn count(self: Self) Size { 783 return self.size; 784 } 785 786 fn header(self: Self) *Header { 787 return @ptrCast(@as([*]Header, @ptrCast(@alignCast(self.metadata.?))) - 1); 788 } 789 790 fn keys(self: Self) [*]K { 791 return self.header().keys; 792 } 793 794 fn values(self: Self) [*]V { 795 return self.header().values; 796 } 797 798 pub fn capacity(self: Self) Size { 799 if (self.metadata == null) return 0; 800 801 return self.header().capacity; 802 } 803 804 pub fn iterator(self: *const Self) Iterator { 805 return .{ .hm = self }; 806 } 807 808 pub fn keyIterator(self: Self) KeyIterator { 809 if (self.metadata) |metadata| { 810 return .{ 811 .len = self.capacity(), 812 .metadata = metadata, 813 .items = self.keys(), 814 }; 815 } else { 816 return .{ 817 .len = 0, 818 .metadata = undefined, 819 .items = undefined, 820 }; 821 } 822 } 823 824 pub fn valueIterator(self: Self) ValueIterator { 825 if (self.metadata) |metadata| { 826 return .{ 827 .len = self.capacity(), 828 .metadata = metadata, 829 .items = self.values(), 830 }; 831 } else { 832 return .{ 833 .len = 0, 834 .metadata = undefined, 835 .items = undefined, 836 }; 837 } 838 } 839 840 /// Insert an entry in the map. Assumes it is not already present. 841 pub fn putNoClobber(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!void { 842 if (@sizeOf(Context) != 0) 843 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putNoClobberContext instead."); 844 return self.putNoClobberContext(allocator, key, value, undefined); 845 } 846 pub fn putNoClobberContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!void { 847 { 848 self.pointer_stability.lock(); 849 defer self.pointer_stability.unlock(); 850 try self.growIfNeeded(allocator, 1, ctx); 851 } 852 self.putAssumeCapacityNoClobberContext(key, value, ctx); 853 } 854 855 /// Asserts there is enough capacity to store the new key-value pair. 856 /// Clobbers any existing data. To detect if a put would clobber 857 /// existing data, see `getOrPutAssumeCapacity`. 858 pub fn putAssumeCapacity(self: *Self, key: K, value: V) void { 859 if (@sizeOf(Context) != 0) 860 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putAssumeCapacityContext instead."); 861 return self.putAssumeCapacityContext(key, value, undefined); 862 } 863 pub fn putAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) void { 864 const gop = self.getOrPutAssumeCapacityContext(key, ctx); 865 gop.value_ptr.* = value; 866 } 867 868 /// Insert an entry in the map. Assumes it is not already present, 869 /// and that no allocation is needed. 870 pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void { 871 if (@sizeOf(Context) != 0) 872 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putAssumeCapacityNoClobberContext instead."); 873 return self.putAssumeCapacityNoClobberContext(key, value, undefined); 874 } 875 pub fn putAssumeCapacityNoClobberContext(self: *Self, key: K, value: V, ctx: Context) void { 876 assert(!self.containsContext(key, ctx)); 877 878 const hash: Hash = ctx.hash(key); 879 const mask = self.capacity() - 1; 880 var idx: usize = @truncate(hash & mask); 881 882 var metadata = self.metadata.? + idx; 883 while (metadata[0].isUsed()) { 884 idx = (idx + 1) & mask; 885 metadata = self.metadata.? + idx; 886 } 887 888 assert(self.available > 0); 889 self.available -= 1; 890 891 const fingerprint = Metadata.takeFingerprint(hash); 892 metadata[0].fill(fingerprint); 893 self.keys()[idx] = key; 894 self.values()[idx] = value; 895 896 self.size += 1; 897 } 898 899 /// Inserts a new `Entry` into the hash map, returning the previous one, if any. 900 pub fn fetchPut(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!?KV { 901 if (@sizeOf(Context) != 0) 902 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchPutContext instead."); 903 return self.fetchPutContext(allocator, key, value, undefined); 904 } 905 pub fn fetchPutContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!?KV { 906 const gop = try self.getOrPutContext(allocator, key, ctx); 907 var result: ?KV = null; 908 if (gop.found_existing) { 909 result = KV{ 910 .key = gop.key_ptr.*, 911 .value = gop.value_ptr.*, 912 }; 913 } 914 gop.value_ptr.* = value; 915 return result; 916 } 917 918 /// Inserts a new `Entry` into the hash map, returning the previous one, if any. 919 /// If insertion happens, asserts there is enough capacity without allocating. 920 pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV { 921 if (@sizeOf(Context) != 0) 922 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchPutAssumeCapacityContext instead."); 923 return self.fetchPutAssumeCapacityContext(key, value, undefined); 924 } 925 pub fn fetchPutAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) ?KV { 926 const gop = self.getOrPutAssumeCapacityContext(key, ctx); 927 var result: ?KV = null; 928 if (gop.found_existing) { 929 result = KV{ 930 .key = gop.key_ptr.*, 931 .value = gop.value_ptr.*, 932 }; 933 } 934 gop.value_ptr.* = value; 935 return result; 936 } 937 938 /// If there is an `Entry` with a matching key, it is deleted from 939 /// the hash map, and then returned from this function. 940 pub fn fetchRemove(self: *Self, key: K) ?KV { 941 if (@sizeOf(Context) != 0) 942 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchRemoveContext instead."); 943 return self.fetchRemoveContext(key, undefined); 944 } 945 pub fn fetchRemoveContext(self: *Self, key: K, ctx: Context) ?KV { 946 return self.fetchRemoveAdapted(key, ctx); 947 } 948 pub fn fetchRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV { 949 if (self.getIndex(key, ctx)) |idx| { 950 const old_key = &self.keys()[idx]; 951 const old_val = &self.values()[idx]; 952 const result = KV{ 953 .key = old_key.*, 954 .value = old_val.*, 955 }; 956 self.metadata.?[idx].remove(); 957 old_key.* = undefined; 958 old_val.* = undefined; 959 self.size -= 1; 960 self.available += 1; 961 return result; 962 } 963 964 return null; 965 } 966 967 /// Find the index containing the data for the given key. 968 fn getIndex(self: Self, key: anytype, ctx: anytype) ?usize { 969 if (self.size == 0) { 970 // We use cold instead of unlikely to force a jump to this case, 971 // no matter the weight of the opposing side. 972 @branchHint(.cold); 973 return null; 974 } 975 976 // If you get a compile error on this line, it means that your generic hash 977 // function is invalid for these parameters. 978 const hash: Hash = ctx.hash(key); 979 980 const mask = self.capacity() - 1; 981 const fingerprint = Metadata.takeFingerprint(hash); 982 // Don't loop indefinitely when there are no empty slots. 983 var limit = self.capacity(); 984 var idx = @as(usize, @truncate(hash & mask)); 985 986 var metadata = self.metadata.? + idx; 987 while (!metadata[0].isFree() and limit != 0) { 988 if (metadata[0].isUsed() and metadata[0].fingerprint == fingerprint) { 989 const test_key = &self.keys()[idx]; 990 991 if (ctx.eql(key, test_key.*)) { 992 return idx; 993 } 994 } 995 996 limit -= 1; 997 idx = (idx + 1) & mask; 998 metadata = self.metadata.? + idx; 999 } 1000 1001 return null; 1002 } 1003 1004 pub fn getEntry(self: Self, key: K) ?Entry { 1005 if (@sizeOf(Context) != 0) 1006 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getEntryContext instead."); 1007 return self.getEntryContext(key, undefined); 1008 } 1009 pub fn getEntryContext(self: Self, key: K, ctx: Context) ?Entry { 1010 return self.getEntryAdapted(key, ctx); 1011 } 1012 pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry { 1013 if (self.getIndex(key, ctx)) |idx| { 1014 return Entry{ 1015 .key_ptr = &self.keys()[idx], 1016 .value_ptr = &self.values()[idx], 1017 }; 1018 } 1019 return null; 1020 } 1021 1022 /// Insert an entry if the associated key is not already present, otherwise update preexisting value. 1023 pub fn put(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!void { 1024 if (@sizeOf(Context) != 0) 1025 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putContext instead."); 1026 return self.putContext(allocator, key, value, undefined); 1027 } 1028 pub fn putContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!void { 1029 const result = try self.getOrPutContext(allocator, key, ctx); 1030 result.value_ptr.* = value; 1031 } 1032 1033 /// Get an optional pointer to the actual key associated with adapted key, if present. 1034 pub fn getKeyPtr(self: Self, key: K) ?*K { 1035 if (@sizeOf(Context) != 0) 1036 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getKeyPtrContext instead."); 1037 return self.getKeyPtrContext(key, undefined); 1038 } 1039 pub fn getKeyPtrContext(self: Self, key: K, ctx: Context) ?*K { 1040 return self.getKeyPtrAdapted(key, ctx); 1041 } 1042 pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K { 1043 if (self.getIndex(key, ctx)) |idx| { 1044 return &self.keys()[idx]; 1045 } 1046 return null; 1047 } 1048 1049 /// Get a copy of the actual key associated with adapted key, if present. 1050 pub fn getKey(self: Self, key: K) ?K { 1051 if (@sizeOf(Context) != 0) 1052 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getKeyContext instead."); 1053 return self.getKeyContext(key, undefined); 1054 } 1055 pub fn getKeyContext(self: Self, key: K, ctx: Context) ?K { 1056 return self.getKeyAdapted(key, ctx); 1057 } 1058 pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K { 1059 if (self.getIndex(key, ctx)) |idx| { 1060 return self.keys()[idx]; 1061 } 1062 return null; 1063 } 1064 1065 /// Get an optional pointer to the value associated with key, if present. 1066 pub fn getPtr(self: Self, key: K) ?*V { 1067 if (@sizeOf(Context) != 0) 1068 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getPtrContext instead."); 1069 return self.getPtrContext(key, undefined); 1070 } 1071 pub fn getPtrContext(self: Self, key: K, ctx: Context) ?*V { 1072 return self.getPtrAdapted(key, ctx); 1073 } 1074 pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V { 1075 if (self.getIndex(key, ctx)) |idx| { 1076 return &self.values()[idx]; 1077 } 1078 return null; 1079 } 1080 1081 /// Get a copy of the value associated with key, if present. 1082 pub fn get(self: Self, key: K) ?V { 1083 if (@sizeOf(Context) != 0) 1084 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getContext instead."); 1085 return self.getContext(key, undefined); 1086 } 1087 pub fn getContext(self: Self, key: K, ctx: Context) ?V { 1088 return self.getAdapted(key, ctx); 1089 } 1090 pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V { 1091 if (self.getIndex(key, ctx)) |idx| { 1092 return self.values()[idx]; 1093 } 1094 return null; 1095 } 1096 1097 pub fn getOrPut(self: *Self, allocator: Allocator, key: K) Allocator.Error!GetOrPutResult { 1098 if (@sizeOf(Context) != 0) 1099 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContext instead."); 1100 return self.getOrPutContext(allocator, key, undefined); 1101 } 1102 pub fn getOrPutContext(self: *Self, allocator: Allocator, key: K, ctx: Context) Allocator.Error!GetOrPutResult { 1103 const gop = try self.getOrPutContextAdapted(allocator, key, ctx, ctx); 1104 if (!gop.found_existing) { 1105 gop.key_ptr.* = key; 1106 } 1107 return gop; 1108 } 1109 pub fn getOrPutAdapted(self: *Self, allocator: Allocator, key: anytype, key_ctx: anytype) Allocator.Error!GetOrPutResult { 1110 if (@sizeOf(Context) != 0) 1111 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContextAdapted instead."); 1112 return self.getOrPutContextAdapted(allocator, key, key_ctx, undefined); 1113 } 1114 pub fn getOrPutContextAdapted(self: *Self, allocator: Allocator, key: anytype, key_ctx: anytype, ctx: Context) Allocator.Error!GetOrPutResult { 1115 { 1116 self.pointer_stability.lock(); 1117 defer self.pointer_stability.unlock(); 1118 self.growIfNeeded(allocator, 1, ctx) catch |err| { 1119 // If allocation fails, try to do the lookup anyway. 1120 // If we find an existing item, we can return it. 1121 // Otherwise return the error, we could not add another. 1122 const index = self.getIndex(key, key_ctx) orelse return err; 1123 return GetOrPutResult{ 1124 .key_ptr = &self.keys()[index], 1125 .value_ptr = &self.values()[index], 1126 .found_existing = true, 1127 }; 1128 }; 1129 } 1130 return self.getOrPutAssumeCapacityAdapted(key, key_ctx); 1131 } 1132 1133 pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult { 1134 if (@sizeOf(Context) != 0) 1135 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutAssumeCapacityContext instead."); 1136 return self.getOrPutAssumeCapacityContext(key, undefined); 1137 } 1138 pub fn getOrPutAssumeCapacityContext(self: *Self, key: K, ctx: Context) GetOrPutResult { 1139 const result = self.getOrPutAssumeCapacityAdapted(key, ctx); 1140 if (!result.found_existing) { 1141 result.key_ptr.* = key; 1142 } 1143 return result; 1144 } 1145 pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult { 1146 1147 // If you get a compile error on this line, it means that your generic hash 1148 // function is invalid for these parameters. 1149 const hash: Hash = ctx.hash(key); 1150 1151 const mask = self.capacity() - 1; 1152 const fingerprint = Metadata.takeFingerprint(hash); 1153 var limit = self.capacity(); 1154 var idx = @as(usize, @truncate(hash & mask)); 1155 1156 var first_tombstone_idx: usize = self.capacity(); // invalid index 1157 var metadata = self.metadata.? + idx; 1158 while (!metadata[0].isFree() and limit != 0) { 1159 if (metadata[0].isUsed() and metadata[0].fingerprint == fingerprint) { 1160 const test_key = &self.keys()[idx]; 1161 // If you get a compile error on this line, it means that your generic eql 1162 // function is invalid for these parameters. 1163 1164 if (ctx.eql(key, test_key.*)) { 1165 return GetOrPutResult{ 1166 .key_ptr = test_key, 1167 .value_ptr = &self.values()[idx], 1168 .found_existing = true, 1169 }; 1170 } 1171 } else if (first_tombstone_idx == self.capacity() and metadata[0].isTombstone()) { 1172 first_tombstone_idx = idx; 1173 } 1174 1175 limit -= 1; 1176 idx = (idx + 1) & mask; 1177 metadata = self.metadata.? + idx; 1178 } 1179 1180 if (first_tombstone_idx < self.capacity()) { 1181 // Cheap try to lower probing lengths after deletions. Recycle a tombstone. 1182 idx = first_tombstone_idx; 1183 metadata = self.metadata.? + idx; 1184 } 1185 // We're using a slot previously free or a tombstone. 1186 self.available -= 1; 1187 1188 metadata[0].fill(fingerprint); 1189 const new_key = &self.keys()[idx]; 1190 const new_value = &self.values()[idx]; 1191 new_key.* = undefined; 1192 new_value.* = undefined; 1193 self.size += 1; 1194 1195 return GetOrPutResult{ 1196 .key_ptr = new_key, 1197 .value_ptr = new_value, 1198 .found_existing = false, 1199 }; 1200 } 1201 1202 pub fn getOrPutValue(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!Entry { 1203 if (@sizeOf(Context) != 0) 1204 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutValueContext instead."); 1205 return self.getOrPutValueContext(allocator, key, value, undefined); 1206 } 1207 pub fn getOrPutValueContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!Entry { 1208 const res = try self.getOrPutAdapted(allocator, key, ctx); 1209 if (!res.found_existing) { 1210 res.key_ptr.* = key; 1211 res.value_ptr.* = value; 1212 } 1213 return Entry{ .key_ptr = res.key_ptr, .value_ptr = res.value_ptr }; 1214 } 1215 1216 /// Return true if there is a value associated with key in the map. 1217 pub fn contains(self: Self, key: K) bool { 1218 if (@sizeOf(Context) != 0) 1219 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call containsContext instead."); 1220 return self.containsContext(key, undefined); 1221 } 1222 pub fn containsContext(self: Self, key: K, ctx: Context) bool { 1223 return self.containsAdapted(key, ctx); 1224 } 1225 pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool { 1226 return self.getIndex(key, ctx) != null; 1227 } 1228 1229 fn removeByIndex(self: *Self, idx: usize) void { 1230 self.metadata.?[idx].remove(); 1231 self.keys()[idx] = undefined; 1232 self.values()[idx] = undefined; 1233 self.size -= 1; 1234 self.available += 1; 1235 } 1236 1237 /// If there is an `Entry` with a matching key, it is deleted from 1238 /// the hash map, and this function returns true. Otherwise this 1239 /// function returns false. 1240 /// 1241 /// TODO: answer the question in these doc comments, does this 1242 /// increase the unused capacity by one? 1243 pub fn remove(self: *Self, key: K) bool { 1244 if (@sizeOf(Context) != 0) 1245 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call removeContext instead."); 1246 return self.removeContext(key, undefined); 1247 } 1248 1249 /// TODO: answer the question in these doc comments, does this 1250 /// increase the unused capacity by one? 1251 pub fn removeContext(self: *Self, key: K, ctx: Context) bool { 1252 return self.removeAdapted(key, ctx); 1253 } 1254 1255 /// TODO: answer the question in these doc comments, does this 1256 /// increase the unused capacity by one? 1257 pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool { 1258 if (self.getIndex(key, ctx)) |idx| { 1259 self.removeByIndex(idx); 1260 return true; 1261 } 1262 1263 return false; 1264 } 1265 1266 /// Delete the entry with key pointed to by key_ptr from the hash map. 1267 /// key_ptr is assumed to be a valid pointer to a key that is present 1268 /// in the hash map. 1269 /// 1270 /// TODO: answer the question in these doc comments, does this 1271 /// increase the unused capacity by one? 1272 pub fn removeByPtr(self: *Self, key_ptr: *K) void { 1273 // if @sizeOf(K) == 0 then there is at most one item in the hash 1274 // map, which is assumed to exist as key_ptr must be valid. This 1275 // item must be at index 0. 1276 const idx = if (@sizeOf(K) > 0) 1277 @as([*]K, @ptrCast(key_ptr)) - self.keys() 1278 else 1279 0; 1280 1281 self.removeByIndex(idx); 1282 } 1283 1284 fn initMetadatas(self: *Self) void { 1285 @memset(@as([*]u8, @ptrCast(self.metadata.?))[0 .. @sizeOf(Metadata) * self.capacity()], 0); 1286 } 1287 1288 // This counts the number of occupied slots (not counting tombstones), which is 1289 // what has to stay under the max_load_percentage of capacity. 1290 fn load(self: Self) Size { 1291 const max_load = (self.capacity() * max_load_percentage) / 100; 1292 assert(max_load >= self.available); 1293 return @as(Size, @truncate(max_load - self.available)); 1294 } 1295 1296 fn growIfNeeded(self: *Self, allocator: Allocator, new_count: Size, ctx: Context) Allocator.Error!void { 1297 if (new_count > self.available) { 1298 try self.grow(allocator, capacityForSize(self.load() + new_count), ctx); 1299 } 1300 } 1301 1302 pub fn clone(self: Self, allocator: Allocator) Allocator.Error!Self { 1303 if (@sizeOf(Context) != 0) 1304 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call cloneContext instead."); 1305 return self.cloneContext(allocator, @as(Context, undefined)); 1306 } 1307 pub fn cloneContext(self: Self, allocator: Allocator, new_ctx: anytype) Allocator.Error!HashMapUnmanaged(K, V, @TypeOf(new_ctx), max_load_percentage) { 1308 var other: HashMapUnmanaged(K, V, @TypeOf(new_ctx), max_load_percentage) = .empty; 1309 if (self.size == 0) 1310 return other; 1311 1312 const new_cap = capacityForSize(self.size); 1313 try other.allocate(allocator, new_cap); 1314 other.initMetadatas(); 1315 other.available = @truncate((new_cap * max_load_percentage) / 100); 1316 1317 var i: Size = 0; 1318 var metadata = self.metadata.?; 1319 const keys_ptr = self.keys(); 1320 const values_ptr = self.values(); 1321 while (i < self.capacity()) : (i += 1) { 1322 if (metadata[i].isUsed()) { 1323 other.putAssumeCapacityNoClobberContext(keys_ptr[i], values_ptr[i], new_ctx); 1324 if (other.size == self.size) 1325 break; 1326 } 1327 } 1328 1329 return other; 1330 } 1331 1332 /// Set the map to an empty state, making deinitialization a no-op, and 1333 /// returning a copy of the original. 1334 pub fn move(self: *Self) Self { 1335 self.pointer_stability.assertUnlocked(); 1336 const result = self.*; 1337 self.* = .empty; 1338 return result; 1339 } 1340 1341 /// Rehash the map, in-place. 1342 /// 1343 /// Over time, due to the current tombstone-based implementation, a 1344 /// HashMap could become fragmented due to the buildup of tombstone 1345 /// entries that causes a performance degradation due to excessive 1346 /// probing. The kind of pattern that might cause this is a long-lived 1347 /// HashMap with repeated inserts and deletes. 1348 /// 1349 /// After this function is called, there will be no tombstones in 1350 /// the HashMap, each of the entries is rehashed and any existing 1351 /// key/value pointers into the HashMap are invalidated. 1352 pub fn rehash(self: *Self, ctx: anytype) void { 1353 const mask = self.capacity() - 1; 1354 1355 var metadata = self.metadata.?; 1356 var keys_ptr = self.keys(); 1357 var values_ptr = self.values(); 1358 var curr: Size = 0; 1359 1360 // While we are re-hashing every slot, we will use the 1361 // fingerprint to mark used buckets as being used and either free 1362 // (needing to be rehashed) or tombstone (already rehashed). 1363 1364 while (curr < self.capacity()) : (curr += 1) { 1365 metadata[curr].fingerprint = Metadata.free; 1366 } 1367 1368 // Now iterate over all the buckets, rehashing them 1369 1370 curr = 0; 1371 while (curr < self.capacity()) { 1372 if (!metadata[curr].isUsed()) { 1373 assert(metadata[curr].isFree()); 1374 curr += 1; 1375 continue; 1376 } 1377 1378 const hash = ctx.hash(keys_ptr[curr]); 1379 const fingerprint = Metadata.takeFingerprint(hash); 1380 var idx = @as(usize, @truncate(hash & mask)); 1381 1382 // For each bucket, rehash to an index: 1383 // 1) before the cursor, probed into a free slot, or 1384 // 2) equal to the cursor, no need to move, or 1385 // 3) ahead of the cursor, probing over already rehashed 1386 1387 while ((idx < curr and metadata[idx].isUsed()) or 1388 (idx > curr and metadata[idx].fingerprint == Metadata.tombstone)) 1389 { 1390 idx = (idx + 1) & mask; 1391 } 1392 1393 if (idx < curr) { 1394 assert(metadata[idx].isFree()); 1395 metadata[idx].fill(fingerprint); 1396 keys_ptr[idx] = keys_ptr[curr]; 1397 values_ptr[idx] = values_ptr[curr]; 1398 1399 metadata[curr].used = 0; 1400 assert(metadata[curr].isFree()); 1401 keys_ptr[curr] = undefined; 1402 values_ptr[curr] = undefined; 1403 1404 curr += 1; 1405 } else if (idx == curr) { 1406 metadata[idx].fingerprint = fingerprint; 1407 curr += 1; 1408 } else { 1409 assert(metadata[idx].fingerprint != Metadata.tombstone); 1410 metadata[idx].fingerprint = Metadata.tombstone; 1411 if (metadata[idx].isUsed()) { 1412 std.mem.swap(K, &keys_ptr[curr], &keys_ptr[idx]); 1413 std.mem.swap(V, &values_ptr[curr], &values_ptr[idx]); 1414 } else { 1415 metadata[idx].used = 1; 1416 keys_ptr[idx] = keys_ptr[curr]; 1417 values_ptr[idx] = values_ptr[curr]; 1418 1419 metadata[curr].fingerprint = Metadata.free; 1420 metadata[curr].used = 0; 1421 keys_ptr[curr] = undefined; 1422 values_ptr[curr] = undefined; 1423 1424 curr += 1; 1425 } 1426 } 1427 } 1428 } 1429 1430 fn grow(self: *Self, allocator: Allocator, new_capacity: Size, ctx: Context) Allocator.Error!void { 1431 @branchHint(.cold); 1432 const new_cap = @max(new_capacity, minimal_capacity); 1433 assert(new_cap > self.capacity()); 1434 assert(std.math.isPowerOfTwo(new_cap)); 1435 1436 var map: Self = .{}; 1437 try map.allocate(allocator, new_cap); 1438 errdefer comptime unreachable; 1439 map.pointer_stability.lock(); 1440 map.initMetadatas(); 1441 map.available = @truncate((new_cap * max_load_percentage) / 100); 1442 1443 if (self.size != 0) { 1444 const old_capacity = self.capacity(); 1445 for ( 1446 self.metadata.?[0..old_capacity], 1447 self.keys()[0..old_capacity], 1448 self.values()[0..old_capacity], 1449 ) |m, k, v| { 1450 if (!m.isUsed()) continue; 1451 map.putAssumeCapacityNoClobberContext(k, v, ctx); 1452 if (map.size == self.size) break; 1453 } 1454 } 1455 1456 self.size = 0; 1457 self.pointer_stability = .{}; 1458 std.mem.swap(Self, self, &map); 1459 map.deinit(allocator); 1460 } 1461 1462 fn allocate(self: *Self, allocator: Allocator, new_capacity: Size) Allocator.Error!void { 1463 const header_align = @alignOf(Header); 1464 const key_align = if (@sizeOf(K) == 0) 1 else @alignOf(K); 1465 const val_align = if (@sizeOf(V) == 0) 1 else @alignOf(V); 1466 const max_align: Alignment = comptime .fromByteUnits(@max(header_align, key_align, val_align)); 1467 1468 const new_cap: usize = new_capacity; 1469 const meta_size = @sizeOf(Header) + new_cap * @sizeOf(Metadata); 1470 comptime assert(@alignOf(Metadata) == 1); 1471 1472 const keys_start = std.mem.alignForward(usize, meta_size, key_align); 1473 const keys_end = keys_start + new_cap * @sizeOf(K); 1474 1475 const vals_start = std.mem.alignForward(usize, keys_end, val_align); 1476 const vals_end = vals_start + new_cap * @sizeOf(V); 1477 1478 const total_size = max_align.forward(vals_end); 1479 1480 const slice = try allocator.alignedAlloc(u8, max_align, total_size); 1481 const ptr: [*]u8 = @ptrCast(slice.ptr); 1482 1483 const metadata = ptr + @sizeOf(Header); 1484 1485 const hdr = @as(*Header, @ptrCast(@alignCast(ptr))); 1486 if (@sizeOf([*]V) != 0) { 1487 hdr.values = @ptrCast(@alignCast((ptr + vals_start))); 1488 } 1489 if (@sizeOf([*]K) != 0) { 1490 hdr.keys = @ptrCast(@alignCast((ptr + keys_start))); 1491 } 1492 hdr.capacity = new_capacity; 1493 self.metadata = @ptrCast(@alignCast(metadata)); 1494 } 1495 1496 fn deallocate(self: *Self, allocator: Allocator) void { 1497 if (self.metadata == null) return; 1498 1499 const header_align = @alignOf(Header); 1500 const key_align = if (@sizeOf(K) == 0) 1 else @alignOf(K); 1501 const val_align = if (@sizeOf(V) == 0) 1 else @alignOf(V); 1502 const max_align = comptime @max(header_align, key_align, val_align); 1503 1504 const cap: usize = self.capacity(); 1505 const meta_size = @sizeOf(Header) + cap * @sizeOf(Metadata); 1506 comptime assert(@alignOf(Metadata) == 1); 1507 1508 const keys_start = std.mem.alignForward(usize, meta_size, key_align); 1509 const keys_end = keys_start + cap * @sizeOf(K); 1510 1511 const vals_start = std.mem.alignForward(usize, keys_end, val_align); 1512 const vals_end = vals_start + cap * @sizeOf(V); 1513 1514 const total_size = std.mem.alignForward(usize, vals_end, max_align); 1515 1516 const slice = @as([*]align(max_align) u8, @ptrCast(@alignCast(self.header())))[0..total_size]; 1517 allocator.free(slice); 1518 1519 self.metadata = null; 1520 self.available = 0; 1521 } 1522 1523 /// This function is used in the debugger pretty formatters in lib/lldb/ to fetch the 1524 /// header type to facilitate fancy debug printing for this type. 1525 fn dbHelper(self: *Self, hdr: *Header, entry: *Entry) void { 1526 _ = self; 1527 _ = hdr; 1528 _ = entry; 1529 } 1530 1531 comptime { 1532 if (!builtin.strip_debug_info) switch (builtin.zig_backend) { 1533 .stage2_llvm => _ = &dbHelper, 1534 .stage2_x86_64 => _ = @as(KV, undefined), 1535 else => {}, 1536 }; 1537 } 1538 }; 1539 } 1540 1541 const testing = std.testing; 1542 const expect = std.testing.expect; 1543 const expectEqual = std.testing.expectEqual; 1544 1545 test "basic usage" { 1546 var map = AutoHashMap(u32, u32).init(std.testing.allocator); 1547 defer map.deinit(); 1548 1549 const count = 5; 1550 var i: u32 = 0; 1551 var total: u32 = 0; 1552 while (i < count) : (i += 1) { 1553 try map.put(i, i); 1554 total += i; 1555 } 1556 1557 var sum: u32 = 0; 1558 var it = map.iterator(); 1559 while (it.next()) |kv| { 1560 sum += kv.key_ptr.*; 1561 } 1562 try expectEqual(total, sum); 1563 1564 i = 0; 1565 sum = 0; 1566 while (i < count) : (i += 1) { 1567 try expectEqual(i, map.get(i).?); 1568 sum += map.get(i).?; 1569 } 1570 try expectEqual(total, sum); 1571 } 1572 1573 test "ensureTotalCapacity" { 1574 var map = AutoHashMap(i32, i32).init(std.testing.allocator); 1575 defer map.deinit(); 1576 1577 try map.ensureTotalCapacity(20); 1578 const initial_capacity = map.capacity(); 1579 try testing.expect(initial_capacity >= 20); 1580 var i: i32 = 0; 1581 while (i < 20) : (i += 1) { 1582 try testing.expect(map.fetchPutAssumeCapacity(i, i + 10) == null); 1583 } 1584 // shouldn't resize from putAssumeCapacity 1585 try testing.expect(initial_capacity == map.capacity()); 1586 } 1587 1588 test "ensureUnusedCapacity with tombstones" { 1589 var map = AutoHashMap(i32, i32).init(std.testing.allocator); 1590 defer map.deinit(); 1591 1592 var i: i32 = 0; 1593 while (i < 100) : (i += 1) { 1594 try map.ensureUnusedCapacity(1); 1595 map.putAssumeCapacity(i, i); 1596 _ = map.remove(i); 1597 } 1598 } 1599 1600 test "clearRetainingCapacity" { 1601 var map = AutoHashMap(u32, u32).init(std.testing.allocator); 1602 defer map.deinit(); 1603 1604 map.clearRetainingCapacity(); 1605 1606 try map.put(1, 1); 1607 try expectEqual(map.get(1).?, 1); 1608 try expectEqual(map.count(), 1); 1609 1610 map.clearRetainingCapacity(); 1611 map.putAssumeCapacity(1, 1); 1612 try expectEqual(map.get(1).?, 1); 1613 try expectEqual(map.count(), 1); 1614 1615 const cap = map.capacity(); 1616 try expect(cap > 0); 1617 1618 map.clearRetainingCapacity(); 1619 map.clearRetainingCapacity(); 1620 try expectEqual(map.count(), 0); 1621 try expectEqual(map.capacity(), cap); 1622 try expect(!map.contains(1)); 1623 } 1624 1625 test "grow" { 1626 var map = AutoHashMap(u32, u32).init(std.testing.allocator); 1627 defer map.deinit(); 1628 1629 const growTo = 12456; 1630 1631 var i: u32 = 0; 1632 while (i < growTo) : (i += 1) { 1633 try map.put(i, i); 1634 } 1635 try expectEqual(map.count(), growTo); 1636 1637 i = 0; 1638 var it = map.iterator(); 1639 while (it.next()) |kv| { 1640 try expectEqual(kv.key_ptr.*, kv.value_ptr.*); 1641 i += 1; 1642 } 1643 try expectEqual(i, growTo); 1644 1645 i = 0; 1646 while (i < growTo) : (i += 1) { 1647 try expectEqual(map.get(i).?, i); 1648 } 1649 } 1650 1651 test "clone" { 1652 var map = AutoHashMap(u32, u32).init(std.testing.allocator); 1653 defer map.deinit(); 1654 1655 var a = try map.clone(); 1656 defer a.deinit(); 1657 1658 try expectEqual(a.count(), 0); 1659 1660 try a.put(1, 1); 1661 try a.put(2, 2); 1662 try a.put(3, 3); 1663 1664 var b = try a.clone(); 1665 defer b.deinit(); 1666 1667 try expectEqual(b.count(), 3); 1668 try expectEqual(b.get(1).?, 1); 1669 try expectEqual(b.get(2).?, 2); 1670 try expectEqual(b.get(3).?, 3); 1671 1672 var original = AutoHashMap(i32, i32).init(std.testing.allocator); 1673 defer original.deinit(); 1674 1675 var i: u8 = 0; 1676 while (i < 10) : (i += 1) { 1677 try original.putNoClobber(i, i * 10); 1678 } 1679 1680 var copy = try original.clone(); 1681 defer copy.deinit(); 1682 1683 i = 0; 1684 while (i < 10) : (i += 1) { 1685 try testing.expect(copy.get(i).? == i * 10); 1686 } 1687 } 1688 1689 test "ensureTotalCapacity with existing elements" { 1690 var map = AutoHashMap(u32, u32).init(std.testing.allocator); 1691 defer map.deinit(); 1692 1693 try map.put(0, 0); 1694 try expectEqual(map.count(), 1); 1695 try expectEqual(map.capacity(), @TypeOf(map).Unmanaged.minimal_capacity); 1696 1697 try map.ensureTotalCapacity(65); 1698 try expectEqual(map.count(), 1); 1699 try expectEqual(map.capacity(), 128); 1700 } 1701 1702 test "ensureTotalCapacity satisfies max load factor" { 1703 var map = AutoHashMap(u32, u32).init(std.testing.allocator); 1704 defer map.deinit(); 1705 1706 try map.ensureTotalCapacity(127); 1707 try expectEqual(map.capacity(), 256); 1708 } 1709 1710 test "remove" { 1711 var map = AutoHashMap(u32, u32).init(std.testing.allocator); 1712 defer map.deinit(); 1713 1714 var i: u32 = 0; 1715 while (i < 16) : (i += 1) { 1716 try map.put(i, i); 1717 } 1718 1719 i = 0; 1720 while (i < 16) : (i += 1) { 1721 if (i % 3 == 0) { 1722 _ = map.remove(i); 1723 } 1724 } 1725 try expectEqual(map.count(), 10); 1726 var it = map.iterator(); 1727 while (it.next()) |kv| { 1728 try expectEqual(kv.key_ptr.*, kv.value_ptr.*); 1729 try expect(kv.key_ptr.* % 3 != 0); 1730 } 1731 1732 i = 0; 1733 while (i < 16) : (i += 1) { 1734 if (i % 3 == 0) { 1735 try expect(!map.contains(i)); 1736 } else { 1737 try expectEqual(map.get(i).?, i); 1738 } 1739 } 1740 } 1741 1742 test "reverse removes" { 1743 var map = AutoHashMap(u32, u32).init(std.testing.allocator); 1744 defer map.deinit(); 1745 1746 var i: u32 = 0; 1747 while (i < 16) : (i += 1) { 1748 try map.putNoClobber(i, i); 1749 } 1750 1751 i = 16; 1752 while (i > 0) : (i -= 1) { 1753 _ = map.remove(i - 1); 1754 try expect(!map.contains(i - 1)); 1755 var j: u32 = 0; 1756 while (j < i - 1) : (j += 1) { 1757 try expectEqual(map.get(j).?, j); 1758 } 1759 } 1760 1761 try expectEqual(map.count(), 0); 1762 } 1763 1764 test "multiple removes on same metadata" { 1765 var map = AutoHashMap(u32, u32).init(std.testing.allocator); 1766 defer map.deinit(); 1767 1768 var i: u32 = 0; 1769 while (i < 16) : (i += 1) { 1770 try map.put(i, i); 1771 } 1772 1773 _ = map.remove(7); 1774 _ = map.remove(15); 1775 _ = map.remove(14); 1776 _ = map.remove(13); 1777 try expect(!map.contains(7)); 1778 try expect(!map.contains(15)); 1779 try expect(!map.contains(14)); 1780 try expect(!map.contains(13)); 1781 1782 i = 0; 1783 while (i < 13) : (i += 1) { 1784 if (i == 7) { 1785 try expect(!map.contains(i)); 1786 } else { 1787 try expectEqual(map.get(i).?, i); 1788 } 1789 } 1790 1791 try map.put(15, 15); 1792 try map.put(13, 13); 1793 try map.put(14, 14); 1794 try map.put(7, 7); 1795 i = 0; 1796 while (i < 16) : (i += 1) { 1797 try expectEqual(map.get(i).?, i); 1798 } 1799 } 1800 1801 test "put and remove loop in random order" { 1802 var map = AutoHashMap(u32, u32).init(std.testing.allocator); 1803 defer map.deinit(); 1804 1805 var keys = std.array_list.Managed(u32).init(std.testing.allocator); 1806 defer keys.deinit(); 1807 1808 const size = 32; 1809 const iterations = 100; 1810 1811 var i: u32 = 0; 1812 while (i < size) : (i += 1) { 1813 try keys.append(i); 1814 } 1815 var prng = std.Random.DefaultPrng.init(std.testing.random_seed); 1816 const random = prng.random(); 1817 1818 while (i < iterations) : (i += 1) { 1819 random.shuffle(u32, keys.items); 1820 1821 for (keys.items) |key| { 1822 try map.put(key, key); 1823 } 1824 try expectEqual(map.count(), size); 1825 1826 for (keys.items) |key| { 1827 _ = map.remove(key); 1828 } 1829 try expectEqual(map.count(), 0); 1830 } 1831 } 1832 1833 test "remove many elements in random order" { 1834 const Map = AutoHashMap(u32, u32); 1835 const n = 1000 * 100; 1836 var map = Map.init(std.heap.page_allocator); 1837 defer map.deinit(); 1838 1839 var keys = std.array_list.Managed(u32).init(std.heap.page_allocator); 1840 defer keys.deinit(); 1841 1842 var i: u32 = 0; 1843 while (i < n) : (i += 1) { 1844 keys.append(i) catch unreachable; 1845 } 1846 1847 var prng = std.Random.DefaultPrng.init(std.testing.random_seed); 1848 const random = prng.random(); 1849 random.shuffle(u32, keys.items); 1850 1851 for (keys.items) |key| { 1852 map.put(key, key) catch unreachable; 1853 } 1854 1855 random.shuffle(u32, keys.items); 1856 i = 0; 1857 while (i < n) : (i += 1) { 1858 const key = keys.items[i]; 1859 _ = map.remove(key); 1860 } 1861 } 1862 1863 test "put" { 1864 var map = AutoHashMap(u32, u32).init(std.testing.allocator); 1865 defer map.deinit(); 1866 1867 var i: u32 = 0; 1868 while (i < 16) : (i += 1) { 1869 try map.put(i, i); 1870 } 1871 1872 i = 0; 1873 while (i < 16) : (i += 1) { 1874 try expectEqual(map.get(i).?, i); 1875 } 1876 1877 i = 0; 1878 while (i < 16) : (i += 1) { 1879 try map.put(i, i * 16 + 1); 1880 } 1881 1882 i = 0; 1883 while (i < 16) : (i += 1) { 1884 try expectEqual(map.get(i).?, i * 16 + 1); 1885 } 1886 } 1887 1888 test "putAssumeCapacity" { 1889 var map = AutoHashMap(u32, u32).init(std.testing.allocator); 1890 defer map.deinit(); 1891 1892 try map.ensureTotalCapacity(20); 1893 var i: u32 = 0; 1894 while (i < 20) : (i += 1) { 1895 map.putAssumeCapacityNoClobber(i, i); 1896 } 1897 1898 i = 0; 1899 var sum = i; 1900 while (i < 20) : (i += 1) { 1901 sum += map.getPtr(i).?.*; 1902 } 1903 try expectEqual(sum, 190); 1904 1905 i = 0; 1906 while (i < 20) : (i += 1) { 1907 map.putAssumeCapacity(i, 1); 1908 } 1909 1910 i = 0; 1911 sum = i; 1912 while (i < 20) : (i += 1) { 1913 sum += map.get(i).?; 1914 } 1915 try expectEqual(sum, 20); 1916 } 1917 1918 test "repeat putAssumeCapacity/remove" { 1919 var map = AutoHashMap(u32, u32).init(std.testing.allocator); 1920 defer map.deinit(); 1921 1922 try map.ensureTotalCapacity(20); 1923 const limit = map.unmanaged.available; 1924 1925 var i: u32 = 0; 1926 while (i < limit) : (i += 1) { 1927 map.putAssumeCapacityNoClobber(i, i); 1928 } 1929 1930 // Repeatedly delete/insert an entry without resizing the map. 1931 // Put to different keys so entries don't land in the just-freed slot. 1932 i = 0; 1933 while (i < 10 * limit) : (i += 1) { 1934 try testing.expect(map.remove(i)); 1935 if (i % 2 == 0) { 1936 map.putAssumeCapacityNoClobber(limit + i, i); 1937 } else { 1938 map.putAssumeCapacity(limit + i, i); 1939 } 1940 } 1941 1942 i = 9 * limit; 1943 while (i < 10 * limit) : (i += 1) { 1944 try expectEqual(map.get(limit + i), i); 1945 } 1946 try expectEqual(map.unmanaged.available, 0); 1947 try expectEqual(map.unmanaged.count(), limit); 1948 } 1949 1950 test "getOrPut" { 1951 var map = AutoHashMap(u32, u32).init(std.testing.allocator); 1952 defer map.deinit(); 1953 1954 var i: u32 = 0; 1955 while (i < 10) : (i += 1) { 1956 try map.put(i * 2, 2); 1957 } 1958 1959 i = 0; 1960 while (i < 20) : (i += 1) { 1961 _ = try map.getOrPutValue(i, 1); 1962 } 1963 1964 i = 0; 1965 var sum = i; 1966 while (i < 20) : (i += 1) { 1967 sum += map.get(i).?; 1968 } 1969 1970 try expectEqual(sum, 30); 1971 } 1972 1973 test "basic hash map usage" { 1974 var map = AutoHashMap(i32, i32).init(std.testing.allocator); 1975 defer map.deinit(); 1976 1977 try testing.expect((try map.fetchPut(1, 11)) == null); 1978 try testing.expect((try map.fetchPut(2, 22)) == null); 1979 try testing.expect((try map.fetchPut(3, 33)) == null); 1980 try testing.expect((try map.fetchPut(4, 44)) == null); 1981 1982 try map.putNoClobber(5, 55); 1983 try testing.expect((try map.fetchPut(5, 66)).?.value == 55); 1984 try testing.expect((try map.fetchPut(5, 55)).?.value == 66); 1985 1986 const gop1 = try map.getOrPut(5); 1987 try testing.expect(gop1.found_existing == true); 1988 try testing.expect(gop1.value_ptr.* == 55); 1989 gop1.value_ptr.* = 77; 1990 try testing.expect(map.getEntry(5).?.value_ptr.* == 77); 1991 1992 const gop2 = try map.getOrPut(99); 1993 try testing.expect(gop2.found_existing == false); 1994 gop2.value_ptr.* = 42; 1995 try testing.expect(map.getEntry(99).?.value_ptr.* == 42); 1996 1997 const gop3 = try map.getOrPutValue(5, 5); 1998 try testing.expect(gop3.value_ptr.* == 77); 1999 2000 const gop4 = try map.getOrPutValue(100, 41); 2001 try testing.expect(gop4.value_ptr.* == 41); 2002 2003 try testing.expect(map.contains(2)); 2004 try testing.expect(map.getEntry(2).?.value_ptr.* == 22); 2005 try testing.expect(map.get(2).? == 22); 2006 2007 const rmv1 = map.fetchRemove(2); 2008 try testing.expect(rmv1.?.key == 2); 2009 try testing.expect(rmv1.?.value == 22); 2010 try testing.expect(map.fetchRemove(2) == null); 2011 try testing.expect(map.remove(2) == false); 2012 try testing.expect(map.getEntry(2) == null); 2013 try testing.expect(map.get(2) == null); 2014 2015 try testing.expect(map.remove(3) == true); 2016 } 2017 2018 test "getOrPutAdapted" { 2019 const AdaptedContext = struct { 2020 fn eql(self: @This(), adapted_key: []const u8, test_key: u64) bool { 2021 _ = self; 2022 return std.fmt.parseInt(u64, adapted_key, 10) catch unreachable == test_key; 2023 } 2024 fn hash(self: @This(), adapted_key: []const u8) u64 { 2025 _ = self; 2026 const key = std.fmt.parseInt(u64, adapted_key, 10) catch unreachable; 2027 return (AutoContext(u64){}).hash(key); 2028 } 2029 }; 2030 var map = AutoHashMap(u64, u64).init(testing.allocator); 2031 defer map.deinit(); 2032 2033 const keys = [_][]const u8{ 2034 "1231", 2035 "4564", 2036 "7894", 2037 "1132", 2038 "65235", 2039 "95462", 2040 "0112305", 2041 "00658", 2042 "0", 2043 "2", 2044 }; 2045 2046 var real_keys: [keys.len]u64 = undefined; 2047 2048 inline for (keys, 0..) |key_str, i| { 2049 const result = try map.getOrPutAdapted(key_str, AdaptedContext{}); 2050 try testing.expect(!result.found_existing); 2051 real_keys[i] = std.fmt.parseInt(u64, key_str, 10) catch unreachable; 2052 result.key_ptr.* = real_keys[i]; 2053 result.value_ptr.* = i * 2; 2054 } 2055 2056 try testing.expectEqual(map.count(), keys.len); 2057 2058 inline for (keys, 0..) |key_str, i| { 2059 const result = map.getOrPutAssumeCapacityAdapted(key_str, AdaptedContext{}); 2060 try testing.expect(result.found_existing); 2061 try testing.expectEqual(real_keys[i], result.key_ptr.*); 2062 try testing.expectEqual(@as(u64, i) * 2, result.value_ptr.*); 2063 try testing.expectEqual(real_keys[i], map.getKeyAdapted(key_str, AdaptedContext{}).?); 2064 } 2065 } 2066 2067 test "ensureUnusedCapacity" { 2068 var map = AutoHashMap(u64, u64).init(testing.allocator); 2069 defer map.deinit(); 2070 2071 try map.ensureUnusedCapacity(32); 2072 const capacity = map.capacity(); 2073 try map.ensureUnusedCapacity(32); 2074 2075 // Repeated ensureUnusedCapacity() calls with no insertions between 2076 // should not change the capacity. 2077 try testing.expectEqual(capacity, map.capacity()); 2078 } 2079 2080 test "removeByPtr" { 2081 var map = AutoHashMap(i32, u64).init(testing.allocator); 2082 defer map.deinit(); 2083 2084 var i: i32 = undefined; 2085 2086 i = 0; 2087 while (i < 10) : (i += 1) { 2088 try map.put(i, 0); 2089 } 2090 2091 try testing.expect(map.count() == 10); 2092 2093 i = 0; 2094 while (i < 10) : (i += 1) { 2095 const key_ptr = map.getKeyPtr(i); 2096 try testing.expect(key_ptr != null); 2097 2098 if (key_ptr) |ptr| { 2099 map.removeByPtr(ptr); 2100 } 2101 } 2102 2103 try testing.expect(map.count() == 0); 2104 } 2105 2106 test "removeByPtr 0 sized key" { 2107 var map = AutoHashMap(u0, u64).init(testing.allocator); 2108 defer map.deinit(); 2109 2110 try map.put(0, 0); 2111 2112 try testing.expect(map.count() == 1); 2113 2114 const key_ptr = map.getKeyPtr(0); 2115 try testing.expect(key_ptr != null); 2116 2117 if (key_ptr) |ptr| { 2118 map.removeByPtr(ptr); 2119 } 2120 2121 try testing.expect(map.count() == 0); 2122 } 2123 2124 test "repeat fetchRemove" { 2125 var map: AutoHashMapUnmanaged(u64, void) = .empty; 2126 defer map.deinit(testing.allocator); 2127 2128 try map.ensureTotalCapacity(testing.allocator, 4); 2129 2130 map.putAssumeCapacity(0, {}); 2131 map.putAssumeCapacity(1, {}); 2132 map.putAssumeCapacity(2, {}); 2133 map.putAssumeCapacity(3, {}); 2134 2135 // fetchRemove() should make slots available. 2136 var i: usize = 0; 2137 while (i < 10) : (i += 1) { 2138 try testing.expect(map.fetchRemove(3) != null); 2139 map.putAssumeCapacity(3, {}); 2140 } 2141 2142 try testing.expect(map.get(0) != null); 2143 try testing.expect(map.get(1) != null); 2144 try testing.expect(map.get(2) != null); 2145 try testing.expect(map.get(3) != null); 2146 } 2147 2148 test "getOrPut allocation failure" { 2149 var map: std.StringHashMapUnmanaged(void) = .empty; 2150 try testing.expectError(error.OutOfMemory, map.getOrPut(std.testing.failing_allocator, "hello")); 2151 } 2152 2153 test "rehash" { 2154 var map = AutoHashMap(usize, usize).init(std.testing.allocator); 2155 defer map.deinit(); 2156 2157 var prng = std.Random.DefaultPrng.init(0); 2158 const random = prng.random(); 2159 2160 const count = 4 * random.intRangeLessThan(u32, 100_000, 500_000); 2161 2162 for (0..count) |i| { 2163 try map.put(i, i); 2164 if (i % 3 == 0) { 2165 try expectEqual(map.remove(i), true); 2166 } 2167 } 2168 2169 map.rehash(); 2170 2171 try expectEqual(map.count(), count * 2 / 3); 2172 2173 for (0..count) |i| { 2174 if (i % 3 == 0) { 2175 try expectEqual(map.get(i), null); 2176 } else { 2177 try expectEqual(map.get(i).?, i); 2178 } 2179 } 2180 } 2181 2182 test "removeByPtr, key is array" { 2183 const gpa = testing.allocator; 2184 2185 var map: AutoHashMapUnmanaged([2]u32, u32) = .empty; 2186 defer map.deinit(gpa); 2187 2188 const key: [2]u32 = .{ 1, 2 }; 2189 try map.put(gpa, key, 3); 2190 2191 try expectEqual(1, map.count()); 2192 try expectEqual(3, map.get(key)); 2193 2194 const key_ptr = map.getKeyPtr(key).?; 2195 map.removeByPtr(key_ptr); 2196 2197 try expectEqual(0, map.count()); 2198 try expectEqual(null, map.get(key)); 2199 } 2200