/* The replacement data needed by replacement policies. Each replacement policy
 *  should have its own implementation of replacement data.
 */
struct ReplacementData {};

class ReplaceableEntry {
  protected:
    // Set & way to which this entry belongs.
    uint32_t _set;
    uint32_t _way;
  public:
    /* Replacement data associated to this entry.
     * It must be instantiated by the replacement policy before being used. */
    std::shared_ptr<replacement_policy::ReplacementData> replacementData;
}

class TaggedEntry : public ReplaceableEntry {
    // Valid bit. The contents of this entry are only valid if it is set.
    bool _valid;

    // Secure bit. Marks whether entry's address in the secure memory space.
    bool _secure;

    /// The entry's tag.
    Addr _tag;
};

class CacheBlk : public TaggedEntry {
  public:
    // Contains a copy of the data in this block for easy access.
    uint8_t *data = nullptr;

    /**
     * Cache block's enum listing the supported coherence bits.
     */
    enum CoherenceBits : unsigned {
        /** write permission */
        WritableBit =       0x02,
        /**
         * Read permission. Note that a block can be valid but not readable
         * if there is an outstanding write upgrade miss.
         */
        ReadableBit =       0x04,
        /** dirty (modified) */
        DirtyBit =          0x08,

        /**
         * Helper enum value that includes all other bits. Whenever a new
         * bits is added, this should be updated.
         */
        AllBits  =          0x0E,
    };
  protected:
    /**
     * Represents that the indicated thread context has a "lock" on
     * the block, in the LL/SC sense.
     */
    class Lock {};

    /** The current coherence status of this block. */
    unsigned coherence;
}

class QueueEntry : public Packet::SenderState, public Named {
  protected:
    /** Tick when ready to issue */
    Tick readyTime;
    /** True if the entry is uncacheable */
    bool _isUncacheable;

  public:
     /** True if the entry has been sent downstream. */
    bool inService;
    /** Order number assigned to disambiguate writes and misses. */
    Counter order;
    /** Block aligned address. */
    Addr blkAddr;
    /** Block size of the cache. */
    unsigned blkSize;
    /** True if the entry targets the secure memory space. */
    bool isSecure;

    /* Since multiple references to the same
     * address can arrive while a packet is not serviced, each packet is
     * stored in a target containing its availability, order and other info,
     * and the queue entry stores these similar targets in a list. */
    class Target {
      public:
        const Tick recvTime;  //!< Time when request was received (for stats)
        const Tick readyTime; //!< Time when request is ready to be serviced
        const Counter order;  //!< Global order (for memory consistency mgmt)
        const PacketPtr pkt;  //!< Pending request packet.
    };
};

template<class Entry>
class Queue : public Drainable, public Named {
  protected:
    /** Local label (for functional print requests) */
    const std::string label;

    /* The total number of entries in this queue. */
    const int numEntries;

    /** The number of entries to hold as a temporary overflow space. */
    const int numReserve;
    /**  Actual storage. */
    std::vector<Entry> entries;
    /** Holds pointers to all allocated entries. */
    typename Entry::List allocatedList;
    /** Holds pointers to entries that haven't been sent downstream. */
    typename Entry::List readyList;
    /** Holds non allocated entries. */
    typename Entry::List freeList;
    /** The number of entries that are in service. */
    int _numInService;
    /** The number of currently allocated entries. */
    int allocated;
}

class MSHR : public QueueEntry, public Printable {
  private:

    /** Flag set by downstream caches */
    bool downstreamPending;

    /**
     * Here we use one flag to track both if:
     *
     * 1. We are going to become owner or not, i.e., we will get the
     * block in an ownership state (Owned or Modified) with BlkDirty
     * set. This determines whether or not we are going to become the
     * responder and ordering point for future requests that we snoop.
     *
     * 2. We know that we are going to get a writable block, i.e. we
     * will get the block in writable state (Exclusive or Modified
     * state) with BlkWritable set. That determines whether additional
     * targets with needsWritable set will be able to be satisfied, or
     * if not should be put on the deferred list to possibly wait for
     * another request that does give us writable access.
     *
     * Condition 2 is actually just a shortcut that saves us from
     * possibly building a deferred target list and calling
     * promoteWritable() every time we get a writable block. Condition
     * 1, tracking ownership, is what is important. However, we never
     * receive ownership without marking the block dirty, and
     * consequently use pendingModified to track both ownership and
     * writability rather than having separate pendingDirty and
     * pendingWritable flags.
     */
    bool pendingModified;

    /** Did we snoop an invalidate while waiting for data? */
    bool postInvalidate;

    /** Did we snoop a read while waiting for data? */
    bool postDowngrade;

  public:

    /** Track if we sent this as a whole line write or not */
    bool wasWholeLineWrite;

    /** True if the entry is just a simple forward from an upper level */
    bool isForward;

    class Target : public QueueEntry::Target
    {
      public:

        enum Source
        {
            FromCPU,
            FromSnoop,
            FromPrefetcher
        };

        const Source source;  //!< Request from cpu, memory, or prefetcher?

        /**
         * We use this flag to track whether we have cleared the
         * downstreamPending flag for the MSHR of the cache above
         * where this packet originates from and guard noninitial
         * attempts to clear it.
         *
         * The flag markedPending needs to be updated when the
         * TargetList is in service which can be:
         * 1) during the Target instantiation if the MSHR is in
         * service and the target is not deferred,
         * 2) when the MSHR becomes in service if the target is not
         * deferred,
         * 3) or when the TargetList is promoted (deferredTargets ->
         * targets).
         */
        bool markedPending;

        const bool allocOnFill;   //!< Should the response servicing this
                                  //!< target list allocate in the cache?
    };
    class TargetList : public std::list<Target>, public Named {
      public:
        bool needsWritable;
        bool hasUpgrade;
        /** Set when the response should allocate on fill */
        bool allocOnFill;
        /**
         * Determine whether there was at least one non-snooping
         * target coming from another cache.
         */
        bool hasFromCache;
      private:
        /** Address of the cache block for this list of targets. */
        Addr blkAddr;
    
        /** Size of the cache block. */
        Addr blkSize;
    
        /** Indicates whether we can merge incoming write requests */
        bool canMergeWrites;
    
        // NOTE: std::vector<bool> might not meet satisfy the
        // ForwardIterator requirement and therefore cannot be used
        // for writesBitmap.
        /**
          * Track which bytes are written by requests in this target
          * list.
          */
        std::vector<char> writesBitmap;
    };
    /** A list of MSHRs. */
    typedef std::list<MSHR *> List;
    /** MSHR list iterator. */
    typedef List::iterator Iterator;

    /**
     * Pointer to this MSHR on the ready list.
     * @sa MissQueue, MSHRQueue::readyList
     */
    Iterator readyIter;

    /**
     * Pointer to this MSHR on the allocated list.
     * @sa MissQueue, MSHRQueue::allocatedList
     */
    Iterator allocIter;

    /** List of all requests that match the address */
    TargetList targets;

    TargetList deferredTargets;
};

class WriteQueueEntry : public QueueEntry, public Printable {
  public:
    class TargetList : public std::list<Target> {
      public:
        TargetList() {}
        void add(PacketPtr pkt, Tick readyTime, Counter order);
        bool trySatisfyFunctional(PacketPtr pkt);
        void print(std::ostream &os, int verbosity,
                   const std::string &prefix) const;
    };
    /** A list of write queue entriess. */
    typedef std::list<WriteQueueEntry *> List;
    /** WriteQueueEntry list iterator. */
    typedef List::iterator Iterator;
    bool sendPacket(BaseCache &cache) override;

  private:
    /** Pointer to this entry on the ready list.
     * @sa MissQueue, WriteQueue::readyList
     */
    Iterator readyIter;

    /** Pointer to this entry on the allocated list.
     * @sa MissQueue, WriteQueue::allocatedList
     */
    Iterator allocIter;

    /** List of all requests that match the address */
    TargetList targets;
};