#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;
}