2 * stringmap.c: sucky implementation of binary trees
4 * This makes no attempt to balance the tree, so has bad worst-case behaviour.
5 * Also, I haven't implemented removal of items from the tree. So sue me.
7 * Copyright (c) 2001 Chris Lightfoot. All rights reserved.
11 static const char rcsid[] = "$Id: stringmap.c,v 1.4 2010/11/27 11:06:12 pdw Exp $";
17 #include "stringmap.h"
22 * Allocate memory for a new stringmap. */
23 stringmap stringmap_new() {
26 S = xcalloc(sizeof *S, 1);
32 * Free memory for a stringmap. */
33 void stringmap_delete(stringmap S) {
35 if (S->l) stringmap_delete(S->l);
36 if (S->g) stringmap_delete(S->g);
42 /* stringmap_delete_free:
43 * Free memory for a stringmap, and the objects contained in it, assuming that
44 * they are pointers to memory allocated by xmalloc(3). */
45 void stringmap_delete_free(stringmap S) {
47 if (S->l) stringmap_delete_free(S->l);
48 if (S->g) stringmap_delete_free(S->g);
56 * Insert into S an item having key k and value d. Returns a pointer to
57 * the existing item value, or NULL if a new item was created.
59 item *stringmap_insert(stringmap S, const char *k, const item d) {
68 int i = strcmp(k, S2->key);
73 if (S2->l) S2 = S2->l;
75 if (!(S2->l = stringmap_new())) return NULL;
76 S2->l->key = xstrdup(k);
81 if (S2->g) S2 = S2->g;
83 if (!(S2->g = stringmap_new())) return NULL;
84 S2->g->key = xstrdup(k);
94 * Find in d an item having key k in the stringmap S, returning the item found
95 * on success NULL if no key was found. */
96 stringmap stringmap_find(const stringmap S, const char *k) {
99 if (!S || S->key == NULL) return 0;
101 i = strcmp(k, S2->key);
102 if (i == 0) return S2;
104 if (S2->l) S2 = S2->l;
107 if (S2->g) S2 = S2->g;