Merge of itasc branch. Project files, scons and cmake should be working. Makefile...
[blender.git] / intern / itasc / Cache.hpp
1 /* $Id: Cache.hpp 21152 2009-06-25 11:57:19Z ben2610 $
2  * Cache.hpp
3  *
4  *  Created on: Feb 24, 2009
5  *      Author: benoit tbolsee
6  */
7
8 #ifndef CACHE_HPP_
9 #define CACHE_HPP_
10
11 #include <map>
12
13 namespace iTaSC {
14
15 #define CACHE_LOOKUP_TABLE_SIZE                         128
16 #define CACHE_DEFAULT_BUFFER_SIZE                       32768
17 #define CACHE_CHANNEL_EXTEND_SIZE                       10
18 #define CACHE_MAX_ITEM_SIZE                                     0x3FFF0
19
20 /* macro to get the alignement gap after an item header */
21 #define CACHE_ITEM_GAPB(item)                           (unsigned int)(((size_t)item+sizeof(CacheItem))&(sizeof(void*)-1))
22 /* macro to get item data position, item=CacheItem pointer */
23 #define CACHE_ITEM_DATA_POINTER(item)           (void*)((unsigned char*)item+sizeof(CacheItem)+CACHE_ITEM_GAPB(item))
24 /* macro to get item size in 32bit words from item address and length, item=CacheItem pointer */
25 #define CACHE_ITEM_SIZEW(item,length)           (unsigned int)((sizeof(CacheItem)+CACHE_ITEM_GAPB(item)+(((length)+3)&~0x3))>>2)
26 /* macto to move from one item to the next, item=CacheItem pointer, updated by the macro */
27 #define CACHE_NEXT_ITEM(item)                           ((item)+(item)->m_sizeW)
28 #define CACHE_BLOCK_ITEM_ADDR(chan,buf,block)   (&(buf)->m_firstItem+(((unsigned int)(block)<<chan->m_positionToBlockShiftW)+(buf)->lookup[block].m_offsetW))
29 #define CACHE_ITEM_ADDR(buf,pos)                        (&(buf)->m_firstItem+(pos))
30 #define CACHE_ITEM_POSITIONW(buf,item)          (unsigned int)(item-&buf->m_firstItem)
31
32 typedef unsigned int CacheTS;
33
34 struct Timestamp 
35 {
36         double realTimestamp;
37         double realTimestep;
38         CacheTS cacheTimestamp;
39         unsigned int numstep:8;
40         unsigned int substep:1;
41         unsigned int reiterate:1;
42         unsigned int cache:1;
43         unsigned int update:1;
44         unsigned int interpolate:1;
45         unsigned int dummy:19;
46
47         Timestamp() { memset(this, 0, sizeof(Timestamp)); }
48 };
49
50 /* utility function to return second timestamp to millisecond */
51 inline void setCacheTimestamp(Timestamp& timestamp)
52 {
53         if (timestamp.realTimestamp < 0.0 || timestamp.realTimestamp > 4294967.295)
54                 timestamp.cacheTimestamp = 0;
55         else
56                 timestamp.cacheTimestamp = (CacheTS)(timestamp.realTimestamp*1000.0+0.5);
57 }
58
59
60 /*
61 class Cache:
62 Top level class, only one instance of this class should exists.
63 A device (=constraint, object) uses this class to create a cache entry for its data.
64 A cache entry is divided into cache channels, each providing a separate buffer for cache items.
65 The cache channels must be declared by the devices before they can be used.
66 The device must specify the largest cache item (limited to 256Kb) so that the cache
67 buffer can be organized optimally.
68 Cache channels are identified by small number (starting from 0) allocated by the cache system.
69 Cache items are inserted into cache channels ordered by timestamp. Writing is always done
70 at the end of the cache buffer: writing an item automatically clears all items with 
71 higher timestamp.
72 A cache item is an array of bytes provided by the device; the format of the cache item is left 
73 to the device. 
74 The device can retrieve a cache item associated with a certain timestamp. The cache system
75 returns a pointer that points directly in the cache buffer to avoid unnecessary copy. 
76 The pointer is guaranteed to be pointer aligned so that direct mapping to C structure is possible 
77 (=32 bit aligned on 32 systems and 64 bit aligned on 64 bits system).
78
79 Timestamp = rounded time in millisecond.
80 */
81
82 struct CacheEntry;
83 struct CacheBuffer;
84 struct CacheItem;
85 struct CacheChannel;
86
87 class Cache 
88 {
89 private:
90         /* map between device and cache entry.
91            Dynamically updated when more devices create cache channels */
92         typedef std::map<const void *, struct CacheEntry*> CacheMap;
93         CacheMap  m_cache;
94         const CacheItem *getCurrentCacheItemInternal(const void *device, int channel, CacheTS timestamp);
95    
96 public:
97         Cache();
98         ~Cache();
99         /* add a cache channel, maxItemSize must be < 256k.
100            name : channel name, truncated at 31 characters
101            msxItemSize : maximum size of item in bytes, items of larger size will be rejected
102            return value >= 0: channel id, -1: error */
103         int addChannel(const void *device, const char *name, unsigned int maxItemSize);
104
105         /* delete a cache channel (and all associated buffers and items) */
106         int deleteChannel(const void *device, int channel);
107         /* delete all channels of a device and remove the device from the map */
108         int deleteDevice(const void *device);
109         /* removes all cache items, leaving the special item at timestamp=0. 
110            if device=NULL, apply to all devices. */
111         void clearCacheFrom(const void *device, CacheTS timestamp);
112
113         /* add a new cache item
114            channel: the cache channel (as returned by AddChannel
115            data, length: the cache item and length in bytes
116                          If data is NULL, the memory is allocated in the cache but not writen
117            return: error: NULL, success: pointer to item in cache */
118         void *addCacheItem(const void *device, int channel, CacheTS timestamp, void *data, unsigned int length);
119
120         /* specialized function to add a vector of double in the cache
121            It will first check if a vector exist already in the cache for the same timestamp
122            and compared the cached vector with the new values. 
123            If all values are within threshold, the vector is updated but the cache is not deleted
124            for the future timestamps. */
125         double *addCacheVectorIfDifferent(const void *device, int channel, CacheTS timestamp, double *data, unsigned int length, double threshold);
126
127         /* returns the cache item with timestamp that is just before the given timestamp.
128            returns the data pointer or NULL if there is no cache item before timestamp.
129            On return, timestamp is updated with the actual timestamp of the item being returned.
130            Note that the length of the item is not returned, it is up to the device to organize
131            the data so that length can be retrieved from the data if needed.
132            Device can NULL, it will then just look the first channel available, useful to 
133            test the status of the cache. */
134         const void *getPreviousCacheItem(const void *device, int channel, CacheTS *timestamp);
135
136         /* returns the cache item with the timestamp that is exactly equal to the given timestamp
137            If there is no cache item for this timestamp, returns NULL.*/
138         const void *getCurrentCacheItem(const void *device, int channel, CacheTS timestamp);
139
140 };
141
142 /* the following structures are not internal use only, they should not be used directly */
143
144 struct CacheEntry 
145 {
146         CacheChannel *m_channelArray;           // array of channels, automatically resized if more channels are created
147         unsigned int m_count;                           // number of channel in channelArray
148         CacheEntry() : m_channelArray(NULL), m_count(0) {}
149         ~CacheEntry();
150 };
151
152 struct CacheChannel
153 {
154         CacheItem* initItem;                            // item corresponding to timestamp=0
155         struct CacheBuffer *m_firstBuffer;      // first buffer of list
156         struct CacheBuffer *m_lastBuffer;               // last buffer of list to which an item was written
157         char m_name[32];                                                // channel name
158         unsigned char m_busy;                                   // =0 if channel is free, !=0 when channel is in use
159         unsigned char m_positionToBlockShiftW;  // number of bits to shift a position in word to get the block number
160         unsigned short m_positionToOffsetMaskW;   // bit mask to apply on a position in word to get offset in a block
161         unsigned int m_maxItemSizeB;                    // maximum item size in bytes
162         unsigned int m_bufferSizeW;                     // size of item buffer in word to allocate when a new buffer must be created
163         unsigned int m_blockSizeW;                      // block size in words of the lookup table
164         unsigned int m_lastTimestamp;                   // timestamp of the last item that was written
165         unsigned int m_lastItemPositionW;               // position in words in lastBuffer of the last item written
166         void clear();
167         CacheBuffer* allocBuffer();
168         CacheItem* findItemOrLater(unsigned int timestamp, CacheBuffer **rBuffer);
169         CacheItem* findItemEarlier(unsigned int timestamp, CacheBuffer **rBuffer);
170         // Internal function: finds an item in a buffer that is < timeOffset
171         // timeOffset must be a valid offset for the buffer and the buffer must not be empty
172         // on return highBlock contains the block with items above or equal to timeOffset
173         CacheItem *_findBlock(CacheBuffer *buffer, unsigned short timeOffset, unsigned int *highBlock);
174 };
175
176 struct CacheBlock {
177         unsigned short m_timeOffset;            // timestamp relative to m_firstTimestamp
178         unsigned short m_offsetW;                       // position in words of item relative to start of block
179 };
180
181 /* CacheItem is the header of each item in the buffer, must be 32bit
182    Items are always 32 bits aligned and size is the number of 32 bit words until the
183    next item header, including an eventual pre and post padding gap for pointer alignment */
184 struct CacheItem
185 {
186         unsigned short m_timeOffset;            // timestamp relative to m_firstTimestamp
187         unsigned short m_sizeW;                 // size of item in 32 bit words
188         // item data follows header immediately or after a gap if position is not pointer aligned
189 };
190
191 // Buffer header
192 // Defined in a macro to avoid sizeof() potential problem.
193 //      next                            for linked list. = NULL for last buffer
194 //  m_firstTimestamp            timestamp of first item in this buffer
195 //  m_lastTimestamp             timestamp of last item in this buffer
196 //                                              m_lastTimestamp must be < m_firstTimestamp+65536
197 //  m_lastItemPositionW position in word of last item written
198 //  m_firstFreePositionW        position in word where a new item can be written, 0 if buffer is empty
199 //  lookup                              lookup table for fast access to item by timestamp
200 //                                              The buffer is divided in blocks of 2**n bytes with n chosen so that 
201 //                                              there are no more than CACHE_LOOKUP_TABLE_SIZE blocks and that each 
202 //                                              block will contain at least one item. 
203 //                                              Each element of the lookup table gives the timestamp and offset 
204 //                                              of the last cache item occupying (=starting in) the corresponding block.
205 #define CACHE_HEADER \
206         struct CacheBuffer *m_next;             \
207         unsigned int m_firstTimestamp;  \
208         unsigned int m_lastTimestamp;           \
209                                                                         \
210         unsigned int m_lastItemPositionW;       \
211         unsigned int m_firstFreePositionW;\
212         struct CacheBlock lookup[CACHE_LOOKUP_TABLE_SIZE]
213
214 struct CacheBufferHeader {
215         CACHE_HEADER;
216 };
217 #define CACHE_BUFFER_HEADER_SIZE        (sizeof(struct CacheBufferHeader))
218 struct CacheBuffer
219 {
220         CACHE_HEADER;
221         struct CacheItem m_firstItem;                   // the address of this field marks the start of the buffer
222 };
223
224
225 }
226
227 #endif /* CACHE_HPP_ */