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
32template <typename NODE>
33class LinkedList
34{
35    NODE*  mFirst;
36    NODE*  mLast;
37
38public:
39                LinkedList() : mFirst(0), mLast(0) { }
40    bool        isEmpty() const { return mFirst == 0; }
41    NODE const* head() const { return mFirst; }
42    NODE*       head() { return mFirst; }
43    NODE const* tail() const { return mLast; }
44    NODE*       tail() { return mLast; }
45
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
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
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
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
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
94class SimpleBestFitAllocator
95{
96public:
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
108private:
109    struct chunk_t {
110        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