/[ascend]/trunk/base/generic/compiler/numlist.c
ViewVC logotype

Contents of /trunk/base/generic/compiler/numlist.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 709 - (show annotations) (download) (as text)
Wed Jun 28 16:28:57 2006 UTC (13 years, 9 months ago) by johnpye
File MIME type: text/x-csrc
File size: 43801 byte(s)
Monster commit!
Lots of recommenting and reorganising of external relations-related stuff.
Replaced a lot of ascmalloc and asccalloc calls with the new ASC_NEW* macros.
Fixed (?) the problem Art is having with icons in PyGTK.
Turned on -Wall in SConstruct and fixed up a stack of warnings.
Removed the redundant exit(2) from after Asc_Panic calls and added __attribute__((noreturn)).
Set doxygen to create callgraphs to level 2, updated doxyfile to version 1.4.7.
Fixed up building of extfntest.c.
1 /*
2 * numlist.h
3 * by Ben Allan
4 * December 20, 1997
5 * Part of ASCEND
6 * Version: $Revision: 1.6 $
7 * Version control file: $RCSfile: numlist.c,v $
8 * Date last modified: $Date: 1998/06/16 16:38:43 $
9 * Last modified by: $Author: mthomas $
10 *
11 * This file is part of the Ascend Language Interpreter.
12 *
13 * Copyright (C) 1998 Carnegie Mellon University
14 *
15 * The Ascend Language Interpreter is free software; you can
16 * redistribute it and/or modify it under the terms of the GNU
17 * General Public License as published by the Free Software
18 * Foundation; either version 2 of the License, or (at your option)
19 * any later version.
20 *
21 * The Ascend Language Interpreter is distributed in hope that it
22 * will be useful, but WITHOUT ANY WARRANTY; without even the implied
23 * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
24 * See the GNU General Public License for more details.
25 *
26 * You should have received a copy of the GNU General Public License
27 * along with the program; if not, write to the Free Software
28 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139 USA. Check
29 * the file named COPYING.
30 */
31
32 #include <utilities/ascConfig.h>
33 #include <utilities/ascMalloc.h>
34 #include <utilities/ascPanic.h>
35 #include <utilities/ascPrint.h>
36 #include <general/list.h>
37 #include "numlist.h" /* should be in general/ */
38 #if NUMLISTUSESPOOL
39 #include <general/pool.h>
40 #endif
41
42 /*
43 * This is an element in a list of
44 * numbers and ranges.
45 * Valid numbers are 1..INT_MAX.
46 * Numbers are stored in increasing order.
47 * Valid numbers are 1..INT_MAX.
48 * numpair is a range which include all numbers from .lo to .hi
49 * including the limits of the range. A range may go from i to i.
50 * but not from j to i where j >i.
51 */
52 struct numpair {
53 int lo, hi;
54 };
55
56 /*
57 * These are the objects we hand out to the user.
58 * but they don't need to know that.
59 */
60 struct numpair_list {
61 struct numpair_list *head;
62 struct numpair *list; /* array of pairs */
63 /* if not NULL, list is piece of core rooted in list of head.
64 * if NULL this list's data is referenced by refcount pointers.
65 * When refcount is 0, destroying the numpair_list
66 * should entail destroying its data and head list as well.
67 * The g_recycled_npl may reference a list, as will all the
68 * lists created using the data of this list.
69 */
70 int len; /* size of list, meaning data in use */
71 int cap; /* capacity of allocated list, if allocated, else -1. */
72 int refcount; /* number of sharers in data space if head is NULL. */
73 #if 0 /* may need this on long pointer hardware */
74 #if (SIZEOF_VOID_P == 8)
75 int pad;
76 #endif
77 #endif
78 };
79
80 struct shared_data {
81 struct numpair_list *headlist;/* list allocated bigger than needed. */
82 int headcap; /* size of allocation in headlist */
83 int headfree; /* elements in headlist data at end
84 * not in use. */
85 };
86
87 /*
88 * List of head lists with space available.
89 * Cap will grow to the size needed.
90 * Size will shrink to zero cap/NULL when len -> 0.
91 */
92 static struct {
93 struct shared_data *shared; /* array of shared list records */
94 int shared_cap ; /* array size. */
95 int shared_len ; /* array size in use */
96 } g_recycled_npl = {NULL,0,0};
97 #define GRN g_recycled_npl /* cheesy alias */
98 #define GROW_GRN 0.5 /* grow by this fraction of previous size */
99 #define INITSIZE_GRN 100
100
101 /*
102 * set the largest number of elements we are willing to
103 * sacrifice when declaring a shared data entirely used up.
104 * must be at least 1. If having short headfree values
105 * causes a long search for free space, then increase minfree.
106 */
107 #define MINFREE 1
108
109 /*
110 * set the number of elements to put in a shared head list.
111 * should be reasonably large. Memory will be allocated in
112 * blocks of SHRSIZE*sizeof(struct numpair) when creating
113 * shareable data spaces.
114 * All lists larger than this will be individually created.
115 */
116 #define SHRSIZE 1024
117
118 /*
119 * in shared lists, we will stick a checknum in between
120 * shared data chunks. If this is overwritten, someone
121 * has overrun a list.
122 */
123 #define NHCHECKNUM INT_MAX
124
125 /*
126 * we should pool the heads.
127 */
128 #if NUMLISTUSESPOOL
129
130 static pool_store_t g_numlist_head_pool = NULL;
131 /* global for our memory manager */
132 /* aim for 4096 chunks including malloc overhead */
133 #define PNL_LEN 10
134 #ifdef __alpha
135 #define PNL_WID 100
136 #else
137 #define PNL_WID 201
138 #endif
139 /* retune rpwid if the size of struct numlist changes */
140 #define PNL_ELT_SIZE (sizeof(struct numpair_list))
141 #define PNL_MORE_ELTS 10
142 /*
143 * Number of slots filled if more elements needed.
144 * So if the pool grows, it grows by PNL_MORE_ELTS*PNL_WID elements at a time.
145 */
146 #define PNL_MORE_BARS 500
147 /* This is the number of pool bar slots to add during expansion.
148 not all the slots will be filled immediately. */
149
150 /* This function is called at compiler startup time and destroy at shutdown. */
151 static
152 void numlist_init_pool(void) {
153 if (g_numlist_head_pool != NULL ) {
154 Asc_Panic(2, NULL, "ERROR: numlist_init_pool called twice.\n");
155 }
156 g_numlist_head_pool = pool_create_store(PNL_LEN, PNL_WID, PNL_ELT_SIZE,
157 PNL_MORE_ELTS, PNL_MORE_BARS);
158 if (g_numlist_head_pool == NULL) {
159 Asc_Panic(2, NULL, "ERROR: numlist_init_pool unable to allocate pool.\n");
160 }
161 }
162
163 static
164 void numlist_destroy_pool(void) {
165 if (g_numlist_head_pool==NULL) return;
166 pool_clear_store(g_numlist_head_pool);
167 pool_destroy_store(g_numlist_head_pool);
168 g_numlist_head_pool = NULL;
169 }
170
171 #ifdef THIS_IS_AN_UNUSED_FUNCTION
172 /*@unused@*/
173 static
174 void numlist_report_pool(FILE *f)
175 {
176 if (g_numlist_head_pool==NULL) {
177 FPRINTF(f,"NumlistHeadPool is empty\n");
178 }
179 FPRINTF(f,"NumlistHeadPool ");
180 pool_print_store(f,g_numlist_head_pool,0);
181 }
182 #endif
183
184 static
185 struct numpair_list *GetPoolHead()
186 {
187 if (g_numlist_head_pool == NULL) {
188 numlist_init_pool();
189 }
190 return (struct numpair_list *)(pool_get_element(g_numlist_head_pool));
191 }
192
193 #define NHMALLOC GetPoolHead()
194 /* get a token. Token is the size of the struct struct numpair_list */
195 #define NHFREE(p) (pool_free_element(g_numlist_head_pool,((void *)p)))
196 /* return a struct numpair_list */
197 #else
198 #define NHFREE(p) ascfree(p)
199 #define NHMALLOC ASC_NEW(struct numpair_list)
200 #endif
201
202
203 /* write np up to len to stderr */
204 static
205 void NPWrite(FILE *fp, struct numpair *p, int len)
206 {
207 int i;
208 if (fp == NULL) {
209 fp = stderr;
210 }
211 if (p == NULL) {
212 return;
213 }
214 FPRINTF(fp,"0x%p: ",p);
215 for (i = 0; i < len; i++) {
216 if (p[i].lo != p[i].hi) {
217 FPRINTF(fp,"%d..%d, ", p[i].lo, p[i].hi);
218 } else {
219 FPRINTF(fp,"%d, ",p[i].hi);
220 }
221 }
222 FPRINTF(fp,"\n");
223 return;
224 }
225
226 /* conditionally exported */
227 void NLPWrite(FILE *fp, Numlist_p nlp)
228 {
229 if (nlp == NULL) {
230 return;
231 }
232 NPWrite(fp,nlp->list,nlp->len);
233 if (fp == NULL) {
234 fp = stderr;
235 }
236 FPRINTF(fp,"len = %d, cap = %d\n",nlp->len,nlp->cap);
237 }
238
239 /*
240 * nlp = NumpairExpandableList(nlp,size);
241 * Expands the size of nlp, which must be created
242 * with NumpairExpandableList. If nlp is NULL, creates
243 * the list with the size specified.
244 * If insufficient memory to create or expand to size
245 * required, returns NULL.
246 */
247 Numlist_p NumpairExpandableList(Numlist_p nlp, int newsize)
248 {
249 struct numpair *newdata;
250 if (nlp == NULL) {
251 if (newsize == 0) {
252 return NULL;
253 } else {
254 nlp = NHMALLOC;
255 if (nlp == NULL) {
256 return NULL; /* not reached */
257 }
258 }
259 nlp->list = ASC_NEW_ARRAY(struct numpair,newsize);
260 if (nlp->list == NULL) {
261 NHFREE(nlp);
262 return NULL;
263 }
264 nlp->refcount = 1;
265 nlp->len = 0;
266 nlp->cap = newsize;
267 nlp->head = NULL;
268 } else {
269 if (nlp->head != NULL || nlp->refcount != 1 || nlp->cap == -1) {
270 Asc_Panic(2,"Numlist_p to be expanded is not expandable",
271 "NumpairExpandableList");
272 return NULL; /*not reached */
273 }
274 if (nlp->cap >= newsize) {
275 return nlp;
276 }
277 }
278 newdata = (struct numpair *)ascrealloc(nlp->list,
279 sizeof(struct numpair)*newsize);
280 if (newdata == NULL) {
281 return NULL;
282 } else {
283 nlp->list = newdata;
284 nlp->cap = newsize;
285 return nlp;
286 }
287 }
288
289 /*
290 * Destroy a list. list may have come from
291 * NumpairCopyList or NumpairExpandableList.
292 */
293 void NumpairDestroyList(Numlist_p nlp)
294 {
295 if (nlp == NULL) {
296 return;
297 }
298 /* nlp sharing data space it doesn't own */
299 if (nlp->head != NULL) {
300 #ifndef NDEBUG
301 /* check for overrun */
302 if (nlp->list !=NULL) {
303 if (nlp->list[-1].lo != NHCHECKNUM || nlp->list[-1].hi != NHCHECKNUM) {
304 Asc_Panic(2,"Write past end of numlist detected",
305 "NumpairDestroyList");
306 /* not reached */
307 }
308 }
309 #endif
310 nlp->head->refcount--;
311 if (nlp->head->refcount == 0 ) {
312 /* this reference may have kept its nlp around
313 * after the head was destroyed officially.
314 */
315 ascfree(nlp->head->list);
316 nlp->head->refcount = -3;
317 NHFREE(nlp->head);
318 }
319 assert(nlp->refcount == 1);
320 nlp->refcount = -2;
321 NHFREE(nlp);
322 return;
323 }
324 /* this owns a data space that may be shared */
325 nlp->refcount--;
326 if (nlp->refcount < 1) {
327 /* nobody else cares about data, so destroy all */
328 ascfree(nlp->list);
329 nlp->refcount = -2;
330 NHFREE(nlp);
331 }
332 }
333
334 /* called only by numpaircopylist.
335 * copy a list. data capacity will be dlen, but list
336 * result will only know its size of nlp->len.
337 * Result is potentially to become shared data space of size dlen,
338 * so someone other than
339 * the list is responsible for tracking capacity.
340 * At any rate, the result of this function is not expandable, appendable.
341 */
342 static
343 Numlist_p NumpairDuplicate(Numlist_p nlp,int dlen)
344 {
345 Numlist_p result;
346 struct numpair *data, *src;
347 int len,i;
348
349 assert(nlp != NULL);
350
351 result = NHMALLOC;
352 if (result == NULL) {
353 return NULL;
354 }
355 len = nlp->len;
356 result->list = ASC_NEW_ARRAY(struct numpair,dlen);
357 result->head = NULL;
358 if (result->list == NULL) {
359 NHFREE(result);
360 return NULL;
361 }
362 result->refcount = 1;
363 result->len = len;
364 /* result->cap = dlen; somebody else's problem */
365 result->cap = -1; /* how odd! but this means list is not expandable */
366 data = result->list;
367 src = nlp->list;
368 for (i=0;i < len; i++) {
369 data[i].lo = src[i].lo;
370 data[i].hi = src[i].hi;
371 }
372 return result;
373 }
374
375 /*
376 * find a list in GRN.shared which is big enough to hold need
377 * data. return -1 if none found.
378 */
379 static
380 int GetHead(int need)
381 {
382 int len,i;
383 len = GRN.shared_len;
384 i = 0;
385 while (i<len && GRN.shared[i].headfree < need) {
386 i++;
387 }
388 if (i == len) {
389 return -1;
390 }
391 return i;
392 }
393 /*
394 * if insufficient memory, this simply won't grow the GRN and
395 * the list won't get pooled for future use or referenced.
396 */
397 static
398 void AddToGRN(Numlist_p nlp, int cap)
399 {
400 struct shared_data *resize;
401 int newsize;
402 if (nlp==NULL) {
403 return;
404 }
405 if (GRN.shared_cap == GRN.shared_len) {
406 if (GRN.shared == NULL) { /*create*/
407 GRN.shared = (struct shared_data *)ascmalloc(INITSIZE_GRN*
408 sizeof(struct shared_data));
409 if (GRN.shared == NULL) {
410 return;
411 }
412 GRN.shared_cap = INITSIZE_GRN;
413 } else { /* grow */
414 newsize = (int)(GROW_GRN*(double)GRN.shared_cap) + GRN.shared_cap;
415 resize = (struct shared_data *)ascrealloc(GRN.shared,
416 newsize*sizeof(struct shared_data));
417 if (resize==NULL) {
418 return;
419 }
420 GRN.shared = resize;
421 }
422 }
423 GRN.shared[GRN.shared_len].headlist = nlp;
424 GRN.shared[GRN.shared_len].headcap = cap;
425 GRN.shared[GRN.shared_len++].headfree = cap - nlp->len;
426 nlp->refcount++;
427 }
428
429 /* return a singleton list */
430 Numlist_p NumpairElementary(int num)
431 {
432 struct numpair_list nl;
433 struct numpair np;
434
435 /* fake list not allocated, the use copy operator */
436 nl.len = 1;
437 nl.list = &np;
438 nl.head = NULL;
439 nl.refcount=0;
440 np.lo = np.hi = num;
441
442 return NumpairCopyList(&nl);
443 }
444
445 /*
446 * nlp2 = NumpairCopyList(nlp);
447 * Numlist_p nlp2, nlp;
448 * Returns an efficiently allocated numpair_list containing the
449 * data of the list given. The data in this list may or may not
450 * be in a shared allocation, depending on the list size.
451 */
452 Numlist_p NumpairCopyList(Numlist_p nlp)
453 {
454 Numlist_p head, result;
455 struct numpair *data, *src;
456 int len,i, cell,nextelt;
457 assert(nlp != NULL);
458
459 /* if oversized list. create, copy, return */
460 if (nlp->len >= SHRSIZE - MINFREE) {
461 return NumpairDuplicate(nlp,nlp->len);
462 }
463
464 /* list we'd like to copy by using data space at end of some other list.
465 * Get index of head with shareable data. if not available, make one and
466 * add it to puddle of shared lists.
467 */
468 cell = GetHead(nlp->len+1); /* we're putting in the checknum so 1 more */
469 if (cell != -1) {
470 len = nlp->len;
471 /* get elements needed from just after end of data in head */
472 head = GRN.shared[cell].headlist;
473 nextelt = GRN.shared[cell].headcap - GRN.shared[cell].headfree;
474 data = &(head->list[nextelt]);
475 /* deduct from remaining in cell */
476 GRN.shared[cell].headfree -= (len+1);
477 if (GRN.shared[cell].headfree < MINFREE) {
478 /* eliminate reference at shared[cell] and decrease list len. */
479 head->refcount--;
480 if (cell < GRN.shared_len-1) {
481 /* copy tail to replace cell, if cell isn't tail */
482 GRN.shared[cell] = GRN.shared[GRN.shared_len-1];
483 }
484 GRN.shared_len--;
485 if ( GRN.shared_len ==0) {
486 ascfree(GRN.shared);
487 GRN.shared = NULL;
488 GRN.shared_cap = 0;
489 }
490 }
491 result = NHMALLOC;
492 if (result == NULL) {
493 return NULL;
494 }
495 data[0].lo = NHCHECKNUM;
496 data[0].hi = NHCHECKNUM;
497 data++; /* skip past pad */
498 result->list = data;
499 result->head = head;
500 result->refcount = 1;
501 head->refcount++;
502 src = nlp->list;
503 for (i=0;i < len; i++) {
504 data[i].lo = src[i].lo;
505 data[i].hi = src[i].hi;
506 }
507 result->len = len;
508 result->cap = -1;
509 return result;
510 } else {
511 /* create list, copy data to it, add list to shared pool,
512 * and return resulting list.
513 */
514 result = NumpairDuplicate(nlp,SHRSIZE);
515 if (result != NULL) {
516 AddToGRN(result,SHRSIZE);
517 }
518 return result;
519 }
520 /* not reached */
521 }
522
523 /* third arg is a pair of long, not a pointer.
524 * assumes p.lo >= r[rlen-1].lo
525 */
526 static
527 int ExtendResult(struct numpair *r, CONST int rlen, CONST struct numpair p)
528 {
529 int idx;
530 if (rlen) {
531 idx = rlen - 1;
532 if (p.lo > r[idx].hi+1) {
533 /* add new disjoint element to r. len++ */
534 r[rlen].lo = p.lo;
535 r[rlen].hi = p.hi;
536 return rlen + 1;
537 }
538 /* extend range to p.hi if needed. no len change. */
539 if (p.hi > r[idx].hi) {
540 r[idx].hi = p.hi;
541 }
542 return rlen;
543 } else {
544 /* first ever element */
545 r[0].lo = p.lo;
546 r[0].hi = p.hi;
547 return 1;
548 }
549 }
550
551 /*
552 * err = NumpairMergeLists(list1,list2,result);
553 * struct numpair_list *list1, *list2, *result;
554 * The maximum needed size of result is list1->len+list2->len.
555 * The size of result is not checked and this will
556 * corrupt memory if result needed is larger than result given.
557 * Result must be expandable. list1,list2 need not be.
558 * Result is overwritten even if it already has nonzero length.
559 */
560 static
561 void NumpairMergeLists(Numlist_p nlp1, Numlist_p nlp2, Numlist_p nlpr)
562 {
563 int n1,len1, n2,len2,lenr; /* lengths of lists */
564 struct numpair *p1, *p2, *r; /* data from lists */
565
566 len1 = nlp1->len;
567 len2 = nlp2->len;
568 p1 = nlp1->list;
569 p2 = nlp2->list;
570 r = nlpr->list;
571 n1 = n2 = lenr = 0;
572
573 while (n1 < len1 && n2 < len2) {
574 /* copy all p1 entries starting before p2 entry */
575 while (n1 < len1 && p1[n1].lo <= p2[n2].lo) {
576 lenr = ExtendResult(r,lenr,p1[n1]);
577 n1++;
578 }
579 if (n1 == len1) {
580 break;
581 }
582 /* copy all p2 entries starting before p1 entry */
583 while (n2 < len2 && p2[n2].lo < p1[n1].lo) {
584 lenr = ExtendResult(r,lenr,p2[n2]);
585 n2++;
586 }
587 }
588 /* clean up leftovers. only one of the following while loops will go */
589 while (n1 < len1) {
590 lenr = ExtendResult(r,lenr,p1[n1]);
591 n1++;
592 }
593 while (n2 < len2) {
594 lenr = ExtendResult(r,lenr,p2[n2]);
595 n2++;
596 }
597 nlpr->len = lenr;
598 }
599
600
601 /*
602 * NumpairCalcUnion(enlp1,nlp2,enlp3);
603 * Numlist_p enlp1,nlp2,enlp3;
604 * Calculates the union of enlp1, nlp2 and leaves the result in
605 * enlp1. enlp3 is used if needed and is left in an indeterminate
606 * state.
607 */
608 void NumpairCalcUnion(Numlist_p enlp1, Numlist_p nlp2, Numlist_p enlp3)
609 {
610 Numlist_p t;
611 struct numpair *src, *data; /* data from lists */
612 int len, i;
613
614 assert(enlp1 != NULL);
615 assert(enlp3 != NULL);
616 assert(nlp2 != NULL);
617 assert(enlp1 != enlp3);
618
619 /* handle case of no previous data in enlp1 */
620 if (enlp1->len == 0) {
621 t = NumpairExpandableList(enlp1, nlp2->len);
622 if (t == NULL) { /* ack! */
623 return;
624 }
625 data = enlp1->list;
626 src = nlp2->list;
627 len = nlp2->len;
628 enlp1->len = len;
629 for (i=0;i < len; i++) {
630 data[i].lo = src[i].lo;
631 data[i].hi = src[i].hi;
632 }
633 return; /* simple case done */
634 }
635 /* make sure we have memory for worst case */
636 t = NumpairExpandableList(enlp3, enlp1->len + nlp2->len);
637 if (t==NULL) { /* ack! */
638 return;
639 }
640 NumpairMergeLists(enlp1, nlp2, enlp3);
641 t = NumpairExpandableList(enlp1, enlp3->len);
642 if (t==NULL) { /* ack! */
643 return;
644 }
645 /* copy back data to enlp1 */
646 data = enlp1->list;
647 src = enlp3->list;
648 len = enlp3->len;
649 enlp1->len = len;
650 for (i=0;i < len; i++) {
651 data[i].lo = src[i].lo;
652 data[i].hi = src[i].hi;
653 }
654 }
655
656 void NumpairCalcIntersection(Numlist_p nlp1, Numlist_p nlp2, Numlist_p enlp3)
657 {
658 struct numpair *s1, *s2, *r; /* data from lists */
659 struct numpair overlap;
660 int i, j, lenr;
661 int l1,l2;
662
663 assert(nlp1 != NULL);
664 assert(nlp2 != NULL);
665 assert(enlp3 != NULL);
666 assert(nlp1 != enlp3);
667 assert(nlp2 != enlp3);
668
669 l1 = nlp1->len;
670 l2 = nlp2->len;
671 s1 = nlp1->list;
672 s2 = nlp2->list;
673
674 NumpairClearList(enlp3);
675 /* skip the nobrainers */
676 if (!l1 ||
677 !l2 ||
678 s2[0].lo > s1[l1-1].hi ||
679 s1[0].lo > s2[l2-1].hi) {
680 return;
681 }
682 NumpairExpandableList(enlp3, l1 + l2);
683 if (s1==NULL) {
684 Asc_Panic(2,"Numlist_p enlp3 to be expanded. Insufficient memory.",
685 "NumpairCalcIntersection");
686 }
687 lenr = i = j = 0;
688 while (j < l2 && i < l1) {
689 /* could we test elsewhere for i,j and break? */
690 while (i < l1 && s1[i].hi < s2[j].lo) {
691 /* move i up to next j it might overlap */
692 i++;
693 }
694 if (i >= l1) {
695 /* ran out of data */
696 break;
697 }
698 while (j < l2 && s2[j].hi < s1[i].lo) {
699 /* move j up to next i it might overlap */
700 j++;
701 }
702 if (j >= l2) {
703 /* ran out of data */
704 break;
705 }
706 /* max lo1,lo2 */
707 overlap.lo = (s1[i].lo > s2[j].lo) ? s1[i].lo : s2[j].lo;
708 /* min hi1, hi2, and note which to move next, or both */
709 if (s1[i].hi < s2[j].hi) {
710 overlap.hi = s1[i].hi;
711 i++;
712 } else {
713 overlap.hi = s2[j].hi;
714 if (s1[i].hi == s2[j++].hi) {
715 /* hi1 == hi2, move both i j up */
716 i++;
717 }
718 }
719 if (overlap.hi >= overlap.lo) {
720 NumpairExpandableList(enlp3, enlp3->len + 1);
721 r = enlp3->list;
722 lenr = ExtendResult(r,lenr,overlap);
723 } /* else the search ahead switched tracks */
724 }
725 enlp3->len = lenr;
726 }
727
728 /*
729 * merges multiple lists efficiently and returns an
730 * efficient copy of the result.
731 */
732 Numlist_p NumpairCombineLists(struct gl_list_t *gl,
733 Numlist_p elp1, Numlist_p elp2)
734 {
735 unsigned long glen, next;
736 Numlist_p nlp1,nlp2, tmp, s1,t2;
737
738 assert(gl!=NULL);
739 assert(elp1!=NULL);
740 assert(elp2!=NULL);
741 assert(elp1!=elp2);
742 assert(elp1->cap >= 0);
743 assert(elp2->cap >= 0);
744
745 glen = gl_length(gl);
746 switch (glen) {
747 case 0:
748 return NULL;
749 case 1:
750 return NumpairCopyList((Numlist_p)gl_fetch(gl,1));
751 default:
752 break;
753 }
754 /* at least 2 lists */
755 nlp1 = (Numlist_p)gl_fetch(gl,1);
756 nlp2 = (Numlist_p)gl_fetch(gl,2);
757 s1 = elp1 = NumpairExpandableList(elp1, nlp1->len + nlp2->len);
758 if (s1==NULL) {
759 Asc_Panic(2,"Numlist_p s1 to be expanded. Insufficient memory.",
760 "NumpairCombineLists");
761 }
762 NumpairClearList(s1);
763 NumpairMergeLists(nlp1,nlp2,s1);
764 t2 = elp2;
765 next = 3;
766 /* on the first trip through the loop, elp2 is the target and elp1 source.
767 * then they are swapped.
768 * on the second trip through elp1 is the target, elp2 source.
769 * each trip through the loop also includes the next nlp.
770 * on loop exit, s1 is always points to the most recent target.
771 */
772 while (next <= glen) {
773 nlp1 = (Numlist_p)gl_fetch(gl,next);
774 t2 = NumpairExpandableList(t2, nlp1->len + s1->len);
775 if (t2==NULL) {
776 Asc_Panic(2,"Numlist_p t2 to be expanded. Insufficient memory.",
777 "NumpairCombineLists");
778 }
779 NumpairClearList(t2);
780 NumpairMergeLists(nlp1,s1,t2);
781 tmp = s1;
782 s1 = t2;
783 t2 = tmp;
784 next++;
785 }
786 return NumpairCopyList(s1);
787 }
788
789 /*
790 * We trust that no number difference is actually ever > INT_MAX.
791 * This is a loose comparator. One argument must be a singleton
792 * with lo =0 and hi the value. This is the key value we want
793 * to know is in the list or not.
794 * The other must be a normal element i..i or i..j,j>i.
795 * This is for use with bsearch.
796 */
797 static
798 int CmpNumpairs(CONST void *c1, CONST void *c2)
799 {
800 CONST struct numpair *n1, *n2;
801 assert(c1!=NULL);
802 assert(c2!=NULL);
803 n1 = (struct numpair *)c1;
804 n2 = (struct numpair *)c2;
805 if (n1->lo == 0) {
806 assert(n2->lo != 0);
807 /* n1 single, n2 range */
808 if (n1->hi < n2->lo) {
809 return -1;
810 }
811 if (n1->hi > n2->hi) {
812 return 1;
813 }
814 return 0; /* within range */
815 } else {
816 /* n1 range, n2 single */
817 assert(n2->lo == 0);
818 if (n2->hi < n1->lo) {
819 return 1;
820 }
821 if (n2->hi > n1->hi) {
822 return -1;
823 }
824 return 0; /* within range */
825 }
826 }
827
828 /* want to return -1 if num > n2, 1 if num <n2, 0 if in n2. */
829 static
830 int CmpIntToPair(int num, struct numpair *n2)
831 {
832 assert(n2->lo != 0);
833 /* n2 normal range */
834 if (num < n2->lo) {
835 return 1;
836 }
837 if (num > n2->hi) {
838 return -1;
839 }
840 return 0; /* within range */
841 }
842
843 /* add a number somewhere into the list (sorted order)
844 * list must be expandable.
845 */
846 void NumpairAppendList(Numlist_p enlp, int num)
847 {
848 Numlist_p nnlp;
849 struct numpair *data;
850 int comparison;
851 unsigned int lower,upper,search=0;
852
853 assert(enlp!=NULL);
854 assert(enlp->cap >=0);
855
856 /* expand list if potentially needed */
857 nnlp = NumpairExpandableList(enlp, enlp->len+1);
858 if (nnlp == NULL) {
859 Asc_Panic(2,"Numlist_p to be appended. Insufficient memory.",
860 "NumpairAppendList");
861 return; /* not reached */
862 }
863
864 data = enlp->list;
865
866 /* no data case */
867 if (enlp->len==0) {
868 data[0].lo = data[0].hi = num;
869 enlp->len = 1;
870 return;
871 }
872
873 /* boundary cases */
874 /* low */
875 if (num < data[0].lo) {
876 if (num+1 == data[0].lo) {
877 /* extend lower end */
878 data[0].lo = num;
879 return;
880 } else {
881 /* insert at 0 */
882 for (upper = enlp->len; upper > 0; upper--) {
883 data[upper].lo = data[upper-1].lo;
884 data[upper].hi = data[upper-1].hi;
885 }
886 data[0].lo = data[0].hi = num;
887 enlp->len++;
888 return;
889 }
890 }
891
892 upper = enlp->len - 1;
893
894 /* high */
895 if (num > data[upper].hi) {
896 if (num-1 == data[upper].hi) {
897 /* extend upper end */
898 data[upper].hi = num;
899 return;
900 } else {
901 /* append */
902 data[enlp->len].lo = data[enlp->len].hi = num;
903 enlp->len++;
904 return;
905 }
906 }
907 /* prepend and append eliminated */
908 /* num belongs on the interior of the list */
909 lower = 0;
910 while (lower <= upper) {
911 search = (lower + upper) >> 1; /* integer divide by two */
912 comparison = CmpIntToPair(num,&data[search]);
913 if (comparison == 0) {
914 /* nothing to do -- got it in the list already */
915 return;
916 }
917 if (comparison < 0) {
918 lower = search + 1;
919 } else {
920 upper = search - 1;
921 }
922 }
923 /* that we got here means num is not in list and that
924 * lower > upper. num goes between the two remaining
925 * elements somehow or on an end.
926 * So we have several cases to handle:
927 * We are inserting on or between L:num:H
928 * a) L.hi << num << H.lo --> insert element.
929 * b) L.hi +1 == num << H.lo --> update L.hi
930 * c) L.hi << num == H.lo -1 --> update H.lo
931 * d) L.hi +1 == num == H.lo -1 --> assign H.hi to L.hi, delete H, shift.
932 */
933 /* swap lower and upper so we can read the code. */
934 /* --> lower == upper-- */
935 search = upper;
936 upper = lower;
937 lower = search;
938 if (data[lower].hi+1 == num) {
939 /* b,d */
940 if (data[upper].lo - 1 != num) {
941 data[lower].hi = num; /*b*/
942 } else {
943 data[lower].hi = data[upper].hi; /* merge adjacent cells, d */
944 /* shift cells on right 1 to left */
945 search = (--(enlp->len));
946 for ( ; upper < search; upper++) {
947 data[upper].lo = data[upper+1].lo;
948 data[upper].hi = data[upper+1].hi;
949 }
950 }
951 return;
952 } else {
953 /* a,c */
954 if (data[upper].lo - 1 != num) {
955 /*a, insert element */
956 for (search = enlp->len; search > upper; search--) {
957 data[search].lo = data[search-1].lo;
958 data[search].hi = data[search-1].hi;
959 }
960 data[upper].lo = data[upper].hi = num;
961 enlp->len++;
962 } else {
963 data[upper].lo = num; /*c*/
964 }
965 return;
966 }
967 }
968
969 int NumpairListLen(Numlist_p nlp)
970 {
971 assert(nlp!=NULL);
972 return nlp->len;
973 }
974
975 void NumpairClearList(Numlist_p enlp)
976 {
977 assert(enlp != NULL);
978 assert(enlp->cap >= 0);
979 enlp->len = 0;
980 }
981
982 /*
983 * NumberInList(nlp,number);
984 * Returns 1 if number is in list and 0 if it is not.
985 */
986 int NumpairNumberInList(Numlist_p nlp, int num)
987 {
988 switch (nlp->len) {
989 case 0:
990 return 0;
991 case 1:
992 if (num < nlp->list[0].lo || num > nlp->list[0].hi) {
993 return 0;
994 } else {
995 return 1;
996 }
997 case 2:
998 if (num < nlp->list[0].lo || num > nlp->list[1].hi) {
999 return 0;
1000 }
1001 if (num <= nlp->list[0].hi || num >= nlp->list[1].lo) {
1002 return 1;
1003 } else {
1004 return 0;
1005 }
1006 case 3:
1007 if (num < nlp->list[0].lo || num > nlp->list[2].hi) {
1008 return 0;
1009 }
1010 /* num is now within combined range of the 3 elements */
1011 if (num <= nlp->list[0].hi || num >= nlp->list[2].lo) {
1012 /* num is in element 0 or 2 */
1013 return 1;
1014 }
1015 /* num is in element 1 or not in list. */
1016 if (num < nlp->list[1].lo || num > nlp->list[1].hi) {
1017 return 0;
1018 } else {
1019 return 1;
1020 }
1021 default: {
1022 struct numpair test;
1023 char *location; /* location of answer, but we only care if NULL or not */
1024 test.lo = 0;
1025 test.hi = num;
1026 location = bsearch(&test,nlp->list,nlp->len,sizeof(struct numpair),
1027 CmpNumpairs);
1028 return (location != NULL);
1029 }
1030 }
1031 }
1032
1033 /*
1034 * NumberInListHinted(nlp,number,hint);
1035 * Returns 1 if number is in list and 0 if it is not.
1036 */
1037 static
1038 int InListDecreasingHint(Numlist_p nlp, int num, int *hint)
1039 {
1040 int np;
1041 struct numpair *list;
1042
1043 np = *hint;
1044 assert(np < nlp->len);
1045 list = nlp->list;
1046 if (np < 0) {
1047 np = nlp->len - 1;
1048 }
1049 /* linear search left from np to 0 for a range with lo <= num */
1050 while (np > 0 && list[np].lo > num) {
1051 np--;
1052 }
1053 /* now we may have fallen off low-end of list. so do
1054 * complete check whether num is in the range list[np].
1055 */
1056 *hint = np;
1057 if (num < list[np].lo || num > list[np].hi) {
1058 return 0;
1059 } else {
1060 return 1;
1061 }
1062 }
1063
1064 /*
1065 * NumberInListHintedDecreasing(nlp,number,hint);
1066 * Returns 1 if number is in list at or to the left of
1067 * hint for lists bigger than 3. hint is ignored for
1068 * small lists. To initiate a series of searches, call
1069 * with *hint == -1.
1070 * Cost O(len) per call worst case, but O(1) if used
1071 * properly.
1072 * Note that if hint value is incorrect, this may lie.
1073 */
1074 int NumpairNumberInListHintedDecreasing(Numlist_p nlp, int num, int *hint)
1075 {
1076 assert(hint != NULL);
1077 switch (nlp->len) {
1078 case 0:
1079 return 0;
1080 case 1:
1081 if (num < nlp->list[0].lo || num > nlp->list[0].hi) {
1082 return 0;
1083 } else {
1084 return 1;
1085 }
1086 case 2:
1087 if (num < nlp->list[0].lo || num > nlp->list[1].hi) {
1088 return 0;
1089 }
1090 if (num <= nlp->list[0].hi || num >= nlp->list[1].lo) {
1091 return 1;
1092 } else {
1093 return 0;
1094 }
1095 case 3:
1096 if (num < nlp->list[0].lo || num > nlp->list[2].hi) {
1097 return 0;
1098 }
1099 /* num is now within combined range of the 3 elements */
1100 if (num <= nlp->list[0].hi || num >= nlp->list[2].lo) {
1101 /* num is in element 0 or 2 */
1102 return 1;
1103 }
1104 /* num is in element 1 or not in list. */
1105 if (num < nlp->list[1].lo || num > nlp->list[1].hi) {
1106 return 0;
1107 } else {
1108 return 1;
1109 }
1110 default:
1111 return InListDecreasingHint(nlp,num,hint);
1112 }
1113 }
1114
1115 /*
1116 * prev = NumpairPrevNumber(nlp,last,hint);
1117 * int *hint;
1118 * int last;
1119 * Returns the next lower number in the list preceding
1120 * last. If last is 0, returns highest
1121 * number in the list. *hint should be the output from the
1122 * last call to this function on nlp, or -1. This function lets
1123 * you write a list iteration. If last given is 0, hint ignored.
1124 * Remember that 0 is never really a valid list element.
1125 */
1126 int NumpairPrevNumber(Numlist_p nlp, int last, int *hint)
1127 {
1128 struct numpair test;
1129 char *location;
1130 if (last < 1) {
1131 *hint = nlp->len - 1;
1132 return nlp->list[*hint].hi;
1133 }
1134
1135 if (*hint < 0 || *hint >= nlp->len) {
1136 /* given hint is junk. */
1137 *hint = nlp->len - 1;
1138 }
1139 if (nlp->list[*hint].hi < last) {
1140 /* so-so hint type 1*/
1141 (*hint)++;
1142 if (*hint < nlp->len) {
1143 test.lo = 0;
1144 test.hi = last;
1145 location = bsearch(&test,&(nlp->list[*hint]),nlp->len - (*hint),
1146 sizeof(struct numpair), CmpNumpairs);
1147 if (location == NULL) {
1148 *hint = -1;
1149 return 0;
1150 }
1151 *hint = (((struct numpair *)location) - nlp->list);
1152 assert(*hint < nlp->len);
1153 } else {
1154 /* last wasn't in this list. user is an idiot */
1155 *hint = -1;
1156 return 0;
1157 }
1158 } else {
1159 if (nlp->list[*hint].lo > last) {
1160 /* so-so hint type 2*/
1161 (*hint)--;
1162 if (*hint > -1) {
1163 test.lo = 0;
1164 test.hi = last;
1165 location = bsearch(&test, nlp->list, (*hint)+1,
1166 sizeof(struct numpair), CmpNumpairs);
1167 if (location == NULL) {
1168 *hint = -1;
1169 return 0;
1170 }
1171 *hint = (((struct numpair *)location) - nlp->list);
1172 assert(*hint < nlp->len);
1173 } else {
1174 /* last wasn't in this list. user is an idiot */
1175 *hint = -1;
1176 return 0;
1177 }
1178 }
1179 }
1180 /* so at last * hint is on the element of list where last was found */
1181 if (nlp->list[*hint].lo < last) {
1182 return last - 1; /* hint stays same. in middle of range */
1183 }
1184 if (*hint > 0) {
1185 /* move to previous range */
1186 (*hint)--;
1187 return nlp->list[*hint].hi;
1188 } else {
1189 *hint = -1;
1190 return 0;
1191 }
1192 }
1193
1194 /*
1195 * prev = NumpairNextNumber(nlp,last,hint);
1196 * int *hint;
1197 * int last;
1198 * Returns the next higher number in the list following
1199 * last. If last is >= end of list, returns 0.
1200 * *hint should be the output from the
1201 * last call to this function on nlp, or 0. This function lets
1202 * you write a list iteration. If last 0, hint ignored.
1203 * Remember that 0 is never really a valid list element.
1204 */
1205 int NumpairNextNumber(Numlist_p nlp,int last,int *hint)
1206 {
1207 struct numpair test;
1208 char *location;
1209
1210 if (last < 1) {
1211 *hint = 0;
1212 return nlp->list[*hint].lo;
1213 }
1214
1215 if (*hint < 0 || *hint >= nlp->len) {
1216 /* given hint is junk. */
1217 *hint = 0;
1218 }
1219 if (nlp->list[*hint].lo > last) {
1220 /* so-so hint type 1*/
1221 (*hint)--;
1222 if (*hint > -1) {
1223 test.lo = 0;
1224 test.hi = last;
1225 location = bsearch(&test,nlp->list, *hint,
1226 sizeof(struct numpair), CmpNumpairs);
1227 if (location == NULL) {
1228 *hint = -1;
1229 return 0;
1230 }
1231 *hint = (((struct numpair *)location) - nlp->list);
1232 assert(*hint < nlp->len);
1233 } else {
1234 /* last wasn't in this list. user is an idiot */
1235 *hint = -1;
1236 return 0;
1237 }
1238 } else {
1239 if (nlp->list[*hint].hi < last) {
1240 /* so-so hint type 2*/
1241 (*hint)++;
1242 if (*hint >= nlp->len) {
1243 test.lo = 0;
1244 test.hi = last;
1245 location = bsearch(&test, &(nlp->list[*hint]), nlp->len - (*hint),
1246 sizeof(struct numpair), CmpNumpairs);
1247 if (location == NULL) {
1248 *hint = -1;
1249 return 0;
1250 }
1251 *hint = (((struct numpair *)location) - nlp->list);
1252 assert(*hint < nlp->len);
1253 } else {
1254 /* last wasn't in this list. user is an idiot */
1255 *hint = -1;
1256 return 0;
1257 }
1258 }
1259 }
1260 /* so at last * hint is on the element of list where last was found */
1261 if (nlp->list[*hint].hi > last) {
1262 return last + 1; /* hint stays same. in middle of range */
1263 }
1264 if (*hint < (nlp->len - 1)) {
1265 /* move to next range */
1266 (*hint)++;
1267 return nlp->list[*hint].lo;
1268 } else {
1269 *hint = -1;
1270 return 0;
1271 }
1272 }
1273
1274 void NumpairListIterate(Numlist_p nlp,NPLFunc func,void *userdata)
1275 {
1276 int r,i, rlen,ihi;
1277 if (nlp == NULL || func == NULL || nlp->len == 0) {
1278 return;
1279 }
1280 for (r = 0, rlen = nlp->len; r < rlen; r++) {
1281 for (i = nlp->list[r].lo, ihi = nlp->list[r].hi; i <= ihi; i++) {
1282 (*func)(i,userdata);
1283 }
1284 }
1285 }
1286
1287 /*
1288 * common = NumpairGTIntersection(nlp1,nlp2,lowlimit);
1289 * int lowlimit;
1290 * Returns the first number that is both common to nlp1, nlp2
1291 * and > lowlimit.
1292 * If no number > lowlimit is common, returns 0.
1293 * normally lowlimit should be common to both lists, but this
1294 * is not required.
1295 */
1296 int NumpairGTIntersection(Numlist_p nlp1, Numlist_p nlp2, int low)
1297 {
1298 int i,j; /* indices into the lists of nlp1, nlp2 */
1299 int l1,l2;
1300 struct numpair *s1,*s2;
1301 int change, ilo, ihi;
1302
1303 l1 = nlp1->len;
1304 l2 = nlp2->len;
1305 s1 = nlp1->list;
1306 s2 = nlp2->list;
1307 /* skip the nobrainers */
1308 if (!l1 || !l2 || low > s1[l1-1].hi || low > s2[l2-1].hi) {
1309 return 0;
1310 }
1311 /* find i nearest to low limit in list 1. this could be pivoted. */
1312 for ( i = 0; i < l1; i++) {
1313 if ( s1[i].hi > low) {
1314 /* found first entry containing a number > low */
1315 break;
1316 }
1317 }
1318
1319 /* find j nearest to low limit in list 2 */
1320 for ( j = 0; j < l2; j++) {
1321 if ( s2[j].hi > low) {
1322 /* found first entry containing a number > low */
1323 break;
1324 }
1325 }
1326
1327 change = 1;
1328 /* now find first overlapping ij pair of ranges */
1329 while (change) {
1330 change = 0;
1331 while ( j < l2 && i < l1 && s1[i].lo > s2[j].hi) {
1332 j++;
1333 change = 1;
1334 }
1335 while ( i < l1 && j < l2 && s2[j].lo > s1[i].hi) {
1336 i++;
1337 change = 1;
1338 }
1339 }
1340 if (i == l1 || j == l2) {
1341 /* no overlap */
1342 return 0;
1343 }
1344 ilo = (s1[i].lo > s2[j].lo) ? s1[i].lo : s2[j].lo;
1345 ihi = (s1[i].hi < s2[j].hi) ? s1[i].hi : s2[j].hi;
1346 assert(ihi >= ilo);
1347 if (ilo <= low) {
1348 ilo = low + 1;
1349 }
1350 if (ilo > ihi) {
1351 return 0;
1352 }
1353 return ilo;
1354 }
1355
1356 int NumpairIntersectionLTHinted(Numlist_p nlp1, int *hint1,
1357 Numlist_p nlp2, int *hint2,
1358 int high)
1359 {
1360 int i,j; /* indices into the lists of nlp1, nlp2 */
1361 int l1,l2;
1362 struct numpair *s1,*s2;
1363 int change, ilo, ihi;
1364
1365 l1 = nlp1->len;
1366 l2 = nlp2->len;
1367 s1 = nlp1->list;
1368 s2 = nlp2->list;
1369 if (high <= 0) {
1370 high = INT_MAX;
1371 }
1372 /* skip the nobrainers */
1373 if (!l1 || !l2 || high < s1[0].lo || high < s2[0].lo) {
1374 return 0;
1375 }
1376 /* find i nearest to high limit in list 1. this could be pivoted. */
1377 if (*hint1 >= 0) {
1378 i = *hint1;
1379 } else {
1380 i = l1 - 1;
1381 }
1382 for ( ; i >= 0; i--) {
1383 if ( s1[i].lo < high) {
1384 /* found first entry containing a number < high */
1385 break;
1386 }
1387 }
1388
1389 /* find j nearest to high limit in list 2 */
1390 if (*hint2 >= 0) {
1391 j = *hint2;
1392 } else {
1393 j = l2 - 1;
1394 }
1395 for ( ; j >= 0; j--) {
1396 if ( s2[j].lo < high) {
1397 /* found first entry containing a number < high */
1398 break;
1399 }
1400 }
1401
1402 change = 1;
1403 /* now find first overlapping ij pair of ranges */
1404 while (change) {
1405 change = 0;
1406 while ( j >= 0 && i >= 0 && s1[i].hi < s2[j].lo) {
1407 j--;
1408 change = 1;
1409 }
1410 while ( i >= 0 && j >= 0 && s2[j].hi < s1[i].lo) {
1411 i--;
1412 change = 1;
1413 }
1414 }
1415 if (i < 0 || j < 0) {
1416 /* no overlap */
1417 return 0;
1418 }
1419 /* compute overlap */
1420 ilo = (s1[i].lo > s2[j].lo) ? s1[i].lo : s2[j].lo; /* max .lo */
1421 ihi = (s1[i].hi < s2[j].hi) ? s1[i].hi : s2[j].hi; /* min .hi */
1422 assert(ihi >= ilo);
1423 if (ihi >= high) {
1424 ihi = high - 1;
1425 }
1426 if (ihi < ilo) {
1427 return 0;
1428 }
1429 *hint1 = i;
1430 *hint2 = j;
1431 return ihi;
1432 }
1433
1434 int NumpairCardinality(Numlist_p nlp)
1435 {
1436 int i,len,count;
1437 struct numpair *s;
1438 if (nlp == NULL || nlp->len == 0 || nlp->list == NULL) {
1439 return 0;
1440 }
1441 count = 0;
1442 len = nlp->len;
1443 s = nlp->list;
1444 for (i = 0 ; i < len; i++) {
1445 count += (s[i].hi - s[i].lo); /* to be complete, add 1 at each iteration */
1446 }
1447 /* since we didn't add 1 at each iteration, we can add len at the END
1448 * to save len-1 additions.
1449 */
1450 count += len;
1451 return count;
1452 }
1453
1454 void NumpairClearPuddle(void)
1455 {
1456 int len,i;
1457 len = GRN.shared_len;
1458 i = 0;
1459 for (i = 0; i < len ;i++) {
1460 NumpairDestroyList(GRN.shared[i].headlist);
1461 GRN.shared[i].headlist = NULL;
1462 }
1463 GRN.shared_len = 0;
1464 GRN.shared_cap = 0;
1465 if (GRN.shared != NULL) {
1466 ascfree(GRN.shared);
1467 GRN.shared = NULL;
1468 }
1469 #if NUMLISTUSESPOOL
1470 numlist_destroy_pool();
1471 #endif
1472 }
1473 /*
1474 * test the basic operations.
1475 */
1476 /*
1477 #ifdef NUMPAIRSELFTEST
1478 #define TESTITER 0
1479 #define TESTLT 0
1480 #define TESTGT 0
1481 #define TESTINT 1
1482 FILE *g_ascend_errors = stderr;
1483 int main()
1484 {
1485 Numlist_p p1,p2,p3,ep4,ep5,ep6,ep7,ep8,ep9, es1,es2, p10;
1486 struct gl_list_t *nlpgl;
1487 int last, hint, gt, h1, h2;
1488
1489 gl_init();
1490 gl_init_pool();
1491
1492 p1 = NumpairElementary(7);
1493 FPRINTF(stderr,"p1\n");
1494 NLPWrite(NULL,p1);
1495
1496 p2 = NumpairDuplicate(p1,10);
1497 FPRINTF(stderr,"p2\n");
1498 NLPWrite(NULL,p2);
1499
1500 p3 = NumpairCopyList(p2);
1501 FPRINTF(stderr,"p3\n");
1502 NLPWrite(NULL,p3);
1503
1504 ep4 = NumpairExpandableList(NULL,3);
1505 NumpairAppendList(ep4,5);
1506 FPRINTF(stderr,"ep4\n");
1507 NLPWrite(NULL,ep4);
1508 NumpairAppendList(ep4,9);
1509 FPRINTF(stderr,"ep4\n");
1510 NLPWrite(NULL,ep4);
1511 NumpairAppendList(ep4,6);
1512 FPRINTF(stderr,"ep4\n");
1513 NLPWrite(NULL,ep4);
1514
1515
1516 NumpairAppendList(ep4,4);
1517 FPRINTF(stderr,"ep4\n");
1518 NLPWrite(NULL,ep4);
1519 NumpairAppendList(ep4,10);
1520 FPRINTF(stderr,"ep4\n");
1521 NLPWrite(NULL,ep4);
1522 NumpairAppendList(ep4,14);
1523 FPRINTF(stderr,"ep4\n");
1524 NLPWrite(NULL,ep4);
1525 NumpairAppendList(ep4,17);
1526 FPRINTF(stderr,"ep4\n");
1527 NLPWrite(NULL,ep4);
1528 NumpairAppendList(ep4,23);
1529 FPRINTF(stderr,"ep4\n");
1530 NLPWrite(NULL,ep4);
1531
1532 ep5 = NumpairExpandableList(NULL,8);
1533 FPRINTF(stderr,"ep5\n");
1534 NLPWrite(NULL,ep5);
1535 NumpairMergeLists(p1,ep4,ep5);
1536 FPRINTF(stderr,"ep5\n");
1537 NLPWrite(NULL,ep5);
1538
1539 #if TESTITER
1540 /* test iteration *
1541 FPRINTF(stderr,"\nIteration tests\n");
1542 FPRINTF(stderr,"Prev\n");
1543 hint = 0;
1544 last = 0;
1545 while (hint != -1) {
1546 last = NumpairPrevNumber(ep5,last,&hint);
1547 FPRINTF(stderr,"prev - %d hint %d\n", last , hint );
1548 }
1549
1550 FPRINTF(stderr,"Next\n");
1551 hint = 0;
1552 last = 0;
1553 while (hint != -1) {
1554 last = NumpairNextNumber(ep5,last,&hint);
1555 FPRINTF(stderr,"next - %d hint %d\n", last , hint );
1556 }
1557 #endif
1558 ep6 = NumpairExpandableList(NULL,1);
1559 NumpairAppendList(ep6,18);
1560 NumpairAppendList(ep6,29);
1561 NumpairAppendList(ep6,44);
1562 ep7 = NumpairExpandableList(NULL,1);
1563 NumpairAppendList(ep7,28);
1564 NumpairAppendList(ep7,15);
1565 NumpairAppendList(ep7,3);
1566 ep8 = NumpairExpandableList(NULL,1);
1567 NumpairAppendList(ep8,27);
1568 NumpairAppendList(ep8,13);
1569 NumpairAppendList(ep8,1);
1570 ep9 = NumpairExpandableList(NULL,1);
1571 NumpairAppendList(ep9,72);
1572 NumpairAppendList(ep9,31);
1573 NumpairAppendList(ep9,24);
1574 nlpgl = gl_create(10);
1575 gl_append_ptr(nlpgl,ep4);
1576 gl_append_ptr(nlpgl,ep5);
1577 gl_append_ptr(nlpgl,ep6);
1578 gl_append_ptr(nlpgl,ep7);
1579 gl_append_ptr(nlpgl,ep8);
1580 gl_append_ptr(nlpgl,ep9);
1581
1582 es1 = NumpairExpandableList(NULL,5);
1583 es2 = NumpairExpandableList(NULL,5);
1584
1585 FPRINTF(stderr,"\n MERGE TESTS:\n");
1586 FPRINTF(stderr,"\nep4\n");
1587 NLPWrite(NULL,ep4);
1588
1589 FPRINTF(stderr,"\nep5\n");
1590 NLPWrite(NULL,ep5);
1591
1592 FPRINTF(stderr,"\nep6\n");
1593 NLPWrite(NULL,ep6);
1594
1595 FPRINTF(stderr,"\nep7\n");
1596 NLPWrite(NULL,ep7);
1597
1598 FPRINTF(stderr,"\nep8\n");
1599 NLPWrite(NULL,ep8);
1600
1601 FPRINTF(stderr,"\nep9\n");
1602 NLPWrite(NULL,ep9);
1603
1604 p10 = NumpairCombineLists(nlpgl,es1,es2);
1605
1606 FPRINTF(stderr,"\nes1\n");
1607 NLPWrite(NULL,es1);
1608
1609 FPRINTF(stderr,"\nes2\n");
1610 NLPWrite(NULL,es2);
1611
1612 FPRINTF(stderr,"\np10\n");
1613 NLPWrite(NULL,p10);
1614
1615 #if TESTLT
1616 FPRINTF(stderr,"LTIntersection Test ep5, es2\n");
1617 for (last = 46; last > 0; last--) {
1618 h1 = h2 = -1;
1619 gt = NumpairIntersectionLTHinted(ep5,&h1,es2,&h2,last);
1620 FPRINTF(stderr,"highlimit = %d, result = %d\n",last,gt);
1621 }
1622
1623 FPRINTF(stderr,"LTIntersection Test ep5, es2\n");
1624 h1 = h2 = -1;
1625 for (last = 0; last > 0 || h1 < 0; ) {
1626 gt = NumpairIntersectionLTHinted(ep5,&h1,es2,&h2,last);
1627 FPRINTF(stderr,"highlimit = %d, result = %d\n",last,gt);
1628 FPRINTF(stderr," h1 = %d, h2 = %d\n",h1,h2);
1629 last = gt;
1630 }
1631 #endif
1632 #if TESTGT
1633 FPRINTF(stderr,"GTIntersection Test ep5, es2\n");
1634 for (last = 0; last < 46; last++) {
1635 gt = NumpairGTIntersection(ep5,es2,last);
1636 FPRINTF(stderr,"lowlimit = %d, result = %d\n",last,gt);
1637 }
1638
1639 FPRINTF(stderr,"GTIntersection Test es2, ep5\n");
1640 for (last = 0; last < 46; last++) {
1641 gt = NumpairGTIntersection(es2,ep5,last);
1642 FPRINTF(stderr,"lowlimit = %d, result = %d\n",last,gt);
1643 }
1644
1645 FPRINTF(stderr,"GTIntersection Test ep5, ep5\n");
1646 for (last = 0; last < 26; last++) {
1647 gt = NumpairGTIntersection(ep5,ep5,last);
1648 FPRINTF(stderr,"lowlimit = %d, result = %d\n",last,gt);
1649 }
1650 #endif
1651 FPRINTF(stderr,"\nCalcIntersection Test ep8+29, es1\n");
1652 NumpairAppendList(ep8,29);
1653 FPRINTF(stderr,"ep8\n");
1654 NLPWrite(NULL,ep8);
1655 FPRINTF(stderr,"\nes1\n");
1656 NLPWrite(NULL,es1);
1657 NumpairClearList(ep5);
1658 NumpairCalcIntersection(ep8,es1,ep5);
1659 FPRINTF(stderr,"\nresult ep5:\n");
1660 NLPWrite(NULL,ep5);
1661 FPRINTF(stderr,"\nCalcIntersection Test es1, ep8+29\n");
1662 NumpairClearList(ep5);
1663 NumpairCalcIntersection(es1,ep8,ep5);
1664 FPRINTF(stderr,"\nresult ep5:\n");
1665 NLPWrite(NULL,ep5);
1666 NumpairClearList(ep4);
1667 NumpairClearList(ep5);
1668 NumpairClearList(ep6);
1669 for (h1 = 6; h1 <37; h1++) {
1670 NumpairAppendList(ep4,h1);
1671 }
1672 NumpairAppendList(ep4,45);
1673 NumpairAppendList(ep4,81);
1674 NumpairAppendList(ep4,82);
1675 for (h1 = 84; h1 <104; h1++) {
1676 NumpairAppendList(ep4,h1);
1677 }
1678 NumpairAppendList(ep5,34);
1679 NumpairAppendList(ep5,35);
1680 NumpairAppendList(ep5,52);
1681 NumpairAppendList(ep5,71);
1682 NumpairAppendList(ep5,97);
1683 NumpairAppendList(ep5,115);
1684 FPRINTF(stderr,"\nep4:\n");
1685 NLPWrite(NULL,ep4);
1686 FPRINTF(stderr,"\nep5:\n");
1687 NLPWrite(NULL,ep5);
1688 NumpairCalcIntersection(ep4,ep5,ep6);
1689 FPRINTF(stderr,"\nresult ep4 ^ ep5:\n");
1690 NLPWrite(NULL,ep6);
1691 NumpairCalcIntersection(ep5,ep4,ep6);
1692 FPRINTF(stderr,"\nresult ep5 ^ ep4:\n");
1693 NLPWrite(NULL,ep6);
1694
1695
1696 NumpairDestroyList(p1);
1697 NumpairDestroyList(p2);
1698 NumpairDestroyList(p3);
1699 NumpairDestroyList(ep4);
1700 NumpairDestroyList(ep5);
1701 NumpairDestroyList(ep6);
1702 NumpairDestroyList(ep7);
1703 NumpairDestroyList(ep8);
1704 NumpairDestroyList(ep9);
1705 NumpairDestroyList(p10);
1706 NumpairDestroyList(es1);
1707 NumpairDestroyList(es2);
1708
1709 NumpairClearPuddle();
1710 gl_destroy(nlpgl);
1711
1712 gl_emptyrecycler(); /* empty the reused list pool *
1713 gl_destroy_pool(); /* empty the reused list head pool *
1714
1715 exit(0);
1716 }
1717 *//*#endif*/

john.pye@anu.edu.au
ViewVC Help
Powered by ViewVC 1.1.22