Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/usr.bin/m4 Import new m4 from OpenBSD.
details: https://anonhg.NetBSD.org/src/rev/50e8837a7120
branches: trunk
changeset: 748545:50e8837a7120
user: christos <christos%NetBSD.org@localhost>
date: Mon Oct 26 21:08:59 2009 +0000
description:
Import new m4 from OpenBSD.
diffstat:
usr.bin/m4/lib/ohash.h | 73 ++++++++++
usr.bin/m4/lib/ohash_create_entry.c | 38 +++++
usr.bin/m4/lib/ohash_delete.c | 31 ++++
usr.bin/m4/lib/ohash_do.c | 111 +++++++++++++++
usr.bin/m4/lib/ohash_entries.c | 26 +++
usr.bin/m4/lib/ohash_enum.c | 36 +++++
usr.bin/m4/lib/ohash_init.3 | 229 +++++++++++++++++++++++++++++++++
usr.bin/m4/lib/ohash_init.c | 41 +++++
usr.bin/m4/lib/ohash_int.h | 19 ++
usr.bin/m4/lib/ohash_interval.3 | 90 ++++++++++++
usr.bin/m4/lib/ohash_interval.c | 36 +++++
usr.bin/m4/lib/ohash_lookup_interval.c | 68 +++++++++
usr.bin/m4/lib/ohash_lookup_memory.c | 64 +++++++++
usr.bin/m4/lib/ohash_qlookup.c | 27 +++
usr.bin/m4/lib/ohash_qlookupi.c | 29 ++++
usr.bin/m4/lib/strtonum.c | 66 +++++++++
usr.bin/m4/parser.y | 80 +++++++++++
usr.bin/m4/tokenizer.l | 97 +++++++++++++
18 files changed, 1161 insertions(+), 0 deletions(-)
diffs (truncated from 1233 to 300 lines):
diff -r 418ae32b0ec9 -r 50e8837a7120 usr.bin/m4/lib/ohash.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/usr.bin/m4/lib/ohash.h Mon Oct 26 21:08:59 2009 +0000
@@ -0,0 +1,73 @@
+#ifndef OHASH_H
+#define OHASH_H
+/* $OpenBSD: ohash.h,v 1.8 2005/12/29 18:54:47 jaredy Exp $ */
+/* ex:ts=8 sw=4:
+ */
+
+/* Copyright (c) 1999, 2004 Marc Espie <espie%openbsd.org@localhost>
+ *
+ * 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.
+ */
+
+struct ohash_info {
+ ptrdiff_t key_offset;
+ void *data; /* user data */
+ void *(*halloc)(size_t, void *);
+ void (*hfree)(void *, size_t, void *);
+ void *(*alloc)(size_t, void *);
+};
+
+struct _ohash_record;
+
+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.
+ */
+__BEGIN_DECLS
+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 *, u_int32_t);
+unsigned int ohash_lookup_memory(struct ohash *, const char *,
+ size_t, u_int32_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 **);
+u_int32_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 *);
+__END_DECLS
+#endif
+
diff -r 418ae32b0ec9 -r 50e8837a7120 usr.bin/m4/lib/ohash_create_entry.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/usr.bin/m4/lib/ohash_create_entry.c Mon Oct 26 21:08:59 2009 +0000
@@ -0,0 +1,38 @@
+/* $OpenBSD: ohash_create_entry.c,v 1.2 2004/06/22 20:00:16 espie Exp $ */
+/* ex:ts=8 sw=4:
+ */
+
+/* Copyright (c) 1999, 2004 Marc Espie <espie%openbsd.org@localhost>
+ *
+ * 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 "ohash_int.h"
+
+/* 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;
+}
diff -r 418ae32b0ec9 -r 50e8837a7120 usr.bin/m4/lib/ohash_delete.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/usr.bin/m4/lib/ohash_delete.c Mon Oct 26 21:08:59 2009 +0000
@@ -0,0 +1,31 @@
+/* $OpenBSD: ohash_delete.c,v 1.2 2004/06/22 20:00:16 espie Exp $ */
+/* ex:ts=8 sw=4:
+ */
+
+/* Copyright (c) 1999, 2004 Marc Espie <espie%openbsd.org@localhost>
+ *
+ * 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 "ohash_int.h"
+/* 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.hfree)(h->t, sizeof(struct _ohash_record) * h->size,
+ h->info.data);
+#ifndef NDEBUG
+ h->t = NULL;
+#endif
+}
diff -r 418ae32b0ec9 -r 50e8837a7120 usr.bin/m4/lib/ohash_do.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/usr.bin/m4/lib/ohash_do.c Mon Oct 26 21:08:59 2009 +0000
@@ -0,0 +1,111 @@
+/* $OpenBSD: ohash_do.c,v 1.4 2004/06/22 20:00:16 espie Exp $ */
+/* ex:ts=8 sw=4:
+ */
+
+/* Copyright (c) 1999, 2004 Marc Espie <espie%openbsd.org@localhost>
+ *
+ * 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 "ohash_int.h"
+
+static void ohash_resize(struct ohash *);
+
+static void
+ohash_resize(struct ohash *h)
+{
+ struct _ohash_record *n;
+ unsigned int ns, j;
+ unsigned int i, incr;
+
+ if (4 * h->deleted < h->total)
+ ns = h->size << 1;
+ else if (3 * h->deleted > 2 * h->total)
+ ns = h->size >> 1;
+ 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.halloc)(sizeof(struct _ohash_record) * ns, 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.hfree)(h->t, sizeof(struct _ohash_record) * h->size,
+ 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;
+}
diff -r 418ae32b0ec9 -r 50e8837a7120 usr.bin/m4/lib/ohash_entries.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/usr.bin/m4/lib/ohash_entries.c Mon Oct 26 21:08:59 2009 +0000
@@ -0,0 +1,26 @@
+/* $OpenBSD: ohash_entries.c,v 1.2 2004/06/22 20:00:16 espie Exp $ */
+/* ex:ts=8 sw=4:
+ */
+
+/* Copyright (c) 1999, 2004 Marc Espie <espie%openbsd.org@localhost>
+ *
+ * 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 "ohash_int.h"
+
+unsigned int
+ohash_entries(struct ohash *h)
+{
+ return h->total - h->deleted;
+}
diff -r 418ae32b0ec9 -r 50e8837a7120 usr.bin/m4/lib/ohash_enum.c
Home |
Main Index |
Thread Index |
Old Index