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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
/* ScummVM - Graphic Adventure Engine
*
* ScummVM is the legal property of its developers, whose names
* are too numerous to list here. Please refer to the COPYRIGHT
* file distributed with this source distribution.
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*
* $URL$
* $Id$
*
*/
/* Heap-like managed structure */
#ifndef SCI_ENGINE_HEAPMGR_H
#define SCI_ENGINE_HEAPMGR_H
#include "sci/tools.h"
#include "sci/sci_memory.h"
namespace Sci {
#define HEAPENTRY_INVALID -1
// FIXME: We write (i == 0 || i > 0) instead of (i >= 0) to silence certain annoying warnings:
// generated by GCC: "comparison is always true due to limited range of data type".
#define ENTRY_IS_VALID(t, i) ((i == 0 || i > 0) && (i) < (t)->max_entry && (t)->table[(i)].next_free == (i))
#define DECLARE_HEAPENTRY(ENTRY) \
struct ENTRY##Entry { \
int next_free; /* Only used for free entries */ \
ENTRY entry; \
}; \
\
struct ENTRY##Table { \
int entries_nr; /* Number of entries allocated */ \
int first_free; /* Beginning of a singly linked list for entries */ \
int entries_used; /* Statistical information */ \
int max_entry; /* Highest entry used */ \
ENTRY##Entry *table; \
}; \
\
void init_##ENTRY##_table(ENTRY##Table *table); \
int alloc_##ENTRY##_entry(ENTRY##Table *table); \
void free_##ENTRY##_entry(ENTRY##Table *table, int index);
#define DEFINE_HEAPENTRY_WITH_CLEANUP(ENTRY, INITIAL, INCREMENT, CLEANUP_FN) \
void init_##ENTRY##_table(ENTRY##Table *table) { \
table->entries_nr = INITIAL; \
table->max_entry = 0; \
table->entries_used = 0; \
table->first_free = HEAPENTRY_INVALID; \
table->table = (ENTRY##Entry *)sci_malloc(sizeof(ENTRY##Entry) * INITIAL);\
memset(table->table, 0, sizeof(ENTRY##Entry) * INITIAL); \
} \
\
void free_##ENTRY##_entry(ENTRY##Table *table, int index) { \
ENTRY##Entry *e = table->table + index; \
\
if (index < 0 || index >= table->max_entry) { \
fprintf(stderr, "heapmgr: Attempt to release" \
" invalid table index %d!\n", index); \
BREAKPOINT(); \
} \
CLEANUP_FN(&(e->entry)); \
\
e->next_free = table->first_free; \
table->first_free = index; \
table->entries_used--; \
} \
\
int alloc_##ENTRY##_entry(ENTRY##Table *table) { \
table->entries_used++; \
if (table->first_free != HEAPENTRY_INVALID) { \
int oldff = table->first_free; \
table->first_free = table->table[oldff].next_free; \
\
table->table[oldff].next_free = oldff; \
return oldff; \
} else { \
if (table->max_entry == table->entries_nr) { \
table->entries_nr += INCREMENT; \
\
table->table = (ENTRY##Entry *)sci_realloc(table->table,\
sizeof(ENTRY##Entry) * table->entries_nr);\
memset(&table->table[table->entries_nr-INCREMENT], 0, INCREMENT * sizeof(ENTRY##Entry));\
} \
table->table[table->max_entry].next_free = table->max_entry; /* Tag as 'valid' */\
return table->max_entry++; \
} \
}
#define _HEAPENTRY_IGNORE_ME(x)
#define DEFINE_HEAPENTRY(e, i, p) DEFINE_HEAPENTRY_WITH_CLEANUP(e, i, p, _HEAPENTRY_IGNORE_ME)
} // End of namespace Sci
#endif // SCI_ENGINE_HEAPMGR_H
|
