| 125 |
theseven |
1 |
#ifndef INCLUDED_tlsfbits
|
|
|
2 |
#define INCLUDED_tlsfbits
|
|
|
3 |
|
|
|
4 |
#include "../../global.h"
|
|
|
5 |
|
|
|
6 |
#if defined(__cplusplus)
|
|
|
7 |
#define tlsf_decl inline
|
|
|
8 |
#else
|
|
|
9 |
#define tlsf_decl static
|
|
|
10 |
#endif
|
|
|
11 |
|
|
|
12 |
/*
|
|
|
13 |
** Architecture-specific bit manipulation routines.
|
|
|
14 |
**
|
|
|
15 |
** TLSF achieves O(1) cost for malloc and free operations by limiting
|
|
|
16 |
** the search for a free block to a free list of guaranteed size
|
|
|
17 |
** adequate to fulfill the request, combined with efficient free list
|
|
|
18 |
** queries using bitmasks and architecture-specific bit-manipulation
|
|
|
19 |
** routines.
|
|
|
20 |
**
|
|
|
21 |
** Most modern processors provide instructions to count leading zeroes
|
|
|
22 |
** in a word, find the lowest and highest set bit, etc. These
|
|
|
23 |
** specific implementations will be used when available, falling back
|
|
|
24 |
** to a reasonably efficient generic implementation.
|
|
|
25 |
**
|
|
|
26 |
** NOTE: TLSF spec relies on ffs/fls returning value 0..31.
|
|
|
27 |
** ffs/fls return 1-32 by default, returning 0 for error.
|
|
|
28 |
*/
|
|
|
29 |
|
|
|
30 |
/*
|
|
|
31 |
** gcc 3.4 and above have builtin support, specialized for architecture.
|
|
|
32 |
** Some compilers masquerade as gcc; patchlevel test filters them out.
|
|
|
33 |
*/
|
|
|
34 |
|
|
|
35 |
|
|
|
36 |
tlsf_decl int tlsf_fls_generic(unsigned int word) ICODE_ATTR;
|
|
|
37 |
tlsf_decl int tlsf_fls_generic(unsigned int word)
|
|
|
38 |
{
|
|
|
39 |
int bit = 32;
|
|
|
40 |
|
|
|
41 |
if (!word) bit -= 1;
|
|
|
42 |
if (!(word & 0xffff0000)) { word <<= 16; bit -= 16; }
|
|
|
43 |
if (!(word & 0xff000000)) { word <<= 8; bit -= 8; }
|
|
|
44 |
if (!(word & 0xf0000000)) { word <<= 4; bit -= 4; }
|
|
|
45 |
if (!(word & 0xc0000000)) { word <<= 2; bit -= 2; }
|
|
|
46 |
if (!(word & 0x80000000)) { word <<= 1; bit -= 1; }
|
|
|
47 |
|
|
|
48 |
return bit;
|
|
|
49 |
}
|
|
|
50 |
|
|
|
51 |
/* Implement ffs in terms of fls. */
|
|
|
52 |
tlsf_decl int tlsf_ffs(unsigned int word) ICODE_ATTR;
|
|
|
53 |
tlsf_decl int tlsf_ffs(unsigned int word)
|
|
|
54 |
{
|
|
|
55 |
return tlsf_fls_generic(word & (~word + 1)) - 1;
|
|
|
56 |
}
|
|
|
57 |
|
|
|
58 |
tlsf_decl int tlsf_fls(unsigned int word) ICODE_ATTR;
|
|
|
59 |
tlsf_decl int tlsf_fls(unsigned int word)
|
|
|
60 |
{
|
|
|
61 |
return tlsf_fls_generic(word) - 1;
|
|
|
62 |
}
|
|
|
63 |
|
|
|
64 |
|
|
|
65 |
#undef tlsf_decl
|
|
|
66 |
|
|
|
67 |
#endif
|