blob: e32e5e9c66dfd9566405999c0d64d3e5dbeaacf8 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
// file : xsde/cxx/stack.hxx
// author : Boris Kolpackov <boris@codesynthesis.com>
// copyright : Copyright (c) 2005-2011 Code Synthesis Tools CC
// license : GNU GPL v2 + exceptions; see accompanying LICENSE file
#ifndef XSDE_CXX_STACK_HXX
#define XSDE_CXX_STACK_HXX
#include <stddef.h> // size_t
#include <xsde/cxx/config.hxx>
namespace xsde
{
namespace cxx
{
// POD stack with pre-allocated first element. You may
// need to pad your elements to get the proper alignment.
//
struct stack
{
#ifndef XSDE_EXCEPTIONS
enum error
{
error_none,
error_no_memory
};
#endif
~stack ();
stack (size_t element_size, void* first_element);
private:
stack (stack&);
stack& operator= (stack&);
public:
void
pop ();
#ifdef XSDE_EXCEPTIONS
void
#else
error
#endif
push ();
void*
top ();
void
clear ();
bool
empty () const;
// Note: expensive, non-inline function.
//
size_t
size () const;
size_t
element_size () const;
private:
#ifdef XSDE_EXCEPTIONS
void
#else
error
#endif
push_impl ();
private:
// The stack is implemented as a doubly-linked list of memory
// regions. The first region is special since it is the single,
// pre-allocated element. It also doesn't have the embedded
// 'next' and 'prev' fields. Instead, the next_ member is used
// for this purpose. The memory blocks have fixed sizes: 1, 8,
// 16, ... elements.
//
struct block
{
block* prev;
block* next;
//char data[0]; Sufficiently padded (2 * sizeof(void*)).
};
size_t el_size_; // Element size in bytes.
block* cur_; // Current block (the first element if cap_ == 1).
block* next_; // Next block of the special first block.
size_t cap_; // Capacity of the current block in elements.
size_t num_; // Number of elements in the current block.
};
}
}
#include <xsde/cxx/stack.ixx>
#endif // XSDE_CXX_STACK_HXX
|
