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" 25f5a83a9c024dee0617dbc3dab98cd307e8d54665Jamie Gennis#include "pmemalloc.h" 260235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 270235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin// ---------------------------------------------------------------------------- 280235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 290235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin/* 300235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin * A simple templatized doubly linked-list implementation 310235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin */ 320235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 330235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavintemplate <typename NODE> 340235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavinclass LinkedList 350235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin{ 360235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin NODE* mFirst; 370235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin NODE* mLast; 380235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 390235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavinpublic: 400235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin LinkedList() : mFirst(0), mLast(0) { } 410235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin bool isEmpty() const { return mFirst == 0; } 420235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin NODE const* head() const { return mFirst; } 430235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin NODE* head() { return mFirst; } 440235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin NODE const* tail() const { return mLast; } 450235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin NODE* tail() { return mLast; } 460235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 470235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin void insertAfter(NODE* node, NODE* newNode) { 480235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin newNode->prev = node; 490235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin newNode->next = node->next; 500235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin if (node->next == 0) mLast = newNode; 510235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin else node->next->prev = newNode; 520235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin node->next = newNode; 530235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } 540235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 550235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin void insertBefore(NODE* node, NODE* newNode) { 560235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin newNode->prev = node->prev; 570235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin newNode->next = node; 580235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin if (node->prev == 0) mFirst = newNode; 590235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin else node->prev->next = newNode; 600235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin node->prev = newNode; 610235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } 620235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 630235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin void insertHead(NODE* newNode) { 640235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin if (mFirst == 0) { 650235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin mFirst = mLast = newNode; 660235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin newNode->prev = newNode->next = 0; 670235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } else { 680235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin newNode->prev = 0; 690235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin newNode->next = mFirst; 700235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin mFirst->prev = newNode; 710235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin mFirst = newNode; 720235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } 730235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } 740235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 750235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin void insertTail(NODE* newNode) { 760235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin if (mLast == 0) { 770235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin insertHead(newNode); 780235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } else { 790235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin newNode->prev = mLast; 800235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin newNode->next = 0; 810235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin mLast->next = newNode; 820235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin mLast = newNode; 830235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } 840235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } 850235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 860235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin NODE* remove(NODE* node) { 870235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin if (node->prev == 0) mFirst = node->next; 880235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin else node->prev->next = node->next; 890235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin if (node->next == 0) mLast = node->prev; 900235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin else node->next->prev = node->prev; 910235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin return node; 920235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } 930235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin}; 940235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 95f5a83a9c024dee0617dbc3dab98cd307e8d54665Jamie Gennisclass SimpleBestFitAllocator : public PmemUserspaceAllocator::Deps::Allocator 960235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin{ 970235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavinpublic: 980235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 9979c9ceea6ec3ac708ec7e27ab3af54ffdaf9338fMathias Agopian SimpleBestFitAllocator(); 10079c9ceea6ec3ac708ec7e27ab3af54ffdaf9338fMathias Agopian SimpleBestFitAllocator(size_t size); 101f5a83a9c024dee0617dbc3dab98cd307e8d54665Jamie Gennis virtual ~SimpleBestFitAllocator(); 1020235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 103f5a83a9c024dee0617dbc3dab98cd307e8d54665Jamie Gennis virtual ssize_t setSize(size_t size); 10479c9ceea6ec3ac708ec7e27ab3af54ffdaf9338fMathias Agopian 105f5a83a9c024dee0617dbc3dab98cd307e8d54665Jamie Gennis virtual ssize_t allocate(size_t size, uint32_t flags = 0); 106f5a83a9c024dee0617dbc3dab98cd307e8d54665Jamie Gennis virtual ssize_t deallocate(size_t offset); 107f5a83a9c024dee0617dbc3dab98cd307e8d54665Jamie Gennis virtual size_t size() const; 1080235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 1090235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavinprivate: 1100235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin struct chunk_t { 1110235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin chunk_t(size_t start, size_t size) 1120235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin : start(start), size(size), free(1), prev(0), next(0) { 1130235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin } 1140235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin size_t start; 1150235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin size_t size : 28; 1160235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin int free : 4; 1170235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin mutable chunk_t* prev; 1180235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin mutable chunk_t* next; 1190235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin }; 1200235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 1210235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin ssize_t alloc(size_t size, uint32_t flags); 1220235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin chunk_t* dealloc(size_t start); 1230235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 1240235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin static const int kMemoryAlign; 1250235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin mutable Locker mLock; 1260235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin LinkedList<chunk_t> mList; 1270235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin size_t mHeapSize; 1280235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin}; 1290235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin 1300235ebcc09fe10371788dfcefa4e3f12de3783e4Dima Zavin#endif /* GRALLOC_ALLOCATOR_H_ */ 131