BGI/soap_src/soap_builder/highOccBuilder.h

   1
   2 struct highOccPatternCell {
   3     unsigned int l[1024*1024];
   4     unsigned int r[1024*1024];
   5     struct highOccPatternCell * next;
   6 };
   7
   8
   9 //hashtable essentials
  10 unsigned int ho_hashTableSize=14814445;
  11 unsigned int ho_prime=3080419483; //a relative prime to the dna length
  12 unsigned int ho_hash_a=0, ho_hash_b=0;
  13 unsigned int ho_ttlItem=0;
  14 unsigned int ho_ttlOccurrence=0;
  15
  16 //hash func
  17 typedef struct hashItem * hashItemPtr;
  18 struct hashItem {
  19     unsigned int sa_l;
  20     unsigned int sa_r;
  21     unsigned int occCount;
  22     unsigned int occIndex;
  23     hashItemPtr next;
  24 };
  25
  26
  27 typedef struct hashTyp * hashTypPtr;
  28 struct hashTyp {
  29     unsigned int count;
  30     unsigned int index;
  31     hashItemPtr item;
  32 };
  33
  34 hashTypPtr ho_hashtable;
  35
  36
  37 //===============================
  38 const unsigned int ho_Size = 104857600;
  39
  40 typedef struct ho_cellSpace * ho_cellSpacePtr;
  41 struct ho_cellSpace {
  42     unsigned int count;
  43     unsigned int *saL;
  44     unsigned int *saR;
  45     struct ho_cellSpace * next;
  46 };
  47
  48
  49 ho_cellSpacePtr ho_root;
  50 ho_cellSpacePtr ho_currentRoot;
  51
  52 void ho_initialize() {
  53 //    fprintf(stderr,"Initialize temporary hash.\n");
  54     srand((unsigned)time(0));
  55     ho_hash_a= rand()%ho_prime;
  56     ho_hash_b= rand()%ho_prime;
  57
  58     ho_root=malloc(sizeof(struct ho_cellSpace));
  59     ho_root->saL = malloc(sizeof(unsigned int) * ho_Size );
  60     ho_root->saR = malloc(sizeof(unsigned int) * ho_Size );
  61     ho_root->count=0;
  62     ho_root->next=NULL;
  63
  64     ho_currentRoot=ho_root;
  65
  66
  67     ho_ttlItem=0;
  68     ho_ttlOccurrence=0;
  69 }
  70
  71 void ho_append(unsigned int saL, unsigned int saR) {
  72     if (ho_currentRoot->count >= ho_Size) {
  73         ho_currentRoot->next = malloc(sizeof(struct ho_cellSpace));
  74         ho_currentRoot=ho_currentRoot->next;
  75
  76         ho_currentRoot->saL=malloc(sizeof(unsigned int)*ho_Size);
  77         ho_currentRoot->saR=malloc(sizeof(unsigned int)*ho_Size);
  78         ho_currentRoot->count=0;
  79         ho_currentRoot->next=NULL;
  80     }
  81     ho_currentRoot->saL[ho_currentRoot->count]=saL;
  82     ho_currentRoot->saR[ho_currentRoot->count]=saR;
  83     ho_currentRoot->count++;
  84     ho_ttlItem++;
  85     ho_ttlOccurrence+=saR-saL+1;
  86 }
  87
  88 void ho_recurFree(ho_cellSpacePtr node) {
  89     if (node!=NULL) {
  90         ho_recurFree(node->next);
  91         free(node);
  92     }
  93 }
  94 void ho_recurFreeItem(hashItemPtr node) {
  95     if (node!=NULL) {
  96         ho_recurFreeItem(node->next);
  97         free(node);
  98     }
  99 }
 100
 101 unsigned int ho_count() {
 102     return ho_ttlItem;
 103 }
 104 void ho_free() {
 105     ho_recurFree(ho_root);
 106     unsigned int i;
 107      for (i=0;i<ho_hashTableSize;i++) {
 108          if (ho_hashtable[i].count>0) {
 109             ho_recurFreeItem(ho_hashtable[i].item);
 110          }
 111      }
 112 }
 113
 114
 115
 116 unsigned int ho_hash(unsigned int key) {
 117     //g(x)=(ax+b) mod p
 118     unsigned long long multipleA=(key * ho_hash_a)% ho_prime;
 119     unsigned int g=(unsigned int) (( multipleA + ho_hash_b ) % ho_prime);
 120
 121     //f(x)=g(x) mod n
 122     unsigned int f=g % (ho_hashTableSize);
 123
 124     return f;
 125 }