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