generic queue packages

generic queue packages

[cis.ohio-state.edu!pacific.mps.ohio-state.edu!zaphod.mps.ohio-state.edu!h]

I have a few questions regarding Grady Booch's generic queue packages.

For my application, I plan on using package
Queue_Priority_Balking_Multiple_Unbounded_Managed_Iterator.  I need to know if
there is any problem using this package if my node is a variant record.

I also need to know if it is possible to prioritize my queue on more than one
field of my record (for example, a "time" field and an "event_type" field).



Toby McEvoy

Re: generic queue packages

[pa.dec.com!engage.pko.dec.com!nntpd.lkg.dec.com!nntpd2.cxo.dec.com!etre!w]

tmm@dayvd.dayton.saic.com wrote:
: I have a few questions regarding Grady Booch's generic queue packages.
: 
: For my application, I plan on using package
: Queue_Priority_Balking_Multiple_Unbounded_Managed_Iterator.  I need to know i
f
: there is any problem using this package if my node is a variant record.
: 
: I also need to know if it is possible to prioritize my queue on more than one
: field of my record (for example, a "time" field and an "event_type" field).
: 
: 
: 
: Toby McEvoy

Toby,
	I've used a variant of that particular package.  From "eye-balling"
that code and the package you mention above, there should be no problem.
Remember that a variant record will have the maximum size elements used when
allocating the memory for the elements in your queue.  Be aware that your
element allocation code should have a robust exception handler in case your
queue grows too large.
	The ability to prioritize the queue on multiple fields will depend on
how you've constructed the queue.  I'd recommend two indexes into an unordered
queue.  This way you can manipulate the index faster than the queue elements.

Aloha,
	Richard

Richard Wallace
Senior Software Engineer
Digital Equipment Corporation
301 Rockrimmon Blvd. South
CXO2-1/7A
Colorado Springs, CO 80919-2398
(719)548-2792
<wallace@cookie.enet.dec.com>

"The opinions expressed are my own, B.P. may not *quite* agree..."

Re: generic queue packages

[John Goodsen]

wallace@cookie.enet.dec.com (Richard Wallace) writes:

>Remember that a variant record will have the maximum size elements used when
>allocating the memory for the elements in your queue.  
>

Not true.  It is implementation dependent.  An implmentation
*may* choose to use run-time logic and allocate the proper
size based upon the variant.

Doesn't DEC Ada do just this ???

>Richard Wallace
>Senior Software Engineer
>Digital Equipment Corporation
>301 Rockrimmon Blvd. South
>CXO2-1/7A
>Colorado Springs, CO 80919-2398
>(719)548-2792
>


-- 
John Goodsen
Software Process & Environments
EVB Software Engineering
jgg@evb.com

Re: generic queue packages

[enterpoop.mit.edu!spool.mu.edu!howland.reston.ans.net!zaphod.mps.ohio-sta]

In article <1993Feb24.212641.8326@evb.com> jgg@evb.com (John Goodsen) writes:
>wallace@cookie.enet.dec.com (Richard Wallace) writes:
>
>>Remember that a variant record will have the maximum size elements used when
>>allocating the memory for the elements in your queue.  
>>
>
>Not true.  It is implementation dependent.  An implmentation
>*may* choose to use run-time logic and allocate the proper
>size based upon the variant.
>
>Doesn't DEC Ada do just this ???

Yes.

Regards,

Bill Lee

Re: generic queue packages

[Michael Feldman]

In article <1993Feb26.031650.3447@leeweyr.sccsi.com> bill@leeweyr.sccsi.com (Bill Lee) writes:
>In article <1993Feb24.212641.8326@evb.com> jgg@evb.com (John Goodsen) writes:
>>wallace@cookie.enet.dec.com (Richard Wallace) writes:
>>
>>>Remember that a variant record will have the maximum size elements used when
>>>allocating the memory for the elements in your queue.  
>>>
>>
>>Not true.  It is implementation dependent.  An implmentation
>>*may* choose to use run-time logic and allocate the proper
>>size based upon the variant.
>>
>>Doesn't DEC Ada do just this ???
>
>Yes.
>
So does much-maligned Meridian.

Folks, what we have here is a classical time-space tradeoff. You can't
have it both ways. Either allocate the space statically, for the
maximum size, or do it dynamically and re-allocate every time the
size changes. (Or allocate in blocks, which is a compromise between
the two.)

This is almost an FAQ. The most intelligent way to deal with variant
records is to make sure that the discriminant has a reasonable type.

TYPE Stupid (Length: Positive := 8) IS RECORD
  String_Part: String(1..Length);
END RECORD;

is a recipe for big trouble. Yet I see it a lot, and not just in old
textbooks. Surely the writer didn't REALLY mean that the string
might possibly be Positive'Last characters long, right? Basically
the writer was too lazy to define a subtype that revealed the realistic
maximum length - 64 maybe, 255, but surely not Positive'Last. That's
32767 even if Integer is 16 bits.

SUBTYPE Realistic IS Integer RANGE 1..64; -- for example
TYPE Smart (Length: Realistic := 8) IS RECORD
  String_Part: String(1..Length);
END RECORD;

will waste at most 64 characters' worth, whether the compiler chooses
static or dynamic allocation. That's a whole lot better than the
roughly 2 gigabytes you'd try to allocate for a record of the first
type, if the compiler used static allocation and Integer was 32 bits.
(TeleSoft and Verdix do this, for example.) So it's (more) portable.

Variant records are a GREAT way to test intelligent design decisions.
Don't blame bad ones on the language or the compiler, friends.

Mike Feldman
------------------------------------------------------------------------
Michael B. Feldman
co-chair, SIGAda Education Committee

Professor, Dept. of Electrical Engineering and Computer Science
School of Engineering and Applied Science
The George Washington University
Washington, DC 20052 USA
(202) 994-5253 (voice)
(202) 994-5296 (fax)
mfeldman@seas.gwu.edu (Internet)

"The most important thing is to be sincere, 
and once you've learned how to fake that, you've got it made." 
-- old show-business adage
------------------------------------------------------------------------

Re: generic queue packages

[Andrew Dunstan]

In article <1993Feb26.190255.24811@seas.gwu.edu>, mfeldman@seas.gwu.edu (Michael Feldman) writes:

[he dislikes]
|> TYPE Stupid (Length: Positive := 8) IS RECORD
|>   String_Part: String(1..Length);
|> END RECORD;
|> 
[he prefers]
|> 
|> SUBTYPE Realistic IS Integer RANGE 1..64; -- for example
|> TYPE Smart (Length: Realistic := 8) IS RECORD
|>   String_Part: String(1..Length);
|> END RECORD;
|> 
|> will waste at most 64 characters' worth, whether the compiler chooses
|> static or dynamic allocation. That's a whole lot better than the
|> roughly 2 gigabytes you'd try to allocate for a record of the first
|> type, if the compiler used static allocation and Integer was 32 bits.
|> (TeleSoft and Verdix do this, for example.) So it's (more) portable.
|> 
|> Variant records are a GREAT way to test intelligent design decisions.
|> Don't blame bad ones on the language or the compiler, friends.
|> 
|> Mike Feldman


A "realistic" maximum might still be quite large. Say we allow lines up
to 255 chrs. Storage of 100,000 lines of average length 10 will still 
waste megabytes of memory if a static allocation strategy is used by the 
compiler.

That is why I generally avoid this sort of use of variant records for
this sort of processing - if I want dynamic sizing I make it explicit
by doing it myself - that makes for portable code. It also means I
don't have to use arbitrary limits on the size of some structure.


-- 
#######################################################################
#  Andrew Dunstan (formerly of the) #   There's nothing good or bad   #
#  Department of Computer Science   #   but thinking makes it so.     #
#  University of Adelaide           #                                 #
#  South Australia                  #          - Shakespeare          #
#  net: andrewd@cs.adelaide.edu.au  #                                 #
#######################################################################

Re: generic queue packages

[Michael Feldman]

In article <1mp0h3INNp2u@huon.itd.adelaide.edu.au> andrewd@cs.adelaide.edu.au (Andrew Dunstan) writes:
>In article <1993Feb26.190255.24811@seas.gwu.edu>, mfeldman@seas.gwu.edu (Michael Feldman) writes:
>
>A "realistic" maximum might still be quite large. Say we allow lines up
>to 255 chrs. Storage of 100,000 lines of average length 10 will still 
>waste megabytes of memory if a static allocation strategy is used by the 
>compiler.

Indeed.
>
>That is why I generally avoid this sort of use of variant records for
>this sort of processing - if I want dynamic sizing I make it explicit
>by doing it myself - that makes for portable code. It also means I
>don't have to use arbitrary limits on the size of some structure.
>
I agree. The price we pay for having powerful structures - in our case
variant records with unconstrained array objects as fields - is that
we need to consider very carefully how to use them, if at all.

If the field in question is a string, using a C-style dynamically
allocated string, with the record containing a pointer thereto,
probably allows one better to control the storage allocation.
I'd probably carry a length field, though, instead of null-terminating
the string C-style, to avoid linear searching to find the length.

Is this what you had in mind, Andrew?

Mike Feldman

PS - it's really nice to discuss some technical issues for a change :-)