/* 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