User Tools

Site Tools


Sidebar

GitHub

CoreLib

Sponsors

This website is sponsored by

Notes

This wiki uses icons from icons8.com licensed under CC BY-ND 3.0.

proposals:data:associativearray:start
Author T. Meissner
Last Update 02.11.2016
Related Proposals TBV2 - Associative arrays

Generic Dictionary (Associative Array)

This generic packages implements a generic dictionary (associative array). It uses dynamic memory allocations and deallocations to grow in size if more items are stored in it. The dictionary is implemented as a protected type and thus requires VHDL-200x.

Implemented methods are:

  • Clear
  • Del
  • Get
  • HasKey
  • Set
  • Count

Here is a VHDL interface definition:

package corelib_Dict is
  generic (
    type KEY_TYPE;
    type VALUE_TYPE;
    function to_hash(d : in KEY_TYPE; size : positive) return natural;
    INIT_SIZE : natural := 128
  );
  
  type PT_DICT is protected

    procedure Set (constant key : in KEY_TYPE; constant data : in VALUE_TYPE);
    procedure Get (constant key : in KEY_TYPE; data : out VALUE_TYPE);
    impure function Get (constant key : KEY_TYPE) return VALUE_TYPE;
    procedure Del (constant key : in KEY_TYPE);
    procedure Clear;
    impure function HasKey (constant key : KEY_TYPE) return boolean;
    impure function Count return natural;

  end protected PT_DICT;

end package corelib_Dict;

Linked Files

General Comments

  • Intended as first contribution for discussion. Basis for implementation could be the implementations realized in libvhdl (libvhdl dictionary) and Vunit (Vunit dictionary). T. Meissner 2016/09/05 17:57
  • I think the generic package should have an InitialSize parameter with an initial value. Patrick Lehmann 2016/09/06 07:26
    • What size should this parameter set? The max. number of keys the dictionary can contain? T. Meissner 2016/09/07 03:58
      • The number of free element positions after initialization. Many data structures support such an additional (constructor) parameter. So in case you expect 10,000 elements to be filled in right after init, you can set InitSize to 10,000 and spare multiple resize operations for e.g. resizes by 100 elements (⇒ 100 resize operations). Patrick Lehmann 2016/09/07 13:48
      • Added an INIT_SIZE parameter to set the initial number of slots in the dictionary T. Meissner - 07.10.2016
  • A dict should distinguish between Set (change a value) and Add (create new key-value-pair). Patrick Lehmann 2016/09/06 07:26
    • Why? In my implementations, Set adds a new key/value pair when the key doesn't exists in the dictionary. If the key exists, Set overwrites the value with the given new one. That's a behaviour like in the Python dictionary where d[key] = value sets (overwrites) dict[key] to value AFAIK T. Meissner 2016/09/08 08:39
  • How does the dict handle duplicates? Patrick Lehmann 2016/09/06 07:26
  • Most dictionaries, I know of, use Contains instead of HasXX (but it's common too). Patrick Lehmann 2016/09/06 07:26
    • I've tried to follow the interface of the interface of dictionary in the Python standard library. So the names are similar. T. Meissner 2016/09/08 03:42
  • Does Size represent the actual size or the data structure size? E.g. my proposed generic list distinguishes between Count (elements) and Size (data structure size). Patrick Lehmann 2016/09/06 07:26
    • Size means the number of key/value pairs stored in the dictionary. I see no real use of getting the size of the stored data structures, you already know that when using the generics to set key & data types. IMHO should the interface be simple instead having functions/procedures for every use case you can think of (So, more the VHDL way instead of the SV one ;)). We should concentrate on the most useful interface functions first. T. Meissner 2016/09/08 03:42
    • Changed the name of Size method into Count, as it sounds more logical because it returns the number of elements in the dictionary. Maybe we can add Size method later, but I don't see an easy way to get the size of each thinkable data structure the user may store (records for example) T. Meissner - 07.10.2016

Supporters

proposals/data/associativearray/start.txt · Last modified: 02.11.2016 22:44 by paebbels