Re: [sv-ec] linked list amortization

From: Gordon Vreugdenhil <gordonv_at_.....>
Date: Wed Sep 26 2007 - 08:41:11 PDT
By the way, as I noted in Mantis 1256, this entire "include" approach is
deeply flawed since the parameterized class source is included in
each include location.

So if you have:

package p;
    `include <list.vh>
    typedef List #(int) int_list;
endpackage

module m;
    `include <list.vh>

    p::int_list A;

    List #(int) B;

    initial A = B;   // illegal
endmodule


The "A = B" is illegal since there are two different List parameterized
classes -- one in p and one in m.  Therefore the specializations
are NOT compatible.

This is going to cause very surprising misbehavior in separate
compilation, etc.

As I suggested in 1256, we really should move "List" either into
package std or should create another std_containers package or
std_list package or similar.

Gord.

Arturo Salz wrote:
> Shalom,
> 
>  
> 
> For the definition of amortized cost, here’s a good online reference:
> 
> http://en.wikipedia.org/wiki/Dynamic_array#Geometric_expansion_and_amortized_cost
> 
>  
> 
> Next, take a look at the STL list documentation (from which SV’s 
> definition is likely derived), which uses almost identical language:
> 
> http://www.sgi.com/tech/stl/List.html
> 
>  
> 
> Perhaps it would be best to remove the “amortized” term to avoid confusion.
> 
>  
> 
>             Arturo
> 
>  
> 
> ------------------------------------------------------------------------
> 
> *From:* owner-sv-ec@eda.org [mailto:owner-sv-ec@eda.org] *On Behalf Of 
> *Bresticker, Shalom
> *Sent:* Tuesday, September 25, 2007 11:27 PM
> *To:* SV_EC List
> *Subject:* [sv-ec] linked list amortization
> 
>  
> 
> Hi,
> 
> In Annex H (Linked lists), the definition of 'list' in H.2 is:
> 
> *list:* A doubly linked list, where every element has a predecessor and 
> successor. A list is a sequence that supports
> both forward and backward traversal, as well as amortized constant time 
> insertion and removal of elements
> at the beginning, end, or middle.
> 
> What does 'amortized' mean here?
> 
> Am I the only one who is not going to understand this?
> 
> Thanks,
> Shalom
> 
>  
> 
> Shalom Bresticker
> Intel Jerusalem LAD DA
> +972 2 589-6852
> +972 54 721-1033
> 
> ---------------------------------------------------------------------
> 
> Intel Israel (74) Limited
> 
>  
> 
> This e-mail and any attachments may contain confidential material for
> 
> the sole use of the intended recipient(s). Any review or distribution
> 
> by others is strictly prohibited. If you are not the intended
> 
> recipient, please contact the sender and delete all copies.
> 
> 
> -- 
> This message has been scanned for viruses and
> dangerous content by *MailScanner* <http://www.mailscanner.info/>*, and is
> believed to be clean.
> -- 
> This message has been scanned for viruses and
> dangerous content by *MailScanner* <http://www.mailscanner.info/>, and is
> believed to be clean. *

-- 
--------------------------------------------------------------------
Gordon Vreugdenhil                                503-685-0808
Model Technology (Mentor Graphics)                gordonv@model.com


-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.
Received on Wed Sep 26 08:41:49 2007

This archive was generated by hypermail 2.1.8 : Wed Sep 26 2007 - 08:42:29 PDT