PRT.DevelopCodeExplArrayMalloc History

Hide minor edits - Show changes to output - Cancel

June 30, 2012, at 04:20 AM by 24.130.186.152 -
Added lines 1-12:

Uses an array of free-lists. For small chunks, below 128 (I think), there is one list for each size, and all in the list are of that same size. For larger chunks, each list has a lower and upper bound on size. The lower bound increases exponentially, and the upper bound is the lower-bound of the next higher list. There is also a bit-vector representing which free-lists are empty. Due to exponential, a 64-bit vector has 256 MB as largest lower-bound.

Each chunk has a pre-amble holding a link to the next chunk in that free-list, and pointers to the neighbor above and neighbor below.

To find a chunk, test if it's small, and if so, do a ceiling to the next larger size, then use bit-vector to find next larger non-empty list, take from there. If larger than needed, shave off extra and put back as a new chunk.

If request is large, then calculate the closest larger lower-bound. Use bit-vector to find first non-empty list of that size or bigger. Take first chunk in that list. Shave off extra and insert as new chunk.

Either way, if that was last chunk in the list, clear bit in bit-vector.

For free, first check the neighbor chunks, and combine with either that are already free. Then calculate the lower-bound that is just larger, and put into the list before that one. Then, set bit in bit-vector.