Panda3D
simpleAllocator.h
Go to the documentation of this file.
1 /**
2  * PANDA 3D SOFTWARE
3  * Copyright (c) Carnegie Mellon University. All rights reserved.
4  *
5  * All use of this software is subject to the terms of the revised BSD
6  * license. You should have received a copy of this license along
7  * with this source code in a file named "LICENSE."
8  *
9  * @file simpleAllocator.h
10  * @author drose
11  * @date 2007-05-12
12  */
13 
14 #ifndef SIMPLEALLOCATOR_H
15 #define SIMPLEALLOCATOR_H
16 
17 #include "pandabase.h"
18 #include "linkedListNode.h"
19 #include "pmutex.h"
20 #include "mutexHolder.h"
21 
23 
24 /**
25  * An implementation of a very simple block allocator. This class can
26  * allocate ranges of nonnegative integers within a specified upper limit; it
27  * uses a simple first-fit algorithm to find the next available space.
28  */
29 class EXPCL_PANDA_GOBJ SimpleAllocator : public LinkedListNode {
30 PUBLISHED:
31  INLINE explicit SimpleAllocator(size_t max_size, Mutex &lock);
32  SimpleAllocator(SimpleAllocator &&from) noexcept;
33  virtual ~SimpleAllocator();
34 
35  INLINE SimpleAllocatorBlock *alloc(size_t size, size_t alignment=1);
36 
37  INLINE bool is_empty() const;
38  INLINE size_t get_total_size() const;
39  INLINE size_t get_max_size() const;
40  INLINE void set_max_size(size_t max_size);
41  INLINE size_t get_contiguous() const;
42 
43  INLINE SimpleAllocatorBlock *get_first_block() const;
44 
45  void output(std::ostream &out) const;
46  void write(std::ostream &out) const;
47 
48 protected:
49  SimpleAllocatorBlock *do_alloc(size_t size, size_t alignment=1);
50  INLINE bool do_is_empty() const;
51 
52  virtual SimpleAllocatorBlock *make_block(size_t start, size_t size);
53  INLINE void mark_contiguous(const LinkedListNode *block);
54  virtual void changed_contiguous();
55 
56 protected:
57 /*
58  * This is implemented as a linked-list chain of allocated blocks. Free
59  * blocks are implicit. Blocks are kept in sorted order from beginning to
60  * end. Allocating a block means creating a new entry in the chain wherever
61  * it may fit; freeing a block means simply removing the allocated block from
62  * the chain. With this simple approach, there is no need to merge adjacent
63  * free blocks to straighten out fragmentation, since free blocks are not
64  * stored. However, it does mean we have to walk through a list of adjacent
65  * allocated blocks in order to find the free blocks.
66  */
67  size_t _total_size;
68  size_t _max_size;
69 
70  // This is what we currently believe our max contiguous space to be. This
71  // guess might be larger than the actual available space, but it will not be
72  // smaller.
73  size_t _contiguous;
74 
75  // This mutex protects all operations within this class. The caller must
76  // pass the reference to a mutex in to the constructor, and the caller
77  // remains responsible for owning the mutex. This allows the mutex to be
78  // shared where appropriate.
79 
80  // A derived class may also use it to protect itself as well, but take care
81  // to call do_alloc() instead of alloc() etc. as necessary.
82  Mutex &_lock;
83 
84  friend class SimpleAllocatorBlock;
85 };
86 
87 /**
88  * A single block as returned from SimpleAllocator::alloc().
89  */
90 class EXPCL_PANDA_GOBJ SimpleAllocatorBlock : public LinkedListNode {
91 protected:
93  size_t start, size_t size);
94 
95 public:
96  SimpleAllocatorBlock() = default;
97  SimpleAllocatorBlock(const SimpleAllocatorBlock &copy) = delete;
99 
100  SimpleAllocatorBlock &operator = (const SimpleAllocatorBlock &copy) = delete;
101  INLINE SimpleAllocatorBlock &operator = (SimpleAllocatorBlock &&from);
102 
103 PUBLISHED:
104  INLINE ~SimpleAllocatorBlock();
105  INLINE void free();
106 
107  INLINE SimpleAllocator *get_allocator() const;
108 
109  INLINE size_t get_start() const;
110  INLINE size_t get_size() const;
111  INLINE bool is_free() const;
112 
113  INLINE size_t get_max_size() const;
114  INLINE bool realloc(size_t size);
115 
116  INLINE SimpleAllocatorBlock *get_next_block() const;
117 
118  void output(std::ostream &out) const;
119 
120 protected:
121  INLINE void do_free();
122  INLINE size_t do_get_max_size() const;
123  INLINE bool do_realloc(size_t size);
124 
125 private:
126  SimpleAllocator *_allocator = nullptr;
127  size_t _start = 0;
128  size_t _size = 0;
129 
130  friend class SimpleAllocator;
131 };
132 
133 INLINE std::ostream &operator << (std::ostream &out, const SimpleAllocator &obj) {
134  obj.output(out);
135  return out;
136 }
137 
138 INLINE std::ostream &operator << (std::ostream &out, const SimpleAllocatorBlock &obj) {
139  obj.output(out);
140  return out;
141 }
142 
143 #include "simpleAllocator.I"
144 
145 #endif
This just stores the pointers to implement a doubly-linked list of some kind of object.
A standard mutex, or mutual exclusion lock.
Definition: pmutex.h:40
A single block as returned from SimpleAllocator::alloc().
An implementation of a very simple block allocator.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.