allocator.h revision 79c9ceea6ec3ac708ec7e27ab3af54ffdaf9338f
10235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin/* 20235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin * Copyright (C) 2009 The Android Open Source Project 30235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin * 40235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin * Licensed under the Apache License, Version 2.0 (the "License"); 50235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin * you may not use this file except in compliance with the License. 60235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin * You may obtain a copy of the License at 70235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin * 80235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin * http://www.apache.org/licenses/LICENSE-2.0 90235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin * 100235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin * Unless required by applicable law or agreed to in writing, software 110235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin * distributed under the License is distributed on an "AS IS" BASIS, 120235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 130235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin * See the License for the specific language governing permissions and 140235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin * limitations under the License. 150235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin */ 160235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 170235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 180235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin#ifndef GRALLOC_ALLOCATOR_H_ 190235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin#define GRALLOC_ALLOCATOR_H_ 200235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 210235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin#include <stdint.h> 220235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin#include <sys/types.h> 230235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 2479c9ceea6ec3ac708ec7e27ab3af54ffdaf9338fMathias Agopian#include "gr.h" 250235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 260235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin// ---------------------------------------------------------------------------- 270235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 280235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin/* 290235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin * A simple templatized doubly linked-list implementation 300235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin */ 310235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 320235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavintemplate <typename NODE> 330235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavinclass LinkedList 340235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin{ 350235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin NODE* mFirst; 360235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin NODE* mLast; 370235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 380235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavinpublic: 390235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin LinkedList() : mFirst(0), mLast(0) { } 400235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin bool isEmpty() const { return mFirst == 0; } 410235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin NODE const* head() const { return mFirst; } 420235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin NODE* head() { return mFirst; } 430235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin NODE const* tail() const { return mLast; } 440235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin NODE* tail() { return mLast; } 450235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 460235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin void insertAfter(NODE* node, NODE* newNode) { 470235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin newNode->prev = node; 480235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin newNode->next = node->next; 490235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin if (node->next == 0) mLast = newNode; 500235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin else node->next->prev = newNode; 510235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin node->next = newNode; 520235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } 530235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 540235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin void insertBefore(NODE* node, NODE* newNode) { 550235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin newNode->prev = node->prev; 560235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin newNode->next = node; 570235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin if (node->prev == 0) mFirst = newNode; 580235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin else node->prev->next = newNode; 590235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin node->prev = newNode; 600235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } 610235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 620235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin void insertHead(NODE* newNode) { 630235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin if (mFirst == 0) { 640235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin mFirst = mLast = newNode; 650235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin newNode->prev = newNode->next = 0; 660235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } else { 670235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin newNode->prev = 0; 680235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin newNode->next = mFirst; 690235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin mFirst->prev = newNode; 700235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin mFirst = newNode; 710235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } 720235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } 730235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 740235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin void insertTail(NODE* newNode) { 750235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin if (mLast == 0) { 760235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin insertHead(newNode); 770235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } else { 780235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin newNode->prev = mLast; 790235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin newNode->next = 0; 800235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin mLast->next = newNode; 810235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin mLast = newNode; 820235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } 830235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } 840235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 850235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin NODE* remove(NODE* node) { 860235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin if (node->prev == 0) mFirst = node->next; 870235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin else node->prev->next = node->next; 880235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin if (node->next == 0) mLast = node->prev; 890235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin else node->next->prev = node->prev; 900235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin return node; 910235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } 920235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin}; 930235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 940235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavinclass SimpleBestFitAllocator 950235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin{ 960235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavinpublic: 970235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 9879c9ceea6ec3ac708ec7e27ab3af54ffdaf9338fMathias Agopian SimpleBestFitAllocator(); 9979c9ceea6ec3ac708ec7e27ab3af54ffdaf9338fMathias Agopian SimpleBestFitAllocator(size_t size); 10079c9ceea6ec3ac708ec7e27ab3af54ffdaf9338fMathias Agopian ~SimpleBestFitAllocator(); 1010235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 10279c9ceea6ec3ac708ec7e27ab3af54ffdaf9338fMathias Agopian ssize_t setSize(size_t size); 10379c9ceea6ec3ac708ec7e27ab3af54ffdaf9338fMathias Agopian 10479c9ceea6ec3ac708ec7e27ab3af54ffdaf9338fMathias Agopian ssize_t allocate(size_t size, uint32_t flags = 0); 10579c9ceea6ec3ac708ec7e27ab3af54ffdaf9338fMathias Agopian ssize_t deallocate(size_t offset); 10679c9ceea6ec3ac708ec7e27ab3af54ffdaf9338fMathias Agopian size_t size() const; 1070235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 1080235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavinprivate: 1090235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin struct chunk_t { 1100235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin chunk_t(size_t start, size_t size) 1110235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin : start(start), size(size), free(1), prev(0), next(0) { 1120235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } 1130235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin size_t start; 1140235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin size_t size : 28; 1150235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin int free : 4; 1160235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin mutable chunk_t* prev; 1170235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin mutable chunk_t* next; 1180235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin }; 1190235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 1200235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin ssize_t alloc(size_t size, uint32_t flags); 1210235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin chunk_t* dealloc(size_t start); 1220235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 1230235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin static const int kMemoryAlign; 1240235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin mutable Locker mLock; 1250235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin LinkedList<chunk_t> mList; 1260235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin size_t mHeapSize; 1270235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin}; 1280235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 1290235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin#endif /* GRALLOC_ALLOCATOR_H_ */ 130