队列即FIFO,一言以蔽之就是先进先出。比如入队列的顺序是1,2,3,4,那么出队列的顺序也是1,2,3,4
除了使用链表和数组实现链表以外,GO语言内置一种新的数据结构叫切片,可以实现类似于动态语言中的list
的一些功能(切片和append),用这个数据结构实现队列非常容易
type fifo struct {
data []int
length int
}
f.data[1:]
就是类似于python中的切片操作,表示切掉第一个值,剩下的保留
func (f *fifo) Pop() (int, error) {
if len(f.data) == 0 {
return 0, errors.New("empty fifo")
} else {
temp := f.data[0]
f.data = f.data[1:]
f.length--
return temp, nil
}
}
append方法是go语言自带的切片处理方法,第一个参数是要操作的切片,随后的参数都是要插入到切片之后的变量,返回值是完成插入后新的切片
func (f *fifo) Push(din int) {
f.data = append(f.data, din)
f.length++
}
func New_fifo() *fifo {
return &fifo{[]int{}, 0}
}
fifo由于其不改变数据顺序常用于实现buffer,常用双口ram+控制逻辑的方法实现fifo
module fifo_control #(
parameter WIDTH = 8,
parameter DEPTH_LOG = 8
)(
input clk, // Clock
input rst_n, // Asynchronous reset active low
input fifo_write_req,
input [WIDTH - 1:0]fifo_write_data,
output reg fifo_full,
input fifo_read_req,
output reg fifo_empty,
output reg ram_write_req,
output reg [DEPTH_LOG - 1:0]ram_write_addr,
output reg [WIDTH - 1:0]ram_write_data,
output reg [DEPTH_LOG - 1:0]ram_read_addr
);
reg [DEPTH_LOG - 1:0]write_point,read_point;
wire almost_full = (write_point == read_point - 1'b1)?1'b1:1'b0;
wire almost_empty = (write_point == read_point + 1'b1)?1'b1:1'b0;
always @(posedge clk or negedge rst_n) begin
if(~rst_n) begin
write_point <= 'b0;
ram_write_req <= 'b0;
end else if((!fifo_full || fifo_read_req) && fifo_write_req) begin
write_point <= write_point + 1'b1;
ram_write_req <= 1'b1;
end else begin
ram_write_req <= 'b0;
end
end
(!fifo_full || fifo_read_req) && fifo_write_req
为写执行条件:
always @ (posedge clk or negedge rst_n) begin
if(~rst_n) begin
fifo_full <= 'b0;
end else if(fifo_read_req && fifo_write_req) begin
fifo_full <= fifo_full;
end else if(fifo_read_req) begin
fifo_full <= 'b0;
end else if(almost_full && fifo_write_req) begin
fifo_full <= 'b1;
end
end
fifo_read_req && fifo_write_req
当读写同时进行时,满信号状态不会改变almost_full && fifo_write_req
当写请求有效且只剩一个空位时,满信号置位fifo_read_req
只要读过一次,不可能满always @ (posedge clk or negedge rst_n) begin
if(~rst_n) begin
ram_write_data <= 'b0;
ram_write_addr <= 'b0;
end else begin
ram_write_data <= fifo_write_data;
ram_write_addr <= write_point;
end
end
always @ (posedge clk or negedge rst_n) begin
if(~rst_n) begin
read_point <= 'b0;
ram_read_addr <= 'b0;
end else if(!fifo_empty && fifo_read_req) begin
read_point <= read_point + 1'b1;
ram_read_addr <= read_point;
end
end
!fifo_empty && fifo_read_req
当fifo非空时,读fifoalways @ (posedge clk or negedge rst_n) begin
if(~rst_n) begin
fifo_empty <= 1'b1;
end else if(fifo_read_req && fifo_write_req) begin
fifo_empty <= fifo_empty;
end else if(fifo_write_req) begin
fifo_empty <= 1'b0;
end else if(almost_empty && fifo_read_req) begin
fifo_empty <= 1'b1;
end
end