/* File: struct_manager.h
** Author(s): Ernie Johnson
** Contact: xsb-contact@cs.sunysb.edu
**
** Copyright (C) The Research Foundation of SUNY, 1986, 1993-1998
**
** XSB is free software; you can redistribute it and/or modify it under the
** terms of the GNU Library General Public License as published by the Free
** Software Foundation; either version 2 of the License, or (at your option)
** any later version.
**
** XSB 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 Library General Public License for
** more details.
**
** You should have received a copy of the GNU Library General Public License
** along with XSB; if not, write to the Free Software Foundation,
** Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**
** $Id: struct_manager.h,v 1.4 2000/10/05 17:23:17 ejohnson Exp $
**
*/
#ifndef STRUCTURE_MANAGER
#define STRUCTURE_MANAGER
/*===========================================================================*/
/*
* Generic Block-Oriented Data Structure Management
* ================================================
*
* The following structure and macros provide a uniform method for
* managing pools of data structures allocated from the system by block
* (rather than individually). By following a few guidelines, the
* implementation of any such structure with this desired allocation
* property is simplified.
*
* Interface:
* ---------
* - SM_InitDecl(StructType,StructsPerBlock,StructNameString)
* - SM_AllocateStruct(SM,pNewStruct)
* - SM_DeallocateStruct(SM,pStruct)
* - SM_DeallocateStructList(SM,pHead,pTail)
* - SM_CurrentCapacity(SM,NumBlocks,NumStructs)
* - SM_CountFreeStructs(SM,NumFree)
* - SM_RawUsage(SM,TotalBlockUsageInBytes)
* - SM_ReleaseResources(SM)
*
* Management Organization:
* -----------------------
* Blocks of structures (records) are allocated from the system, one at a
* time, and maintained on a linked list. The head of this list is the
* most recently allocated block and the one from which individual records
* are parceled out. Deallocated records -- ones which were
* previously-allocated but then returned to the Manager -- are maintained
* in a list for reallocation. Priority is given to these previously-used
* structures during the allocation process. The first word of a block,
* as well as that in a deallocated record, is used as a link for chaining
* these objects in their respective lists. This has implications both
* for the layout of a block and managed records. Ramafications for the
* latter extend only to how one wishes to return records to the Manager
* for reallocation: one-at-a-time or list-at-a-time (see below). The
* allocation of a block occurs on a needs basis. Its overall size is
* determined by the number and size of the records it is to hold. For
* convenience, a field for chaining allocated structures is also
* provided. Note, however, that the responsibility of maintaining this
* list rests solely with the user (read client). Four additional macros
* are provided for aiding in its maintenance, but it is up to the user to
* apply them, and in a reasonable way. Not all records will require this
* feature, and so this field and these macros can be safely ignored.
*
* Use:
* ---
* To use, observe the following guidelines:
*
* 1) Declare a Structure_Manager variable for your data structure AND
* initialize it statically using the macro SM_InitDecl(). Provide
* the macro with the type of your record, the number you wish it to
* allocate at once, and a string which contains the name of the
* structure. For example:
*
* Structure_Manager mySM = SM_InitDecl(int,5,"C integer");
*
* 2) To obtain a new structure from your Manager, make a call to
* SM_AllocateStruct():
*
* SM_AllocateStruct(mySM,pNewStruct)
*
* If chaining of allocated structures is desired, then one can use
* macros SM_AddToAllocList_SL/DL to add the returned record to the
* head of this list. One must define field-access macro(s) to the
* link field(s) of this record type for use by these list-creating
* macros.
*
* 3) If mass deallocation of a list of records is desired, then make
* the first field in your record the link field for supporting the
* list. You may then use macro SM_DeallocateStructList():
*
* SM_DeallocateStructList(mySM,pListHead,pListTail)
*
* Otherwise, you'll have to deallocate them one at a time using
* SM_DeallocateStruct(). If these structs are maintained on the
* allocation chain of the Structure Manager, then they should be
* removed BEFORE the deallocation. One may find the macros
* SM_RemoveFromAllocList_SL/DL helpful for this...
*
* 4) Get info about the state of the Manager using routines
* SM_CurrentCapacity(), SM_CountFreeStructs(), and SM_RawUsage().
*
* 5) Releasing the resources of the Structure Manager returns the blocks
* to the system and resets some of its fields.
*
* 6) With possibly the exception of the allocated-record-chain field,
* avoid direct manipulatiion of the Structure Manager! Use the
* provided interface routines.
*/
typedef struct Structure_Manager {
struct { /* Current block descriptor: */
void *pBlock; /* - current block; head of block chain */
void *pNextStruct; /* - next available struct in current block */
void *pLastStruct; /* - last struct in current block */
} cur_block;
struct { /* Structure characteristics: */
size_t size; /* - size of the structure in bytes */
counter num; /* - number of records per block */
char *name; /* - short description of the struct type */
} struct_desc;
struct { /* Lists of structures: */
void *alloc; /* - convenience hook, not directly maintained */
void *dealloc; /* - deallocated structs, poised for reuse */
} struct_lists;
} Structure_Manager;
/* Macro Short-Hands (mainly for "internal" use)
----------------- */
#define SM_CurBlock(SM) ((SM).cur_block.pBlock)
#define SM_NextStruct(SM) ((SM).cur_block.pNextStruct)
#define SM_LastStruct(SM) ((SM).cur_block.pLastStruct)
#define SM_StructSize(SM) ((SM).struct_desc.size)
#define SM_StructsPerBlock(SM) ((SM).struct_desc.num)
#define SM_StructName(SM) ((SM).struct_desc.name)
#define SM_AllocList(SM) ((SM).struct_lists.alloc)
#define SM_FreeList(SM) ((SM).struct_lists.dealloc)
#define SM_NewBlockSize(SM) /* in bytes */ \
( sizeof(void *) + SM_StructSize(SM) * SM_StructsPerBlock(SM) )
#define SM_CurBlockIsDepleted(SM) \
( IsNULL(SM_CurBlock(SM)) || (SM_NextStruct(SM) > SM_LastStruct(SM)) )
#define SM_NumStructsLeftInBlock(SM) \
( ! SM_CurBlockIsDepleted(SM) \
? ( ((char *)SM_LastStruct(SM) - (char *)SM_NextStruct(SM)) \
/ SM_StructSize(SM) + 1 ) \
: 0 )
#define SM_AllocateFree(SM,pNewStruct) \
pNewStruct = SM_FreeList(SM); \
SM_FreeList(SM) = SMFL_NextFreeStruct(SM_FreeList(SM))
#define SM_AllocateFromBlock(SM,pNewStruct) \
pNewStruct = SM_NextStruct(SM); \
SM_NextStruct(SM) = SMBlk_NextStruct(SM_NextStruct(SM),SM_StructSize(SM))
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
extern void smPrint(Structure_Manager, char *);
extern void smAllocateBlock(Structure_Manager *);
extern void smFreeBlocks(Structure_Manager *);
extern xsbBool smIsValidStructRef(Structure_Manager, void *);
extern xsbBool smIsAllocatedStruct(Structure_Manager, void *);
extern xsbBool smIsAllocatedStructRef(Structure_Manager, void *);
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/* Manipulating the Free List
-------------------------- */
#define SMFL_NextFreeStruct(pFreeStruct) ( *(void **)(pFreeStruct) )
/* Manipulating Allocation Block
----------------------------- */
#define SMBlk_NextBlock(pBlock) ( *(void **)(pBlock) )
#define SMBlk_FirstStruct(pBlock) ( (char *)pBlock + sizeof(void *) )
#define SMBlk_LastStruct(pBlock,StructSize,StructsPerBlock) \
( SMBlk_FirstStruct(pBlock) + StructSize * (StructsPerBlock - 1) )
#define SMBlk_NextStruct(pStruct,StructSize) ( (char *)pStruct + StructSize )
/*-------------------------------------------------------------------------*/
/* Primary Interface Routines
========================== */
/*
* For initialization at declaration time.
*/
#define SM_InitDecl(StructType,StructsPerBlock,NameString) { \
{NULL, NULL, NULL}, \
{sizeof(StructType), StructsPerBlock, NameString}, \
{NULL, NULL} \
}
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/*
* Allocate a structure from the Structure Manager.
*/
#define SM_AllocateStruct(SM,pStruct) { \
\
if ( IsNonNULL(SM_FreeList(SM)) ) { \
SM_AllocateFree(SM,pStruct); \
} \
else { \
if ( SM_CurBlockIsDepleted(SM) ) \
smAllocateBlock(&SM); \
SM_AllocateFromBlock(SM,pStruct); \
} \
}
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/*
* To deallocate a chain of structures -- of the same type -- at once,
* they must ALREADY be linked using the first word in the structure,
* since this conforms with the manner in which records on the free
* chain are maintained. Head and Tail are relative to the ordering
* imposed by this first-word linkage. Otherwise, each structure in
* the chain must be deallocated individually.
*/
#define SM_DeallocateStructList(SM,pHead,pTail) { \
SMFL_NextFreeStruct(pTail) = SM_FreeList(SM); \
SM_FreeList(SM) = pHead; \
}
#define SM_DeallocateStruct(SM,pStruct) \
SM_DeallocateStructList(SM,pStruct,pStruct)
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/*
* Query the manager for the number of allocated blocks and the total
* number of records they hold.
*/
#define SM_CurrentCapacity(SM,NumBlocks,NumStructs) { \
\
void *pBlock; \
\
NumBlocks = 0; \
for ( pBlock = SM_CurBlock(SM); IsNonNULL(pBlock); \
pBlock = SMBlk_NextBlock(pBlock) ) \
NumBlocks++; \
NumStructs = NumBlocks * SM_StructsPerBlock(SM); \
}
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/*
* Query the manager for the number of unallocated records it
* currently has.
*/
#define SM_CountFreeStructs(SM,NumFreeStructs) { \
\
void *pStruct; \
\
if ( IsNonNULL(SM_CurBlock(SM)) ) { \
NumFreeStructs = SM_NumStructsLeftInBlock(SM); \
for ( pStruct = SM_FreeList(SM); IsNonNULL(pStruct); \
pStruct = SMFL_NextFreeStruct(pStruct) ) \
NumFreeStructs++; \
} \
else \
NumFreeStructs = 0; \
}
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/*
* Query the manager for the total number of bytes it obtained from
* the system.
*/
#define SM_RawUsage(SM,UsageInBytes) { \
\
void *pBlock; \
\
UsageInBytes = 0; \
for ( pBlock = SM_CurBlock(SM); IsNonNULL(pBlock); \
pBlock = SMBlk_NextBlock(pBlock) ) \
UsageInBytes = UsageInBytes + SM_NewBlockSize(SM); \
}
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/*
* Return all memory blocks to the system.
*/
#define SM_ReleaseResources(SM) smFreeBlocks(&SM)
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/*
* Place a newly allocated record on the "in use" list, maintained as
* either a singly- or doubly-linked (SL/DL) list.
*/
#define SM_AddToAllocList_SL(SM,pRecord,LinkFieldMacro) { \
LinkFieldMacro(pRecord) = SM_AllocList(SM); \
SM_AllocList(SM) = pRecord; \
}
#define SM_AddToAllocList_DL(SM,pRecord,PrevFieldMacro,NextFieldMacro) { \
PrevFieldMacro(pRecord) = NULL; \
NextFieldMacro(pRecord) = SM_AllocList(SM); \
SM_AllocList(SM) = pRecord; \
if ( IsNonNULL(NextFieldMacro(pRecord)) ) \
PrevFieldMacro(NextFieldMacro(pRecord)) = pRecord; \
}
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/*
* Prepare a record for deallocation by removing it from the "in use" list.
*/
#define SM_RemoveFromAllocList_SL(SM,pRecord,LinkFieldMacro,RecordType) { \
\
RecordType pCur, pPrev; \
\
for ( pPrev = NULL, pCur = SM_AllocList(SM); \
IsNonNULL(pCur); \
pPrev = pCur, pCur = LinkFieldMacro(pCur) ) \
if ( pCur == pRecord ) \
break; \
if ( IsNonNULL(pCur) ) { \
if ( IsNonNULL(pPrev) ) \
LinkFieldMacro(pPrev) = LinkFieldMacro(pCur); \
else \
SM_AllocList(SM) = LinkFieldMacro(pCur); \
LinkFieldMacro(pCur) = NULL; \
} \
else \
xsb_warn("Record not present in given Structure Manager: %s", \
SM_StructName(SM)); \
}
#define SM_RemoveFromAllocList_DL(SM,pRecord,PrevFieldMacro,NextFieldMacro) { \
if ( IsNonNULL(PrevFieldMacro(pRecord)) ) \
NextFieldMacro(PrevFieldMacro(pRecord)) = NextFieldMacro(pRecord); \
else { \
if ( SM_AllocList(SM) == pRecord ) \
SM_AllocList(SM) = NextFieldMacro(pRecord); \
else \
xsb_abort("Record not present in given Structure Manager: %s", \
SM_StructName(SM)); \
} \
if ( IsNonNULL(NextFieldMacro(pRecord)) ) \
PrevFieldMacro(NextFieldMacro(pRecord)) = PrevFieldMacro(pRecord); \
NextFieldMacro(pRecord) = PrevFieldMacro(pRecord) = NULL; \
}
/*===========================================================================*/
#endif
syntax highlighted by Code2HTML, v. 0.9.1