1// BlockAllocatorArea.h
2
3#ifndef BLOCK_ALLOCATOR_AREA_H
4#define BLOCK_ALLOCATOR_AREA_H
5
6#include <util/DoublyLinkedList.h>
7
8#include "BlockAllocator.h"
9#include "BlockAllocatorMisc.h"
10
11
12class BlockAllocator::Area : public DoublyLinkedListLinkImpl<Area> {
13public:
14	static Area *Create(size_t size);
15	void Delete();
16
17	inline void SetBucket(AreaBucket *bucket)		{ fBucket = bucket; }
18	inline AreaBucket *GetBucket() const			{ return fBucket; }
19
20	inline Block *GetFirstBlock() const				{ return fFirstBlock; }
21	inline Block *GetLastBlock() const				{ return fLastBlock; }
22
23	inline TFreeBlock *GetFirstFreeBlock() const	{ return fFirstFree; }
24	inline TFreeBlock *GetLastFreeBlock() const		{ return fLastFree; }
25
26	inline bool IsEmpty() const				{ return (fUsedBlockCount == 0); }
27	inline Block *GetFirstUsedBlock() const;
28
29	static inline size_t GetMaxFreeBytesFor(size_t areaSize);
30
31	inline size_t GetFreeBytes() const		{ return fFreeBytes; }
32	inline bool NeedsDefragmenting() const	{ return (fFreeBlockCount > 1); }
33
34	inline int32 GetBucketIndex();
35
36	Block *AllocateBlock(size_t usableSize, bool dontDefragment = false);
37	void FreeBlock(Block *block, bool dontDefragment = false);
38	Block *ResizeBlock(Block *block, size_t newSize,
39					   bool dontDefragment = false);
40
41	// debugging only
42	bool SanityCheck() const;
43	bool CheckBlock(Block *block, size_t minSize = 0);
44
45private:
46	inline size_t _GetBlockFreeBytes()
47		{ return fFreeBytes + sizeof(BlockHeader); }
48
49	Area(area_id id, size_t size);
50	~Area();
51
52	inline void _FixBlockList(Block *block, Block *prevBlock,
53							  Block *nextBlock);
54	inline void _FixFreeList(TFreeBlock *block, TFreeBlock *prevFree,
55							 TFreeBlock *nextFree);
56
57	TFreeBlock *_FindFreeBlock(size_t minSize);
58	void _InsertFreeBlock(TFreeBlock *block);
59	void _RemoveFreeBlock(TFreeBlock *block);
60	TFreeBlock * _MoveResizeFreeBlock(TFreeBlock *freeBlock, ssize_t offset,
61									  size_t newSize);
62	inline TFreeBlock *_MakeFreeBlock(void *address, ssize_t offset,
63		Block *previous, size_t size, bool hasNext, TFreeBlock *previousFree,
64		TFreeBlock *nextFree);
65	bool _CoalesceWithNext(TFreeBlock *block);
66
67	inline Block *_MakeUsedBlock(void *address, ssize_t offset,
68								 Block *previous, size_t size, bool hasNext);
69
70	inline bool _DefragmentingRecommended();
71	void _Defragment();
72
73private:
74	AreaBucket			*fBucket;
75	area_id				fID;
76	size_t				fSize;
77	size_t				fFreeBytes;
78	size_t				fFreeBlockCount;
79	size_t				fUsedBlockCount;
80	Block				*fFirstBlock;
81	Block				*fLastBlock;
82	TFreeBlock			*fFirstFree;
83	TFreeBlock			*fLastFree;
84};
85
86typedef BlockAllocator::Area Area;
87
88
89// inline methods
90
91// debugging
92#if BA_DEFINE_INLINES
93
94// GetFirstUsedBlock
95inline
96Block *
97BlockAllocator::Area::GetFirstUsedBlock() const
98{
99	// Two assumptions:
100	// 1) There is always a first block. If that isn't so, our structure are
101	//    corrupt.
102	// 2) If the first block is free, the second (if any) is not. Otherwise
103	//    there were adjoining free blocks, which our coalescing strategy
104	//    prevents.
105	return (fFirstBlock->IsFree() ? fFirstBlock->GetNextBlock() : fFirstBlock);
106}
107
108// GetMaxFreeBytesFor
109inline
110size_t
111BlockAllocator::Area::GetMaxFreeBytesFor(size_t areaSize)
112{
113	size_t headerSize = block_align_ceil(sizeof(Area));
114	return Block::GetUsableSizeFor(block_align_floor(areaSize - headerSize));
115}
116
117// GetBucketIndex
118inline
119int32
120BlockAllocator::Area::GetBucketIndex()
121{
122	return bucket_containing_size(GetFreeBytes());
123}
124
125// _FixBlockList
126inline
127void
128BlockAllocator::Area::_FixBlockList(Block *block, Block *prevBlock,
129									Block *nextBlock)
130{
131	if (block) {
132		if (prevBlock)
133			prevBlock->SetNextBlock(block);
134		else
135			fFirstBlock = block;
136		if (nextBlock)
137			nextBlock->SetPreviousBlock(block);
138		else
139			fLastBlock = block;
140	}
141}
142
143// _FixFreeList
144inline
145void
146BlockAllocator::Area::_FixFreeList(TFreeBlock *block, TFreeBlock *prevFree,
147								   TFreeBlock *nextFree)
148{
149	if (block) {
150		if (prevFree)
151			prevFree->SetNextFreeBlock(block);
152		else
153			fFirstFree = block;
154		if (nextFree)
155			nextFree->SetPreviousFreeBlock(block);
156		else
157			fLastFree = block;
158		block->SetPreviousFreeBlock(prevFree);
159		block->SetNextFreeBlock(nextFree);
160	}
161}
162
163// _DefragmentingRecommended
164inline
165bool
166BlockAllocator::Area::_DefragmentingRecommended()
167{
168	// Defragmenting Condition: At least more than 5 free blocks and
169	// free / block ratio greater 1 / 10. Don't know, if that makes any
170	// sense. ;-)
171	return (fFreeBlockCount > 5 && fUsedBlockCount / fFreeBlockCount < 10);
172}
173
174#endif	// BA_DEFINE_INLINES
175
176
177#endif	// BLOCK_ALLOCATOR_AREA_H
178