1
/* This file is part of Malaga, a system for Natural Language Analysis.
2
* Copyright (C) 1995-1999 Bjoern Beutel
5
* Universitaet Erlangen-Nuernberg
6
* Abteilung fuer Computerlinguistik
9
* e-mail: malaga@linguistik.uni-erlangen.de
11
* This program is free software; you can redistribute it and/or modify
12
* it under the terms of the GNU General Public License as published by
13
* the Free Software Foundation; either version 2 of the License, or
14
* (at your option) any later version.
16
* This program is distributed in the hope that it will be useful,
17
* but WITHOUT ANY WARRANTY; without even the implied warranty of
18
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19
* GNU General Public License for more details.
21
* You should have received a copy of the GNU General Public License
22
* along with this program; if not, write to the Free Software
23
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
25
/* description ==============================================================*/
27
/* This module defines a new data type, "pool_t", for growing vectors of items
28
* of an arbitrary type.
29
* A pool is a linked list of chunks which are of fixed size once allocated. */
31
/* includes =================================================================*/
44
/* constants ================================================================*/
46
#define MIN_CHUNK_SIZE 400
47
/* the minimum number of the data table in a chunk */
49
/* macros ===================================================================*/
51
#define CHUNK_DATA(chunk_ptr) ((u_byte_t *) ((chunk_ptr) + 1))
52
/* Use this macro to access the data in a chunk. */
54
/* types ====================================================================*/
56
typedef struct CHUNK_T
58
int_t chunk_size; /* the maximum number of items in this chunk */
59
int_t num_items; /* the actual number of items in this chunk */
60
struct CHUNK_T *next; /* the next chunk in the pool */
61
int_t pad; /* pad to the next 8-byte boundary */
62
/* items follow here */
65
/* the pool implementation type
66
* (use "new_pool" before you use any other functions on a pool variable) */
69
int_t item_size; /* size of the items that are stored in this pool */
70
int_t num_items; /* the overall number of items stored in this pool */
71
int_t chunk_size; /* the size of new chunks */
72
chunk_t *first_chunk; /* first chunk of this pool */
73
chunk_t *current_chunk; /* the chunk where items will currently be stored
74
* (note this isn't necessarily the last chunk) */
77
/* functions ================================================================*/
79
GLOBAL pool_t new_pool (int_t item_size)
80
/* Create a new pool that records items of size <item_size>. */
82
pool_t pool = new_mem (sizeof (struct POOL_T));
84
pool->item_size = item_size;
86
pool->chunk_size = MIN_CHUNK_SIZE / item_size;
87
pool->first_chunk = NULL;
88
pool->current_chunk = NULL;
93
/*---------------------------------------------------------------------------*/
95
GLOBAL void clear_pool (pool_t pool)
96
/* Clear <pool> (do not free any memory used by the pool). */
98
chunk_t *current_chunk;
100
for (current_chunk = pool->first_chunk;
101
current_chunk != NULL;
102
current_chunk = current_chunk->next)
103
current_chunk->num_items = 0;
106
pool->current_chunk = pool->first_chunk;
109
/*---------------------------------------------------------------------------*/
111
GLOBAL void *pool_to_vector (pool_t pool)
112
/* Return <pool> as a C vector (contiguous memory).
113
* The vector can be freed with "free" after use. */
115
void *vector = new_vector (pool->item_size, pool->num_items);
116
u_byte_t *chunk; /* position where next chunk is to be copied */
117
chunk_t *current_chunk;
119
/* Collect all chunks in a new vector */
120
chunk = (u_byte_t *) vector;
121
for (current_chunk = pool->first_chunk;
122
current_chunk != NULL;
123
current_chunk = current_chunk->next)
125
memcpy (chunk, CHUNK_DATA (current_chunk),
126
pool->item_size * current_chunk->num_items);
127
chunk += pool->item_size * current_chunk->num_items;
128
if (current_chunk == pool->current_chunk)
129
/* Only chunks up to <pool_i>->current_chunk have items in them. */
136
/*---------------------------------------------------------------------------*/
138
GLOBAL void write_pool (pool_t pool, FILE *stream, string_t file_name)
139
/* Write <pool> to <stream> (<file_name> is given for error messages). */
141
chunk_t *current_chunk;
143
/* Collect all chunks to the new vector. */
144
for (current_chunk = pool->first_chunk;
145
current_chunk != NULL;
146
current_chunk = current_chunk->next)
148
write_vector (CHUNK_DATA (current_chunk), pool->item_size,
149
current_chunk->num_items, stream, file_name);
150
if (current_chunk == pool->current_chunk)
151
/* Only chunks up to <pool_i>->current_chunk have items in them. */
156
/*---------------------------------------------------------------------------*/
158
GLOBAL void *get_pool_space (pool_t pool, int_t num_items, int_t *index)
159
/* Get space for <num_items> contiguous items in pool <pool>,
160
* return its address as the function's result and the index in *<index>,
161
* if <index> != NULL. */
163
void *new_ptr; /* pointer to the pool space */
164
chunk_t **chunk_ptr; /* address of a chunk pointer */
166
/* Find the first chunk that is big enough. */
167
for (chunk_ptr = &pool->current_chunk;
169
&& (*chunk_ptr)->num_items + num_items > (*chunk_ptr)->chunk_size;
170
chunk_ptr = &(*chunk_ptr)->next)
174
/* If we haven't found a chunk that fits, allocate a new one. */
175
if (*chunk_ptr == NULL)
177
if (pool->chunk_size < num_items)
178
pool->chunk_size = num_items;
180
*chunk_ptr = new_mem (sizeof (chunk_t)
181
+ pool->item_size * pool->chunk_size);
182
(*chunk_ptr)->chunk_size = pool->chunk_size;
183
(*chunk_ptr)->num_items = 0;
184
(*chunk_ptr)->next = NULL;
186
/* If this is the first chunk allocated, save its address. */
187
if (pool->first_chunk == NULL)
188
pool->first_chunk = *chunk_ptr;
191
/* Remember address and index of current position in pool. */
192
new_ptr = (void *) (CHUNK_DATA (*chunk_ptr)
193
+ pool->item_size * (*chunk_ptr)->num_items);
195
*index = pool->num_items;
197
/* Adjust indices. */
198
(*chunk_ptr)->num_items += num_items;
199
pool->num_items += num_items;
201
pool->current_chunk = *chunk_ptr;
206
/*---------------------------------------------------------------------------*/
208
GLOBAL int_t pool_items (pool_t pool)
209
/* Return the number of the items in <pool>. */
211
return pool->num_items;
214
/*---------------------------------------------------------------------------*/
216
GLOBAL void *pool_item (pool_t pool, int_t index)
217
/* Return the address of item with <index> in pool <pool>,
218
* or NULL if there is no such item. */
222
if (index < 0 || index >= pool->num_items)
225
/* Find the right chunk. */
226
chunk = pool->first_chunk;
227
while (index >= chunk->num_items)
229
index -= chunk->num_items;
233
/* Return the address of the item. */
234
return CHUNK_DATA (chunk) + pool->item_size * index;
237
/*---------------------------------------------------------------------------*/
239
GLOBAL int_t pool_index (pool_t pool, void *item)
240
/* Return the index of <item> in <pool>.
241
* Report an error if <item> doesn't exist in <pool>. */
245
u_byte_t *item_i = (u_byte_t *) item;
248
for (chunk = pool->first_chunk; chunk != NULL; chunk = chunk->next)
250
if (item_i >= CHUNK_DATA (chunk)
251
&& item_i < CHUNK_DATA (chunk) + pool->item_size * chunk->num_items)
252
return index + (item_i - CHUNK_DATA (chunk)) / pool->item_size;
254
index += chunk->num_items;
256
error ("item doesn't exist in chunk");
259
/*---------------------------------------------------------------------------*/
261
GLOBAL void *copy_to_pool (pool_t pool,
265
/* Copy the vector *<ptr> of length <num_items> into <pool>.
266
* The items of *<ptr> must be of same size as the items in <pool>.
267
* Return the address of the copy as the function's result and the
268
* index in *<index>, if <index> != NULL. */
270
void *new_ptr = get_pool_space (pool, num_items, index);
272
/* Copy the data into the pool. */
273
memcpy (new_ptr, ptr, pool->item_size * num_items);
278
/*---------------------------------------------------------------------------*/
280
GLOBAL string_t copy_string_to_pool (pool_t pool,
283
/* Copy the string <string> into <pool>, which must be a string pool.
284
* Return the copy of the string as the function's result as well as
285
* its index in *<index>, if <index> != NULL. */
287
return (string_t) (copy_to_pool (pool, (void *) string,
288
strlen (string) + 1, index));
291
/*---------------------------------------------------------------------------*/
293
GLOBAL void free_pool (pool_t *pool)
294
/* Free all memory used by <*pool>. */
296
chunk_t *chunk, *next_chunk;
301
/* Free all chunks of this pool. */
302
for (chunk = (*pool)->first_chunk; chunk != NULL; chunk = next_chunk)
304
next_chunk = chunk->next;
311
/* end of file ==============================================================*/