Blame view

stringmap.c 2.8 KB
pdw committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
/*
 * stringmap.c: sucky implementation of binary trees
 *
 * This makes no attempt to balance the tree, so has bad worst-case behaviour.
 * Also, I haven't implemented removal of items from the tree. So sue me.
 *
 * Copyright (c) 2001 Chris Lightfoot. All rights reserved.
 *
 */

static const char rcsid[] = "$Id$";


#include <stdlib.h>
#include <string.h>

#include "stringmap.h"
#include "vector.h"
chris committed
19
#include "iftop.h"
pdw committed
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

/* stringmap_new:
 * Allocate memory for a new stringmap. */
stringmap stringmap_new() {
    stringmap S;
    
    S = xcalloc(sizeof *S, 1);

    return S;
}

/* stringmap_delete:
 * Free memory for a stringmap. */
void stringmap_delete(stringmap S) {
    if (!S) return;
    if (S->l) stringmap_delete(S->l);
    if (S->g) stringmap_delete(S->g);

    xfree(S->key);
    xfree(S);
}

/* stringmap_delete_free:
 * Free memory for a stringmap, and the objects contained in it, assuming that
 * they are pointers to memory allocated by xmalloc(3). */
void stringmap_delete_free(stringmap S) {
    if (!S) return;
    if (S->l) stringmap_delete_free(S->l);
    if (S->g) stringmap_delete_free(S->g);

    xfree(S->key);
    xfree(S->d.v);
    xfree(S);
}

/* stringmap_insert:
56 57
 * Insert into S an item having key k and value d. Returns a pointer to
 * the existing item value, or NULL if a new item was created. 
pdw committed
58 59
 */
item *stringmap_insert(stringmap S, const char *k, const item d) {
60
    if (!S) return NULL;
pdw committed
61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
    if (S->key == NULL) {
        S->key = xstrdup(k);
        S->d   = d;
        return NULL;
    } else {
        stringmap S2;
        for (S2 = S;;) {
            int i = strcmp(k, S2->key);
            if (i == 0) {
                return &(S2->d);
            }
            else if (i < 0) {
                if (S2->l) S2 = S2->l;
                else {
                    if (!(S2->l = stringmap_new())) return NULL;
                    S2->l->key = xstrdup(k);
                    S2->l->d   = d;
                    return NULL;
                }
            } else if (i > 0) {
                if (S2->g) S2 = S2->g;
                else {
                    if (!(S2->g = stringmap_new())) return NULL;
                    S2->g->key = xstrdup(k);
                    S2->g->d   = d;
                    return NULL;
                }
            }
        }
    }
}

/* stringmap_find:
 * Find in d an item having key k in the stringmap S, returning the item found
 * on success NULL if no key was found. */
stringmap stringmap_find(const stringmap S, const char *k) {
    stringmap S2;
    int i;
    if (!S || S->key == NULL) return 0;
    for (S2 = S;;) {
        i = strcmp(k, S2->key);
        if (i == 0) return S2;
        else if (i < 0) {
            if (S2->l) S2 = S2->l;
            else return NULL;
        } else if (i > 0) {
            if (S2->g) S2 = S2->g;
            else return NULL;
        }
    }
}