How to safely delete entries from a queue

SystemVerilog
1

Hello,

I have a queue from which I would like to delete matching entries. I have a queue as below:



Let us say, the queue that has the following data is named, int  id_q[$] 
Index: 0, id: 0x1b
Index: 1, id: 0x1b
Index: 2, id: 0x1b
Index: 3, id: 0x1b
Index: 4, id: 0x3
Index: 5, id: 0x1b
Index: 6, id: 0xe
Index: 7, id: 0x1c
Index: 8, id: 0x17
Index: 9, id: 0x1b
Index: 10, id: 0x1c
Index: 11, id: 0x1c
Index: 12, id: 0x16
Index: 13, id: 0x1b
Index: 14, id: 0x1b
Index: 15, id: 0x17
Index: 16, id: 0x12
Index: 17, id: 0xa
Index: 18, id: 0x17
Index: 19, id: 0x16
Index: 20, id: 0x1b
Index: 21, id: 0x19

Say, I want to delete all the entries in the queue id_q, that match a particular id. In this case, 0x1b

I tried the following methods:


int index_cu[$];
index_cu      = warp_id_in_use_cu_tx.find_index(i) with (i == 0x1b);

       if(index_cu.size() != 0) begin
         foreach(index_cu[i]) begin
             id_q.delete(index_cu[i]);
           end
         end
       end

Now this complains as the entries are deleted from id_q (as the q_id shrinks, the index number pointed to by index_cu, doesn't exist.

alternatively, I tried, the following

foreach(id_q[i]) begin
  if(id_q[i] == 0x1b) begin
    id_q.delete(i);
  end
end

The above method deletes only certain matching entries of 0x1b only. Doesn't delete all of them ? Why does this happen ? 

Can any one explain what is the safest way to delete all the matching entries from a queue ?

[/code]

2

In reply to mseyunni:

pls use hash array:int hash_array[int];

hash_array[id] = num;
an then translate to queue.

3

In reply to smr1113:
I Think following code will work
int index_cu[$];

    foreach(ia_q[i]) begin
       index_cu = ia_q.find_first_index(i) with (i == 0x1b);
         if(index_cu.size)
         id_q.delete(index_cu[i]);
     end
4

In reply to murali.gubba:

Your code finds only the first matching index. However, I would like to delete all the entries matching a particular id.

5

In reply to smr1113:

Can you elaborate on this ?

6

In reply to mseyunni:
Queues are optimal for adding/deleting items to/from the head or tail of the queue. It would be much more efficient to use an associative array.

int  id_aa[int];

foreach(id_aa[i])
  if(id_aa[i] == 'h1b) 
    id_aa.delete(i);

// alternatively if you expect large arrays and small number of matching items
int index_cu[$];

index_cu      = id_aa.find_index() with (item == 'h1b);
foreach(index_cu[i]) 
   id_aa.delete(index_cu[i]);

The reason your foreach loop with a queue doesn’t work is that every time you delete an item, the next item is moved into the current index that you just compared, and is skipped over. You could do:

for(int i = 0; i<id_q.size(); i++)
  if(id_q[i] == 'h1b)
    id_q.delete(i--);
7

In reply to dave_59:

Hi Dave,

The code below looks similar to what I mentioned in my original post except that the id_q[$] is now declared as an array. Are you suggesting that this should work?

// alternatively if you expect large arrays and small number of matching items
int index_cu[$];
 
index_cu      = id_aa.find_index() with (item == 'h1b);
foreach(index_cu[i]) 
   id_aa.delete(index_cu[i]);

and could you explain how the code below works ?

for(int i = 0; i<id_q.size(); i++)
  if(id_q[i] == 'h1b)
    id_q.delete(i--);
8

In reply to mseyunni:

I guess it depends on what you plan to do with the data after the items have been deletes. The code I wrote using an associative array will have gaps in the index values. If that is a problem, use the queue solution.

9

In reply to mseyunni:

Hello,
I have a queue from which I would like to delete matching entries. I have a queue as below:


Let us say, the queue that has the following data is named, int  id_q[$] 
Index: 0, id: 0x1b
Index: 1, id: 0x1b
Index: 2, id: 0x1b
Index: 3, id: 0x1b
Index: 4, id: 0x3
Index: 5, id: 0x1b
Index: 6, id: 0xe
Index: 7, id: 0x1c
Index: 8, id: 0x17
Index: 9, id: 0x1b
Index: 10, id: 0x1c
Index: 11, id: 0x1c
Index: 12, id: 0x16
Index: 13, id: 0x1b
Index: 14, id: 0x1b
Index: 15, id: 0x17
Index: 16, id: 0x12
Index: 17, id: 0xa
Index: 18, id: 0x17
Index: 19, id: 0x16
Index: 20, id: 0x1b
Index: 21, id: 0x19

Say, I want to delete all the entries in the queue id_q, that match a particular id. In this case, 0x1b
I tried the following methods:


int index_cu[$];
index_cu      = warp_id_in_use_cu_tx.find_index(i) with (i == 0x1b);
if(index_cu.size() != 0) begin
foreach(index_cu[i]) begin
id_q.delete(index_cu[i]);
end
end
end
Now this complains as the entries are deleted from id_q (as the q_id shrinks, the index number pointed to by index_cu, doesn't exist.
alternatively, I tried, the following
foreach(id_q[i]) begin
if(id_q[i] == 0x1b) begin
id_q.delete(i);
end
end
The above method deletes only certain matching entries of 0x1b only. Doesn't delete all of them ? Why does this happen ? 
Can any one explain what is the safest way to delete all the matching entries from a queue ?

[/code]

Yes it could be possible with queue also.For that you need to add some logic inside queue entries deletion logic.
Please refer the below modified code:


 if(index_cu.size() != 0) begin
   foreach(index_cu[i]) begin
     // The value of count should be declared and reset at the proper place
     id_q.delete(index_cu[i] - count);
     // Increment the count to track the no of entries that get deleted
     // To have the broader pictute please refer my below pseudo code
     count++;
   end
end

Refer this pseudo code

10

hi,
you can use following code to delete entries from queue without using an associative array. I have tried this and it works. The code consists of two functions, find_and_delete, which finds out a matching entry in queue and deletes one entry and exits the loop. This function is called number of times equal to the number of matching entries in queue i.e. if there are 9 matching entries, function find_and_delete is called 9 times as below:
You can combine two functions find_and_delete and find_cnt to write a single function which can delete matching entries from queue.


module my_mod();
  
  function int find_and_delete (int x, ref int pq[$]);
    int tmp = 0;
    for (int i = 0; i < mq.size(); i ++) begin
      if (pq[i] == x) begin
        pq.delete (i);
         tmp = 1;
         break;
      end
      /*else begin
          continue;
      end */
    end
    return tmp; 
  endfunction
  
  function int find_cnt (input int x, input int pq[$]); 
    int cnt = 0;
    for ( int i = 0; i < pq.size(); i++) begin
      if (pq[i] == x) begin
        cnt ++;
      end
    end  
    return cnt;
  endfunction
  
  int mq[$] = {1, 2, 2, 2, 3, 2, 4, 2, 2, 6, 2, 8, 2, 2, 4, 5};
  int cnt = 0;
  int tmp1;
  initial  begin
    cnt = find_cnt (2, mq);
    
    for (int i = 0; i < cnt; i++) begin
      tmp1 = find_and_delete (2, mq);
    end
    if (tmp1 == 0) begin
      $display ("no matching entries");
    end
    foreach (mq[i])
      $display (mq[i]);
    mq.delete();
  end
endmodule
11

In reply to mseyunni:

Hi mseyunni,

I think the problem happens when you delete the entries one-by-one. When you remove the first, then the indexes of the remain entries are changed. So you will delete the wrong entries in the later steps.

One solution is to delete the entries in the reverse order, just reverse index_cu before performing the loop for deleting:


int index_cu[$];
index_cu      = warp_id_in_use_cu_tx.find_index(i) with (i == 0x1b);

       if(index_cu.size() != 0) begin
         **index_cu.reverse();**
         foreach(index_cu[i]) begin
             id_q.delete(index_cu[i]);
           end
         end
       end
12

I had the same issue, there’s a trick you can play using $size() which will get evaluated every time through the loop. inc_or_hold accounts for when a delete happens the MS queue location is now shifted.

module top;

int a[$] = {10, 5, 6,7,8 };
int inc_or_hold;

initial begin

  for (int ii=0; ii <a.size() ; ii=ii+inc_or_hold) begin
    if (a[ii] inside {5, 6}) begin
      a.delete(ii);
      inc_or_hold = 0;
    end
    else begin
      inc_or_hold = 1;
    end
  end

  foreach (a[ii]) begin
   $display("%0d %0d", ii, a[ii]);
  end
end


endmodule

ncsim> run
0 10
1 7
2 8

13

I think you could just reverse sort the index queue to be in descending order, that way you are deleting from the largest index first, which will not affect the smaller indices

For example in your initial code


int index_cu[$];
index_cu      = warp_id_in_use_cu_tx.find_index(i) with (i == 0x1b);
index_cu.rsort();

       if(index_cu.size() != 0) begin
         foreach(index_cu[i]) begin
             id_q.delete(index_cu[i]);
           end
         end
       end