/[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 782 - (show annotations) (download) (as text)
Tue Jul 25 02:09:12 2006 UTC (14 years, 4 months ago) by johnpye
File MIME type: text/x-csrc
File size: 43798 byte(s)
Radu Serban sent me a preview of the new version of IDA which has new header file layout.
This patch updates for the new layout.
Also couple of minor fixes for gcc warnings in numlist and library.cpp.
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