From cfe61a9ffca3be9a4104ec3aad56e4618a5d59cd Mon Sep 17 00:00:00 2001 From: Adam Dickmeiss Date: Sun, 2 Dec 2007 11:30:28 +0000 Subject: [PATCH] Added simple string map (hash) utility. --- include/Makefile.am | 4 +- include/zebra_strmap.h | 59 +++++++++++++++++++++ util/.cvsignore | 1 + util/Makefile.am | 8 +-- util/strmap.c | 137 ++++++++++++++++++++++++++++++++++++++++++++++++ util/test_strmap.c | 117 +++++++++++++++++++++++++++++++++++++++++ 6 files changed, 321 insertions(+), 5 deletions(-) create mode 100644 include/zebra_strmap.h create mode 100644 util/strmap.c create mode 100644 util/test_strmap.c diff --git a/include/Makefile.am b/include/Makefile.am index 0082eaa..bb8f0a5 100644 --- a/include/Makefile.am +++ b/include/Makefile.am @@ -1,7 +1,7 @@ -# $Id: Makefile.am,v 1.29 2007-11-06 10:29:58 adam Exp $ +# $Id: Makefile.am,v 1.30 2007-12-02 11:30:28 adam Exp $ noinst_HEADERS = bset.h charmap.h \ direntz.h passwddb.h dfa.h zebra_xpath.h d1_absyn.h \ rset.h dfaset.h sortidx.h zebra-lock.h attrfind.h zebramap.h \ - it_key.h su_codec.h + it_key.h su_codec.h zebra_strmap.h SUBDIRS = idzebra diff --git a/include/zebra_strmap.h b/include/zebra_strmap.h new file mode 100644 index 0000000..3bf0960 --- /dev/null +++ b/include/zebra_strmap.h @@ -0,0 +1,59 @@ +/* $Id: zebra_strmap.h,v 1.1 2007-12-02 11:30:28 adam Exp $ + Copyright (C) 1995-2007 + Index Data ApS + +This file is part of the Zebra server. + +Zebra 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 2, or (at your option) any later +version. + +Zebra 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 this program; if not, write to the Free Software +Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + +*/ + +#ifndef ZEBRA_STRMAP_H +#define ZEBRA_STRMAP_H + +#include +#include +YAZ_BEGIN_CDECL + +typedef struct zebra_strmap *zebra_strmap_t; + +YAZ_EXPORT +zebra_strmap_t zebra_strmap_create(void); + +YAZ_EXPORT +void zebra_strmap_destroy(zebra_strmap_t st); + +YAZ_EXPORT +void zebra_strmap_add(zebra_strmap_t st, const char *name, + void *data_buf, size_t data_len); + +YAZ_EXPORT +void *zebra_strmap_lookup(zebra_strmap_t st, const char *name, int no, + size_t *data_len); + +YAZ_EXPORT +int zebra_strmap_remove(zebra_strmap_t st, const char *name); + +YAZ_END_CDECL + +#endif +/* + * Local variables: + * c-basic-offset: 4 + * indent-tabs-mode: nil + * End: + * vim: shiftwidth=4 tabstop=8 expandtab + */ + diff --git a/util/.cvsignore b/util/.cvsignore index 186ba78..63d5276 100644 --- a/util/.cvsignore +++ b/util/.cvsignore @@ -14,3 +14,4 @@ tstflock.out tstlockscope tstpass tstres +test_strmap diff --git a/util/Makefile.am b/util/Makefile.am index 0ec89c2..57c69aa 100644 --- a/util/Makefile.am +++ b/util/Makefile.am @@ -1,8 +1,8 @@ -## $Id: Makefile.am,v 1.37 2007-11-06 10:30:00 adam Exp $ +## $Id: Makefile.am,v 1.38 2007-12-02 11:30:28 adam Exp $ noinst_LTLIBRARIES = libidzebra-util.la -check_PROGRAMS = tstcharmap tstflock tstlockscope tstpass tstres +check_PROGRAMS = tstcharmap tstflock tstlockscope tstpass tstres test_strmap TESTS = $(check_PROGRAMS) @@ -17,7 +17,7 @@ LDADD = libidzebra-util.la $(YAZLALIB) libidzebra_util_la_SOURCES = version.c zint.c res.c charmap.c zebramap.c \ passwddb.c zebra-lock.c dirent.c xpath.c atoi_zn.c snippet.c flock.c \ - attrfind.c exit.c it_key.c su_codec.c + attrfind.c exit.c it_key.c su_codec.c strmap.c tstpass_SOURCES = tstpass.c @@ -29,6 +29,8 @@ tstlockscope_SOURCES = tstlockscope.c tstres_SOURCES = tstres.c +test_strmap_SOURCES = test_strmap.c + clean-local: -rm -rf *.LCK -rm -rf *.log diff --git a/util/strmap.c b/util/strmap.c new file mode 100644 index 0000000..8f0b237 --- /dev/null +++ b/util/strmap.c @@ -0,0 +1,137 @@ +/* $Id: strmap.c,v 1.1 2007-12-02 11:30:28 adam Exp $ + Copyright (C) 1995-2007 + Index Data ApS + +This file is part of the Zebra server. + +Zebra 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 2, or (at your option) any later +version. + +Zebra 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 this program; if not, write to the Free Software +Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + +*/ + +#include +#include +#include +#include + +struct strmap_entry { + char *name; + size_t data_len; + void *data_buf; + struct strmap_entry *next; +}; + +struct zebra_strmap { + NMEM nmem_str; + NMEM nmem_ent; + int hsize; + struct strmap_entry **entries; + struct strmap_entry *free_entries; +}; + +zebra_strmap_t zebra_strmap_create(void) +{ + int i; + NMEM nmem_ent = nmem_create(); + zebra_strmap_t st = nmem_malloc(nmem_ent, sizeof(*st)); + st->nmem_ent = nmem_ent; + st->nmem_str = nmem_create(); + st->hsize = 1001; + st->free_entries = 0; + st->entries = nmem_malloc(nmem_ent, st->hsize * sizeof(*st->entries)); + for (i = 0; i < st->hsize; i++) + st->entries[i] = 0; + return st; +} + +void zebra_strmap_destroy(zebra_strmap_t st) +{ + if (st) + { + nmem_destroy(st->nmem_str); + nmem_destroy(st->nmem_ent); + } +} + +static struct strmap_entry **hash(zebra_strmap_t st, const char *name) +{ + unsigned hash = 0; + int i; + for (i = 0; name[i]; i++) + hash += hash*65519 + name[i]; + hash = hash % st->hsize; + return st->entries + hash; +} + +void zebra_strmap_add(zebra_strmap_t st, const char *name, + void *data_buf, size_t data_len) +{ + struct strmap_entry **e = hash(st, name); + struct strmap_entry *ne = st->free_entries; + + if (ne) + st->free_entries = ne->next; + else + ne = nmem_malloc(st->nmem_ent, sizeof(*ne)); + ne->next = *e; + *e = ne; + ne->name = nmem_strdup(st->nmem_str, name); + ne->data_buf = nmem_malloc(st->nmem_str, data_len); + memcpy(ne->data_buf, data_buf, data_len); + ne->data_len = data_len; +} + +void *zebra_strmap_lookup(zebra_strmap_t st, const char *name, int no, + size_t *data_len) +{ + struct strmap_entry *e = *hash(st, name); + int i = 0; + for (; e ; e = e->next) + if (!strcmp(name, e->name)) + { + if (i == no) + { + if (data_len) + *data_len = e->data_len; + return e->data_buf; + } + i++; + } + return 0; +} + +int zebra_strmap_remove(zebra_strmap_t st, const char *name) +{ + struct strmap_entry **e = hash(st, name); + for (; *e ; e = &(*e)->next) + if (!strcmp(name, (*e)->name)) + { + struct strmap_entry *tmp = *e; + *e = (*e)->next; + + tmp->next = st->free_entries; + st->free_entries = tmp; + return 1; + } + return 0; +} + +/* + * Local variables: + * c-basic-offset: 4 + * indent-tabs-mode: nil + * End: + * vim: shiftwidth=4 tabstop=8 expandtab + */ + diff --git a/util/test_strmap.c b/util/test_strmap.c new file mode 100644 index 0000000..c376bec --- /dev/null +++ b/util/test_strmap.c @@ -0,0 +1,117 @@ +/* $Id: test_strmap.c,v 1.1 2007-12-02 11:30:28 adam Exp $ + Copyright (C) 1995-2007 + Index Data ApS + +This file is part of the Zebra server. + +Zebra 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 2, or (at your option) any later +version. + +Zebra 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 this program; if not, write to the Free Software +Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + +*/ + +#include +#include +#include +#include + +static void test1(void) +{ + { + zebra_strmap_t sm = zebra_strmap_create(); + YAZ_CHECK(sm); + zebra_strmap_destroy(sm); + } + { + int v1 = 1; + int *data_buf; + size_t data_len; + zebra_strmap_t sm = zebra_strmap_create(); + YAZ_CHECK(!zebra_strmap_lookup(sm, "a", 0, 0)); + + zebra_strmap_add(sm, "a", &v1, sizeof v1); + data_buf = zebra_strmap_lookup(sm, "a", 0, &data_len); + YAZ_CHECK(data_buf && data_len == sizeof v1 + && v1 == *((int*) data_buf)); + + zebra_strmap_remove(sm, "a"); + data_buf = zebra_strmap_lookup(sm, "a", 0, &data_len); + YAZ_CHECK(data_buf == 0); + zebra_strmap_destroy(sm); + } +} + +static void test2(int no_iter) +{ + zebra_strmap_t sm = zebra_strmap_create(); + { + int i; + srand(12); + for (i = 0; i < no_iter; i++) + { + char str[8]; + int j; + int v = i; + + for (j = 0; j < sizeof(str)-1; j++) + str[j] = rand() & 255; + str[j] = '\0'; + + zebra_strmap_add(sm, str, &v, sizeof v); + } + } + { + int i; + srand(12); + for (i = 0; i < no_iter; i++) + { + char str[8]; + int j; + int v = i; + void *data_buf; + size_t data_len; + + for (j = 0; j < sizeof(str)-1; j++) + str[j] = rand() & 255; + str[j] = '\0'; + + j = 0; + while ((data_buf = zebra_strmap_lookup(sm, str, j, &data_len))) + { + if (data_len == sizeof v && v == *((int*) data_buf)) + break; + j++; + } + YAZ_CHECK(data_buf && data_len == sizeof v + && v == *((int*) data_buf)); + } + } + zebra_strmap_destroy(sm); +} + +int main (int argc, char **argv) +{ + YAZ_CHECK_INIT(argc, argv); + YAZ_CHECK_LOG(); + test1(); + test2(50000); + YAZ_CHECK_TERM; +} +/* + * Local variables: + * c-basic-offset: 4 + * indent-tabs-mode: nil + * End: + * vim: shiftwidth=4 tabstop=8 expandtab + */ + -- 1.7.10.4