1/* A sorted string map (see the header). */
2#include "mesh/strmap.h"
3#include "mesh/mt.h"
4
5#include <stdlib.h>
6#include <string.h>
7
8/* The index of key, or where it would go (*found false). */
9static size_t find(const ms_map *m, const char *key, bool *found) {
10    size_t lo = 0, hi = m->n;
11    while (lo < hi) {
12        size_t mid = (lo + hi) / 2;
13        int c = strcmp(m->k[mid], key);
14        if (c == 0) {
15            *found = true;
16            return mid;
17        }
18        if (c < 0) lo = mid + 1;
19        else hi = mid;
20    }
21    *found = false;
22    return lo;
23}
24
25const char *ms_get(const ms_map *m, const char *key) {
26    bool f;
27    size_t i = find(m, key, &f);
28    return f ? m->v[i] : NULL;
29}
30
31bool ms_set(ms_map *m, const char *key, const char *value, bool replace) {
32    bool f;
33    size_t i = find(m, key, &f);
34    if (f) {
35        if (!replace) return false;
36        mt_set(&m->v[i], value);
37        return true;
38    }
39    if (m->n == m->cap) {
40        m->cap = m->cap ? m->cap * 2 : 8;
41        m->k = mt_realloc(m->k, m->cap * sizeof *m->k);
42        m->v = mt_realloc(m->v, m->cap * sizeof *m->v);
43    }
44    memmove(m->k + i + 1, m->k + i, (m->n - i) * sizeof *m->k);
45    memmove(m->v + i + 1, m->v + i, (m->n - i) * sizeof *m->v);
46    m->k[i] = mt_strdup(key);
47    m->v[i] = mt_strdup(value);
48    m->n++;
49    return true;
50}
51
52bool ms_del(ms_map *m, const char *key) {
53    bool f;
54    size_t i = find(m, key, &f);
55    if (!f) return false;
56    free(m->k[i]);
57    free(m->v[i]);
58    memmove(m->k + i, m->k + i + 1, (m->n - i - 1) * sizeof *m->k);
59    memmove(m->v + i, m->v + i + 1, (m->n - i - 1) * sizeof *m->v);
60    m->n--;
61    return true;
62}
63
64void ms_free(ms_map *m) {
65    for (size_t i = 0; i < m->n; i++) {
66        free(m->k[i]);
67        free(m->v[i]);
68    }
69    free(m->k);
70    free(m->v);
71    *m = (ms_map){0};
72}