163b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian/* 263b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian * Copyright (C) 2009 The Android Open Source Project 363b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian * 463b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian * Licensed under the Apache License, Version 2.0 (the "License"); 563b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian * you may not use this file except in compliance with the License. 663b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian * You may obtain a copy of the License at 763b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian * 863b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian * http://www.apache.org/licenses/LICENSE-2.0 963b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian * 1063b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian * Unless required by applicable law or agreed to in writing, software 1163b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian * distributed under the License is distributed on an "AS IS" BASIS, 1263b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1363b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian * See the License for the specific language governing permissions and 1463b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian * limitations under the License. 1563b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian */ 1663b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 1763b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 1863b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian#ifndef GRALLOC_ALLOCATOR_H_ 1963b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian#define GRALLOC_ALLOCATOR_H_ 2063b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 2163b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian#include <stdint.h> 2263b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian#include <sys/types.h> 2363b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 24f882f8e29b6dca40cf93da467120e31b97e27d91Mathias Agopian#include "gr.h" 2563b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 2663b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian// ---------------------------------------------------------------------------- 2763b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 2863b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian/* 2963b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian * A simple templatized doubly linked-list implementation 3063b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian */ 3163b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 3263b00f9573354b80cf6483139766b478bfe2e995Mathias Agopiantemplate <typename NODE> 3363b00f9573354b80cf6483139766b478bfe2e995Mathias Agopianclass LinkedList 3463b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian{ 3563b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian NODE* mFirst; 3663b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian NODE* mLast; 3763b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 3863b00f9573354b80cf6483139766b478bfe2e995Mathias Agopianpublic: 3963b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian LinkedList() : mFirst(0), mLast(0) { } 4063b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian bool isEmpty() const { return mFirst == 0; } 4163b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian NODE const* head() const { return mFirst; } 4263b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian NODE* head() { return mFirst; } 4363b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian NODE const* tail() const { return mLast; } 4463b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian NODE* tail() { return mLast; } 4563b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 4663b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian void insertAfter(NODE* node, NODE* newNode) { 4763b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian newNode->prev = node; 4863b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian newNode->next = node->next; 4963b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian if (node->next == 0) mLast = newNode; 5063b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian else node->next->prev = newNode; 5163b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian node->next = newNode; 5263b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian } 5363b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 5463b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian void insertBefore(NODE* node, NODE* newNode) { 5563b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian newNode->prev = node->prev; 5663b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian newNode->next = node; 5763b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian if (node->prev == 0) mFirst = newNode; 5863b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian else node->prev->next = newNode; 5963b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian node->prev = newNode; 6063b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian } 6163b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 6263b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian void insertHead(NODE* newNode) { 6363b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian if (mFirst == 0) { 6463b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian mFirst = mLast = newNode; 6563b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian newNode->prev = newNode->next = 0; 6663b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian } else { 6763b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian newNode->prev = 0; 6863b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian newNode->next = mFirst; 6963b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian mFirst->prev = newNode; 7063b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian mFirst = newNode; 7163b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian } 7263b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian } 7363b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 7463b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian void insertTail(NODE* newNode) { 7563b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian if (mLast == 0) { 7663b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian insertHead(newNode); 7763b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian } else { 7863b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian newNode->prev = mLast; 7963b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian newNode->next = 0; 8063b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian mLast->next = newNode; 8163b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian mLast = newNode; 8263b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian } 8363b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian } 8463b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 8563b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian NODE* remove(NODE* node) { 8663b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian if (node->prev == 0) mFirst = node->next; 8763b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian else node->prev->next = node->next; 8863b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian if (node->next == 0) mLast = node->prev; 8963b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian else node->next->prev = node->prev; 9063b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian return node; 9163b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian } 9263b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian}; 9363b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 9463b00f9573354b80cf6483139766b478bfe2e995Mathias Agopianclass SimpleBestFitAllocator 9563b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian{ 9663b00f9573354b80cf6483139766b478bfe2e995Mathias Agopianpublic: 9763b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 986a467ca7764f07d1ac0c60268dbf805562f6716fMathias Agopian SimpleBestFitAllocator(); 996a467ca7764f07d1ac0c60268dbf805562f6716fMathias Agopian SimpleBestFitAllocator(size_t size); 1006a467ca7764f07d1ac0c60268dbf805562f6716fMathias Agopian ~SimpleBestFitAllocator(); 10163b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 1026a467ca7764f07d1ac0c60268dbf805562f6716fMathias Agopian ssize_t setSize(size_t size); 1036a467ca7764f07d1ac0c60268dbf805562f6716fMathias Agopian 1046a467ca7764f07d1ac0c60268dbf805562f6716fMathias Agopian ssize_t allocate(size_t size, uint32_t flags = 0); 1056a467ca7764f07d1ac0c60268dbf805562f6716fMathias Agopian ssize_t deallocate(size_t offset); 1066a467ca7764f07d1ac0c60268dbf805562f6716fMathias Agopian size_t size() const; 10763b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 10863b00f9573354b80cf6483139766b478bfe2e995Mathias Agopianprivate: 10963b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian struct chunk_t { 11063b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian chunk_t(size_t start, size_t size) 11163b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian : start(start), size(size), free(1), prev(0), next(0) { 11263b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian } 11363b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian size_t start; 11463b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian size_t size : 28; 11563b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian int free : 4; 11663b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian mutable chunk_t* prev; 11763b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian mutable chunk_t* next; 11863b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian }; 11963b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 12063b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian ssize_t alloc(size_t size, uint32_t flags); 12163b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian chunk_t* dealloc(size_t start); 12263b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 12363b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian static const int kMemoryAlign; 12463b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian mutable Locker mLock; 12563b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian LinkedList<chunk_t> mList; 12663b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian size_t mHeapSize; 12763b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian}; 12863b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian 12963b00f9573354b80cf6483139766b478bfe2e995Mathias Agopian#endif /* GRALLOC_ALLOCATOR_H_ */ 130