hash: replace modulus with mask.

In most places in the hash module, we reduce a hash
code into the power-of-two sized table using
h & (hash->modulus - 1). In some places we wastefully
modulo operation h % hash->modulus. Why don't we
replace the modulus with a mask so we can just do
h & hash->mask.

* hash.c (struct hash_ops): Replace modulus member with
mask, which has a value one less.
(hash_mark, hash_grow, do_make_hash, make_similar_hash,
copy_hash, gethash_c, gethash_e, remhash, clearhash,
hash_iter_next_impl, hash_iter_peek, do_weak_tables):
Work with mask rather than modulus, preserving existing
behavior.

1 files changed, 26 insertions, 26 deletions

diff --git a/hash.c b/hash.c
index de5741d4..1b85e01f 100644
--- a/hash.c
+++ b/hash.c
@@ -72,7 +72,7 @@ struct hash {
   hash_weak_opt_t wkopt;
   struct hash *next;
   val table;
-  ucnum modulus;
+  ucnum mask;
   ucnum count;
   val userdata;
   int usecount;
@@ -726,7 +726,7 @@ static void hash_mark(val hash)
     return;
   case hash_weak_keys:
     /* Mark values only. Don't mark the table. */
-    for (i = 0; i < h->modulus; i++) {
+    for (i = 0; i <= h->mask; i++) {
       for (iter = h->table->v.vec[i]; iter; iter = us_cdr(iter)) {
         val entry = us_car(iter);
         gc_mark(us_cdr(entry));
@@ -735,7 +735,7 @@ static void hash_mark(val hash)
     break;
   case hash_weak_vals:
     /* Mark keys only. Don't mark the table. */
-    for (i = 0; i < h->modulus; i++) {
+    for (i = 0; i <= h->mask; i++) {
       for (iter = h->table->v.vec[i]; iter; iter = us_cdr(iter)) {
         val entry = us_car(iter);
         gc_mark(us_car(entry));
@@ -747,7 +747,7 @@ static void hash_mark(val hash)
     break;
   case hash_weak_and:
     /* Mark key if value is reachable and vice versa. */
-    for (i = 0; i < h->modulus; i++) {
+    for (i = 0; i <= h->mask; i++) {
       for (iter = h->table->v.vec[i]; iter; iter = us_cdr(iter)) {
         val entry = us_car(iter);
         if (gc_is_reachable(us_car(entry)))
@@ -772,21 +772,21 @@ static struct cobj_ops hash_ops = cobj_ops_init(hash_equal_op,
 static void hash_grow(struct hash *h, val hash)
 {
   ucnum i;
-  ucnum new_modulus = 2 * h->modulus;
+  ucnum new_mask = (h->mask << 1) | 1;
   val new_table;
 
-  if (new_modulus > NUM_MAX)
+  if (new_mask > NUM_MAX - 1)
     return;
 
-  new_table = vector(num_fast(new_modulus), nil);
+  new_table = vector(num_fast(new_mask + 1), nil);
 
-  for (i = 0; i < h->modulus; i++) {
+  for (i = 0; i <= h->mask; i++) {
     val conses = h->table->v.vec[i];
 
     while (conses) {
       val entry = us_car(conses);
       val next = us_cdr(conses);
-      loc pchain = mkloc(new_table->v.vec[entry->ch.hash % new_modulus],
+      loc pchain = mkloc(new_table->v.vec[entry->ch.hash & new_mask],
                          new_table);
       us_rplacd(conses, deref(pchain));
       set(pchain, conses);
@@ -794,7 +794,7 @@ static void hash_grow(struct hash *h, val hash)
     }
   }
 
-  h->modulus = new_modulus;
+  h->mask = new_mask;
   h->table = new_table;
   setcheck(hash, new_table);
 }
@@ -921,7 +921,7 @@ static val do_make_hash(hash_weak_opt_t wkopt, hash_type_t type, val seed)
     h->seed = c_unum(default_arg(seed, if3(hash_seed_s, hash_seed, zero)),
                      self);
     h->wkopt = wkopt;
-    h->modulus = c_unum(mod, self);
+    h->mask = c_unum(mod - 1, self);
     h->count = 0;
     h->table = table;
     h->userdata = nil;
@@ -993,7 +993,7 @@ val make_similar_hash(val existing)
   val table = vector(mod, nil);
   val hash = cobj(coerce(mem_t *, h), hash_cls, &hash_ops);
 
-  h->modulus = c_unum(mod, self);
+  h->mask = c_unum(mod - 1, self);
   h->count = 0;
   h->table = table;
   h->userdata = ex->userdata;
@@ -1025,12 +1025,12 @@ val copy_hash(val existing)
   val self = lit("copy-hash");
   struct hash *ex = coerce(struct hash *, cobj_handle(self, existing, hash_cls));
   struct hash *h = coerce(struct hash *, chk_malloc(sizeof *h));
-  val mod = num_fast(ex->modulus);
+  val mod = num_fast(ex->mask + 1);
   val table = vector(mod, nil);
   val hash = cobj(coerce(mem_t *, h), hash_cls, &hash_ops);
   ucnum i;
 
-  h->modulus = ex->modulus;
+  h->mask = ex->mask;
   h->count = ex->count;
   h->table = table;
   h->userdata = ex->userdata;
@@ -1040,7 +1040,7 @@ val copy_hash(val existing)
   h->usecount = 0;
   h->hops = ex->hops;
 
-  for (i = 0; i < h->modulus; i++)
+  for (i = 0; i <= h->mask; i++)
     set(mkloc(h->table->v.vec[i], h->table),
         copy_hash_chain(ex->table->v.vec[i]));
 
@@ -1052,10 +1052,10 @@ val gethash_c(val self, val hash, val key, loc new_p)
   struct hash *h = coerce(struct hash *, cobj_handle(self, hash, hash_cls));
   int lim = hash_traversal_limit;
   ucnum hv = h->hops->hash_fun(key, &lim, h->seed);
-  loc pchain = mkloc(h->table->v.vec[hv & (h->modulus - 1)], h->table);
+  loc pchain = mkloc(h->table->v.vec[hv & h->mask], h->table);
   val old = deref(pchain);
   val cell = h->hops->acons_new_c_fun(key, hv, new_p, pchain);
-  if (old != deref(pchain) && ++h->count > 2 * h->modulus && h->usecount == 0)
+  if (old != deref(pchain) && ++h->count > 2 * h->mask + 2 && h->usecount == 0)
     hash_grow(h, hash);
   return cell;
 }
@@ -1065,7 +1065,7 @@ val gethash_e(val self, val hash, val key)
   struct hash *h = coerce(struct hash *, cobj_handle(self, hash, hash_cls));
   int lim = hash_traversal_limit;
   ucnum hv = h->hops->hash_fun(key, &lim, h->seed);
-  val chain = h->table->v.vec[hv & (h->modulus - 1)];
+  val chain = h->table->v.vec[hv & h->mask];
   return h->hops->assoc_fun(key, hv, chain);
 }
 
@@ -1119,7 +1119,7 @@ val remhash(val hash, val key)
   struct hash *h = coerce(struct hash *, cobj_handle(self, hash, hash_cls));
   int lim = hash_traversal_limit;
   ucnum hv = h->hops->hash_fun(key, &lim, h->seed);
-  val *pchain = &h->table->v.vec[hv % h->modulus];
+  val *pchain = &h->table->v.vec[hv & h->mask];
   val existing = h->hops->assoc_fun(key, hv, *pchain);
 
   if (existing) {
@@ -1144,7 +1144,7 @@ val clearhash(val hash)
   val mod = num_fast(256);
   val table = vector(mod, nil);
   ucnum oldcount = h->count;
-  h->modulus = c_unum(mod, self);
+  h->mask = c_unum(mod - 1, self);
   h->count = 0;
   h->table = table;
   setcheck(hash, table);
@@ -1231,7 +1231,7 @@ static val hash_iter_next_impl(struct hash_iter *hi, val iter)
   if (hi->cons)
     hi->cons = us_cdr(hi->cons);
   while (nilp(hi->cons)) {
-    if (++hi->chain >= h->modulus) {
+    if (++hi->chain > h->mask) {
       hi->hash = nil;
       h->usecount--;
       return nil;
@@ -1261,7 +1261,7 @@ val hash_iter_peek(struct hash_iter *hi)
       return us_car(peek);
   }
   do {
-    if (++chain >= h->modulus)
+    if (++chain > h->mask)
       return nil;
     cell = h->table->v.vec[chain];
   } while (!cell);
@@ -1371,7 +1371,7 @@ static void do_weak_tables(void)
     case hash_weak_keys:
       /* Sweep through all entries. Delete any which have keys
          that are garbage. */
-      for (i = 0; i < h->modulus; i++) {
+      for (i = 0; i <= h->mask; i++) {
         val *pchain = &h->table->v.vec[i];
         val *iter;
 
@@ -1393,7 +1393,7 @@ static void do_weak_tables(void)
     case hash_weak_vals:
       /* Sweep through all entries. Delete any which have values
          that are garbage. */
-      for (i = 0; i < h->modulus; i++) {
+      for (i = 0; i <= h->mask; i++) {
         val *pchain = &h->table->v.vec[i];
         val *iter;
 
@@ -1415,7 +1415,7 @@ static void do_weak_tables(void)
     case hash_weak_and:
       /* Sweep through all entries. Delete any which have keys
          and values that are garbage. */
-      for (i = 0; i < h->modulus; i++) {
+      for (i = 0; i <= h->mask; i++) {
         val *pchain = &h->table->v.vec[i];
         val *iter;
 
@@ -1439,7 +1439,7 @@ static void do_weak_tables(void)
     case hash_weak_or:
       /* Sweep through all entries. Delete any which have keys
          or values that are garbage. */
-      for (i = 0; i < h->modulus; i++) {
+      for (i = 0; i <= h->mask; i++) {
         val *pchain = &h->table->v.vec[i];
         val *iter;