1 /* 2 * Copyright (C) 2009 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 18 #ifndef GRALLOC_ALLOCATOR_H_ 19 #define GRALLOC_ALLOCATOR_H_ 20 21 #include <stdint.h> 22 #include <sys/types.h> 23 24 #include "gr.h" 25 26 // ---------------------------------------------------------------------------- 27 28 /* 29 * A simple templatized doubly linked-list implementation 30 */ 31 32 template <typename NODE> 33 class LinkedList 34 { 35 NODE* mFirst; 36 NODE* mLast; 37 38 public: LinkedList()39 LinkedList() : mFirst(0), mLast(0) { } isEmpty()40 bool isEmpty() const { return mFirst == 0; } head()41 NODE const* head() const { return mFirst; } head()42 NODE* head() { return mFirst; } tail()43 NODE const* tail() const { return mLast; } tail()44 NODE* tail() { return mLast; } 45 insertAfter(NODE * node,NODE * newNode)46 void insertAfter(NODE* node, NODE* newNode) { 47 newNode->prev = node; 48 newNode->next = node->next; 49 if (node->next == 0) mLast = newNode; 50 else node->next->prev = newNode; 51 node->next = newNode; 52 } 53 insertBefore(NODE * node,NODE * newNode)54 void insertBefore(NODE* node, NODE* newNode) { 55 newNode->prev = node->prev; 56 newNode->next = node; 57 if (node->prev == 0) mFirst = newNode; 58 else node->prev->next = newNode; 59 node->prev = newNode; 60 } 61 insertHead(NODE * newNode)62 void insertHead(NODE* newNode) { 63 if (mFirst == 0) { 64 mFirst = mLast = newNode; 65 newNode->prev = newNode->next = 0; 66 } else { 67 newNode->prev = 0; 68 newNode->next = mFirst; 69 mFirst->prev = newNode; 70 mFirst = newNode; 71 } 72 } 73 insertTail(NODE * newNode)74 void insertTail(NODE* newNode) { 75 if (mLast == 0) { 76 insertHead(newNode); 77 } else { 78 newNode->prev = mLast; 79 newNode->next = 0; 80 mLast->next = newNode; 81 mLast = newNode; 82 } 83 } 84 remove(NODE * node)85 NODE* remove(NODE* node) { 86 if (node->prev == 0) mFirst = node->next; 87 else node->prev->next = node->next; 88 if (node->next == 0) mLast = node->prev; 89 else node->next->prev = node->prev; 90 return node; 91 } 92 }; 93 94 class SimpleBestFitAllocator 95 { 96 public: 97 98 SimpleBestFitAllocator(); 99 SimpleBestFitAllocator(size_t size); 100 ~SimpleBestFitAllocator(); 101 102 ssize_t setSize(size_t size); 103 104 ssize_t allocate(size_t size, uint32_t flags = 0); 105 ssize_t deallocate(size_t offset); 106 size_t size() const; 107 108 private: 109 struct chunk_t { chunk_tchunk_t110 chunk_t(size_t start, size_t size) 111 : start(start), size(size), free(1), prev(0), next(0) { 112 } 113 size_t start; 114 size_t size : 28; 115 int free : 4; 116 mutable chunk_t* prev; 117 mutable chunk_t* next; 118 }; 119 120 ssize_t alloc(size_t size, uint32_t flags); 121 chunk_t* dealloc(size_t start); 122 123 static const int kMemoryAlign; 124 mutable Locker mLock; 125 LinkedList<chunk_t> mList; 126 size_t mHeapSize; 127 }; 128 129 #endif /* GRALLOC_ALLOCATOR_H_ */ 130