Associative arrays in system verilog

11 Mar 2022

4 mins

Associative arrays are an extension of dynamic arrays which provide more flexibility in the way in which data can be stored. In associative arrays, the index can be of any data type including strings which makes it very beneficial for certain scenarios. Let's see associative arrays in detail.

What is Associative Array?

Associative arrays are a special type of dynamic arrays in which the memory is not allocated immediately when the array is declared. Instead, the memory is allocated as and when data is stored in the array. As the memory is not allocated immediately thus the allocated memory is not continuous in nature, which makes it slower than dynamic arrays.

This can be compared to key:value pairs in other language. The index can be used as a key to get the value stored. The index can be referred as a key to get the value stored.

Also, the data type of key should not necessarily be a int, but it can be any data type including string or real as well.

Syntax

The declaration of associative array is like that of the dynamic array. Only difference is that while declaring the associative array we need to define the data type of the key in the square brackets.

[value datatype] [arr_name] [index datatype];

// Examples
int arr [string]; // associative array with key as a string and value as integer
string arr2 [int]; // associative array with key as a int and value as string

Example Use Case

Let's assume that we want an array to save the total number of cars for a particular brand in an array. It can be simply done using a dynamic array where each index indicated the number of cars of a particular brand. Only problem in this way of storing is that we must know which index relates to which brand.

Instead, a better approach would be to store it in an associative array. In this instead of index, we use the brand name as the key and store the number of cars associated with the brand as the value.

module associative_array();
    int num_cars[string];

    initial begin
        num_cars = '{"hyndai":2, "suzuki":1, "tata": 3};

        $display("Number of cars = %p", num_cars);
        $display("Number of cars for Suzuki is = %0d", num_cars["suzuki"]);
    end
endmodule

Output

# Number of cars = '{"hyndai":2, "suzuki":1, "tata":3 }
# Number of cars for Suzuki is = 1

Associative arrays are very useful when we want to model memories in test bench.

This is because memories are arrays having large number of elements. If dynamic array is used, then the memory will be allocated immediately the array is defined which can lead to system failures.
In associative array the memory will be allocated only when some value is stored in a particular key. Thus the memory requirement in associative array will on need basis.

Associative Array System Functions

1. int num() - returns the number of value or entries stored in the associative array.
2. int size () - Also returns the number of values stored in the associative array. Returns 0 for empty array
3. int delete([key]) - If key is passed to this function than the value associated with the key is deleted. If no key is provided, then it deletes the entire array.
4. int exists(key) - checks whether a value is associated with the given key or not. If no value is present, it returns 0.
5. int first (ref key) - assigns the key variable passed with first key of the associative array. If array is empty 0 is returned
6. int last(ref key) - assigns the key variable passed with last key of the associative array. If array is empty 0 is returned.
7. int next(ref key) - assigns the key variable passed with the key which comes just after the specified key. If array is empty or if the specified key is last, 0 is returned.
8. int prev(ref key) - assigns the key variable passed with the key which comes just before the specified key. If array is empty or if the specified key is first , 0 is returned.

Example

Let’s use some of these function on the array we have declared and defined in the earlier example.

module associative_array();
    int num_cars[string];
    string brand;
    initial begin
        num_cars = '{"hyundai":2, "suzuki":1, "tata": 3};

        $display("Number of cars = %p", num_cars);
        $display("Number of cars for Suzuki is = %0d", num_cars["suzuki"]);

        // num and size
        $display("Number of brands stored = %0d", num_cars.num());
        $display("Size of the array = %0d\n", num_cars.size());

        // get first brand stored in array
        if(num_cars.first(brand))
            $display("First brand found is = %s", brand);

        // get last brand stored in array
        if(num_cars.last(brand))
            $display("Last brand found is = %s\n", brand);

        // get brand stored before last one
        if(num_cars.prev(brand))
            $display("Brand previous to last brand found is = %s", brand);

        // get brand stored before last one
        if(num_cars.next(brand))
            $display("Brand next to last brand found is = %s\n", brand);

        // get brand stored before last one
        if(num_cars.next(brand))
            $display("Brand next to last brand found is = %s\n", brand);
        else
            $display("Either no brand found or this is the last brand\n");

        // check whether a particular brand found or not
        brand = "suzuki";
        if(num_cars.exists(brand))
            $display("Enteries found for %s", brand);
        else
            $display("No enteries found for %s", brand);

        // check whether a particular brand found or not
        brand = "ferrari";
        if(num_cars.exists(brand))
            $display("Enteries found for %s\n", brand);
        else
            $display("No enteries found for %s\n", brand);

        // delete the array
        num_cars.delete();
        $display("Number of brands after deleting = %0d", num_cars.num());
    end
endmodule

Output

# Number of cars = '{"hyundai":2, "suzuki":1, "tata":3 }
# Number of cars for Suzuki is = 1
# Number of brands stored = 3
# Size of the array = 3
#
# First brand found is = hyundai
# Last brand found is = tata
#
# Brand previous to last brand found is = suzuki
# Brand next to last brand found is = tata
#
# Either no brand found or this is the last brand
#
# Enteries found for suzuki
# No enteries found for ferrari
#
# Number of brands after deleting = 0

Complex Scenarios

Dynamic Array inside Associative array

Extending on our previous scenario, now let's consider that we must store the various car name for a different brand. Now the number of name of elements (i.e., car names) will differ for various brands. In this scenario we use can use associative array with dynamic arrays, in which each key will hold a dynamic array of different size.

module associative_dyn_array();
    int num_cars[string];
    string car_name[string][];

    string brand;
    initial begin
        num_cars = '{"abc":2, "xyz":1, "efg": 3};

        foreach (num_cars[brand]) begin
            car_name[brand] = new [num_cars[brand]];
            for (int i=0; i<car_name[brand].size(); ++i) begin
                car_name[brand][i] = $sformatf("%s i%0d", brand, (i+1)*10);
            end
            $display("Cars for %s brand are: %p", brand, car_name[brand]);
        end
    end
endmodule

Output

# Cars for abc brand are: '{"abc i10", "abc i20"}
# Cars for efg brand are: '{"efg i10", "efg i20", "efg i30"}
# Cars for xyz brand are: '{"xyz i10"}

Associative Array inside Dynamic Array

Let’s suppose we must store the marks achieved by different students for different subjects. In this scenario the number of students may vary, and students can be identified using roll number and thus Dynamic array is the most optimal array for this case. Now different students can have different subjects as optional subjects vary from student to student. Thus, for each student we can use associative array to store the marks.

module dyn_associative_array();
    int marks [][string];
    string sub;
    initial begin
        marks = new [2];

        marks[0] = '{"physics":45, "maths": 65, "emt": 56};
        marks[1] = '{"chemistry":67, "maths": 78, "optical communication": 89};

        foreach (marks[i]) begin
            $display("Marks of student %0d is %p", i+1, marks[i]);
        end

        if(marks[0].first(sub))
            $display("Frist subject of student 1 is: %s", sub);
    end
endmodule

Output

# Marks of student 1 is '{"emt":56, "maths":65, "physics":45 }
# Marks of student 2 is '{"chemistry":67, "maths":78, "optical communication":89 }
# Frist subject of student 1 is: emt

Please note that in the above output, the simulator stores the key in ascending order. This is the reason emt is shown first as “e” comes first in alphabetical order. This is done internally to improve the speed of associative arrays as searching is faster in sorted keys.