OpenCores
URL https://opencores.org/ocsvn/thor/thor/trunk

Subversion Repositories thor

[/] [thor/] [trunk/] [FT64v5/] [software/] [CC64/] [source/] [Set.cpp] - Blame information for rev 48

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 48 robfinch 
#include <stdio.h>
2 
#include <ctype.h>
3 
#include <signal.h>
4 
#include <stdlib.h>
5 
#include <string.h>
6 
#include "stdafx.h"
7 
#include "set.h"
8 
 
9 
/* -------------------------------------------------------------------
10 
        Code for set routines.
11 
------------------------------------------------------------------- */
12 
 
13 
#ifndef min
14 
#define min(a,b)        (((a) < (b)) ? (a) : (b))
15 
#define max(a,b)        (((a) > (b)) ? (a) : (b))
16 
#endif
17 
 
18 
 
19 
void CSet::allocBitStorage()
20 
{
21 
        if (size <= SET_DEFAULT_SIZE)
22 
        {
23 
                size = SET_DEFAULT_SIZE;
24 
                map = dmap;
25 
        }
26 
        else {
27 
                map = (unsigned int *)allocx(sizeof(unsigned int)*size);
28 
//              map = new unsigned int[size];
29 
        }
30 
 
31 
}
32 
 
33 
 
34 
void CSet::copy(const CSet &s)
35 
{
36 
//      if (map != dmap)        // get rid of an old map
37 
//              delete[] map;
38 
        compl = s.compl;
39 
        size = s.size;
40 
        nbits = s.nbits;
41 
        MemberPtr = s.MemberPtr;
42 
 
43 
        // Either assign default map or allocate memory.
44 
        allocBitStorage();
45 
        memcpy(map, s.map, s.size * sizeof(int));
46 
}
47 
 
48 
 
49 
// Assignment (copy) operator
50 
// --------------------------
51 
CSet& CSet::operator=(CSet &s)
52 
{
53 
        if (map != dmap)
54 
                delete[] map;
55 
        compl = s.compl;
56 
        size = s.size;
57 
        nbits = s.nbits;
58 
        MemberPtr = s.MemberPtr;
59 
 
60 
        // Either assign default map or allocate memory.
61 
        allocBitStorage();
62 
        memcpy(map, s.map, s.size * sizeof(int));
63 
        return *this;
64 
}
65 
 
66 
 
67 
// Union of two sets.
68 
// ------------------
69 
CSet CSet::operator|(CSet s)
70 
{
71 
        CSet o;
72 
        int ii, NumWords;
73 
 
74 
        // Set the size of the bitmap to the greater of the two sizes.
75 
        if (size >= s.size)
76 
        {
77 
                o.size = size;
78 
                o.nbits = nbits;
79 
        }
80 
        else
81 
        {
82 
                o.size = s.size;
83 
                o.nbits = s.nbits;
84 
        }
85 
        o.allocBitStorage();
86 
 
87 
        NumWords = min(size, s.size);
88 
        // Set bits in output according to union of two sets.
89 
        for (ii = NumWords - 1; ii >= 0; ii--)
90 
                o.map[ii] = map[ii] | s.map[ii];
91 
        // Copy remaining words to output bitset
92 
        if (s.size > size)
93 
                memcpy(&o.map[size], &s.map[size],
94 
            (s.size - size) * sizeof(int));
95 
        else
96 
                memcpy(&o.map[s.size], &map[s.size],
97 
            (size - s.size) * sizeof(int));
98 
        return o;
99 
}
100 
 
101 
 
102 
// Union to same set.
103 
// ------------------
104 
CSet& CSet::operator|=(CSet s)
105 
{
106 
        int ii;
107 
 
108 
        // Set the size of the bitmap to the greater of the two sizes.
109 
        if (size < s.size)
110 
                enlarge(s.size);
111 
        for (ii = min(size,s.size) -1 ; ii >= 0; ii--)
112 
                map[ii] |= s.map[ii];
113 
        return *this;
114 
}
115 
 
116 
 
117 
void CSet::add(CSet &s)
118 
{
119 
        int ii;
120 
 
121 
        // Set the size of the bitmap to the greater of the two sizes.
122 
        if (size < s.size)
123 
                enlarge(s.size);
124 
        for (ii = min(size,s.size) - 1; ii >= 0; ii--)
125 
                map[ii] |= s.map[ii];
126 
}
127 
 
128 
 
129 
void CSet::add(CSet *s)
130 
{
131 
        int ii;
132 
 
133 
        if (s == nullptr)
134 
                return;
135 
 
136 
        // Set the size of the bitmap to the greater of the two sizes.
137 
        if (size < s->size)
138 
                enlarge(s->size);
139 
        for (ii = min(size,s->size) - 1; ii >= 0; ii--)
140 
                map[ii] |= s->map[ii];
141 
}
142 
 
143 
 
144 
/*      -------------------------------------------------------------------
145 
                Intersection of two sets. If the two sets are not the same
146 
    size then smaller set is used as the size of the output.
147 
-------------------------------------------------------------------- */
148 
 
149 
CSet CSet::operator&(CSet s)
150 
{
151 
        CSet o;
152 
        int ii;
153 
 
154 
        // Set the size of the bitmap to the smaller of the two sizes.
155 
        if (size <= s.size)
156 
        {
157 
                o.size = size;
158 
                o.nbits = nbits;
159 
        }
160 
        else
161 
        {
162 
                o.size = s.size;
163 
                o.nbits = s.nbits;
164 
        }
165 
 
166 
        o.allocBitStorage();
167 
 
168 
        // Set bits in output according to union of two sets.
169 
        for (ii = o.size - 1; ii >= 0; ii--)
170 
                o.map[ii] = map[ii] & s.map[ii];
171 
        return o;
172 
}
173 
 
174 
 
175 
/* --------------------------------------------------------------------
176 
        Intersection to same set.
177 
-------------------------------------------------------------------- */
178 
 
179 
CSet& CSet::operator&=(CSet s)
180 
{
181 
        int ii;
182 
 
183 
        // Set the size of the bitmap to the smaller of the two sizes.
184 
        if (size > s.size)
185 
        {
186 
                memset(&map[size], 0, (size - s.size)*sizeof(int));
187 
                size = s.size;
188 
                nbits = s.nbits;
189 
        }
190 
 
191 
        for (ii = size - 1; ii >= 0; ii--)
192 
                map[ii] &= s.map[ii];
193 
        return *this;
194 
}
195 
 
196 
 
197 
/* --------------------------------------------------------------------
198 
        Enlarge set to 'n'. Enlarge works in chunk sizes.
199 
-------------------------------------------------------------------- */
200 
 
201 
void CSet::enlarge(int n)
202 
{
203 
        unsigned int *p;
204 
 
205 
        if (n < size)
206 
                return;
207 
        n = (n + 4) & ~3;
208 
        //p = new unsigned int[n];
209 
        p = (unsigned int *)allocx(sizeof(int) * n);
210 
        if (p == NULL)
211 
        {
212 
                fprintf(stderr, "Can't get memory to expand set.\n");
213 
                exit(1);
214 
        }
215 
        memcpy(p, map, size * sizeof(int));
216 
        if (memcmp(p,map,size*sizeof(int)) != 0)
217 
                printf("Set.cpp enlarge error");
218 
//      memset(p+size, 0, (n-size) * sizeof(int)); <- allocx zeros memory
219 
//      if (map != dmap)
220 
//              delete[] map;
221 
        map = p;
222 
        size = n;
223 
        nbits = n * sizeof(int) << 3;
224 
}
225 
 
226 
 
227 
/*  Create a new set which contains all members of a set plus a new
228 
    member.
229 
                (s =) s1 + 100;
230 
*/
231 
CSet CSet::operator+(int bit)
232 
{
233 
        CSet s = *this;
234 
 
235 
        if (bit > s.nbits)
236 
                s.enlarge((bit >> SET_NBIT) + 8);
237 
        s.map[bit >> SET_NBIT] |= (1 << (bit & SET_BMASK));
238 
        return s;
239 
}
240 
 
241 
 
242 
/* Create a new set which contains all members of a set except member.
243 
                (s =) s1 - 100;
244 
*/
245 
CSet CSet::operator-(int bit)
246 
{
247 
        CSet s = *this;
248 
 
249 
        if (bit < s.nbits)
250 
                s.map[bit >> SET_NBIT] &= ~(1 << (bit & SET_BMASK));
251 
        return s;
252 
}
253 
 
254 
 
255 
/* Figure out the (symettric)difference between two sets.
256 
*/
257 
CSet CSet::operator-(CSet s)
258 
{
259 
        CSet o;
260 
        int ii;
261 
 
262 
        o.size = max(size, s.size);
263 
        o.nbits = max(nbits, s.nbits);
264 
        o.allocBitStorage();
265 
 
266 
        // Set difference of elements common in both sets.
267 
        for (ii = min(size, s.size); --ii >= 0;)
268 
                o.map[ii] = map[ii] ^ s.map[ii];
269 
        // Set remaining elements equal to elements remaining in larger set.
270 
        if (size < s.size)
271 
                for (ii = s.size; --ii >= size;)
272 
                        o.map[ii] = s.map[ii];
273 
        else if (size > s.size)
274 
                for (ii = size; --ii >= s.size;)
275 
                o.map[ii] = map[ii];
276 
        return o;
277 
}
278 
 
279 
 
280 
// Flip all bits in set.
281 
CSet CSet::operator!()
282 
{
283 
        int ii;
284 
        CSet o;
285 
 
286 
        o = *this;
287 
        for (ii = size; --ii >= 0;)
288 
                o.map[ii] = ~map[ii];
289 
        return o;
290 
}
291 
 
292 
/*
293 
CSet &CSet::operator!()
294 
{
295 
        int ii;
296 
 
297 
        for (ii = size; --ii >= 0;)
298 
                map[ii] = ~map[ii];
299 
        return *this;
300 
}
301 
*/
302 
 
303 
/* --------------------------------------------------------------------
304 
   Get the number of elements in the set.
305 
-------------------------------------------------------------------- */
306 
 
307 
int CSet::NumMember() const
308 
{
309 
        // Stores the number of set bits in each value 0-255
310 
        static unsigned char numbits[] =
311 
        {
312 
                0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
313 
                1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
314 
                1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
315 
                2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
316 
                1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
317 
                2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
318 
                2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
319 
                3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
320 
                1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
321 
                2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
322 
                2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
323 
                3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
324 
                2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
325 
                3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
326 
                3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
327 
                4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
328 
        };
329 
 
330 
        int tot = 0, ii;
331 
        unsigned __int8 *pm = (unsigned __int8 *)map;
332 
 
333 
        for (ii = size * sizeof(int); --ii >= 0;)
334 
                tot += numbits[pm[ii]];
335 
        return (tot);
336 
}
337 
 
338 
 
339 
inline void CSet::clear()   // Zero all bits
340 
    { memset((char *)map, 0, size * sizeof(int)); };
341 
inline void CSet::fill()    // Set all bits
342 
    { memset((char *)map, ~0, size * sizeof(int)); };
343 
inline void CSet::complement() { compl = ~compl; };
344 
 
345 
/* --------------------------------------------------------------------
346 
        Remove member - clears bit in map
347 
-------------------------------------------------------------------- */
348 
 
349 
void CSet::remove(int x)
350 
{
351 
   if (x < nbits)
352 
      map[x >> SET_NBIT] &= ~(1 << (x & SET_BMASK));
353 
}
354 
 
355 
 
356 
/* --------------------------------------------------------------------
357 
        Determines if set is a subset of another.
358 
-------------------------------------------------------------------- */
359 
 
360 
int CSet::subset(CSet &poss) const
361 
{
362 
        unsigned int *subsetp, *setp;
363 
        int common, tail;
364 
 
365 
        if(poss.size > size)
366 
        {
367 
                common = size;
368 
                tail = poss.size - size;
369 
        }
370 
        else
371 
        {
372 
                common = poss.size;
373 
                tail = 0;
374 
        }
375 
        subsetp = poss.map;
376 
        setp = map;
377 
 
378 
        for (; --common >= 0; subsetp++, setp++)
379 
                if ((*subsetp & *setp) != *subsetp)
380 
                        return 0;
381 
        while(--tail >= 0)
382 
                if (*subsetp++)
383 
                        return 0;
384 
        return 1;
385 
}
386 
 
387 
 
388 
/* --------------------------------------------------------------------
389 
        Set set back to default size and clear.
390 
-------------------------------------------------------------------- */
391 
 
392 
void CSet::truncate()
393 
{
394 
        if (map != dmap)
395 
        {
396 
                delete[] map;
397 
                map = dmap;
398 
        }
399 
        size = SET_DEFAULT_SIZE;
400 
        nbits = SET_DEFAULT_SIZE * sizeof(int) * 8;
401 
        memset(dmap, 0, size * sizeof(int));
402 
}
403 
 
404 
 
405 
/* --------------------------------------------------------------------
406 
        Hash the set.
407 
-------------------------------------------------------------------- */
408 
 
409 
unsigned CSet::hash() const
410 
{
411 
        unsigned int *p;
412 
        unsigned total;
413 
        int j;
414 
 
415 
        total = 0;
416 
        j = size;
417 
        p = map;
418 
 
419 
        while(--j >= 0)
420 
                total += *p++;
421 
 
422 
        return total;
423 
}
424 
 
425 
 
426 
/* --------------------------------------------------------------------
427 
                Print the contents of a set bitmap.
428 
-------------------------------------------------------------------- */
429 
 
430 
int CSet::print(int (*OutRout)(void *a, ...), void *param)
431 
{
432 
        int i,DidSomething = 0;
433 
 
434 
        resetPtr();
435 
        while((i = nextMember()) >= 0)
436 
        {
437 
                DidSomething++;
438 
                (*OutRout)(param, "%d", i);
439 
        }
440 
        resetPtr();
441 
        if (!DidSomething)
442 
                (*OutRout)(param, "empty", -2);
443 
        return (DidSomething);
444 
}
445 
 
446 
 
447 
/* --------------------------------------------------------------------
448 
        Description :
449 
                Print the contents of a set bitmap to a string. A maximum of
450 
    bufsz characters will be printed to the buffer. If there are
451 
    more data than will fit in the buffer then "..." is put at the
452 
    end of the list.
453 
-------------------------------------------------------------------- */
454 
 
455 
int CSet::sprint(char *buf, int bufsz)
456 
{
457 
        int i;
458 
        int nn;
459 
 
460 
        resetPtr();
461 
        nn = sprintf_s(buf, bufsz, "{ ");
462 
        while((i = nextMember()) >= 0)
463 
        {
464 
                _itoa_s(i, &buf[nn], bufsz-nn, 10);
465 
                while(buf[nn]) ++nn;
466 
                buf[nn] = ' ';  nn++;
467 
                if (nn > bufsz - 12)
468 
                {
469 
                        strcpy_s(&buf[nn], bufsz-nn,"...");
470 
                        nn += 3;
471 
                        break;
472 
                }
473 
        }
474 
        buf[nn] = '}';  nn++;
475 
        buf[nn] = '\0';
476 
        resetPtr();
477 
        return (nn);
478 
}
479 
 
480 
 
481 
/* --------------------------------------------------------------------
482 
        Comparison function.
483 
                returns
484 
 
485 
         1 if a > b
486 
             -1 if a < b
487 
 
488 
                The first set containing a bit not in the other set is
489 
    considered to be larger.
490 
-------------------------------------------------------------------- */
491 
 
492 
int CSet::cmp(CSet& s) const
493 
{
494 
        int j;
495 
        unsigned int *m1, *m2;
496 
 
497 
        j = min(size, s.size);
498 
 
499 
        for (m1 = map, m2 = s.map; --j >= 0; m1++, m2++)
500 
                if (*m1 != *m2)
501 
                        return (*m1 - *m2);
502 
        // If all words in both sets are the same then check the tail of
503 
    // the larger set and make sure all elements are not set.
504 
        if (size == s.size)
505 
                return 0;
506 
        if (size > s.size)
507 
        {
508 
                for (j = size - s.size; --j >= 0;)
509 
                        if (*m1++)
510 
                                return 1;
511 
        }
512 
        else
513 
        {
514 
                for (j = s.size - size; --j >= 0;)
515 
                        if (*m2++)
516 
                        return -1;
517 
        }
518 
        return 0;
519 
}
520 
 
521 
 
522 
/* --------------------------------------------------------------------
523 
                Get the next member in the set.
524 
-------------------------------------------------------------------- */
525 
 
526 
int CSet::nextMember()
527 
{
528 
        while(MemberPtr < nbits)
529 
        {
530 
                if (test(MemberPtr))
531 
                {
532 
                        MemberPtr++;
533 
                        return (MemberPtr-1);
534 
                }
535 
                MemberPtr++;
536 
        }
537 
        return (-1);
538 
}
539 
 
540 
int CSet::prevMember()
541 
{
542 
        while(MemberPtr > 0)
543 
        {
544 
                if (test(MemberPtr-1))
545 
                {
546 
                        MemberPtr--;
547 
                        return (MemberPtr);
548 
                }
549 
                MemberPtr--;
550 
        }
551 
        return (-1);
552 
}
553 
 
554 
int CSet::lastMember()
555 
{
556 
        int nn = nbits-1;
557 
        while(!test(nn) && nn > 0) nn--;
558 
        return(nn);
559 
}
560 
 
561 
int CSet::Member(int n)
562 
{
563 
        resetPtr();
564 
        while(MemberPtr < nbits && n > -1)
565 
        {
566 
                if (test(MemberPtr))
567 
                {
568 
                        n--;
569 
                        MemberPtr++;
570 
                        if (n < 0)
571 
                        return (MemberPtr-1);
572 
                }
573 
                MemberPtr++;
574 
        }
575 
        return (-1);
576 
}
577 
 
578 
 
579 
/* --------------------------------------------------------------------
580 
-------------------------------------------------------------------- */
581 
 
582 
int CSet::SetTest(CSet &s)
583 
{
584 
        int i, rval = SET_EQUIV;
585 
        unsigned int *p1, *p2;
586 
 
587 
        i = max(size, s.size);
588 
 
589 
        // Make the sets the same size.
590 
        if (s.size > size)
591 
                enlarge(i);
592 
        else if (s.size < size)
593 
                s.enlarge(i);
594 
 
595 
        p1 = map;
596 
        p2 = s.map;
597 
 
598 
        for (; --i >=0; p1++, p2++)
599 
        {
600 
                if (*p1 != *p2)
601 
                {
602 
                        if (*p1 & *p2)
603 
                                return (SET_INTER);
604 
                        rval = SET_DISJ;
605 
                }
606 
                else if (*p1 != 0)
607 
                        if (rval==SET_DISJ)
608 
                                rval = SET_INTER;
609 
        }
610 
        return (rval);
611 
}
612 
 
613 
int CSet::isSubset(CSet &s)
614 
{
615 
        int i;
616 
        unsigned int *p1, *p2;
617 
 
618 
        if (s.size > size)
619 
                return (false);
620 
        p1 = map;
621 
        p2 = s.map;
622 
        for (i = s.size; --i >= 0; p1++, p2++) {
623 
                if ((*p1 & *p2) != *p2)
624 
                        return (false);
625 
        }
626 
        return (true);
627 
}
628 
 
629 
/*
630 
void CSet::Serialize(CArchive& ar)
631 
{
632 
        int nn;
633 
 
634 
        if (ar.IsStoring()) {
635 
                ar << MemberPtr;
636 
                ar << nbits;
637 
                ar << size;
638 
                ar << compl;
639 
                for (nn = 0; nn < size; nn++)
640 
                        ar << map[nn];
641 
        }
642 
        else {
643 
                ar >> MemberPtr;
644 
                ar >> nbits;
645 
                ar >> size;
646 
                ar >> compl;
647 
                enlarge(size);
648 
                for (nn = 0; nn < size; nn++)
649 
                        ar >> map[nn];
650 
        }
651 
}
652 
*/

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.