--- a/Makefile	Mon Dec 20 00:32:20 2010 -0500
+++ b/Makefile	Mon Dec 20 01:15:43 2010 -0500
@@ -1,7 +1,7 @@
 #	$NetBSD$
 
 PROG=	tradcpp
-SRCS=	main.c files.c directive.c eval.c place.c array.c utils.c
+SRCS=	main.c files.c directive.c eval.c macro.c place.c array.c utils.c
 WARNS=	5
 
 .include <bsd.prog.mk>

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/macro.c	Mon Dec 20 01:15:43 2010 -0500
@@ -0,0 +1,306 @@
+#include <stdlib.h>
+#include <string.h>
+
+#include "array.h"
+#include "mode.h"
+#include "place.h"
+#include "macro.h"
+
+struct macro {
+	struct place defplace;
+	struct place expansionplace;
+	unsigned hash;
+	char *name;
+	char *expansion;
+};
+DECLARRAY(macro);
+DEFARRAY(macro, );
+DECLARRAY(macroarray);
+DEFARRAY(macroarray, );
+
+static struct macroarrayarray macros;
+static unsigned total_macros;
+static unsigned hashmask;
+
+////////////////////////////////////////////////////////////
+// macro structure ops
+
+static
+struct macro *
+macro_create(struct place *p1, struct place *p2, unsigned hash,
+	     const char *name, const char *expansion)
+{
+	struct macro *m;
+
+	m = domalloc(sizeof(*m));
+	m->defplace = *p1;
+	m->expansionplace = *p2;
+	m->hash = hash;
+	m->name = dostrdup(name);
+	m->expansion = dostrdup(expansion);
+	return m;
+}
+
+static
+void
+macro_destroy(struct macro *m)
+{
+	free(m->name);
+	free(m->expansion);
+	free(m);
+}
+
+////////////////////////////////////////////////////////////
+// macro table
+
+/*
+ * Unless I've screwed up, this is something called Fletcher's Checksum
+ * that showed up in Dr. Dobbs in, according to my notes, May 1992. The
+ * implementation is new.
+ */
+static
+unsigned
+hashfunc(const char *s)
+{
+	uint16_t x1, x2, a;
+	size_t i, len;
+
+	len = strlen(s);
+
+	x1 = (uint16_t) (len >> 16);
+	x2 = (uint16_t) (len);
+	if (x1==0) {
+		x1++;
+	}
+	if (x2==0) {
+		x2++;
+	}
+
+	for (i=0; i<len; i+=2) {
+		if (i==len-1) {
+			a = (unsigned char)s[i];
+			/* don't run off the end of the array */
+		}
+		else {
+			a = (unsigned char)s[i] +
+				((uint16_t)(unsigned char)s[i+1] << 8);
+		}
+		x1 += a;
+		if (x1 < a) {
+			x1++;
+		}
+		x2 += x1;
+		if (x2 < x1) {
+			x2++;
+		}
+	}
+
+	x1 ^= 0xffff;
+	x2 ^= 0xffff;
+	return ((uint32_t)x2)*65535U + x1;
+}
+
+static
+void
+macrotable_init(void)
+{
+	unsigned i;
+
+	macroarrayarray_init(&macros);
+	macroarrayarray_setsize(&macros, 4);
+	for (i=0; i<4; i++) {
+		macroarrayarray_set(&macros, i, NULL);
+	}
+	total_macros = 0;
+	hashmask = 0x3;
+}
+
+DESTROYALL_ARRAY(macro, );
+
+static
+void
+macrotable_cleanup(void)
+{
+	struct macroarray *bucket;
+	unsigned numbuckets, i;
+
+	numbuckets = macroarrayarray_num(&macros);
+	for (i=0; i<numbuckets; i++) {
+		bucket = macroarrayarray_get(&macros, i);
+		macroarray_destroyall(bucket);
+		macroarray_destroy(bucket);
+	}
+	macroarrayarray_setsize(&macros, 0);
+	macroarrayarray_cleanup(&macros);
+}
+
+static
+struct macro *
+macrotable_find(const char *name, bool remove)
+{
+	unsigned hash;
+	struct macroarray *bucket;
+	struct macro *m, *m2;
+	unsigned i, num;
+
+	hash = hashfunc(name);
+	bucket = macroarrayarray_get(&macros, hash & hashmask);
+	if (bucket == NULL) {
+		return NULL;
+	}
+	num = macroarray_num(bucket);
+	for (i=0; i<num; i++) {
+		m = macroarray_get(bucket, i);
+		if (hash != m->hash) {
+			continue;
+		}
+		if (!strcmp(name, m->name)) {
+			if (remove) {
+				if (i < num-1) {
+					m2 = macroarray_get(bucket, num-1);
+					macroarray_set(bucket, i, m2);
+				}
+				macroarray_setsize(bucket, num-1);
+				total_macros--;
+			}
+			return m;
+		}
+	}
+	return NULL;
+}
+
+static
+void
+macrotable_rehash(void)
+{
+	struct macroarray *newbucket, *oldbucket;
+	struct macro *m;
+	unsigned newmask, tossbit;
+	unsigned numbuckets, i;
+	unsigned oldnum, j, k;
+
+	numbuckets = macroarrayarray_num(&macros);
+	macroarrayarray_setsize(&macros, numbuckets*2);
+
+	assert(hashmask == numbuckets - 1);
+	newmask = (hashmask << 1) | 1U;
+	tossbit = newmask && ~hashmask;
+	hashmask = newmask;
+
+	for (i=0; i<numbuckets; i++) {
+		newbucket = NULL;
+		oldbucket = macroarrayarray_get(&macros, i);
+		oldnum = macroarray_num(oldbucket);
+		for (j=0; j<oldnum; j++) {
+			m = macroarray_get(oldbucket, j);
+			if (m->hash & tossbit) {
+				if (newbucket == NULL) {
+					newbucket = macroarray_create();
+				}
+				macroarray_set(oldbucket, j, NULL);
+				macroarray_add(newbucket, m, NULL);
+			}
+		}
+		for (j=k=0; j<oldnum; j++) {
+			m = macroarray_get(oldbucket, j);
+			if (m != NULL && k < j) {
+				macroarray_set(oldbucket, k++, m);
+			}
+		}
+		macroarray_setsize(oldbucket, k);
+		macroarrayarray_set(&macros, numbuckets + i, newbucket);
+	}
+}
+
+static
+void
+macrotable_add(struct macro *m)
+{
+	unsigned hash;
+	struct macroarray *bucket;
+	unsigned numbuckets;
+
+	numbuckets = macroarrayarray_num(&macros);
+	if (total_macros > 0 && total_macros / numbuckets > 9) {
+		macrotable_rehash();
+	}
+
+	hash = hashfunc(m->name);
+	bucket = macroarrayarray_get(&macros, hash & hashmask);
+	if (bucket == NULL) {
+		bucket = macroarray_create();
+		macroarrayarray_set(&macros, hash & hashmask, bucket);
+	}
+	macroarray_add(bucket, m, NULL);
+	total_macros++;
+}
+
+////////////////////////////////////////////////////////////
+// external macro definition interface
+
+void
+macro_define(struct place *p1, const char *macro,
+	     struct place *p2, const char *expansion)
+{
+	struct macro *m;
+
+	m = macrotable_find(macro, false);
+	if (m != NULL) {
+		if (!strcmp(expansion, m->expansion)) {
+			complain(p1, "Warning: redefinition of %s", macro);
+			if (mode.werror) {
+				complain_fail();
+			}
+			return;
+		}
+		complain(p1, "Redefinition of %s is not identical", macro);
+		complain_fail();
+		return;
+	}
+
+	m = macro_create(p1, p2, hashfunc(macro), macro, expansion);
+	macrotable_add(m);
+}
+
+void
+macro_undef(const char *macro)
+{
+	struct macro *m;
+
+	m = macrotable_find(macro, true);
+	if (m) {
+		macro_destroy(m);
+	}
+}
+
+bool
+macro_isdefined(const char *macro)
+{
+	struct macro *m;
+
+	m = macrotable_find(macro, false);
+	return m != NULL;
+}
+
+////////////////////////////////////////////////////////////
+// macro expansion
+
+char *macroexpand(struct place *, char *buf, size_t len, bool honordefined);
+
+void macro_sendline(struct place *, char *buf, size_t len);
+void macro_sendeof(struct place *);
+
+////////////////////////////////////////////////////////////
+// module initialization
+
+void
+macros_init(void)
+{
+	macrotable_init();
+}
+
+void
+macros_cleanup(void)
+{
+	macrotable_cleanup();
+}

--- a/macro.h	Mon Dec 20 00:32:20 2010 -0500
+++ b/macro.h	Mon Dec 20 01:15:43 2010 -0500
@@ -1,5 +1,11 @@
+#include <stdbool.h>
+#include <stddef.h>
+
 struct place;
 
+void macros_init(void);
+void macros_cleanup(void);
+
 void macro_define(struct place *, const char *macro,
 		  struct place *, const char *expansion);
 void macro_undef(const char *macro);

--- a/main.c	Mon Dec 20 00:32:20 2010 -0500
+++ b/main.c	Mon Dec 20 01:15:43 2010 -0500
@@ -872,6 +872,7 @@
 	place_init();
 	files_init();
 	directive_init();
+	macros_init();
 }
 
 static
@@ -880,6 +881,7 @@
 {
 	unsigned i, num;
 
+	macros_cleanup();
 	directive_cleanup();
 	files_cleanup();
 	place_cleanup();

--- a/place.h	Mon Dec 20 00:32:20 2010 -0500
+++ b/place.h	Mon Dec 20 01:15:43 2010 -0500
@@ -1,3 +1,4 @@
+#include <stdbool.h>
 
 enum places {
 	P_NOWHERE,