4 * @copyright Copyright (C) 2016 Sproute Networks, Inc.
6 * @author Avneesh Sachdev <avneesh@sproute.com>
8 * This file is part of Quagga.
10 * Quagga is free software; you can redistribute it and/or modify it
11 * under the terms of the GNU General Public License as published by the
12 * Free Software Foundation; either version 2, or (at your option) any
15 * Quagga is distributed in the hope that it will be useful, but
16 * WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 * General Public License for more details.
20 * You should have received a copy of the GNU General Public License
21 * along with Quagga; see the file COPYING. If not, write to the Free
22 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
27 * Header file for the linear allocator.
29 * An allocator that allocates memory by walking down towards the end
30 * of a buffer. No attempt is made to reuse blocks that are freed
31 * subsequently. The assumption is that the buffer is big enough to
32 * cover allocations for a given purpose.
40 * Alignment for block allocated by the allocator. Must be a power of 2.
42 #define LINEAR_ALLOCATOR_ALIGNMENT 8
44 #define LINEAR_ALLOCATOR_ALIGN(value) \
45 (((value) + LINEAR_ALLOCATOR_ALIGNMENT - 1) & ~(LINEAR_ALLOCATOR_ALIGNMENT - 1));
48 * linear_allocator_align_ptr
51 linear_allocator_align_ptr (char *ptr)
53 return (char *) LINEAR_ALLOCATOR_ALIGN ((intptr_t) ptr);
56 typedef struct linear_allocator_t_
61 * Current location in the buffer.
71 * Version number of the allocator, this is bumped up when the allocator
72 * is reset and helps identifies bad frees.
77 * The number of blocks that are currently allocated.
83 * linear_allocator_block_t
85 * Header structure at the begining of each block.
87 typedef struct linear_allocator_block_t_
92 * The version of the allocator when this block was allocated.
96 } linear_allocator_block_t;
98 #define LINEAR_ALLOCATOR_BLOCK_IN_USE 0x01
100 #define LINEAR_ALLOCATOR_HDR_SIZE (sizeof(linear_allocator_block_t))
103 * linear_allocator_block_size
105 * The total amount of space a block will take in the buffer,
106 * including the size of the header.
109 linear_allocator_block_size (size_t user_size)
111 return LINEAR_ALLOCATOR_ALIGN (LINEAR_ALLOCATOR_HDR_SIZE + user_size);
115 * linear_allocator_ptr_to_block
117 static inline linear_allocator_block_t *
118 linear_allocator_ptr_to_block (void *ptr)
121 block_ptr = ((char *) ptr) - offsetof (linear_allocator_block_t, data);
126 * linear_allocator_init
129 linear_allocator_init (linear_allocator_t * allocator, char *buf,
132 memset (allocator, 0, sizeof (*allocator));
134 assert (linear_allocator_align_ptr (buf) == buf);
135 allocator->buf = buf;
136 allocator->cur = buf;
137 allocator->end = buf + buf_len;
141 * linear_allocator_reset
143 * Prepare an allocator for reuse.
145 * *** NOTE ** This implicitly frees all the blocks in the allocator.
148 linear_allocator_reset (linear_allocator_t *allocator)
150 allocator->num_allocated = 0;
151 allocator->version++;
152 allocator->cur = allocator->buf;
156 * linear_allocator_alloc
159 linear_allocator_alloc (linear_allocator_t *allocator, size_t user_size)
162 linear_allocator_block_t *block;
164 block_size = linear_allocator_block_size (user_size);
166 if (allocator->cur + block_size > allocator->end)
171 block = (linear_allocator_block_t *) allocator->cur;
172 allocator->cur += block_size;
174 block->flags = LINEAR_ALLOCATOR_BLOCK_IN_USE;
175 block->version = allocator->version;
176 allocator->num_allocated++;
181 * linear_allocator_free
184 linear_allocator_free (linear_allocator_t *allocator, void *ptr)
186 linear_allocator_block_t *block;
188 if (((char *) ptr) < allocator->buf || ((char *) ptr) >= allocator->end)
194 block = linear_allocator_ptr_to_block (ptr);
195 if (block->version != allocator->version)
201 block->flags = block->flags & ~LINEAR_ALLOCATOR_BLOCK_IN_USE;
203 if (--allocator->num_allocated < 0)