[PATCH] Request review for KSharedDataCache

[Oswald Buddenhagen]

On Sat, Apr 10, 2010 at 12:03:56PM -0400, Michael Pyne wrote:
> On Saturday, April 10, 2010 06:42:19 Oswald Buddenhagen wrote:
> > i've also been pondering to suggest a more modern tree based
> > allocator with no paging at all, but this most probably makes no
> > sense for the scalability requirements of a cache.
> 
> Paging wasn't my first idea, but it seemed easiest to implement while
> still meeting most of the requirements. The other problem is I don't
> often have to program in a no-dynamic-allocation class so it's hard
> for me to find algorithms that operate well in this mode without
> requiring malloc.
> 
well, you do have malloc - kinda. any tree-based allocation scheme has
dynamic memory requirements, so it basically needs to self-host its own
meta-data. you may want to read the whitepapers of btrfs or some other
modern fs.
of course, this seems like major overkill for the use cases i can think
of currently.

fwiw, this enters the realm of databases. have you looked for libraries
which might implement a shared-memory database proper? then the whole
thing would become a rather thin wrapper ...

> > this class belongs into kdecore.
> 
> Now that you mention it, that's exactly right. I'll have to figure out
> where to stash it.
> 
io/ seems like a fine choice.
fallback to util/, though that sounds like a place to put stuff which
didn't fit elsewhere. :)

> > > +    T result = a / b;
> > > +    result += (a % b) ? 1 : 0;  // Round up if needed
> > > +    return result;
> > 
> > return (a + b - 1) / b;
> 
> Wouldn't this be more susceptible to overflow in the intermediate calculation?
> 
well, if a + b may blow the range, then you may be in trouble anyway. :)
you could also write
  return (a - 1) / b + 1;
- i just factored out b. this formula is not recommended for unsigned
types unless a >= 1 is guaranteed, of course. :)