L4Re Operating System Framework
Interface and Usage Documentation
Loading...
Searching...
No Matches
item_alloc
Go to the documentation of this file.
1// -*- Mode: C++ -*-
2// vim:ft=cpp
7/*
8 * (c) 2008-2009 Adam Lackorzynski <adam@os.inf.tu-dresden.de>,
9 * Alexander Warg <warg@os.inf.tu-dresden.de>
10 * economic rights: Technische Universität Dresden (Germany)
11 *
12 * This file is part of TUD:OS and distributed under the terms of the
13 * GNU General Public License 2.
14 * Please see the COPYING-GPL-2 file for details.
15 *
16 * As a special exception, you may use this file as part of a free software
17 * library without restriction. Specifically, if other files instantiate
18 * templates or use macros or inline functions from this file, or you compile
19 * this file and link it with other files to produce an executable, this
20 * file does not by itself cause the resulting executable to be covered by
21 * the GNU General Public License. This exception does not however
22 * invalidate any other reasons why the executable file might be covered by
23 * the GNU General Public License.
24 */
25
26#pragma once
27
28#include <l4/cxx/bitmap>
29
30namespace L4Re { namespace Util {
31
33using cxx::Bitmap;
34
39{
40private:
41 long _capacity;
42 long _free_hint;
43 Bitmap_base _bits;
44
45 void hint(long hint)
46 { __atomic_store_n(&_free_hint, hint, __ATOMIC_RELAXED); }
47
48public:
49 bool is_allocated(long item) const noexcept
50 { return _bits[item]; }
51
52 long hint() const { return __atomic_load_n(&_free_hint, __ATOMIC_RELAXED); }
53
54 bool alloc(long item) noexcept
55 {
56 return !_bits.atomic_get_and_set(item);
57 }
58
59 void free(long item) noexcept
60 {
61 if (item < hint())
62 hint(item);
63
64 _bits.atomic_clear_bit(item);
65 }
66
67 Item_alloc_base(long size, void *mem) noexcept
68 : _capacity(size), _free_hint(0), _bits(mem)
69 {}
70
71 long alloc() noexcept
72 {
73 long free_hint = hint();
74
75 for (long i = free_hint; i < _capacity; ++i)
76 if (alloc(i))
77 {
78 hint(i + 1);
79 return i;
80 }
81
82 // _free_hint is not necessarily correct in case of multi-threading! Make
83 // sure we don't miss any potentially free slots.
84 for (long i = 0; i < free_hint && i < _capacity; ++i)
85 if (alloc(i))
86 {
87 hint(i + 1);
88 return i;
89 }
90
91 return -1;
92 }
93
94 long size() const noexcept
95 {
96 return _capacity;
97 }
98};
99
100template< long Bits >
101class Item_alloc : public Item_alloc_base
102{
103private:
104 typename Bitmap_base::Word<Bits>::Type _bits[Bitmap_base::Word<Bits>::Size];
105
106public:
107 Item_alloc() noexcept : Item_alloc_base(Bits, _bits) {}
108};
109
110}}
Helper abstraction for a word contained in the bitmap.
Definition bitmap:91
Basic bitmap abstraction.
Definition bitmap:30
void atomic_clear_bit(long bit) noexcept
Clear bit bit atomically.
Definition bitmap:280
word_type atomic_get_and_set(long bit) noexcept
Set bit bit atomically and return old state.
Definition bitmap:319
A static bitmap.
Definition bitmap:232
L4Re C++ Interfaces.
Definition l4re.dox:17