From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from localhost (fantadrom.bsd.lv [local]); by fantadrom.bsd.lv (OpenSMTPD) with ESMTPA id 421030be; for ; Fri, 13 Feb 2015 04:57:29 -0500 (EST) Date: Fri, 13 Feb 2015 04:57:29 -0500 (EST) Message-Id: <4262405887881327494.enqueue@fantadrom.bsd.lv> X-Mailinglist: mdocml-source Reply-To: source@mdocml.bsd.lv MIME-Version: 1.0 From: schwarze@mdocml.bsd.lv To: source@mdocml.bsd.lv Subject: pod2mdoc: ohash compat glue X-Mailer: activitymail 1.26, http://search.cpan.org/dist/activitymail/ Content-Type: text/plain; charset=utf-8 Log Message: ----------- ohash compat glue Modified Files: -------------- pod2mdoc: Makefile dict.c Added Files: ----------- pod2mdoc: compat_ohash.c compat_ohash.h Revision Data ------------- --- /dev/null +++ compat_ohash.h @@ -0,0 +1,68 @@ +/* $Id: compat_ohash.h,v 1.1 2015/02/13 09:56:59 schwarze Exp $ */ +/* $OpenBSD: ohash.h,v 1.2 2014/06/02 18:52:03 deraadt Exp $ */ + +/* Copyright (c) 1999, 2004 Marc Espie + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +/* Open hashing support. + * Open hashing was chosen because it is much lighter than other hash + * techniques, and more efficient in most cases. + */ + +/* user-visible data structure */ +struct ohash_info { + ptrdiff_t key_offset; + void *data; /* user data */ + void *(*calloc)(size_t, size_t, void *); + void (*free)(void *, void *); + void *(*alloc)(size_t, void *); +}; + +struct _ohash_record; + +/* private structure. It's there just so you can do a sizeof */ +struct ohash { + struct _ohash_record *t; + struct ohash_info info; + unsigned int size; + unsigned int total; + unsigned int deleted; +}; + +/* For this to be tweakable, we use small primitives, and leave part of the + * logic to the client application. e.g., hashing is left to the client + * application. We also provide a simple table entry lookup that yields + * a hashing table index (opaque) to be used in find/insert/remove. + * The keys are stored at a known position in the client data. + */ +void ohash_init(struct ohash *, unsigned, struct ohash_info *); +void ohash_delete(struct ohash *); + +unsigned int ohash_lookup_interval(struct ohash *, const char *, + const char *, uint32_t); +unsigned int ohash_lookup_memory(struct ohash *, const char *, + size_t, uint32_t); +void *ohash_find(struct ohash *, unsigned int); +void *ohash_remove(struct ohash *, unsigned int); +void *ohash_insert(struct ohash *, unsigned int, void *); +void *ohash_first(struct ohash *, unsigned int *); +void *ohash_next(struct ohash *, unsigned int *); +unsigned int ohash_entries(struct ohash *); + +void *ohash_create_entry(struct ohash_info *, const char *, const char **); +uint32_t ohash_interval(const char *, const char **); + +unsigned int ohash_qlookupi(struct ohash *, const char *, const char **); +unsigned int ohash_qlookup(struct ohash *, const char *); Index: dict.c =================================================================== RCS file: /home/cvs/mdocml/pod2mdoc/dict.c,v retrieving revision 1.1 retrieving revision 1.2 diff -Ldict.c -Ldict.c -u -p -r1.1 -r1.2 --- dict.c +++ dict.c @@ -21,7 +21,12 @@ #include #include #include + +#if HAVE_OHASH #include +#else +#include "compat_ohash.h" +#endif #include "dict.h" --- /dev/null +++ compat_ohash.c @@ -0,0 +1,339 @@ +/* $Id: compat_ohash.c,v 1.1 2015/02/13 09:56:59 schwarze Exp $ */ + +#if HAVE_OHASH + +int dummy; + +#else + +/* $OpenBSD: ohash.c,v 1.1 2014/06/02 18:52:03 deraadt Exp $ */ + +/* Copyright (c) 1999, 2004 Marc Espie + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include + +#include +#include +#include +#include +#include +#include "compat_ohash.h" + +struct _ohash_record { + uint32_t hv; + const char *p; +}; + +#define DELETED ((const char *)h) +#define NONE (h->size) + +/* Don't bother changing the hash table if the change is small enough. */ +#define MINSIZE (1UL << 4) +#define MINDELETED 4 + +static void ohash_resize(struct ohash *); + + +/* This handles the common case of variable length keys, where the + * key is stored at the end of the record. + */ +void * +ohash_create_entry(struct ohash_info *i, const char *start, const char **end) +{ + char *p; + + if (!*end) + *end = start + strlen(start); + p = (i->alloc)(i->key_offset + (*end - start) + 1, i->data); + if (p) { + memcpy(p+i->key_offset, start, *end-start); + p[i->key_offset + (*end - start)] = '\0'; + } + return (void *)p; +} + +/* hash_delete only frees the hash structure. Use hash_first/hash_next + * to free entries as well. */ +void +ohash_delete(struct ohash *h) +{ + (h->info.free)(h->t, h->info.data); +#ifndef NDEBUG + h->t = NULL; +#endif +} + +static void +ohash_resize(struct ohash *h) +{ + struct _ohash_record *n; + size_t ns; + unsigned int j; + unsigned int i, incr; + + if (4 * h->deleted < h->total) { + if (h->size >= (UINT_MAX >> 1U)) + ns = UINT_MAX; + else + ns = h->size << 1U; + } else if (3 * h->deleted > 2 * h->total) + ns = h->size >> 1U; + else + ns = h->size; + if (ns < MINSIZE) + ns = MINSIZE; +#ifdef STATS_HASH + STAT_HASH_EXPAND++; + STAT_HASH_SIZE += ns - h->size; +#endif + + n = (h->info.calloc)(ns, sizeof(struct _ohash_record), h->info.data); + if (!n) + return; + + for (j = 0; j < h->size; j++) { + if (h->t[j].p != NULL && h->t[j].p != DELETED) { + i = h->t[j].hv % ns; + incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1; + while (n[i].p != NULL) { + i += incr; + if (i >= ns) + i -= ns; + } + n[i].hv = h->t[j].hv; + n[i].p = h->t[j].p; + } + } + (h->info.free)(h->t, h->info.data); + h->t = n; + h->size = ns; + h->total -= h->deleted; + h->deleted = 0; +} + +void * +ohash_remove(struct ohash *h, unsigned int i) +{ + void *result = (void *)h->t[i].p; + + if (result == NULL || result == DELETED) + return NULL; + +#ifdef STATS_HASH + STAT_HASH_ENTRIES--; +#endif + h->t[i].p = DELETED; + h->deleted++; + if (h->deleted >= MINDELETED && 4 * h->deleted > h->total) + ohash_resize(h); + return result; +} + +void * +ohash_find(struct ohash *h, unsigned int i) +{ + if (h->t[i].p == DELETED) + return NULL; + else + return (void *)h->t[i].p; +} + +void * +ohash_insert(struct ohash *h, unsigned int i, void *p) +{ +#ifdef STATS_HASH + STAT_HASH_ENTRIES++; +#endif + if (h->t[i].p == DELETED) { + h->deleted--; + h->t[i].p = p; + } else { + h->t[i].p = p; + /* Arbitrary resize boundary. Tweak if not efficient enough. */ + if (++h->total * 4 > h->size * 3) + ohash_resize(h); + } + return p; +} + +unsigned int +ohash_entries(struct ohash *h) +{ + return h->total - h->deleted; +} + +void * +ohash_first(struct ohash *h, unsigned int *pos) +{ + *pos = 0; + return ohash_next(h, pos); +} + +void * +ohash_next(struct ohash *h, unsigned int *pos) +{ + for (; *pos < h->size; (*pos)++) + if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL) + return (void *)h->t[(*pos)++].p; + return NULL; +} + +void +ohash_init(struct ohash *h, unsigned int size, struct ohash_info *info) +{ + h->size = 1UL << size; + if (h->size < MINSIZE) + h->size = MINSIZE; +#ifdef STATS_HASH + STAT_HASH_CREATION++; + STAT_HASH_SIZE += h->size; +#endif + /* Copy info so that caller may free it. */ + h->info.key_offset = info->key_offset; + h->info.calloc = info->calloc; + h->info.free = info->free; + h->info.alloc = info->alloc; + h->info.data = info->data; + h->t = (h->info.calloc)(h->size, sizeof(struct _ohash_record), + h->info.data); + h->total = h->deleted = 0; +} + +uint32_t +ohash_interval(const char *s, const char **e) +{ + uint32_t k; + + if (!*e) + *e = s + strlen(s); + if (s == *e) + k = 0; + else + k = *s++; + while (s != *e) + k = ((k << 2) | (k >> 30)) ^ *s++; + return k; +} + +unsigned int +ohash_lookup_interval(struct ohash *h, const char *start, const char *end, + uint32_t hv) +{ + unsigned int i, incr; + unsigned int empty; + +#ifdef STATS_HASH + STAT_HASH_LOOKUP++; +#endif + empty = NONE; + i = hv % h->size; + incr = ((hv % (h->size-2)) & ~1) + 1; + while (h->t[i].p != NULL) { +#ifdef STATS_HASH + STAT_HASH_LENGTH++; +#endif + if (h->t[i].p == DELETED) { + if (empty == NONE) + empty = i; + } else if (h->t[i].hv == hv && + strncmp(h->t[i].p+h->info.key_offset, start, + end - start) == 0 && + (h->t[i].p+h->info.key_offset)[end-start] == '\0') { + if (empty != NONE) { + h->t[empty].hv = hv; + h->t[empty].p = h->t[i].p; + h->t[i].p = DELETED; + return empty; + } else { +#ifdef STATS_HASH + STAT_HASH_POSITIVE++; +#endif + return i; + } + } + i += incr; + if (i >= h->size) + i -= h->size; + } + + /* Found an empty position. */ + if (empty != NONE) + i = empty; + h->t[i].hv = hv; + return i; +} + +unsigned int +ohash_lookup_memory(struct ohash *h, const char *k, size_t size, uint32_t hv) +{ + unsigned int i, incr; + unsigned int empty; + +#ifdef STATS_HASH + STAT_HASH_LOOKUP++; +#endif + empty = NONE; + i = hv % h->size; + incr = ((hv % (h->size-2)) & ~1) + 1; + while (h->t[i].p != NULL) { +#ifdef STATS_HASH + STAT_HASH_LENGTH++; +#endif + if (h->t[i].p == DELETED) { + if (empty == NONE) + empty = i; + } else if (h->t[i].hv == hv && + memcmp(h->t[i].p+h->info.key_offset, k, size) == 0) { + if (empty != NONE) { + h->t[empty].hv = hv; + h->t[empty].p = h->t[i].p; + h->t[i].p = DELETED; + return empty; + } else { +#ifdef STATS_HASH + STAT_HASH_POSITIVE++; +#endif + } return i; + } + i += incr; + if (i >= h->size) + i -= h->size; + } + + /* Found an empty position. */ + if (empty != NONE) + i = empty; + h->t[i].hv = hv; + return i; +} + +unsigned int +ohash_qlookup(struct ohash *h, const char *s) +{ + const char *e = NULL; + return ohash_qlookupi(h, s, &e); +} + +unsigned int +ohash_qlookupi(struct ohash *h, const char *s, const char **e) +{ + uint32_t hv; + + hv = ohash_interval(s, e); + return ohash_lookup_interval(h, s, *e, hv); +} + +#endif /*!HAVE_OHASH*/ Index: Makefile =================================================================== RCS file: /home/cvs/mdocml/pod2mdoc/Makefile,v retrieving revision 1.13 retrieving revision 1.14 diff -LMakefile -LMakefile -u -p -r1.13 -r1.14 --- Makefile +++ Makefile @@ -1,24 +1,97 @@ -VERSION = 0.1 -CFLAGS += -g -W -Wall -Wstrict-prototypes -Wno-unused-parameter -Wwrite-strings -WWWPREFIX = /usr/vhosts/mdocml.bsd.lv/www/htdocs/pod2mdoc +# $Id$ +# +# Copyright (c) 2014 Kristaps Dzonsons +# Copyright (c) 2015 Ingo Schwarze +# +# Permission to use, copy, modify, and distribute this software for any +# purpose with or without fee is hereby granted, provided that the above +# copyright notice and this permission notice appear in all copies. +# +# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES +# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR +# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN +# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF +# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -pod2mdoc: dict.o pod2mdoc.o - $(CC) $(LDFLAGS) -o $@ dict.o pod2mdoc.o -lutil +VERSION = 0.1 -www: index.html pod2mdoc.1.html pod2mdoc-$(VERSION).tgz +# === USER CONFIGURATION =============================================== -installwww: www - mkdir -p $(WWWPREFIX)/snapshots - install -m 0444 index.html pod2mdoc.1.html $(WWWPREFIX) - install -m 0444 pod2mdoc-$(VERSION).tgz $(WWWPREFIX)/snapshots - install -m 0444 pod2mdoc-$(VERSION).tgz \ - $(WWWPREFIX)/snapshots/pod2mdoc.tgz +CFLAGS += -g +CFLAGS += -W -Wall -Wstrict-prototypes +CFLAGS += -Wno-unused-parameter -Wwrite-strings + +# Change to 0 on systems other than OpenBSD that do not provide +# a native ohash library; compat_ohash.* will be used in that case. + +CFLAGS += -DHAVE_OHASH=0 + +# May be needed on systems other than OpenBSD when using HAVE_OHASH=1 +# if ohash.h is not in the default header search path and/or +# the library containing the ohash functions is not in the +# default library search path. + +#CFLAGS += -I/usr/local/include +#LDFLAGS += -L/usr/local/lib + +# Needed for the ohash library on OpenBSD. +# You may have to comment this out on other systems, +# in particular when using HAVE_OHASH=0. + +#LDADD += -lutil + +# === LIST OF FILES ==================================================== + +SRCS = compat_ohash.c \ + dict.c \ + pod2mdoc.c + +DISTFILES = Makefile \ + compat_ohash.h \ + dict.h \ + pod2mdoc.1 \ + $(SRCS) + +OBJS = compat_ohash.o \ + dict.o \ + pod2mdoc.o + +WWW_HTML = index.html \ + pod2mdoc.1.html + +# === DEPENDENCY HANDLING ============================================== -dist: pod2mdoc-$(VERSION).tgz +all: pod2mdoc -pod2mdoc-$(VERSION).tgz: +dist: $(WWW_HTML) pod2mdoc.tgz + +.PHONY: clean installwww + +# === TARGETS CONTAINING SHELL COMMANDS ================================ + +clean: + rm -f pod2mdoc $(OBJS) $(WWW_HTML) pod2mdoc.tgz + rm -rf *.dSYM + +pod2mdoc: $(OBJS) + $(CC) $(LDFLAGS) -o $@ $(OBJS) $(LDADD) + +# --- maintainer targets --- + +WWWPREFIX = /var/www/vhosts/mdocml.bsd.lv/htdocs/pod2mdoc + +installwww: dist + mkdir -p $(WWWPREFIX)/snapshots + install -m 0444 $(WWW_HTML) $(WWWPREFIX) + install -m 0444 pod2mdoc.tgz $(WWWPREFIX)/snapshots + ln -f $(WWWPREFIX)/snapshots/pod2mdoc.tgz \ + $(WWWPREFIX)/snapshots/pod2mdoc-$(VERSION).tgz + +pod2mdoc.tgz: $(DISTFILES) mkdir -p .dist/pod2mdoc-$(VERSION) - install -m 0444 pod2mdoc.c Makefile pod2mdoc.1 .dist/pod2mdoc-$(VERSION) + install -m 0644 $(DISTFILES) .dist/pod2mdoc-$(VERSION) (cd .dist && tar zcf ../$@ pod2mdoc-$(VERSION)) rm -rf .dist @@ -27,8 +100,3 @@ index.html: index.xml pod2mdoc.1.html: pod2mdoc.1 mandoc -Thtml pod2mdoc.1 >$@ - -clean: - rm -f pod2mdoc dict.o pod2mdoc.o pod2mdoc-$(VERSION).tgz \ - index.html pod2mdoc.1.html - rm -rf pod2mdoc.dSYM -- To unsubscribe send an email to source+unsubscribe@mdocml.bsd.lv