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#include "pmemalloc.h"
26
27// ----------------------------------------------------------------------------
28
29/*
30 * A simple templatized doubly linked-list implementation
31 */
32
33template <typename NODE>
34class LinkedList
35{
36    NODE*  mFirst;
37    NODE*  mLast;
38
39public:
40                LinkedList() : mFirst(0), mLast(0) { }
41    bool        isEmpty() const { return mFirst == 0; }
42    NODE const* head() const { return mFirst; }
43    NODE*       head() { return mFirst; }
44    NODE const* tail() const { return mLast; }
45    NODE*       tail() { return mLast; }
46
47    void insertAfter(NODE* node, NODE* newNode) {
48        newNode->prev = node;
49        newNode->next = node->next;
50        if (node->next == 0) mLast = newNode;
51        else                 node->next->prev = newNode;
52        node->next = newNode;
53    }
54
55    void insertBefore(NODE* node, NODE* newNode) {
56         newNode->prev = node->prev;
57         newNode->next = node;
58         if (node->prev == 0)   mFirst = newNode;
59         else                   node->prev->next = newNode;
60         node->prev = newNode;
61    }
62
63    void insertHead(NODE* newNode) {
64        if (mFirst == 0) {
65            mFirst = mLast = newNode;
66            newNode->prev = newNode->next = 0;
67        } else {
68            newNode->prev = 0;
69            newNode->next = mFirst;
70            mFirst->prev = newNode;
71            mFirst = newNode;
72        }
73    }
74
75    void insertTail(NODE* newNode) {
76        if (mLast == 0) {
77            insertHead(newNode);
78        } else {
79            newNode->prev = mLast;
80            newNode->next = 0;
81            mLast->next = newNode;
82            mLast = newNode;
83        }
84    }
85
86    NODE* remove(NODE* node) {
87        if (node->prev == 0)    mFirst = node->next;
88        else                    node->prev->next = node->next;
89        if (node->next == 0)    mLast = node->prev;
90        else                    node->next->prev = node->prev;
91        return node;
92    }
93};
94
95class SimpleBestFitAllocator : public PmemUserspaceAllocator::Deps::Allocator
96{
97public:
98
99    SimpleBestFitAllocator();
100    SimpleBestFitAllocator(size_t size);
101    virtual ~SimpleBestFitAllocator();
102
103    virtual ssize_t setSize(size_t size);
104
105    virtual ssize_t allocate(size_t size, uint32_t flags = 0);
106    virtual ssize_t deallocate(size_t offset);
107    virtual size_t  size() const;
108
109private:
110    struct chunk_t {
111        chunk_t(size_t start, size_t size)
112            : start(start), size(size), free(1), prev(0), next(0) {
113        }
114        size_t              start;
115        size_t              size : 28;
116        int                 free : 4;
117        mutable chunk_t*    prev;
118        mutable chunk_t*    next;
119    };
120
121    ssize_t  alloc(size_t size, uint32_t flags);
122    chunk_t* dealloc(size_t start);
123
124    static const int    kMemoryAlign;
125    mutable Locker      mLock;
126    LinkedList<chunk_t> mList;
127    size_t              mHeapSize;
128};
129
130#endif /* GRALLOC_ALLOCATOR_H_ */
131