// Some very simple hash table code.  See also intcounts.S and
// intcountst.c.
#include <stdio.h>
#include <stdlib.h>


// Example hash table code from
// <https://news.ycombinator.com/item?id=42499866>

enum { nb = 1024 };
struct { int k, v; } hash[nb];

// 0 is an invalid key
void incr(unsigned k)
{
  int i = k % nb, j = i;
  do {
    int k2 = hash[i].k;
    if (k2 && k2 != k) {
      i = (i+1) % nb;
      continue;
    }
    hash[i].k = k;
    hash[i].v++;
    return;
  } while (i != j);
  abort();
}

// Version simplified to 11 lines, including the enum above.  gcc
// 9.4.0 with -Os compiles this to 21 instructions for amd64, counting
// the initial endbr64 but not counting the padding nop at the end,
// vs. 23 instructions for the one above.  Unlike clang for arm64, it
// doesn’t avoid the key equality test in the (common) case where it’s
// redundant because we’ve just inserted it.
int kj[nb], vj[nb];

int inc(unsigned k)
{
  for (unsigned i = 0; i < nb; i++) {
    int j = (k+i) % nb;
    if (!kj[j]) kj[j] = k;
    if (kj[j] == k) return ++vj[j];
  }
  abort();
}

int main()
{
  int xs[] = {2344, 102, 2344, 7, 102, 5, 67, 1, 1025, 17, 2049, 1025, 2344};
  for (int i = 0; i < sizeof(xs)/sizeof(xs[0]); i++) incr(xs[i]), inc(xs[i]);
  for (int i = 0; i < nb; i++) {
    if (hash[i].k) printf("%d: %d\n", hash[i].k, hash[i].v);
    if (kj[i]) printf("%d. %d\n", kj[i], vj[i]);
  }
  // to fail: for (int i = 0; i < nb; i++) incr(i+1);
  return 0;
}