• Andrii Nakryiko's avatar
    libbpf: add resizable non-thread safe internal hashmap · e3b92422
    Andrii Nakryiko authored
    There is a need for fast point lookups inside libbpf for multiple use
    cases (e.g., name resolution for BTF-to-C conversion, by-name lookups in
    BTF for upcoming BPF CO-RE relocation support, etc). This patch
    implements simple resizable non-thread safe hashmap using single linked
    list chains.
    
    Four different insert strategies are supported:
     - HASHMAP_ADD - only add key/value if key doesn't exist yet;
     - HASHMAP_SET - add key/value pair if key doesn't exist yet; otherwise,
       update value;
     - HASHMAP_UPDATE - update value, if key already exists; otherwise, do
       nothing and return -ENOENT;
     - HASHMAP_APPEND - always add key/value pair, even if key already exists.
       This turns hashmap into a multimap by allowing multiple values to be
       associated with the same key. Most useful read API for such hashmap is
       hashmap__for_each_key_entry() iteration. If hashmap__find() is still
       used, it will return last inserted key/value entry (first in a bucket
       chain).
    
    For HASHMAP_SET and HASHMAP_UPDATE, old key/value pair is returned, so
    that calling code can handle proper memory management, if necessary.
    Signed-off-by: default avatarAndrii Nakryiko <andriin@fb.com>
    Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
    e3b92422
hashmap.c 4.63 KB