punk@1: 
punk@1: import FIFO::*;
punk@1: import ConfigReg::*;
punk@1: import RWire::*;
punk@1: 
punk@1: import List::*;
punk@1: import Monad::*;
punk@1: 
punk@1: interface SFIFO#(type alpha_T, type search_T);
punk@1:    method Action enq(alpha_T x);
punk@1:    method Action deq();
punk@1:    method alpha_T first();
punk@1:    method Action clear();
punk@1:    method Bool find(search_T x);   
punk@1:    method Bool find2(search_T x);
punk@1: 
punk@1: endinterface
punk@1: 
punk@1: module mkSFIFO#(function Bool searchfunc(search_T s, alpha_T x)) (SFIFO#(alpha_T, search_T))
punk@1:     provisos
punk@1:       (Bits#(alpha_T,asz));
punk@1: 
punk@1:     Reg#(alpha_T) f0 <- mkConfigRegU();
punk@1:     Reg#(alpha_T) f1 <- mkConfigRegU();
punk@1: 
punk@1:     Reg#(Bool)   vf0 <- mkConfigReg(False);
punk@1:     Reg#(Bool)   vf1 <- mkConfigReg(False);
punk@1: 
punk@1:     PulseWire edge1      <- mkPulseWire();
punk@1:       
punk@1:     method Action enq(alpha_T x) if (!(vf0 && vf1));
punk@1:       if (edge1 || !vf0)//empty or we're dequeueing
punk@1: 	begin
punk@1:           vf0 <= True; //True
punk@1: 	  vf1 <= False;
punk@1: 	   f0 <= x;
punk@1:   	end
punk@1:       else // !vf1 
punk@1:         begin
punk@1:           vf1 <= True;
punk@1:            f1 <= x;
punk@1:  	end
punk@1:     endmethod
punk@1: 										
punk@1:     method Action deq() if (vf0);
punk@1:       edge1.send();
punk@1:       vf0 <= vf1;
punk@1:        f0 <= f1;
punk@1:       vf1 <= False;
punk@1:     endmethod  
punk@1: 
punk@1:     method alpha_T first() if(vf0);
punk@1:       return (f0);
punk@1:     endmethod  
punk@1: 
punk@1:     method Action clear();
punk@1:       vf0 <= False;
punk@1:       vf1 <= False;
punk@1:     endmethod
punk@1: 
punk@1:     method Bool find(search_T sv);
punk@1:       Bool nvf0 = edge1 ? False: vf0;
punk@1:       Bool nvf1 = vf1;
punk@1: 
punk@1:       return (nvf0 && searchfunc(sv, f0) || 
punk@1:               nvf1 && searchfunc(sv, f1));
punk@1:     endmethod
punk@1: 
punk@1:     method Bool find2(search_T sv);
punk@1:       Bool nvf0 = edge1 ? False: vf0;
punk@1:       Bool nvf1 = vf1;
punk@1:       
punk@1:       return (nvf0 && searchfunc(sv, f0) || 
punk@1:               nvf1 && searchfunc(sv, f1));
punk@1:     endmethod
punk@1: 
punk@1: endmodule
punk@1: 
punk@1: module mkSFIFO1#(function Bool searchfunc(search_T s, alpha_T x)) (SFIFO#(alpha_T, search_T))
punk@1:     provisos
punk@1:       (Bits#(alpha_T,asz), Eq#(alpha_T));
punk@1: 
punk@1:     Reg#(alpha_T) f0 <- mkConfigRegU;
punk@1: 
punk@1:     Reg#(Bool)   vf0 <- mkConfigReg(False);
punk@1: 
punk@1:     PulseWire edge1      <- mkPulseWire();
punk@1:       
punk@1:     method Action enq(alpha_T x) if (!vf0);
punk@1:       vf0 <= True; //True
punk@1:       f0 <= x;
punk@1:     endmethod
punk@1: 										
punk@1:     method Action deq() if (vf0);
punk@1:       edge1.send();
punk@1:       vf0 <= False;
punk@1:     endmethod  
punk@1: 
punk@1:     method alpha_T first() if(vf0);
punk@1:       return (f0);
punk@1:     endmethod  
punk@1: 
punk@1:     method Action clear();
punk@1:       vf0 <= False;
punk@1:     endmethod
punk@1: 
punk@1:     method Bool find(search_T sv);
punk@1:       Bool nvf0 = edge1 ? False: vf0;
punk@1: 
punk@1:       return (nvf0 && searchfunc(sv, f0));
punk@1:     endmethod
punk@1: 
punk@1:     method Bool find2(search_T sv);
punk@1:       Bool nvf0 = edge1 ? False: vf0;
punk@1:       return (nvf0 && searchfunc(sv, f0));
punk@1:     endmethod
punk@1: 
punk@1: endmodule
punk@1: 
punk@1: module mkSizedSFIFOInternal#(Integer n, 
punk@1: 			     function Bool searchfunc1(search_T s, alpha_T x), 
punk@1: 			     function Bool searchfunc2(search_T s, alpha_T x))  (SFIFO#(alpha_T, search_T))
punk@1: 				
punk@1:    provisos ( Bits#(alpha_T,alpha_SZ) );
punk@1: 
punk@1:   List#(Reg#(alpha_T)) registers <- replicateM(n, mkRegU);
punk@1:   List#(Reg#(Bool))   valids <- replicateM(n, mkReg(False));
punk@1: 
punk@1:   function Nat getNextFree (List#(Reg#(Bool)) vs);
punk@1: 
punk@1:     Nat res = fromInteger(n - 1);
punk@1: 
punk@1:     for (Integer x = n - 1; x > -1; x = x - 1)
punk@1:       res = !vs[x]._read() ? fromInteger(x) : res;
punk@1: 
punk@1:     return res;
punk@1:   
punk@1:   endfunction
punk@1: 
punk@1:   function Bool notFull();
punk@1:   
punk@1:     Bool full = True;
punk@1: 
punk@1:     for (Integer x = 0; x < n; x = x + 1)
punk@1:       full = full && valids[x]._read();
punk@1: 
punk@1:     return !full;
punk@1:   
punk@1:   endfunction
punk@1: 
punk@1:   method Action enq( alpha_T item ) if ( notFull() );
punk@1:     
punk@1:     Nat k = getNextFree(valids);
punk@1:     select(valids, k)._write(True);
punk@1:     select(registers, k)._write(item);
punk@1:     
punk@1:   endmethod
punk@1: 
punk@1:   method Action deq() if ( valids[0]._read() );
punk@1:     
punk@1:     for (Integer x = 0; x < (n-1); x = x + 1)
punk@1:     begin
punk@1:     
punk@1:       (registers[x]) <= registers[x + 1]._read();
punk@1:       (valids[x]) <= valids[x + 1]._read();
punk@1:     
punk@1:     end
punk@1:     (valids[n-1]) <= False;
punk@1:   endmethod  
punk@1: 
punk@1:   method alpha_T first() if ( valids[0]._read() );
punk@1:     return registers[0]._read();  
punk@1:   endmethod
punk@1: 
punk@1:   method Bool find(search_T sv);
punk@1:     Bool res = False;
punk@1:     
punk@1:     for (Integer x = 0; x < n; x = x + 1)
punk@1:        if ( valids[x]._read() && searchfunc1(sv, registers[x]._read()) )
punk@1:           res = True;
punk@1:     
punk@1:     return res;
punk@1:     
punk@1:   endmethod
punk@1: 
punk@1:   method Bool find2(search_T sv);
punk@1:     Bool res = False;
punk@1:     
punk@1:      for (Integer x = 0; x < n; x = x + 1)
punk@1:         if ( valids[x]._read() && searchfunc2(sv, registers[x]._read()) )
punk@1:            res = True;
punk@1:     
punk@1:     return res;
punk@1:     
punk@1:   endmethod
punk@1: 
punk@1:   method Action clear();
punk@1:   
punk@1:     for (Integer x = 0; x < n; x = x + 1)
punk@1:       (valids[x]) <= False;
punk@1:     
punk@1:   endmethod
punk@1: 
punk@1: endmodule
punk@1: 
punk@1: module mkSizedSFIFO#(Integer n, function Bool searchfunc(search_T s, alpha_T x))  (SFIFO#(alpha_T, search_T))
punk@1:     provisos
punk@1:       (Bits#(alpha_T,asz));
punk@1:    
punk@1:    let foo <- mkSizedSFIFOInternal(n, searchfunc, searchfunc);
punk@1:    return foo;
punk@1: 
punk@1: endmodule