スキップテーブル計算

#include <stdio.h>
#include <stdlib.h>

#define malloc_int(len) (int *)malloc(sizeof(int)*len)

typedef struct b_entry
{
    int val;
    int hash;
    struct b_entry *next_gt, *next_lt;
} b_entry;
#define BHASH(x) ((unsigned int)(x)*54321*54321*54321)

static b_entry *b_buffer;
static int n_b_buffer;

static b_entry *new_entry()
{
    return &b_buffer[n_b_buffer++];
}

static int find_b(int b, b_entry *root)
{
    b_entry *p = root;
    b_entry **prev = NULL;
    int bhash = BHASH(b);

    while(p!=NULL)
    {
	int bcmp = p->hash - bhash;
	if(bcmp==0) bcmp = b-p->val;
        if(bcmp == 0) return 0;
	prev = (bcmp < 0)? &(p->next_lt):&(p->next_gt);
	p = *prev;
    }

    p = new_entry();

    p->val = b;
    p->hash = bhash;
    p->next_lt = p->next_gt = NULL;
    if (prev != NULL) *prev = p;
    return 1;
}

extern void init_skip_tab(int maxbits, char *flag_tab)
{
    int *a_tab2;
    int *b_tab2;

    int *a_tab = malloc_int(2);
    int *b_tab = malloc_int(2);

    int pow3[maxbits+1];
    b_entry root[maxbits+1];
    int i,k, ntab;

    b_buffer = (b_entry *)malloc(sizeof(b_entry)*(1<<maxbits));
    n_b_buffer = 0;

    for (i=0;i<=maxbits;i++)
    {
	pow3[i] = (i==0)? 1:3*pow3[i-1];
	root[i].val = -1;
	root[i].next_gt = root[i].next_lt = NULL;
    }

    // 2m -> m+0
    a_tab[0] = 0; b_tab[0] = 0;
    // 2m+1 -> 6m+4 -> 3m+2
    a_tab[1] = 1; b_tab[1] = 2;

    for(ntab = 2;ntab <= (1<<(maxbits-1)); ntab <<=1)
    {
        a_tab2 = malloc_int(ntab*2);
        b_tab2 = malloc_int(ntab*2);

        for(i=0;i<ntab;i++)
        {
	    for (k=0;k<2;k++)
	    {
	        int a3 = a_tab[i];
	        int b = b_tab[i] + k*pow3[a3];

	        if (b&1)
	        {
	            b = b*3+1;
		    a3++;
	        }
	        a_tab2[i+k*ntab]=a3;
	        b_tab2[i+k*ntab]=b/2;
	    }
        }
        free(a_tab);
        free(b_tab);

        a_tab = a_tab2;
        b_tab = b_tab2;
    }

    k=0;
    for(i=0;i<ntab;i++)
    {
	int a3 = a_tab[i];
	int b = b_tab[i];
        b_entry *p = &root[a3];

	if (p->val == -1)
	{
	    p->val = b;
	    flag_tab[i] =1;
	}
	else
	{
	    flag_tab[i] = find_b(b, p);
	}
	k += flag_tab[i];
    }
    printf("# %d Ratio %6.3f (%d/%d)\n",maxbits,k*1.0/ntab,k,ntab);
    free(a_tab2);
    free(b_tab2);

    free(b_buffer);
}