[Moved] Access type and pointer (sorted linked List )

maturainfankam · Aug 5, 2014

Hello everybody,
i have some problem to use the pointer in VHDl.
to begin a have contruct a linked list with three element 10 => 12 => 14. Nun a want to add the value 13 on the List ( between 12 and 14) so that i get always a sorted list.
But that not work:
you can see the code in appendex.
Thanks for answers.
Jean

Code:

syntax=vhdl 
library ieee;
use ieee.std_logic_1164.all;            -- biblio for std_logic


entity pointer is

  port (
    rst : in std_logic;
    clk : in std_logic;
    re  : in std_logic);

end pointer;

architecture arch of pointer is

  type CELL;
  type LINK is access CELL;

  type CELL is record
                 value : natural;
                 NEXTP : LINK;
               end record CELL;

  shared variable HEAD, current, previous : LINK;  --Zeiger auf CELL
  shared variable tests                   : boolean := false;

  signal output : natural;

begin  -- architecture

  MAKE_LL                  : process
    variable tempptr, temp : LINK;
    variable find          : boolean := false;
  begin  -- process
    HEAD                             := new CELL'(14, HEAD);
    HEAD                             := new CELL'(12, HEAD);
    HEAD                             := new CELL'(10, HEAD);
    current                          := HEAD;

    while current /= null and find = false loop
      if current.value > 13 then
        find         := true;
      else
        previous     := current;
        current      := current.NEXTP;
      end if;
    end loop;
    if previous = null then
      HEAD           := new CELL'(13, HEAD);
    elsif current = null then
      tempptr        := new CELL'(13, null);
      previous.NEXTP := tempptr;
    else
      tempptr        := new CELL'(13, tempptr);
      temp           := tempptr;
      tempptr        := current;
      previous.NEXTP := tempptr;
--      current        := previous.NEXTP;
--      previous.NEXTP := temp;
--          current := temp;
      report "previous and current don't point of null" severity note;
      --deallocate(tempptr);
      -- deallocate(temp);
    end if;
    tests            := true;
    wait;
  end process;

  LESEN_LL : process

    variable testnew : LINK;
  begin  -- process
    testnew     := HEAD;
    if tests then
      while testnew /= null loop
        output <= testnew.value;
        wait for 20 ns;
        testnew := testnew.NEXTP;
        if testnew = null then
          wait;
        end if;
      end loop;
    end if;
    wait for 10 ns;
  end process;

  
end arch;

ads-ee · Aug 5, 2014

Are you trying to design something to use in an FPGA or ASIC or are you trying to write a program? First tell us which, otherwise we'll assume you want to develop some hardware and want to put this in an FPGA, which means it needs to represent hardware.

This is written as if you believe VHDL is a software programming language. VHDL stands for VHSIC Hardware Description Language not Software Programming Language (if you want the VHDL equivalent go get an ADA compiler). Unless you know what the hardware (logic) you want you shouldn't be writing the VHDL. The VHDL should be describing a design you've already done on paper or in your head.

maturainfankam · Aug 5, 2014

Dear ads-ee
i try to write first a modell with linked List to sort some entries. The linked list are dynamic, that mean i can add a new or delete a existed or move a value from one position to another to get already a sorted List. when a finish the modell, i want to
to develop some hardware and put this in an FPGA.
Thanks for answer.
jean.

FvM · Aug 5, 2014

VHDL has some abstract language elements that can be e.g. useful for testbenches, but aren't synthesizable. Dynamic object allocation as used in your code is an example of non-synthesizable VHDL. Although some code lines are apparently copied directly from the VHDL language reference manual, you will hardly find it in a "VHDL design for FPGA" text book.

A synthesizable sort algorithm would preferably work in an adressable memory (RAM) and perform the sort sequentially, one step per clock cycle.

ads-ee · Aug 5, 2014

What you have written now would never get through synthesis. You have no clock(s) in the design so how are you going to "store" anything in your linked list. You need a clock to store something in a register (flip-flop) and/or a block RAM.

If you want to put the design in an FPGA, you need to implement this dynamic list with a block RAM in the FPGA. You'll need to keep track of the addresses of the next/previous entry in the linked list. As this isn't software you have to build all the hardware to do this. You'll also have to decide, the maximum allowable size of this list as hardware is more or less finite compared to the GB of memory in a processor system.

If you decide the relatively small amount of memory in an FPGA isn't big enough then you'll have to use external memory. I would consider anything other than a simple asynchronous SRAM interface as far to advanced for you to implement, so accept the fact you can only implement a relatively small linked list in the FPGA memory.

You should sit down and draw up the circuit that implements your algorithm, or a least create a block diagram of the circuit and then come up with details for the each of those blocks that can be implemented using registers, multiplexers, memories, FSMs, etc.

regards

maturainfankam · Aug 5, 2014

thanks for answer,
the code that i want first to write is not synthetizable, i want only one modell for the simulation and to test only with simulation if this work. the not synthetizable modell is the reference modell and is only for simulation. I want to write the synthetizable modell later using registers, multiplexers, memories, FSMs, etc.

i have already solve one step for my problem and this is the code.
next step ist to delete node or change the position of a node.
Thanks for your help.
Jean

Code VHDL - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
library ieee;
use ieee.std_logic_1164.all;            -- biblio for std_logic
 
entity pointer is
 
  port (
    rst : in std_logic;
    clk : in std_logic;
    re  : in std_logic);
 
end pointer;
 
architecture arch of pointer is
 
  type CELL;
  type LINK is access CELL;
 
  type CELL is record
                 value : natural;
                 NEXTP : LINK;
               end record CELL;
 
  shared variable HEAD, current, current1,current2, previous1,previous2, previous : LINK;  --Zeiger auf CELL
  shared variable tests                   : boolean := false;
 
  signal output : natural;
 
begin  -- architecture
 
  MAKE_LL                  : process
    variable tempptr, tempptr1,tempptr2 : LINK;
    variable find, find1,find2,find3         : boolean := false;
  begin  -- process
    HEAD                             := new CELL'(14, HEAD);
    HEAD                             := new CELL'(12, HEAD);
    HEAD                             := new CELL'(10, HEAD);
    current                          := HEAD;
 
     while current /= null and find = false loop
       if current.value > 13 then
         find         := true;
       else
         previous     := current;
         current      := current.NEXTP;
       end if;
     end loop;
     if previous = null then
       HEAD           := new CELL'(13, HEAD);
     elsif current = null then
       tempptr        := new CELL'(13, null);
       previous.NEXTP := tempptr;
     else
       tempptr        := new CELL'(13, current);
       --temp           := tempptr;
      -- tempptr        := current;
       previous.NEXTP := tempptr;
 --      current        := previous.NEXTP;
 --      previous.NEXTP := temp;
 --          current := temp;
       report "previous and current don't point of null" severity note;
       --deallocate(tempptr);
       -- deallocate(temp);
     end if;
    
    current1                          := HEAD;   
 while current1 /= null and find2 = false loop
       if current1.value > 5 then
         find2         := true;
       else
         previous1     := current1;
         current1      := current1.NEXTP;
       end if;
     end loop;
     if previous1 = null then
       HEAD           := new CELL'(5, HEAD);
     elsif current1 = null then
       tempptr1        := new CELL'(5, null);
       previous1.NEXTP := tempptr1;
     else
       tempptr1        := new CELL'(5, current1);
       --temp           := tempptr;
      -- tempptr        := current;
       previous1.NEXTP := tempptr1;
 --      current        := previous.NEXTP;
 --      previous.NEXTP := temp;
 --          current := temp;
       report "previous and current don't point of null" severity note;
       --deallocate(tempptr);
       -- deallocate(temp);
     end if;
 
 
    current2                          := HEAD;   
 while current2 /= null and find3 = false loop
       if current2.value > 15 then
         find3         := true;
       else
         previous2     := current2;
         current2      := current2.NEXTP;
       end if;
     end loop;
     if previous2 = null then
       HEAD           := new CELL'(15, HEAD);
     elsif current2 = null then
       tempptr2        := new CELL'(15, null);
       previous2.NEXTP := tempptr2;
     else
       tempptr2        := new CELL'(15, current2);
       --temp           := tempptr;
      -- tempptr        := current;
       previous2.NEXTP := tempptr2;
 --      current        := previous.NEXTP;
 --      previous.NEXTP := temp;
 --          current := temp;
       report "previous and current don't point of null" severity note;
       --deallocate(tempptr);
       -- deallocate(temp);
     end if;
 
    tests            := true;
    wait;
  end process;
 
  LESEN_LL : process
 
    variable testnew : LINK;
  begin  -- process
    testnew     := HEAD;
    if tests then
      while testnew /= null loop
        output <= testnew.value;
        wait for 20 ns;
        testnew := testnew.NEXTP;
        if testnew = null then
          wait;
        end if;
      end loop;
    end if;
    wait for 10 ns;
  end process;
 
end arch;

Welcome to EDAboard.com

[Moved] Access type and pointer (sorted linked List )

maturainfankam

Newbie level 4

ads-ee

Super Moderator

maturainfankam

Newbie level 4

FvM

Super Moderator

ads-ee

Super Moderator

maturainfankam

Newbie level 4

Similar threads

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Connect with us

Online statistics

Forum statistics