8 typedef struct __freenode_t {
9 uint32_t level:28, cnt:4;
10 struct __freenode_t *next;
11 } freenode_t, *freenode_p;
13 #define freenode_lt(a,b) ((a)->cnt < (b)->cnt || ((a)->cnt == (b)->cnt && (a)->level < (b)->level))
14 KSORT_INIT(node, freenode_p, freenode_lt)
16 /* Memory pool, similar to the one in bam_pileup.c */
22 static mempool_t *mp_init()
24 return (mempool_t*)calloc(1, sizeof(mempool_t));
26 static void mp_destroy(mempool_t *mp)
29 for (k = 0; k < mp->n; ++k) free(mp->buf[k]);
30 free(mp->buf); free(mp);
32 static inline freenode_t *mp_alloc(mempool_t *mp)
35 if (mp->n == 0) return (freenode_t*)calloc(1, sizeof(freenode_t));
36 else return mp->buf[--mp->n];
38 static inline void mp_free(mempool_t *mp, freenode_t *p)
40 --mp->cnt; p->next = 0; p->cnt = TV_GAP;
41 if (mp->n == mp->max) {
42 mp->max = mp->max? mp->max<<1 : 256;
43 mp->buf = (freenode_t**)realloc(mp->buf, sizeof(freenode_t*) * mp->max);
49 struct __bam_lplbuf_t {
50 int max, n_cur, n_pre;
51 int max_level, *cur_level, *pre_level;
53 freenode_t **aux, *head, *tail;
60 void bam_lplbuf_reset(bam_lplbuf_t *buf)
63 bam_plbuf_reset(buf->plbuf);
64 for (p = buf->head; p->next;) {
69 buf->head = buf->tail;
71 buf->n_cur = buf->n_pre = 0;
75 static int tview_func(uint32_t tid, uint32_t pos, int n, const bam_pileup1_t *pl, void *data)
77 bam_lplbuf_t *tv = (bam_lplbuf_t*)data;
80 // allocate memory if necessary
81 if (tv->max < n) { // enlarge
84 tv->cur_level = (int*)realloc(tv->cur_level, sizeof(int) * tv->max);
85 tv->pre_level = (int*)realloc(tv->pre_level, sizeof(int) * tv->max);
89 for (p = tv->head; p->next; p = p->next)
90 if (p->cnt > 0) --p->cnt;
91 // calculate cur_level[]
93 for (i = l = 0; i < n; ++i) {
94 const bam_pileup1_t *p = pl + i;
96 if (tv->head->next && tv->head->cnt == 0) { // then take a free slot
97 freenode_t *p = tv->head->next;
98 tv->cur_level[i] = tv->head->level;
99 mp_free(tv->mp, tv->head);
102 } else tv->cur_level[i] = ++tv->max_level;
104 tv->cur_level[i] = tv->pre_level[l++];
105 if (p->is_tail) { // then return a free slot
106 tv->tail->level = tv->cur_level[i];
107 tv->tail->next = mp_alloc(tv->mp);
108 tv->tail = tv->tail->next;
112 if (tv->cur_level[i] > max_level) max_level = tv->cur_level[i];
113 ((bam_pileup1_t*)p)->level = tv->cur_level[i];
115 assert(l == tv->n_pre);
116 tv->func(tid, pos, n, pl, tv->user_data);
117 // sort the linked list
120 if (tv->n_nodes + 1 > tv->m_aux) { // enlarge
121 tv->m_aux = tv->n_nodes + 1;
122 kroundup32(tv->m_aux);
123 tv->aux = (freenode_t**)realloc(tv->aux, sizeof(void*) * tv->m_aux);
125 for (p = tv->head, i = l = 0; p->next;) {
126 if (p->level > max_level) { // then discard this entry
135 tv->aux[i] = tv->tail; // add a proper tail for the loop below
138 ks_introsort(node, tv->n_nodes, tv->aux);
139 for (i = 0; i < tv->n_nodes; ++i) tv->aux[i]->next = tv->aux[i+1];
140 tv->head = tv->aux[0];
141 } else tv->head = tv->tail;
144 tv->max_level = max_level;
145 memcpy(tv->pre_level, tv->cur_level, tv->n_cur * 4);
146 // squeeze out terminated levels
147 for (i = l = 0; i < n; ++i) {
148 const bam_pileup1_t *p = pl + i;
150 tv->pre_level[l++] = tv->pre_level[i];
154 fprintf(stderr, "%d\t", pos+1);
155 for (i = 0; i < n; ++i) {
156 const bam_pileup1_t *p = pl + i;
157 if (p->is_head) fprintf(stderr, "^");
158 if (p->is_tail) fprintf(stderr, "$");
159 fprintf(stderr, "%d,", p->level);
161 fprintf(stderr, "\n");
166 bam_lplbuf_t *bam_lplbuf_init(bam_pileup_f func, void *data)
169 tv = (bam_lplbuf_t*)calloc(1, sizeof(bam_lplbuf_t));
171 tv->head = tv->tail = mp_alloc(tv->mp);
173 tv->user_data = data;
174 tv->plbuf = bam_plbuf_init(tview_func, tv);
175 return (bam_lplbuf_t*)tv;
178 void bam_lplbuf_destroy(bam_lplbuf_t *tv)
181 free(tv->cur_level); free(tv->pre_level);
182 bam_plbuf_destroy(tv->plbuf);
184 for (p = tv->head; p->next;) {
186 mp_free(tv->mp, p); p = q;
189 assert(tv->mp->cnt == 0);
194 int bam_lplbuf_push(const bam1_t *b, bam_lplbuf_t *tv)
196 return bam_plbuf_push(b, tv->plbuf);
199 int bam_lpileup_file(bamFile fp, int mask, bam_pileup_f func, void *func_data)
204 b = (bam1_t*)calloc(1, sizeof(bam1_t));
205 buf = bam_lplbuf_init(func, func_data);
206 bam_plbuf_set_mask(buf->plbuf, mask);
207 while ((ret = bam_read1(fp, b)) >= 0)
208 bam_lplbuf_push(b, buf);
209 bam_lplbuf_push(0, buf);
210 bam_lplbuf_destroy(buf);
211 free(b->data); free(b);