#12

// binsort.c --- binsort with specified maximum
#include <stdlib.h>
void binsort(int n, int *a, int max) {
  int i, k = 0, *bin = (int*)malloc((max+1) * sizeof(int));
  for(i = 0; i <= max; ++i) { bin[i] = 0; }
  for(i = 0; i < n; ++i) { ++bin[a[i]]; }
  for(i = 0; i <= max; ++i) {
    while(--bin[i] >= 0) { a[k++] = i; }
  }
  free(bin);
}
// radixsort.c --- radixsort (upper->lower) from specified mask
static void swap(int *a, int i, int j) {
  int x = a[i]; a[i] = a[j]; a[j] = x;
}
static void rs(int *a, int i, int j, int mask) {
  if(i >= j || mask == 0) { return; }
  int k, s;
  for(s = k = i; k <= j; ++k) {
    if((a[k]&mask) == 0) { swap(a, s++, k); }
  }
  rs(a, i, s-1, mask/2); rs(a, s, j, mask/2);
}
void radixsort(int n, int *a) { rs(a, 0, n-1, 0x40000000); }
// itbl.h --- int table api.
struct itbl;
typedef struct itbl *itblp;
itblp itbl_new();                     // allocate new tbl
void itbl_put(itblp t, int k, int v); // store value
int itbl_get(itblp t, int k);         // obtain value
// itbl.c --- itbl impl with arry of records.
#include <stdlib.h>
#include "itbl.h"
typedef struct ent { int key, val; } * entp;
struct itbl { int size, lim; entp arr; };
itblp itbl_new() {
  itblp p = (itblp)malloc(sizeof(struct itbl));
  p->arr = (entp)malloc(100 * sizeof(struct ent));
  p->size = 0; p->lim = 100; return p;
}
static void enlarge(itblp p) {
  entp a = (entp)malloc(p->lim * 2 * sizeof(struct ent));
  for(int i = 0; i < p->size; ++i) { a[i] = p->arr[i]; }
  free(p->arr); p->arr = a; p->lim *= 2;
}
static entp lookup(itblp p, int k) {
  for(int i = 0; i < p->size; ++i) {
    if(p->arr[i].key == k) { return p->arr + i; }
  }
  return NULL;
}
void itbl_put(itblp p, int k, int v) {
  entp e = lookup(p, k);
  if(e != NULL) { e->val = v; return; }
  if(p->size + 1 >= p->lim) { enlarge(p); }
  p->arr[p->size].key = k; p->arr[p->size++].val = v;
}
int itbl_get(itblp p, int k) {
  entp e = lookup(p, k); return e == NULL ? -1 : e->val;
}
// itbldemo.c --- register primes with ranks.
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <math.h>
#include "itbl.h"

bool isprime(int n) {
  int lim = (int)sqrt(n);
  for(int i = 2; i <= lim; ++i) { if(n % i == 0) { return false; } }
  return true;
}
int regist(itblp t, int lim) {
  int r = 0;
  for(int i = 2; i <= lim; ++i) { if(isprime(i)) { itbl_put(t, i, ++r); } }
  return r;
}
int main(int argc, char *argv[]) {
  itblp t = itbl_new();
  printf("max rank = %d\n", regist(t, 10000));
  for(int i = 1; i < argc; ++i) {
    int k = atoi(argv[i]); printf("%d: %d\n", k, itbl_get(t, k));
  }
  return 0;
}
// test_itbl.c --- unit test for itable.
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "itbl.h"
void expect_itbl(int n) {
  struct timespec tm1, tm2, tm3;
  itblp t = itbl_new();
  int *a = (int*)malloc(n * sizeof(int));
  for(int i = 0; i < n; ++i) { a[i] = rand(); }
  clock_gettime(CLOCK_REALTIME, &tm1);
  for(int i = 0; i < n; ++i) { itbl_put(t, a[i], a[i]+1); }
  clock_gettime(CLOCK_REALTIME, &tm2);
  for(int i = 0; i < n; ++i) { itbl_get(t, a[i]); }
  clock_gettime(CLOCK_REALTIME, &tm3);
  int c = 0;
  for(int i = 0; i < n; ++i) {
    int v = itbl_get(t, a[i]);
    if(v == a[i]+1) { continue; }
    if(++c < 5) {
      printf(" NG: #\%d get[%d] == %d, expected %d\n", i, a[i], v, a[i]+1);
    } else if(c == 5) {
      printf("more wrong value omitted.\n");
    }
  }
  double dt1 = (tm2.tv_sec-tm1.tv_sec) + 1e-9*(tm2.tv_nsec-tm1.tv_nsec);
  double dt2 = (tm3.tv_sec-tm2.tv_sec) + 1e-9*(tm3.tv_nsec-tm2.tv_nsec);
  printf("%s size=%d tput=%.4f tget=%.4f %s\n", c==0?"OK":"NG", n, dt1, dt2);
  free(a);
}
int main(int argc, char *argv[]) {
  srand(time(NULL));
  for(int i = 1; i < argc; ++i) { expect_itbl(atoi(argv[i])); }
  return 0;
}
// itbl2.c --- itbl impl with sorted arry of records.
#include <stdlib.h>
#include "itbl.h"
typedef struct ent { int key, val; } * entp;
struct itbl { int size, lim; entp arr; };
itblp itbl_new() {
  itblp p = (itblp)malloc(sizeof(struct itbl));
  p->arr = (entp)malloc(100 * sizeof(struct ent));
  p->size = 0; p->lim = 100; return p;
}
static void enlarge(itblp p) {
  entp a = (entp)malloc(p->lim * 2 * sizeof(struct ent));
  for(int i = 0; i < p->size; ++i) { a[i] = p->arr[i]; }
  free(p->arr); p->arr = a; p->lim *= 2;
}
static entp lookup2(itblp p, int k, int i, int j) {
  if(i > j) { return NULL; }
  int m = (i + j) / 2;
  if(p->arr[m].key == k)     { return p->arr + m; }
  else if(p->arr[m].key > k) { return lookup2(p, k, i, m-1); }
  else                       { return lookup2(p, k, m+1, j); }
}
void shiftup(itblp p) {
  entp a = p->arr;
  for(int i = p->size-1; i > 0 && a[i-1].key > a[i].key; --i) {
    struct ent x = a[i-1]; a[i-1] = a[i]; a[i] = x;
  }
}
void itbl_put(itblp p, int k, int v) {
  entp e = lookup2(p, k, 0, p->size-1);
  if(e != NULL) { e->val = v; return; }
  if(p->size + 1 >= p->lim) { enlarge(p); }
  p->arr[p->size].key = k; p->arr[p->size++].val = v; shiftup(p);
}
int itbl_get(itblp p, int k) {
  entp e = lookup2(p, k, 0, p->size-1);
  return e == NULL ? -1 : e->val;
}
// hashtbl.c --- itbl impl w/ random rehashing.
#include <stdlib.h>
#include "itbl.h"
typedef struct ent { int key, val; } *entp;
struct itbl { int size; entp arr; };
#define INITSIZE 999983
#define REHASH 97
itblp itbl_new() {
  itblp p = (itblp)malloc(sizeof(struct itbl));
  p->arr = (entp)malloc(INITSIZE * sizeof(struct ent));
  p->size = INITSIZE;
  for(int i = 0; i < p->size; ++i) { p->arr[i].key = -1; }
  return p;
}
static int h1(itblp p, int n) { return n % p->size; }
static int h2(int n) { return n % REHASH + 3; }
void itbl_put(itblp p, int k, int v) {
  int i = h1(p, k), d = h2(k), c = 0;
  while(p->arr[i].key != k && p->arr[i].key != -1) {
    if(++c > p->size) { return; }
    i = (i + d) % p->size;
  }
  p->arr[i].key = k; p->arr[i].val = v;
}
int itbl_get(itblp p, int k) {
  int i = h1(p, k), d = h2(k), c = 0;
  while(p->arr[i].key != k) {
    if(++c > p->size || p->arr[i].key == -1) { return -1; }
    i = (i + d) % p->size;
  }
  return p->arr[i].val;
}