1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
56
57
58
59
60
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
|
/*
* 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: stringmap.c,v 1.4 2010/11/27 11:06:12 pdw Exp $";
#include <stdlib.h>
#include <string.h>
#include "stringmap.h"
#include "vector.h"
#include "iftop.h"
/* 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:
* 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.
*/
item *stringmap_insert(stringmap S, const char *k, const item d) {
if (!S) return NULL;
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;
}
}
}
|
