smap_api.md

STC smap: Sorted Map

A smap is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function keyCompare. Search, removal, and insertion operations have logarithmic complexity. smap is implemented as an AA-tree (Arne Andersson, 1993), which tends to create a flatter structure (slightly more balanced) than red-black trees.

Iterator invalidation: Iterators are invalidated after insert and erase. References are only invalidated after erase. It is possible to erase individual elements while iterating through the container by using the returned iterator from erase_at(), which references the next element. Alternatively erase_range() can be used.

See the c++ class std::map for a functional description.

Header file and declaration

#define T <ct>, <kt>, <vt>[, (<opt>)] // shorthand for defining map name, i_key, i_val, and i_opt
// Common <opt> traits:
//   c_compare_key - Key type <kt> is a comparable typedef'ed type.
//                 Binds <kt>_cmp() "member" function name.
//   c_class_key - Additionally binds <kt>_clone() and <kt>_drop() function names.
//                 All containers used as keys themselves can be specified with the c_class_key trait.
//   c_pro_key   - "Pro" key type, use e.g. for built-in `cstr`, `zsview`, `rc`, `arc`, `box` as i_key.
//                 These support conversion to/from a "raw" input type (such as const char*) when
//                 using <ct>_emplace*() functions, and may do optimized lookups via the raw type.
//   c_class_val - Only binds <vt>_clone() and <vt>_drop() function names.
//   c_pro_val   - "Pro" val type, use e.g. for built-in `cstr`, `zsview`, `rc`, `arc`, `box` as i_val.
//                 These support conversion to/from a "raw" input type (such as const char*) when
//                 using <ct>_emplace*() functions.

// Alternative to defining T:
#define i_key <t>        // define key type. container type name <ct> defaults to smap_<kt>.
#define i_val <t>        // define val type.

// Override/define when not the <opt> traits are specified:
#define i_cmp <fn>       // Three-way comparison of two i_key (or i_keyraw)
#define i_less <fn>      // Alternative less-comparison. i_cmp is deduced from i_less.
#define i_eq <fn>        // Optional equality comparison, otherwise deduced from given i_cmp.
#define i_keydrop <fn>   // Destroy key func - defaults to empty destruct
#define i_keyclone <fn>  // Required if i_keydrop is defined
#define i_valdrop <fn>   // Destroy value func - defaults to empty destructor
#define i_valclone <fn>  // Required if i_valdrop is defined

#include <stc/sortedmap.h>

• In the following, X is the value of i_key unless T is defined.
• emplace-functions are only available when i_keyraw/i_valraw are implicitly or explicitly defined (e.g. via c_pro_key).

Methods

smap_X          smap_X_init(void);
sset_X          smap_X_with_capacity(isize_t cap);

smap_X          smap_X_clone(smap_x map);
void            smap_X_copy(smap_X* self, const smap_X* other);
void            smap_X_take(smap_X* self, smap_X unowned);                               // take ownership of unowned
smap_X          smap_X_move(smap_X* self);                                               // move
void            smap_X_drop(const smap_X* self);                                         // destructor

void            smap_X_clear(smap_X* self);
bool            smap_X_reserve(smap_X* self, isize_t cap);
void            smap_X_shrink_to_fit(smap_X* self);

bool            smap_X_is_empty(const smap_X* self);
isize_t         smap_X_size(const smap_X* self);
isize_t         smap_X_capacity(const smap_X* self);

const X_mapped* smap_X_at(const smap_X* self, i_keyraw rkey);                            // rkey must be in map
X_mapped*       smap_X_at_mut(smap_X* self, i_keyraw rkey);                              // mutable at
const i_key*    smap_X_get(const smap_X* self, i_keyraw rkey);                           // return NULL if not found
i_key*          smap_X_get_mut(smap_X* self, i_keyraw rkey);                             // mutable get
bool            smap_X_contains(const smap_X* self, i_keyraw rkey);
smap_X_iter     smap_X_find(const smap_X* self, i_keyraw rkey);
i_key*          smap_X_find_it(const smap_X* self, i_keyraw rkey, smap_X_iter* out);     // return NULL if not found
smap_X_iter     smap_X_lower_bound(const smap_X* self, i_keyraw rkey);                   // find closest entry >= rkey

i_key*          smap_X_front(const smap_X* self);
i_key*          smap_X_back(const smap_X* self);

smap_X_result   smap_X_put(smap_X* self, i_keyraw rkey, i_valraw rmapped);               // alias for emplace_or_assign() / insert_or_assign()
smap_X_result   smap_X_push(smap_X* self, smap_X_value entry);                           // always assign entry (i_key/i_val pair)

smap_X_result   smap_X_insert_or_assign(smap_X* self, i_key key, i_val mapped);          // always assign mapped
smap_X_result   smap_X_insert(smap_X* self, i_key key, i_val mapped);                    // no change if key is in map

smap_X_result   smap_X_emplace_or_assign(smap_X* self, i_keyraw rkey, i_valraw rmapped); // always assign mapped, only for i_keyraw != i_key
smap_X_result   smap_X_emplace(smap_X* self, i_keyraw rkey, i_valraw rmapped);           // no change if key is in map, only for i_keyraw != i_key

int             smap_X_erase(smap_X* self, i_keyraw rkey);
smap_X_iter     smap_X_erase_at(smap_X* self, smap_X_iter it);                           // returns iter after it
smap_X_iter     smap_X_erase_range(smap_X* self, smap_X_iter it1, smap_X_iter it2);      // returns updated it2

smap_X_iter     smap_X_begin(const smap_X* self);
smap_X_iter     smap_X_end(const smap_X* self);
void            smap_X_next(smap_X_iter* iter);
smap_X_iter     smap_X_advance(smap_X_iter it, isize_t n);

bool            smap_X_eq(const smap_X* c1, const smap_X* c2);
i_key           smap_X_value_clone(const smap_X* self, i_key val);
smap_X_raw      smap_X_value_toraw(const i_key* pval);
void            smap_X_value_drop(i_key* pval);

Types

Type name	Type definition	Used to represent...
smap_X	struct { ... }	The smap type
smap_X_key	i_key	The key type
smap_X_mapped	i_val	The mapped type
smap_X_value	struct { i_key first; i_val second; }	The value: key is immutable
smap_X_keyraw	i_keyraw	The raw key type
smap_X_rmapped	i_valraw	The raw mapped type
smap_X_raw	struct { i_keyraw first; i_valraw second; }	i_keyraw+i_valraw type
smap_X_result	struct { smap_X_value *ref; bool inserted; }	Result of insert/put/emplace
smap_X_iter	struct { smap_X_value *ref; ... }	Iterator type

Examples

[ Run this code ]

#include <stc/cstr.h>

#define i_pro_key cstr // special macro for i_key = cstr
#define i_pro_val cstr // ditto
#include <stc/sortedmap.h>

int main(void)
{
    // Create a sorted map of three strings (maps to string)
    smap_cstr colors = c_make(smap_cstr, {
        {"RED", "#FF0000"},
        {"GREEN", "#00FF00"},
        {"BLUE", "#0000FF"}
    });

    // Iterate and print keys and values of sorted map
    for (c_each(i, smap_cstr, colors)) {
        printf("Key:[%s] Value:[%s]\n", cstr_str(&i.ref->first), cstr_str(&i.ref->second));
    }

    // Add two new entries to the sorted map
    smap_cstr_emplace(&colors, "BLACK", "#000000");
    smap_cstr_emplace(&colors, "WHITE", "#FFFFFF");

    // Output values by key
    printf("The HEX of color RED is:[%s]\n", cstr_str(smap_cstr_at(&colors, "RED")));
    printf("The HEX of color BLACK is:[%s]\n", cstr_str(smap_cstr_at(&colors, "BLACK")));

    smap_cstr_drop(&colors);
}

Example 2

Translate a C++ example using insert and emplace to STC:

[ Run this code ]

#include <stc/cstr.h>
#define T strmap, cstr, cstr, (c_pro_key | c_pro_val)
#include <stc/sortedmap.h>

static void print_node(const strmap_value* node) {
    printf("[%s] = %s\n", cstr_str(&node->first), cstr_str(&node->second));
}

static void print_result(strmap_result result) {
    printf("%s", result.inserted ? "inserted: " : "ignored:  ");
    print_node(result.ref);
}

int main(void)
{
    strmap m = {0};

    print_result( strmap_emplace(&m, "a", "a") );
    print_result( strmap_emplace(&m, "b", "abcd") );
    print_result( strmap_insert(&m, cstr_lit("c"), cstr_with_size(10, 'c') ) );
    print_result( strmap_emplace(&m, "c", "Won't be inserted") );

    for (c_each(p, strmap, m)) { print_node(p.ref); }
    strmap_drop(&m);
}

Example 3

This example uses a smap with cstr as mapped value. Note the i_pro_val usage.

[ Run this code ]

#include <stc/cstr.h>


#define T IdMap, int, cstr, (c_pro_val)
#include <stc/sortedmap.h>

int main(void)
{
    uint32_t col = 0xcc7744ff;
    IdMap idnames = c_make(IdMap, {{100, "Red"}, {110, "Blue"}});

    // Assign/overwrite an existing mapped value with a const char*
    IdMap_put(&idnames, 110, "White");

    // Insert (or assign) a new cstr object
    IdMap_insert_or_assign(&idnames, 120, cstr_from_fmt("#%08x", col));

    // emplace() adds only when key does not already exist:
    IdMap_emplace(&idnames, 100, "Green"); // ignored

    for (c_each_kv(id, name, IdMap, idnames))
        printf("%d: %s\n", *id, cstr_str(name));

    IdMap_drop(&idnames);
}

Example 4

Demonstrate smap with plain-old-data key type Vec3i and int as mapped type: smap<Vec3i, int>.

[ Run this code ]

#include <stdio.h>
typedef struct { int x, y, z; } Vec3i;

static int Vec3i_cmp(const Vec3i* a, const Vec3i* b) {
    int c;
    if ((c = a->x - b->x) != 0) return c;
    if ((c = a->y - b->y) != 0) return c;
    return a->z - b->z;
}

#define T smap_vi, Vec3i, int
#define i_cmp Vec3i_cmp
#include <stc/sortedmap.h>

int main(void)
{
    smap_vi vmap = {0};

    smap_vi_insert(&vmap, (Vec3i){100, 0, 0}, 1);
    smap_vi_insert(&vmap, (Vec3i){0, 100, 0}, 2);
    smap_vi_insert(&vmap, (Vec3i){0, 0, 100}, 3);
    smap_vi_insert(&vmap, (Vec3i){100, 100, 100}, 4);

    for (c_each_kv(v, n, smap_vi, vmap))
        printf("{ %3d, %3d, %3d }: %d\n", v->x, v->y, v->z, *n);

    smap_vi_drop(&vmap);
}