/* * Copyright (c)1998 by Angry Red Planet. * * This code is distributed under a modified form of the * Artistic License. A copy of this license should have * been included with it; if this wasn't the case, the * entire package can be obtained at * . * * ---------------------------------------------------------------------- * * ArpIndexedList.h * * This class represents a list whose contents can be efficiently accessed. * The list stores subclasses of ArpIndexedNode -- node subclasses are responsible * for implementing Index() and returning a value. This list class takes the Index * and hashes it into a chain. Each chain will contain up to n indexes (set by the * constructor). * * ---------------------------------------------------------------------- * * Known Bugs * ~~~~~~~~~~ * * • The list does not shrink as events are removed. * * ---------------------------------------------------------------------- * * History * ~~~~~~~ * 11.01.98 hackborn * The function NodeAt(), when passed ARP_BACKWARDS, calls NodeBefore(). This * function seeks backwards through the list to find the first node before the time * supplied. For some reason, I wrote it to respond with an error if the time * supplied is greater than the end of the chain. This doesn't make sense to me * upon using it -- clients shouldn't need to know if a time passed in goes beyond * the end of the list, that situation would just be an efficient way of getting * the tail node. So I've changed this to reassign an end-of-the-list time when * the supplied value is too large. * * 09.05.98 hackborn * Created this file */ #ifndef ARPCOLLECTIONS_ARPINDEXEDLIST_H #define ARPCOLLECTIONS_ARPINDEXEDLIST_H #ifndef _LOCKER_H #include #endif #ifndef ARPCOLLECTIONS_ARPINDEXEDNODE_H #include #endif //#include "Synchronization.h" #define ARP_FORWARDS (1) #define ARP_BACKWARDS (2) // The default number of indexes that we allow in a single chain. // See the description for the chainIndexes variable. #define ARP_DEFAULT_CHAIN_INDEXES (40) class ArpIndexedList { friend class ArpIndexedListAccess; public: ArpIndexedList(int32 chainIndexesArg = ARP_DEFAULT_CHAIN_INDEXES); virtual ~ArpIndexedList(); protected: // CHAIN ACCESSING ArpIndexedNode* HeadNode(); ArpIndexedNode* TailNode() { return tailNode; } virtual status_t ChainHeadFrom(int32 index, ArpIndexedNode **node); // Answer the index at the chain head for the supplied index. B_ERROR is // returned if the index isn't in the chain. int32 IndexHeadFrom(int32 index); status_t NodeAt(int32 index, ArpIndexedNode **node, int32 findNode = 0, int32 direction = ARP_FORWARDS); status_t NodeFor(int32 index, void *rawData, ArpIndexedNode **answer); int32 Count(); int32 ChainIndexes(); // CHAIN MANIPULATION status_t AddNode(ArpIndexedNode *node); status_t RemoveNode(ArpIndexedNode *node); status_t DeleteNode(ArpIndexedNode *node); status_t RemoveHeadNode(ArpIndexedNode **removedNode); status_t RemoveTailNode(ArpIndexedNode **removedNode); virtual void AddedNode(ArpIndexedNode *node); /* The following two methods are notification that a node is about to * be removed, and that it has been removed, respectively. Subclasses * overriding RemovingNode() must make sure to call the superclass method. */ virtual void RemovingNode(ArpIndexedNode *node); virtual void RemovedNode(ArpIndexedNode *node) { } void GrowToAtLeast(int32 countArg); // Increase the size of chain to at least // the supplied value. void DeleteOnlyNodes(); void DeleteNodeContents(); // TESTING bool Includes(int32 index, void *rawData); // UTILITY virtual ArpIndexedList* Copy(); virtual void CopyTo(ArpIndexedList *copy); virtual void ReplaceWith(ArpIndexedList *ail); void Print(); // Sometimes the tail node will get out of sync. The following can // be used in those situations to sync it back up. void SyncTailNode(); // Probably need these, have to wait and see. // void VerifyPosition(MidiEvent*); // void VerifyListPosition(MidiAbstractList*); virtual int32 HashForIndex(int32 index); // Answer the proper index into the // chain array based on the supplied time // FILE IO // void KeepChainsConsistent(MidiListNode*); // These should be private, this is a convenience for the file IO. ArpIndexedNode **chain; // This dynamic array stores midi events // in spaced intervals -- the first element // will have 'next' elements from 00 to // nn, the next element will have events // from nn+1 to mm, etc. When we need to // add higher events, we grow the chain. long count; // the size of the chain private: // ReadWriteLock chainLock; int32 chainIndexes; // The number of indexes we allow between chains. // Note the word 'index' instead of 'node.' // Multiple nodes can share the same index, so the // actual chain size might be larger. ArpIndexedNode *tmpE; // This is just a place to hold on to a tmp // event without always creating a new one. // Originally for use for Next(), so a new // event for comparison isn't allocated with // every call to that function. NOTE: there // is never any guarantee what may be in this // event. Functions should ALWAYS set before // using. ArpIndexedNode *tailNode; // This does NOT CURRENTLY represent the tail // node -- I just added it as a quick hack // for the MidiReader. Don't use it! // CHAIN ACCESSING status_t NodeBefore(int32 index, ArpIndexedNode **answer, int32 findNode); status_t NodeAfter(int32 index, ArpIndexedNode **answer, int32 findNode); // CHAIN MANIPULATION status_t pAddNode(ArpIndexedNode *node); status_t pRemoveNode(ArpIndexedNode *node); void pAddNodeAtChainHead(ArpIndexedNode *node, int32 hash); status_t pRemoveChainHeadAt(int32 hash, ArpIndexedNode **node); void pFreeChain(); // TESTING bool HashExists(int32 hash); // UTILITY ArpIndexedNode* NextChainHeadFrom(int32 hash); }; class ArpIndexedListAccess { public: enum AccessMode { AccessRead, AccessWrite }; ArpIndexedListAccess(ArpIndexedList& list, AccessMode=AccessWrite); virtual ~ArpIndexedListAccess(); virtual void DeleteList(); // CHAIN ACCESSING ArpIndexedNode* HeadNode() { return List()->HeadNode(); } ArpIndexedNode* TailNode() { return List()->TailNode(); } status_t ChainHeadFrom(int32 index, ArpIndexedNode **node) { return(List()->ChainHeadFrom(index, node)); } // Answer the index at the chain head for the supplied index. B_ERROR is // returned if the index isn't in the chain. int32 IndexHeadFrom(int32 index) { return List()->IndexHeadFrom(index); } status_t NodeAt(int32 index, ArpIndexedNode **node, int32 findNode = 0, int32 direction = ARP_FORWARDS) { return(List()->NodeAt(index, node, findNode, direction)); } status_t NodeFor(int32 index, void *rawData, ArpIndexedNode **answer) { return(List()->NodeFor(index, rawData, answer)); } int32 Count() { return(List()->Count()); } // CHAIN MANIPULATION status_t AddNode(ArpIndexedNode *node) { return List()->AddNode(node); } status_t RemoveNode(ArpIndexedNode *node) { return List()->RemoveNode(node); } status_t DeleteNode(ArpIndexedNode *node) { return List()->DeleteNode(node); } void DeleteOnlyNodes() { List()->DeleteOnlyNodes(); } void DeleteNodeContents() { List()->DeleteNodeContents(); } // TESTING bool Includes(int32 index, void *rawData) { return List()->Includes(index, rawData); } // UTILITY ArpIndexedList* Copy() { return List()->Copy(); } void ReplaceWith(ArpIndexedList *ail) { List()->ReplaceWith(ail); } void Print() { List()->Print(); } virtual int32 HashForIndex(int32 index) { return List()->HashForIndex(index); } protected: ArpIndexedList& list; AccessMode mode; virtual ArpIndexedList* List(); // ReadLockEntry* reader; // WriteLockEntry* writer; }; #endif /* ARP_INDEXED_LIST_H */