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