1<?xml version="1.0" encoding="UTF-8" standalone="no"?>
2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Chapter��21.��The bitmap_allocator</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.78.1" /><meta name="keywords" content="ISO C++, allocator" /><meta name="keywords" content="ISO C++, library" /><meta name="keywords" content="ISO C++, runtime, library" /><link rel="home" href="../index.html" title="The GNU C++ Library" /><link rel="up" href="extensions.html" title="Part��III.�� Extensions" /><link rel="prev" href="mt_allocator_ex_multi.html" title="Multiple Thread Example" /><link rel="next" href="bitmap_allocator_impl.html" title="Implementation" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter��21.��The bitmap_allocator</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="mt_allocator_ex_multi.html">Prev</a>��</td><th width="60%" align="center">Part��III.��
3  Extensions
4  
5</th><td width="20%" align="right">��<a accesskey="n" href="bitmap_allocator_impl.html">Next</a></td></tr></table><hr /></div><div class="chapter"><div class="titlepage"><div><div><h2 class="title"><a id="manual.ext.allocator.bitmap"></a>Chapter��21.��The bitmap_allocator</h2></div></div></div><div class="toc"><p><strong>Table of Contents</strong></p><dl class="toc"><dt><span class="section"><a href="bitmap_allocator.html#allocator.bitmap.design">Design</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html">Implementation</a></span></dt><dd><dl><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.free_list_store">Free List Store</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.super_block">Super Block</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.super_block_data">Super Block Data Layout</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.max_wasted">Maximum Wasted Percentage</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.allocate"><code class="function">allocate</code></a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.deallocate"><code class="function">deallocate</code></a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.questions">Questions</a></span></dt><dd><dl><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.question.1">1</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.question.2">2</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.question.3">3</a></span></dt></dl></dd><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.locality">Locality</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.grow_policy">Overhead and Grow Policy</a></span></dt></dl></dd></dl></div><p>
6</p><div class="section"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="allocator.bitmap.design"></a>Design</h2></div></div></div><p>
7    As this name suggests, this allocator uses a bit-map to keep track
8    of the used and unused memory locations for its book-keeping
9    purposes.
10  </p><p>
11    This allocator will make use of 1 single bit to keep track of
12    whether it has been allocated or not. A bit 1 indicates free,
13    while 0 indicates allocated. This has been done so that you can
14    easily check a collection of bits for a free block. This kind of
15    Bitmapped strategy works best for single object allocations, and
16    with the STL type parameterized allocators, we do not need to
17    choose any size for the block which will be represented by a
18    single bit. This will be the size of the parameter around which
19    the allocator has been parameterized. Thus, close to optimal
20    performance will result. Hence, this should be used for node based
21    containers which call the allocate function with an argument of 1.
22  </p><p>
23    The bitmapped allocator's internal pool is exponentially growing.
24    Meaning that internally, the blocks acquired from the Free List
25    Store will double every time the bitmapped allocator runs out of
26    memory.
27  </p><p>
28    The macro <code class="literal">__GTHREADS</code> decides whether to use
29    Mutex Protection around every allocation/deallocation. The state
30    of the macro is picked up automatically from the gthr abstraction
31    layer.
32  </p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="mt_allocator_ex_multi.html">Prev</a>��</td><td width="20%" align="center"><a accesskey="u" href="extensions.html">Up</a></td><td width="40%" align="right">��<a accesskey="n" href="bitmap_allocator_impl.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Multiple Thread Example��</td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top">��Implementation</td></tr></table></div></body></html>