[interfacekit] Re: BBlockCache bug

> I noticed the same thing about the destructor and the implementation.  I 
> coded up a new
> implementation last night using fMark as the delimiter between used and 
> unused blocks so
> it works like this:
> 
> 1. The fCache member is an array of (void *)'s.  The array is fCacheSize big 
> and each
> element of the array points to a block of memory fBlockSize long.
> 
> 2. The elements in the array are ordered like this:
>      0 ... (fMark - 1) - these pointers are currently in use
>      fMark ... (fCacheSize - 1) - these pointers are currently not in use
> That way, you only need fMark to know which blocks are in use and which ones 
> aren't
> 
> 3. To get a buffer, you just return fCache[fMark] and increment fMark.  This 
> is O(1) which
> is good and much better than our current implementation.
What happens if fMark is larger than the numbers of existing buffers?

> 4. To return a buffer back to the cache, it searches from 0 ... (fMark - 1) 
> to find the
> block which is being returned.  Then it swaps the matching element with the 
> one at (fMark
> - 1) and decrements fMark.  Swapping the pointers is a pretty cheap operation 
> but finding
Bad.

> the buffer in the array is O(n) which isn't the best.  I think Be's 
> implementation is the
Bad.

> I have a rough implementation of the above and a couple of simple tests so 
> far.  I will
> try to finish off the tests and compare all three implementations (Be's, our 
> existing one
> and the one proposed above) to see which we should go with.

I'm going to rewrite it using two single linked lists (used and free), that 
should be the fastest
but still simple implementation. The Get and Save functions will both be O(1).

Should be ready until tomorrow.

regards
Marcus

Other related posts: