Eli   Documents
Eli: Translator Construction Made Easy

General Information

o Eli: Translator Construction Made Easy
o Global Index
o Frequently Asked Questions
o Typical Eli Usage Errors

Tutorials

o Quick Reference Card
o Guide For new Eli Users
o Release Notes of Eli
o Tutorial on Name Analysis
o Tutorial on Scope Graphs
o Tutorial on Type Analysis
o Typical Eli Usage Errors

Reference Manuals

o User Interface
o Eli products and parameters
o LIDO Reference Manual
o Typical Eli Usage Errors

Libraries

o Eli library routines
o Specification Module Library

Translation Tasks

o Lexical analysis specification
o Syntactic Analysis Manual
o Computation in Trees

Tools

o LIGA Control Language
o Debugging Information for LIDO
o Graphical ORder TOol

o FunnelWeb User's Manual

o Pattern-based Text Generator
o Property Definition Language
o Operator Identification Language
o Tree Grammar Specification Language
o Command Line Processing
o COLA Options Reference Manual

o Generating Unparsing Code

o Monitoring a Processor's Execution

Administration

o System Administration Guide
Mail Home

Library Reference

Previous Chapter Next Chapter Table of Contents

Memory Object Management

This module provides high-speed memory allocation that supports "growing" objects -- objects whose size is not known a priori. Any number of regions can be defined, and storage managed independently by region. Within one region the storage is allocated and freed in a last-in, first-out manner that allows freeing of a large number of objects with a single operation. 

#include "obstack.h"

void obstack_init(ObstackP obstack);
void obstack_begin(ObstackP obstack, int size);
int obstack_chunk_size(ObstackP obstack);
int obstack_alignment_mask(ObstackP obstack);




void *obstack_alloc(ObstackP obstack, int size);
void *obstack_copy(ObstackP obstack, void *data, int size);
void *obstack_copy0(ObstackP obstack, void *data, int size);
void *obstack_strcpy(ObstackP obstack, char *data);




void obstack_blank(ObstackP obstack, int size);
void obstack_grow(ObstackP obstack, void *data, int size);
void obstack_grow0(ObstackP obstack, void *data, int size);
void obstack_1grow(ObstackP obstack, int data_char);
void obstack_ptr_grow(ObstackP obstack, void *data);
void obstack_int_grow(ObstackP obstack, int data);






void obstack_blank_fast(ObstackP obstack, int size);
void obstack_1grow_fast(ObstackP obstack, int data_char);
void obstack_ptr_grow_fast(ObstackP obstack, void *data);
void obstack_int_grow_fast(ObstackP obstack, int data);




void *obstack_finish(ObstackP obstack);

void obstack_free(ObstackP obstack, void *block);

void *obstack_base(ObstackP obstack);
void *obstack_next_free(ObstackP obstack);
int obstack_object_size(ObstackP obstack);
int obstack_room(ObstackP obstack);

Each region is represented by a data structure of type Obstack. A pointer of type ObstackP, which addresses this data structure, is used to specify the region. Here is an example showing how a region might be declared and initialized: 

Obstack obstk;

obstack_init(&obstk);

All the apparent functions operating on regions are macros. Each takes a pointer of type ObstackP as its first argument. This pointer may be evaluated many times, so you should not use an expression as the first argument of any of these macros. (Any arguments other than the first are evaluated exactly once.) If you need to compute the appropriate ObstackP, use the following strategy: 

_obstack = (address expression); obstack_xxx(_obstack, ...);

The variable _obstack is of type ObstackP, and is exported by the module for use by clients. Its value is never inspected or changed by the module itself or any of the macros.

A region is a collection of objects managed in a last-in, first-out manner. Each region is independent of the others, and is characterized by a chunk size and an alignment. As objects are added to the collection, blocks of memory of the given chunk size are allocated to hold them. The address of each object in the collection is guaranteed to be divisible by the alignment, which must be a power of 2.

When the storage already available for a collection is insufficient for an object being added to the collection, then a new chunk is allocated. The size of the new chunk is the minimum of the chunk size parameter and twice the size of the object to be added. Thus the chunk size parameter does not limit the size of an object that can be stored in the collection, but it does affect the number of system requests for storage. If it is not specified when the collection is initialized, a default value equivalent to one virtual memory page is used. Chunks are normally allocated by malloc or realloc, but you can substitute a different storage allocator by re-defining the macros obstack_chunk_alloc and obstack_chunk_realloc to be the names of your allocator functions. Be certain that your allocator copes with memory exhaustion. Give the macro definition before including the module interface specification: 

#define obstack_chunk_alloc MyMalloc
#include "obstack.h"

After an object is added to a collection, the next available address is adjusted to be divisible by the alignment parameter of the collection. If any address is suitable as an object address then the alignment should be 1 (the zeroth power of 2). The default alignment value is that suitable for an object of the primitive type double, normally the type that is most stringently aligned.

The first macro applied to a region must be either obstack_init or obstack_begin, both of which create an empty collection of objects. A collection initialized by obstack_init will have the default value for its chunk size, while obstack_begin allows the user to set that value. If the size argument of the obstack_begin call is 0 then the default value is used. This value may be inspected or changed at any time via the operation obstack_chunk_size. Similarly, the default alignment mask may be inspected or changed at any time via the operation obstack_alignment_mask. These two macros may be called either on the left side of an assignment (to change the value) or within an expression (to inspect the value). If the chunk size is changed, it can be returned to its default value by assigning the value 0 to obstack_chunk_size: 

obstack_chunk_size(&obstk) = 0;

The alignment mask is an integer one less than the power of 2 that must divide each object address. To make a change in the alignment mask effective, you must create an empty object. For example, the following code guarantees that the addresses of objects subsequently created in the collection obstk will be divisible by 4: 

obstack_alignment_mask(&obstk) = 3; (void)obstack_alloc(&obstk, 0);

Once a region has been initialized, there are two basic strategies for creating objects: allocation and growth. Objects are allocated when their size is known a priori; they are grown when their size is not known a priori.

Allocation is the simplest strategy. Suppose that it was necessary to create an object capable of storing an array of five integers. The call (int *)obstack_alloc(&MyStack, 5 * sizeof(int)) would create such an object in the collection MyStack, and yield a pointer to that object. The contents of the created object are undefined. If an array of five integers was already stored in the variable ArrayValue, and this array was to be the initial contents of the created object, then the call (int *)obstack_copy(&MyStack, ArrayValue, 5 * sizeof(int)) would create and initialize an appropriate object. The operation obstack_copy0 is identical to obstack_copy, except that it adds a single zero byte after the value that was copied. An object whose initial contents are to be the characters of an existing null-terminated string should be created by the operation obstack_strcpy. This operation does not require a length specification; it determines the length from the given string.

With the growth strategy, a single object is created by a sequence of macro calls rather than a single call. Each call causes the object to grow in size, and possibly establishes some of the initial contents of the object. An object can be moved by the module while that object is growing. The last call in the sequence is to either obstack_finish or some allocation operation, which terminates the object's growth and fixes its address.

An obstack can only accomodate a single growing object at any time. While that object is growing, no allocation operations may be issued for the obstack. After obstack_finish has been called, completing the growth of the object, the obstack is again able to accept any operation. Thus the legal sequence of operations on an obstack can be described by the following regular expression (A stands for an allocation operation and G stands for a growth operation): 

obstack_init ( A | G+ ( obstack_finish | A ) )*

Macros implementing the growth strategy parallel, for the most part, the macros implementing the allocation strategy. They have the same pattern of arguments as their allocation counterparts, but do not return a pointer to an object because no object exists until the call of obstack_finish. To grow an object by a given amount without specifying the initial contents of that part of the object, use obstack_blank. If an initial contents is known, grow the object with one of the operations obstack_grow or obstack_grow0 as appropriate.

The special operation obstack_1grow is used for placing characters into a growing object. It's argument is the actual value that is the initial content, rather than the address of that value as in the other growth and allocation macros. Here is an example of how obstack_strcpy could be implemented using obstack_1grow: 

char *
obstack_strcpy(obstk, data)
ObstackP obstk; char *data;
{ register char c, *p = data;
  if (p) while (c = *p++) obstack_1grow(obstk, c);
  obstack_1grow(obstk, '\0');
  return (char *)obstack_finish(obstk);
}

The growth macros check that the current chunk has enough space in it for the growth increment. If the check fails, a new chunk is allocated and the growing object is copied into the new chunk. Two additional operations, obstack_blank_fast and obstack_1grow_fast, can be used when sufficient space in the current chunk can be guaranteed. These macros are identical to their normal counterparts obstack_blank and obstack_1grow, except that they do not check the space remaining in the current chunk. The operation obstack_room returns the amount of free space in the current chunk.

The collection of objects in a region is managed in a last-in, first-out manner. This means that there is an operation, obstack_free, to remove objects from the collection. A call of obstack_free specifies a region and an object in that region. This call removes the specified object and all objects added to the collection after the specified object was added.

If an obstack_free operation frees all of the objects in a chunk, that chunk is returned to the underlying storage allocator. Chunks are normally returned by free, but you can specify a different routine by re-defining the macro obstack_chunk_free to be the name of that routine. (The macros obstack_chunk_alloc, obstack_chunk_realloc and obstack_chunk_free must be defined consistently.)

While an object is being grown, its current base address can be obtained by calling the macro obstack_base, its current size by calling obstack_object_size, and the address of the first location above it by calling obstack_next_free. This allows one to build a module that will give clients access to the contents of an immature object while it is still growing. Don't forget that the base address will change during the growth period if the object outgrows the current chunk. Also, obstack_next_free can be used on the left-hand side of an assignment, thereby providing a way to "shrink" a growing object. Its value should never be increased, nor should it be decreased beyond the value yielded by obstack_base.

Previous Chapter Next Chapter Table of Contents