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 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210
|
/* Copyright (c) 2002,2003,2004,2009 James M. Kretchmar
*
* This file is part of Owl.
*
* Owl is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* Owl is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Owl. If not, see <http://www.gnu.org/licenses/>.
*
* ---------------------------------------------------------------
*
* As of Owl version 2.1.12 there are patches contributed by
* developers of the branched BarnOwl project, Copyright (c)
* 2006-2009 The BarnOwl Developers. All rights reserved.
*/
/* Dictionary data abstraction.
* Maps from strings to pointers.
* Stores as a sorted list of key/value pairs.
* O(n) on inserts and deletes.
* O(n) on searches, although it should switch to a binary search for O(log n)
*/
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include "owl.h"
static const char fileIdent[] = "$Id: dict.c,v 1.4 2009/03/29 12:38:20 kretch Exp $";
#define INITSIZE 30
#define GROWAT 2
#define GROWBY 1.5
int owl_dict_create(owl_dict *d) {
d->size=0;
d->els=(owl_dict_el *)owl_malloc(INITSIZE*sizeof(owl_dict_el));
d->avail=INITSIZE;
if (d->els==NULL) return(-1);
return(0);
}
int owl_dict_get_size(owl_dict *d) {
return(d->size);
}
/* Finds the position of an element with key k, or of the element where
* this element would logically go, and stores the index in pos.
* TODO: optimize to do a binary search.
* Returns 1 if found, else 0. */
int _owl_dict_find_pos(owl_dict *d, char *k, int *pos) {
int i;
for (i=0; (i<d->size) && strcmp(k,d->els[i].k)>0; i++);
*pos = i;
if (i>=d->size || strcmp(k,d->els[i].k)) {
return(0);
} else {
return(1);
}
}
/* returns the value corresponding to key k */
void *owl_dict_find_element(owl_dict *d, char *k) {
int found, pos;
found = _owl_dict_find_pos(d, k, &pos);
if (!found) {
return(NULL);
}
return(d->els[pos].v);
}
/* creates a list and fills it in with keys. duplicates the keys,
* so they will need to be freed by the caller. */
int owl_dict_get_keys(owl_dict *d, owl_list *l) {
int i;
char *dupk;
if (owl_list_create(l)) return(-1);
for (i=0; i<d->size; i++) {
if ((dupk = owl_strdup(d->els[i].k)) == NULL) return(-1);
owl_list_append_element(l, (void*)dupk);
}
return(0);
}
void owl_dict_noop_free(void *x) {
return;
}
/* Returns 0 on success. Will copy the key but make
a reference to the value. Will clobber an existing
entry with the same key iff free_on_replace!=NULL,
and will run free_on_replace on the old element.
Will return -2 if replace=NULL and match was found.
*/
int owl_dict_insert_element(owl_dict *d, char *k, void *v, void (*free_on_replace)(void *old)) {
int pos, found;
char *dupk;
found = _owl_dict_find_pos(d, k, &pos);
if (found && free_on_replace) {
free_on_replace(d->els[pos].v);
d->els[pos].v = v;
return(0);
} else if (found && !free_on_replace) {
return(-2);
} else {
if ((d->size+1) > (d->avail/GROWAT)) {
d->els=owl_realloc(d->els, d->avail*GROWBY*sizeof(void *));
d->avail=d->avail*GROWBY;
if (d->els==NULL) return(-1);
}
if ((dupk = owl_strdup(k)) == NULL) return(-1);
if (pos!=d->size) {
/* shift forward to leave us a slot */
memmove((void*)(d->els+pos+1), (void*)(d->els+pos),
sizeof(owl_dict_el)*(d->size-pos));
}
d->size++;
d->els[pos].k = dupk;
d->els[pos].v = v;
return(0);
}
}
/* Doesn't free the value of the element, but does
* return it so the caller can free it. */
void *owl_dict_remove_element(owl_dict *d, char *k) {
int i;
int pos, found;
void *v;
found = _owl_dict_find_pos(d, k, &pos);
if (!found) return(NULL);
owl_free(d->els[pos].k);
v = d->els[pos].v;
for (i=pos; i<d->size-1; i++) {
d->els[i]=d->els[i+1];
}
d->size--;
return(v);
}
/* elefree should free the value as well */
void owl_dict_free_all(owl_dict *d, void (*elefree)(void *)) {
int i;
for (i=0; i<d->size; i++) {
owl_free(d->els[i].k);
if (elefree) (elefree)(d->els[i].v);
}
if (d->els) owl_free(d->els);
}
void owl_dict_free_simple(owl_dict *d) {
owl_dict_free_all(d, NULL);
}
/************* REGRESSION TESTS **************/
#ifdef OWL_INCLUDE_REG_TESTS
#define FAIL_UNLESS(desc,pred) printf("\t%-4s: %s\n", (pred)?"ok":(numfailed++,"FAIL"), desc)
int owl_dict_regtest(void) {
owl_dict d;
owl_list l;
int numfailed=0;
char *av="aval", *bv="bval", *cv="cval", *dv="dval";
printf("BEGIN testing owl_dict\n");
FAIL_UNLESS("create", 0==owl_dict_create(&d));
FAIL_UNLESS("insert b", 0==owl_dict_insert_element(&d, "b", (void*)bv, owl_dict_noop_free));
FAIL_UNLESS("insert d", 0==owl_dict_insert_element(&d, "d", (void*)dv, owl_dict_noop_free));
FAIL_UNLESS("insert a", 0==owl_dict_insert_element(&d, "a", (void*)av, owl_dict_noop_free));
FAIL_UNLESS("insert c", 0==owl_dict_insert_element(&d, "c", (void*)cv, owl_dict_noop_free));
FAIL_UNLESS("reinsert d (no replace)", -2==owl_dict_insert_element(&d, "d", (void*)dv, 0));
FAIL_UNLESS("find a", (void*)av==owl_dict_find_element(&d, "a"));
FAIL_UNLESS("find b", (void*)bv==owl_dict_find_element(&d, "b"));
FAIL_UNLESS("find c", (void*)cv==owl_dict_find_element(&d, "c"));
FAIL_UNLESS("find d", (void*)dv==owl_dict_find_element(&d, "d"));
FAIL_UNLESS("find e (non-existent)", NULL==owl_dict_find_element(&d, "e"));
FAIL_UNLESS("remove d", (void*)dv==owl_dict_remove_element(&d, "d"));
FAIL_UNLESS("find d (post-removal)", NULL==owl_dict_find_element(&d, "d"));
FAIL_UNLESS("get_size", 3==owl_dict_get_size(&d));
FAIL_UNLESS("get_keys", 0==owl_dict_get_keys(&d, &l));
FAIL_UNLESS("get_keys result size", 3==owl_list_get_size(&l));
/* these assume the returned keys are sorted */
FAIL_UNLESS("get_keys result val",0==strcmp("a",owl_list_get_element(&l,0)));
FAIL_UNLESS("get_keys result val",0==strcmp("b",owl_list_get_element(&l,1)));
FAIL_UNLESS("get_keys result val",0==strcmp("c",owl_list_get_element(&l,2)));
owl_list_free_all(&l, owl_free);
owl_dict_free_all(&d, NULL);
if (numfailed) printf("*** WARNING: failures encountered with owl_dict\n");
printf("END testing owl_dict (%d failures)\n", numfailed);
return(numfailed);
}
#endif /* OWL_INCLUDE_REG_TESTS */
|