shithub: neatpost

Info  •  Files  •  Log  •  Branches

dict: use more characters in the hash function

--- a/dict.c

+++ b/dict.c

@@ -3,7 +3,6 @@

 #include <string.h>

 #include "post.h"

-#define DHASH(d, s)	((unsigned char) (s)[0])

 #define CNTMIN		(1 << 10)

 struct dict {

@@ -13,6 +12,7 @@

 	int size;

 	int n;

 	int notfound;		/* the value returned for missing keys */

+	int hashlen;		/* the number of characters used for hashing */

 	int dupkeys;		/* duplicate keys if set */

 };

@@ -23,11 +23,19 @@

 	d->size = size;

 }

-struct dict *dict_make(int notfound, int dupkeys)

+/*

+ * initialise a dictionary

+ *

+ * notfound: the value returned for missing keys.

+ * dupkeys: if nonzero, store a copy of keys inserted via dict_put().

+ * hashlen: the number of characters used for hashing

+ */

+struct dict *dict_make(int notfound, int dupkeys, int hashlen)

 {

 	struct dict *d = malloc(sizeof(*d));

 	memset(d, 0, sizeof(*d));

 	d->n = 1;

+	d->hashlen = hashlen ? hashlen : 32;

 	d->dupkeys = dupkeys;

 	d->notfound = notfound;

 	d->map = iset_make();

@@ -47,6 +55,15 @@

 	free(d);

 }

+static int dict_hash(struct dict *d, char *key)

+{

+	unsigned long hash = (unsigned char) *key++;

+	int i = d->hashlen;

+	while (--i > 0 && *key)

+		hash = (hash << 5) + hash + (unsigned char) *key++;

+	return hash & 0x3ff;

+}

+

 void dict_put(struct dict *d, char *key, int val)

 {

 	int idx;

@@ -61,13 +78,13 @@

 	idx = d->n++;

 	d->key[idx] = key;

 	d->val[idx] = val;

-	iset_put(d->map, DHASH(d, key), idx);

+	iset_put(d->map, dict_hash(d, key), idx);

 }

 /* return the index of key in d */

 int dict_idx(struct dict *d, char *key)

 {

-	int h = DHASH(d, key);

+	int h = dict_hash(d, key);

 	int *b = iset_get(d->map, h);

 	int *r = b + iset_len(d->map, h);

 	while (b && --r >= b)

@@ -95,7 +112,7 @@

 /* match a prefix of key; in the first call, *idx should be -1 */

 int dict_prefix(struct dict *d, char *key, int *pos)

 {

-	int *r = iset_get(d->map, DHASH(d, key));

+	int *r = iset_get(d->map, dict_hash(d, key));

 	while (r && r[++*pos] >= 0) {

 		int idx = r[*pos];

 		int plen = strlen(d->key[idx]);

--- a/font.c

+++ b/font.c

@@ -117,9 +117,9 @@

 	}

 	memset(fn, 0, sizeof(*fn));

 	snprintf(fn->desc, sizeof(fn->desc), "%s", path);

-	fn->gl_dict = dict_make(-1, 1);

-	fn->ch_dict = dict_make(-1, 1);

-	fn->ch_map = dict_make(-1, 1);

+	fn->gl_dict = dict_make(-1, 1, 0);

+	fn->ch_dict = dict_make(-1, 1, 0);

+	fn->ch_map = dict_make(-1, 1, 0);

 	while (fscanf(fin, "%s", tok) == 1) {

 		if (!strcmp("char", tok)) {

 			font_readchar(fn, fin, &ch_n, &ch_g);

--- a/post.h

+++ b/post.h

@@ -96,7 +96,7 @@

 int iset_len(struct iset *iset, int key);

 /* mapping strings to longs */

-struct dict *dict_make(int notfound, int dupkeys);

+struct dict *dict_make(int notfound, int dupkeys, int hashlen);

 void dict_free(struct dict *d);

 void dict_put(struct dict *d, char *key, int val);

 int dict_get(struct dict *d, char *key);