1 // utility functions
2 // Copyright (C) 2005-2012 Tim Blechmann
3 //
4 // This program is free software; you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation; either version 2 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program; see the file COPYING. If not, write to
16 // the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 // Boston, MA 02111-1307, USA.
18
19 #pragma once
20
21 #include <cstddef>
22 #include <cassert>
23
24 #include <type_traits>
25
26 #include <boost/checked_delete.hpp>
27 #include <boost/intrusive_ptr.hpp>
28 #include <boost/noncopyable.hpp>
29 #include <boost/detail/atomic_count.hpp>
30
31 #include "branch_hints.hpp"
32
33 typedef unsigned int uint;
34
35 #include "function_attributes.h"
36
37
38 namespace nova {
39
40 /* we're using some member of the boost namespace */
41 using boost::intrusive_ptr;
42
43 /* some basic math functions */
ispoweroftwo(int i)44 inline bool ispoweroftwo(int i) { return (i & (i - 1)) == 0; }
45
46
47 template <unsigned int n> struct is_power_of_two {
48 static const bool val = (n % 2 == 0) && (is_power_of_two<(n >> 1)>::val);
49 };
50
51 template <> struct is_power_of_two<2> { static const bool val = true; };
52
log2(int n)53 inline int log2(int n) {
54 if (unlikely(n <= 0))
55 return (0);
56
57 #ifdef __GNUC__
58 return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(n);
59 #else
60 int r = -1;
61 while (n) {
62 r++;
63 n >>= 1;
64 }
65 return r;
66 #endif
67 }
68
nextpoweroftwo(int n)69 inline int nextpoweroftwo(int n) {
70 n = n - 1;
71 const uint bitspace = sizeof(int) * 8 / 2;
72 for (uint i = 1; i != bitspace; i *= 2)
73 n = n | (n >> i);
74
75 return n + 1;
76 }
77
78 using std::size_t;
79
80 /** \brief base class for a callback function */
81 template <typename t> class runnable {
82 public:
83 virtual ~runnable(void) = default;
84
85 virtual t run(void) = 0;
86 };
87
88
89 template <class T> struct default_deleter {
operator ()nova::default_deleter90 void operator()(T* t) { delete t; }
91 };
92
93 struct delayed_deleter {
94 template <typename T> inline void operator()(T*);
95 };
96
97 struct checked_deleter {
operator ()nova::checked_deleter98 template <class T> void operator()(T* x) const { boost::checked_delete(x); }
99 };
100
101
102 template <typename deleter = checked_deleter> struct intrusive_refcountable : public deleter {
intrusive_refcountablenova::intrusive_refcountable103 intrusive_refcountable(void): use_count_(0) {}
104
105 intrusive_refcountable(intrusive_refcountable const& rhs) = delete;
106 intrusive_refcountable& operator=(intrusive_refcountable const& rhs) = delete;
107
108 virtual ~intrusive_refcountable(void) = default;
109
add_refnova::intrusive_refcountable110 void add_ref(void) { ++use_count_; }
111
releasenova::intrusive_refcountable112 void release(void) {
113 if (--use_count_ == 0)
114 deleter::operator()(this);
115 }
116
intrusive_ptr_add_ref(intrusive_refcountable * p)117 inline friend void intrusive_ptr_add_ref(intrusive_refcountable* p) { p->add_ref(); }
118
intrusive_ptr_release(intrusive_refcountable * p)119 inline friend void intrusive_ptr_release(intrusive_refcountable* p) { p->release(); }
120
121 boost::detail::atomic_count use_count_;
122 };
123
124 template <class t, class compare = std::less<t>> struct compare_by_instance {
operator ()nova::compare_by_instance125 bool operator()(const t* lhs, const t* rhs) {
126 assert(lhs and rhs);
127 compare cmp;
128 return cmp(*lhs, *rhs);
129 }
130 };
131
132
string_hash(const char * str)133 PURE inline std::size_t string_hash(const char* str) {
134 std::size_t ret = 0;
135
136 // sdbm hash ... later try another function!
137 int c;
138 while ((c = *str++))
139 ret = c + (ret << 6) + (ret << 16) - ret;
140
141 return ret;
142 }
143
144 struct linear_allocator {
linear_allocatornova::linear_allocator145 linear_allocator(char* chunk): chunk(chunk) {}
146
allocnova::linear_allocator147 template <typename T> T* alloc(int count = 1) {
148 T* ret = reinterpret_cast<T*>(chunk);
149 chunk += count * sizeof(T);
150 return ret;
151 }
152
153 private:
154 char* chunk;
155 };
156
157 } /* namespace nova */
158