Wed, 9 Feb 1994 12:44:24 GMT

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) |

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.