Pascal compiler and sets

ssimmons@convex.com (Steve Simmons)
Wed, 9 Feb 1994 12:44:24 GMT

          From comp.compilers
Related articles
Pascal compiler and sets dallison@bfsec.bt.co.uk (1994-02-08)
Re: Pascal compiler and sets davisdm@widget.msfc.nasa.gov (1994-02-08)
Re: Pascal compiler and sets mauney@adm.csc.ncsu.edu (1994-02-08)
Re: Pascal compiler and sets samiam@netcom.com (1994-02-09)
Pascal compiler and sets ssimmons@convex.com (1994-02-09)
Re: Pascal compiler and sets stenuit@axp05.acset.be (1994-02-10)
Re: Pascal compiler and sets wjw@eb.ele.tue.nl (1994-02-10)
Re: Pascal compiler and sets synaptx!thymus!daveg@uunet.UU.NET (Dave Gillespie) (1994-02-10)
| List of all articles for this month |
Newsgroups: comp.compilers
From: ssimmons@convex.com (Steve Simmons)
Keywords: Pascal
Organization: CONVEX News Network, Engineering (cnn.eng), Richardson, Tx USA
References: 94-02-051
Date: Wed, 9 Feb 1994 12:44:24 GMT

> How are sets usually implemented in Pascal? Is there a small limit placed
> on the size of sets? I can think of a number of implementation methods,
> but would like to see how it is normally done so that I dont have to do
> much more work.


First, there is no standard implementation of sets in Pascal and so
they can be implemented either as Bit Vectors or Linked Lists.


The maximum size of a set is dependent upon its definition; however,
it can be statically computed. Therefore, it is usually best to implement
them as bit vectors because the following four set operations must
be performed (UNION, INTERSECTION, DIFFERENCE, and IN).


For example, the implementation would appear as the following if you
have a RISC machine of 32 bit words and a set of 50 items....


UNION SET3 = SET1+SET2


                LD SET1, R1
                LD SET2, R2
                BITOR R1, R2, R3
                ST R3, SET3
                LD SET1+4, R1
                LD SET2+4, R2
                BITOR R1, R2, R3
                ST R3, SET3+4


INTERSECTION SET3 = SET1*SET2


                LD SET1, R1
                LD SET2, R2
                BITAND R1, R2, R3
                ST R3, SET3
                LD SET1+4, R1
                LD SET2+4, R2
                BITAND R1, R2, R3
                ST R3, SET3+4




DIFFERENCE SET3 = SET1-SET2


                LD SET1, R1
                LD SET2, R2
                BITCMP R2 ; 1's complement
                BITAND R1, R2, R3
                ST R3, SET3
                LD SET1+4, R1
                LD SET2+4, R2
                BITCMP R2 ; 1's complement
                BITAND R1, R2, R3
                ST R3, SET3+4






IN X IN SET1


              LD XPOS, R1 // A value of 1-50
              DIV R1, 32, R2 // This can be a bit shift of 5
              MOD R1, 32, R3 // This can be a bit mask of the lower 5.
              ADD SET1, R2
              LD (R2), R4
              SHIFT 1, R3, R5
              BITAND R5, R4, R6
              BRANCH IF ZERO




              If X's position is know at compilation time, then this can be
              constant folded.


Thank you.


Steve Simmons
--

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.