1 #ifdef _cplusplus
2 extern "C" {
3 #endif
4 #include "singleseqspace.h"
5
6
7
8 /* Function: lookup_Sequence_SinglePosSpace(space,pos)
9 *
10 * Descrip: New return using binary choping
11 *
12 *
13 * Arg: space [UNKN ] Undocumented argument [SinglePosSpace *]
14 * Arg: pos [UNKN ] Undocumented argument [long]
15 *
16 * Return [UNKN ] Undocumented return value [SinglePosSequence *]
17 *
18 */
19 # line 36 "singleseqspace.dy"
lookup_Sequence_SinglePosSpace(SinglePosSpace * space,long pos)20 SinglePosSequence * lookup_Sequence_SinglePosSpace(SinglePosSpace * space,long pos)
21 {
22 int index_pos;
23
24 assert(pos < space->current_end);
25 assert(pos >= 0);
26
27 if( space->is_static != 0 ) {
28 /* can make explicit calculation for position */
29
30 index_pos = (int) (pos / space->average_len);
31 if( space->sns[index_pos]->start == -1 ) {
32 /* was a padding position */
33 for(index_pos--;index_pos >= 0 && space->sns[index_pos]->start == -1;index_pos--) {
34 /*fprintf(stderr,"Regressed %d with %d [pos %d]\n",index_pos,space->sns[index_pos]->start,pos);*/
35 }
36 assert(index_pos >= 0 );
37 }
38
39 if( space->sns[index_pos] == NULL ) {
40 fatal("Going to return %d for %d with %d - max %d\n",index_pos,pos,space->average_len,space->current_end);
41 }
42
43 return space->sns[index_pos];
44 }
45
46
47 assert(pos < space->current_end);
48
49 index_pos = find_position_SinglePosSpace(space,0,space->len-1,pos);
50
51
52 return space->sns[index_pos];
53 }
54
55
56 /* Function: find_position_SinglePosSpace(space,lower,higher,position)
57 *
58 * Descrip: Recursive function for finding position
59 *
60 *
61 * Arg: space [UNKN ] Undocumented argument [SinglePosSpace *]
62 * Arg: lower [UNKN ] Undocumented argument [int]
63 * Arg: higher [UNKN ] Undocumented argument [int]
64 * Arg: position [UNKN ] Undocumented argument [int]
65 *
66 * Return [UNKN ] Undocumented return value [int]
67 *
68 */
69 # line 75 "singleseqspace.dy"
find_position_SinglePosSpace(SinglePosSpace * space,int lower,int higher,int position)70 int find_position_SinglePosSpace(SinglePosSpace * space,int lower,int higher,int position)
71 {
72 int mid;
73 /*
74 fprintf(stderr,"To find position %d Entering with.... %d to %d\n",position,lower,higher);
75 */
76
77 if( lower+2 >= higher ) {
78 if( position >= space->sns[lower]->start && position < space->sns[lower]->end )
79 return lower;
80 if( position >= space->sns[higher]->start && position < space->sns[higher]->end )
81 return higher;
82 }
83
84 mid = (lower + (int)((higher-lower)/2));
85
86 if( position >= space->sns[mid]->start && position < space->sns[mid]->end )
87 return mid;
88
89
90 if( position >= space->sns[mid]->end ) {
91 /* top half */
92 return find_position_SinglePosSpace(space,mid,higher,position);
93 } else {
94 return find_position_SinglePosSpace(space,lower,mid,position);
95 }
96
97 }
98
99
100 /* Function: add_Sequence_SinglePosSpace(space,length,data)
101 *
102 * Descrip: Adds a sequence to a single number space, giving out the start
103 * position for this sequence
104 *
105 *
106 * Arg: space [UNKN ] Undocumented argument [SinglePosSpace *]
107 * Arg: length [UNKN ] Undocumented argument [long int]
108 * Arg: data [UNKN ] Undocumented argument [void *]
109 *
110 * Return [UNKN ] Undocumented return value [long int]
111 *
112 */
113 # line 109 "singleseqspace.dy"
add_Sequence_SinglePosSpace(SinglePosSpace * space,long int length,void * data)114 long int add_Sequence_SinglePosSpace(SinglePosSpace * space,long int length,void * data)
115 {
116 int seq_size = 1;
117 int i;
118 SinglePosSequence * a;
119 SinglePosSequence * dummy;
120
121
122
123 assert(space);
124 assert(data);
125 assert(length >= 0);
126
127 a = SinglePosSequence_alloc();
128 a->start = space->current_end;
129
130 if( space->is_static != 0 ) {
131 if( length > space->max_length ) {
132 seq_size = (length / space->max_length) +1;
133 } else {
134 seq_size = 1;
135 }
136
137 a->end = space->current_end + (space->max_length*seq_size);
138 space->average_len = space->max_length;
139 } else {
140 a->end = space->current_end + length;
141 space->average_len = a->end / length;
142 }
143
144 a->data = data;
145
146 add_SinglePosSpace(space,a);
147
148 /* pad for long sequences */
149 if( seq_size > 1 ) {
150 for(i=1;i<seq_size;i++) {
151 dummy = SinglePosSequence_alloc();
152 dummy->start = -1;
153 dummy->end = -1;
154 dummy->data = NULL;
155 add_SinglePosSpace(space,dummy);
156 }
157 }
158
159 space->current_end = a->end;
160
161
162 return a->start;
163 }
164
165 /* Function: new_SinglePosSpace(has_maxlen,max_length)
166 *
167 * Descrip: Provides a new single number space
168 *
169 *
170 * Arg: has_maxlen [UNKN ] Undocumented argument [int]
171 * Arg: max_length [UNKN ] Undocumented argument [int]
172 *
173 * Return [UNKN ] Undocumented return value [SinglePosSpace *]
174 *
175 */
176 # line 163 "singleseqspace.dy"
new_SinglePosSpace(int has_maxlen,int max_length)177 SinglePosSpace * new_SinglePosSpace(int has_maxlen,int max_length)
178 {
179 SinglePosSpace * out;
180
181 out = SinglePosSpace_alloc_std();
182
183 out->is_static = has_maxlen;
184 out->max_length = max_length;
185
186 return out;
187
188 }
189
190 # line 181 "singleseqspace.c"
191 /* Function: hard_link_SinglePosSequence(obj)
192 *
193 * Descrip: Bumps up the reference count of the object
194 * Meaning that multiple pointers can 'own' it
195 *
196 *
197 * Arg: obj [UNKN ] Object to be hard linked [SinglePosSequence *]
198 *
199 * Return [UNKN ] Undocumented return value [SinglePosSequence *]
200 *
201 */
hard_link_SinglePosSequence(SinglePosSequence * obj)202 SinglePosSequence * hard_link_SinglePosSequence(SinglePosSequence * obj)
203 {
204 if( obj == NULL ) {
205 warn("Trying to hard link to a SinglePosSequence object: passed a NULL object");
206 return NULL;
207 }
208 obj->dynamite_hard_link++;
209 return obj;
210 }
211
212
213 /* Function: SinglePosSequence_alloc(void)
214 *
215 * Descrip: Allocates structure: assigns defaults if given
216 *
217 *
218 *
219 * Return [UNKN ] Undocumented return value [SinglePosSequence *]
220 *
221 */
SinglePosSequence_alloc(void)222 SinglePosSequence * SinglePosSequence_alloc(void)
223 {
224 SinglePosSequence * out;/* out is exported at end of function */
225
226
227 /* call ckalloc and see if NULL */
228 if((out=(SinglePosSequence *) ckalloc (sizeof(SinglePosSequence))) == NULL) {
229 warn("SinglePosSequence_alloc failed ");
230 return NULL; /* calling function should respond! */
231 }
232 out->dynamite_hard_link = 1;
233 #ifdef PTHREAD
234 pthread_mutex_init(&(out->dynamite_mutex),NULL);
235 #endif
236 out->start = 0;
237 out->end = 0;
238
239
240 return out;
241 }
242
243
244 /* Function: free_SinglePosSequence(obj)
245 *
246 * Descrip: Free Function: removes the memory held by obj
247 * Will chain up to owned members and clear all lists
248 *
249 *
250 * Arg: obj [UNKN ] Object that is free'd [SinglePosSequence *]
251 *
252 * Return [UNKN ] Undocumented return value [SinglePosSequence *]
253 *
254 */
free_SinglePosSequence(SinglePosSequence * obj)255 SinglePosSequence * free_SinglePosSequence(SinglePosSequence * obj)
256 {
257 int return_early = 0;
258
259
260 if( obj == NULL) {
261 warn("Attempting to free a NULL pointer to a SinglePosSequence obj. Should be trappable");
262 return NULL;
263 }
264
265
266 #ifdef PTHREAD
267 assert(pthread_mutex_lock(&(obj->dynamite_mutex)) == 0);
268 #endif
269 if( obj->dynamite_hard_link > 1) {
270 return_early = 1;
271 obj->dynamite_hard_link--;
272 }
273 #ifdef PTHREAD
274 assert(pthread_mutex_unlock(&(obj->dynamite_mutex)) == 0);
275 #endif
276 if( return_early == 1)
277 return NULL;
278 /* obj->data is linked in */
279
280
281 ckfree(obj);
282 return NULL;
283 }
284
285
286 /* Function: swap_SinglePosSpace(list,i,j)
287 *
288 * Descrip: swap function: an internal for qsort_SinglePosSpace
289 * swaps two positions in the array
290 *
291 *
292 * Arg: list [UNKN ] List of structures to swap in [SinglePosSequence **]
293 * Arg: i [UNKN ] swap position [int]
294 * Arg: j [UNKN ] swap position [int]
295 *
296 */
297 /* swap function for qsort function */
swap_SinglePosSpace(SinglePosSequence ** list,int i,int j)298 void swap_SinglePosSpace(SinglePosSequence ** list,int i,int j)
299 {
300 SinglePosSequence * temp;
301 temp=list[i];
302 list[i]=list[j];
303 list[j]=temp;
304 }
305
306
307 /* Function: qsort_SinglePosSpace(list,left,right,comp)
308 *
309 * Descrip: qsort - lifted from K&R
310 * sorts the array using quicksort
311 * Probably much better to call sort_SinglePosSpace which sorts from start to end
312 *
313 *
314 * Arg: list [UNKN ] List of structures to swap in [SinglePosSequence **]
315 * Arg: left [UNKN ] left position [int]
316 * Arg: right [UNKN ] right position [int]
317 * Arg: comp [FUNCP] Function which returns -1 or 1 to sort on [int (*comp]
318 *
319 */
qsort_SinglePosSpace(SinglePosSequence ** list,int left,int right,int (* comp)(SinglePosSequence *,SinglePosSequence *))320 void qsort_SinglePosSpace(SinglePosSequence ** list,int left,int right,int (*comp)(SinglePosSequence * ,SinglePosSequence * ))
321 {
322 int i,last;
323 if( left >= right )
324 return;
325
326
327 swap_SinglePosSpace(list,left,(left+right)/2);
328 last = left;
329 for ( i=left+1; i <= right;i++) {
330 if( (*comp)(list[i],list[left]) < 0)
331 swap_SinglePosSpace (list,++last,i);
332 }
333 swap_SinglePosSpace (list,left,last);
334 qsort_SinglePosSpace(list,left,last-1,comp);
335 qsort_SinglePosSpace(list,last+1,right,comp);
336 }
337
338
339 /* Function: sort_SinglePosSpace(obj,comp)
340 *
341 * Descrip: sorts from start to end using comp
342 * sorts the array using quicksort by calling qsort_SinglePosSpace
343 *
344 *
345 * Arg: obj [UNKN ] Object containing list [SinglePosSpace *]
346 * Arg: comp [FUNCP] Function which returns -1 or 1 to sort on [int (*comp]
347 *
348 */
sort_SinglePosSpace(SinglePosSpace * obj,int (* comp)(SinglePosSequence *,SinglePosSequence *))349 void sort_SinglePosSpace(SinglePosSpace * obj,int (*comp)(SinglePosSequence *, SinglePosSequence *))
350 {
351 qsort_SinglePosSpace(obj->sns,0,obj->len-1,comp);
352 return;
353 }
354
355
356 /* Function: expand_SinglePosSpace(obj,len)
357 *
358 * Descrip: Really an internal function for add_SinglePosSpace
359 *
360 *
361 * Arg: obj [UNKN ] Object which contains the list [SinglePosSpace *]
362 * Arg: len [UNKN ] Length to add one [int]
363 *
364 * Return [UNKN ] Undocumented return value [boolean]
365 *
366 */
expand_SinglePosSpace(SinglePosSpace * obj,int len)367 boolean expand_SinglePosSpace(SinglePosSpace * obj,int len)
368 {
369
370
371 if( obj->maxlen > obj->len ) {
372 warn("expand_SinglePosSpace called with no need");
373 return TRUE;
374 }
375
376
377 if( (obj->sns = (SinglePosSequence ** ) ckrealloc (obj->sns,sizeof(SinglePosSequence *)*len)) == NULL) {
378 warn("ckrealloc failed for expand_SinglePosSpace, returning FALSE");
379 return FALSE;
380 }
381 obj->maxlen = len;
382 return TRUE;
383 }
384
385
386 /* Function: add_SinglePosSpace(obj,add)
387 *
388 * Descrip: Adds another object to the list. It will expand the list if necessary
389 *
390 *
391 * Arg: obj [UNKN ] Object which contains the list [SinglePosSpace *]
392 * Arg: add [OWNER] Object to add to the list [SinglePosSequence *]
393 *
394 * Return [UNKN ] Undocumented return value [boolean]
395 *
396 */
397 /* will expand function if necessary */
add_SinglePosSpace(SinglePosSpace * obj,SinglePosSequence * add)398 boolean add_SinglePosSpace(SinglePosSpace * obj,SinglePosSequence * add)
399 {
400 if( obj->len >= obj->maxlen) {
401 if( expand_SinglePosSpace(obj,obj->len + SinglePosSpaceLISTLENGTH) == FALSE)
402 return FALSE;
403 }
404
405
406 obj->sns[obj->len++]=add;
407 return TRUE;
408 }
409
410
411 /* Function: flush_SinglePosSpace(obj)
412 *
413 * Descrip: Frees the list elements, sets length to 0
414 * If you want to save some elements, use hard_link_xxx
415 * to protect them from being actually destroyed in the free
416 *
417 *
418 * Arg: obj [UNKN ] Object which contains the list [SinglePosSpace *]
419 *
420 * Return [UNKN ] Undocumented return value [int]
421 *
422 */
flush_SinglePosSpace(SinglePosSpace * obj)423 int flush_SinglePosSpace(SinglePosSpace * obj)
424 {
425 int i;
426
427
428 for(i=0;i<obj->len;i++) { /*for i over list length*/
429 if( obj->sns[i] != NULL) {
430 free_SinglePosSequence(obj->sns[i]);
431 obj->sns[i] = NULL;
432 }
433 } /* end of for i over list length */
434
435
436 obj->len = 0;
437 return i;
438 }
439
440
441 /* Function: SinglePosSpace_alloc_std(void)
442 *
443 * Descrip: Equivalent to SinglePosSpace_alloc_len(SinglePosSpaceLISTLENGTH)
444 *
445 *
446 *
447 * Return [UNKN ] Undocumented return value [SinglePosSpace *]
448 *
449 */
SinglePosSpace_alloc_std(void)450 SinglePosSpace * SinglePosSpace_alloc_std(void)
451 {
452 return SinglePosSpace_alloc_len(SinglePosSpaceLISTLENGTH);
453 }
454
455
456 /* Function: SinglePosSpace_alloc_len(len)
457 *
458 * Descrip: Allocates len length to all lists
459 *
460 *
461 * Arg: len [UNKN ] Length of lists to allocate [int]
462 *
463 * Return [UNKN ] Undocumented return value [SinglePosSpace *]
464 *
465 */
SinglePosSpace_alloc_len(int len)466 SinglePosSpace * SinglePosSpace_alloc_len(int len)
467 {
468 SinglePosSpace * out; /* out is exported at the end of function */
469
470
471 /* Call alloc function: return NULL if NULL */
472 /* Warning message alread in alloc function */
473 if((out = SinglePosSpace_alloc()) == NULL)
474 return NULL;
475
476
477 /* Calling ckcalloc for list elements */
478 if((out->sns = (SinglePosSequence ** ) ckcalloc (len,sizeof(SinglePosSequence *))) == NULL) {
479 warn("Warning, ckcalloc failed in SinglePosSpace_alloc_len");
480 return NULL;
481 }
482 out->len = 0;
483 out->maxlen = len;
484
485
486 return out;
487 }
488
489
490 /* Function: hard_link_SinglePosSpace(obj)
491 *
492 * Descrip: Bumps up the reference count of the object
493 * Meaning that multiple pointers can 'own' it
494 *
495 *
496 * Arg: obj [UNKN ] Object to be hard linked [SinglePosSpace *]
497 *
498 * Return [UNKN ] Undocumented return value [SinglePosSpace *]
499 *
500 */
hard_link_SinglePosSpace(SinglePosSpace * obj)501 SinglePosSpace * hard_link_SinglePosSpace(SinglePosSpace * obj)
502 {
503 if( obj == NULL ) {
504 warn("Trying to hard link to a SinglePosSpace object: passed a NULL object");
505 return NULL;
506 }
507 obj->dynamite_hard_link++;
508 return obj;
509 }
510
511
512 /* Function: SinglePosSpace_alloc(void)
513 *
514 * Descrip: Allocates structure: assigns defaults if given
515 *
516 *
517 *
518 * Return [UNKN ] Undocumented return value [SinglePosSpace *]
519 *
520 */
SinglePosSpace_alloc(void)521 SinglePosSpace * SinglePosSpace_alloc(void)
522 {
523 SinglePosSpace * out; /* out is exported at end of function */
524
525
526 /* call ckalloc and see if NULL */
527 if((out=(SinglePosSpace *) ckalloc (sizeof(SinglePosSpace))) == NULL) {
528 warn("SinglePosSpace_alloc failed ");
529 return NULL; /* calling function should respond! */
530 }
531 out->dynamite_hard_link = 1;
532 #ifdef PTHREAD
533 pthread_mutex_init(&(out->dynamite_mutex),NULL);
534 #endif
535 out->current_end = 0;
536 out->sns = NULL;
537 out->len = out->maxlen = 0;
538 out->average_len = 0;
539 out->is_static = 0;
540 out->max_length = 1000;
541
542
543 return out;
544 }
545
546
547 /* Function: free_SinglePosSpace(obj)
548 *
549 * Descrip: Free Function: removes the memory held by obj
550 * Will chain up to owned members and clear all lists
551 *
552 *
553 * Arg: obj [UNKN ] Object that is free'd [SinglePosSpace *]
554 *
555 * Return [UNKN ] Undocumented return value [SinglePosSpace *]
556 *
557 */
free_SinglePosSpace(SinglePosSpace * obj)558 SinglePosSpace * free_SinglePosSpace(SinglePosSpace * obj)
559 {
560 int return_early = 0;
561 int i;
562
563
564 if( obj == NULL) {
565 warn("Attempting to free a NULL pointer to a SinglePosSpace obj. Should be trappable");
566 return NULL;
567 }
568
569
570 #ifdef PTHREAD
571 assert(pthread_mutex_lock(&(obj->dynamite_mutex)) == 0);
572 #endif
573 if( obj->dynamite_hard_link > 1) {
574 return_early = 1;
575 obj->dynamite_hard_link--;
576 }
577 #ifdef PTHREAD
578 assert(pthread_mutex_unlock(&(obj->dynamite_mutex)) == 0);
579 #endif
580 if( return_early == 1)
581 return NULL;
582 if( obj->sns != NULL) {
583 for(i=0;i<obj->len;i++) {
584 if( obj->sns[i] != NULL)
585 free_SinglePosSequence(obj->sns[i]);
586 }
587 ckfree(obj->sns);
588 }
589 /* obj->last_accessed is linked in */
590
591
592 ckfree(obj);
593 return NULL;
594 }
595
596
597
598 #ifdef _cplusplus
599 }
600 #endif
601