/* librock/exec/struct/fsil.c version Copyright (c) 2001-2002, Forrest J. Cavalier III, doing business as Mib Software, Saylorsburg Pennsylvania USA Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. Neither the name of the author nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifdef librock_NOTLIBROCK /**************************************************************/ /* ABOUT THIS FILE: GUIDE TO QUICK REUSE WITHOUT REWORK This file uses many preprocessor conditional blocks and features to publish http://www.mibsoftware.com/librock/ You can disable those features with little or no editing, and reuse this file: 1. At compile time, enable this conditional block by defining the preprocessor symbol librock_NOTLIBROCK, either with a compiler command line parameter, or as a #define in a source file which then #includes this source file. 2. Define any preprocessor symbols in this block (if any) appropriately for your machine and compilation environment. 3. Copy and use the declarations from this block in your source files as appropriate. This file is originally from the librock library, which is Free (libre), free (no cost), rock-stable API, and works on gcc/MSVC/Windows/Linux/BSD/more. Get originals, updates, license certificates, more, at http://www.mibsoftware.com/librock/ (Change log appears at end of this file.) */ #define librock_ISOLATED #define librock_assert(a) #define librock_PRIVATE #define librock_PTR #define librock_CONST const #include #include struct librock_FSIL_s { /* Fixed size item list */ struct librock_FSIL_s librock_PTR *flink; int inseg; /* number in this FSIL */ int isize; int grow; /* Also: max allowed in this FSIL segment */ int shrink; }; /**************************************************************/ #endif #ifndef librock_ISOLATED /**************************************************************/ #define librock_IMPLEMENT_fsil #include #include #ifndef librock_assert #include #define librock_assert assert #endif #include #include /**************************************************************/ #endif #ifdef librock_IMPL_LIDESC #ifndef librock_NOIMPL_LIDESC_fsil /**************************************************************/ #include /* librock_LIDESC_HC=12440211096131f5976d36be0cddca4cd9152e45 */ void *librock_LIDESC_fsil[] = { "\n" __FILE__ librock_LIDESC_librock "\n", 0 }; /**************************************************************/ #endif #endif #ifndef librock_WRAP /**************************************************************/ #define librock_body_FSILnew librock_FSILnew #define librock_body_FSILdelete librock_FSILdelete #define librock_body_FSILdeleteAt librock_FSILdeleteAt #define librock_body_FSILinsertAt librock_FSILinsertAt #define librock_body_FSILpoint librock_FSILpoint #define librock_body_FSILinsertcopyAt librock_FSILinsertcopyAt #define librock_body_FSILitemcount librock_FSILitemcount /* librock_PRIVATE */ #define librock_body_FSILsplit librock_FSILsplit /* librock_PRIVATE */ #define librock_body__NewFSIL librock__NewFSIL /* librock_PRIVATE */ #define librock_body_FSILfindsegment librock_FSILfindsegment /* librock_PRIVATE */ #define librock_body_FSILshrink librock_FSILshrink /**************************************************************/ #endif #ifndef librock_NOIMPL__NewFSIL /**************************************************************/ librock_PRIVATE struct librock_FSIL_s librock_PTR *librock_body__NewFSIL(void librock_PTR *related,int isize,int grow,int shrink) { struct librock_FSIL_s librock_PTR *newfsil; librock_assert(isize); /* if (grow * (long) isize + sizeof(struct FSIL) < 1024) { grow = 1024 - sizeof(struct FSIL) / isize; } */ if (grow < 16) { grow = 16; } /* if ((long) grow * isize > 65536) { grow = (int) (64000L / isize); } */ newfsil = (struct librock_FSIL_s librock_PTR *) malloc(grow*isize+sizeof(*newfsil)); if (newfsil) { newfsil->flink = 0; newfsil->isize = isize; newfsil->grow = grow; if (shrink >= grow) { shrink = grow / 2; } newfsil->shrink = shrink; newfsil->inseg = 0; } else { /* assert(mib_fheapchk(related) == _HEAPOK); */ } return newfsil; } /* NewFSIL */ /**************************************************************/ #endif /* NOIMP section */ #ifndef librock_NOIMPL_FSILnew /**************************************************************/ struct librock_FSIL_s librock_PTR *librock_body_FSILnew(int isize,int grow,int shrink) {/* Copyright 1998-2001, Forrest J. Cavalier III d-b-a Mib Software Licensed under BSD-ish license, NO WARRANTY. Copies must retain this block. License, originals, details: http://www.mibsoftware.com/librock/ */ #ifdef librock_MANUAL_FSILnew /* librock_FSILnew - Create a fixed-size item list (FSIL). Integer indexed storage for fixed-size items. librock_FSILdelete - Deallocate all memory used by an FSIL. librock_FSILpoint - Return a temporary pointer to an indexed item. librock_FSILinsertAt - Insert an item at index, or end of list. librock_FSILinsertcopyAt - Insert and initialize an item at index, or end of list. librock_FSILdeleteAt - Delete an item at index librock_FSILitemcount - Return number of items in an librock_FSIL. */ /**/ #include struct librock_FSIL_s * librock_body_FSILnew( int isize,int grow,int shrink ); void librock_body_FSILdelete( struct librock_FSIL_s librock_PTR *m ); void * librock_body_FSILpoint( struct librock_FSIL_s librock_PTR *m, long index ); int librock_body_FSILdeleteAt( struct librock_FSIL_s librock_PTR *m, long index ); void * librock_body_FSILinsertcopyAt( struct librock_FSIL_s *m, long index, void *init) /* These routines implement storage for a list of fixed-size items accessed by integer index. Items can be inserted and deleted from the list, which may move items around in memory. Memory allocations using malloc() are "pooled" so that a block of malloc()ed memory is used to store more than one item. Call librock_FSILnew() to create the FSIL. isize is the item size. If grow is not 0 the blocks requested from malloc() will hold grow number of items. See librock_FSILdeleteAt() for a description of the shrink parameter. The return value is the parameter to give to other librock_FSIL functions. Call librock_FSILdelete() to free() all memory used by the FSIL obtained by calling librock_FSILnew(). Call librock_FSILpoint() to obtain a pointer to the memory block of the indexed item. The returned pointer is stale (invalid) after the next call to any function which inserts or deletes items (which can move items in memory.) Call librock_FSILinsertAt() to insert items. A pointer to storage for the indexed item is returned. Use -1 to append at the end of the list. The returned pointer is stale (invalid) after the next call to any function which inserts or deletes items (which can move items in memory.) Use librock_FSILinsertcopyAt() to insert an item and initialize with a copy of an existing memory block. Use -1 to append at the end of the list. Call librock_FSILdeleteAt() to delete items. If shrink was not 0 and smaller than grow for the call to librock_FSILnew() then a check is made to coalesce blocks so that there are fewer than shrink items spare in each block. Excess blocks are free()d. librock_FSILdeleteAt returns 0 if successful, non-zero if the index is invalid. Call librock_FSILitemcount() to count the number of items presently in the FSIL. Typical use is */ #ifdef librock_TYPICAL_USE_FSIL #include struct mystruct_s { int member; } *p; struct librock_FSIL_s *pfsil = librock_FSILnew( /*item size=*/ sizeof(*p), /*blocks hold=*/ 16, /*spare per block=*/ 3); p = librock_FSILinsertAt(pfsil,-1); if (!p) { /* ERROR HANDLING */ } p->member = 0; /* ... */ p = librock_FSILinsertcopyAt(pfsil,-1,p); p->member = 1; /* ... */ while(librock_FSILitemcount(pfsil)) { p = (struct mystruct_s *) librock_FSILpoint(pfsil,0); printf("%d\n",p->member); librock_FSILdeleteAt(pfsil,0); } librock_FSILdelete(pfsil); #endif /* malloc() free() memmove() memcpy() */ /* Copyright 1998-2002 Forrest J. Cavalier III, http://www.mibsoftware.com Licensed under BSD-ish license, NO WARRANTY. Copies must retain this block. License text in librock_LIDESC_HC=12440211096131f5976d36be0cddca4cd9152e45 */ #endif /* MANUAL */ /*-------------------------------------------*/ return librock__NewFSIL(0,isize,grow,shrink); } /* NewFSIL */ /**************************************************************/ #endif /* NOIMP section */ #ifndef librock_NOIMPL_FSILdelete /**************************************************************/ void librock_body_FSILdelete(struct librock_FSIL_s librock_PTR *m) {/* Copyright 1998-2001, Forrest J. Cavalier III d-b-a Mib Software Licensed under BSD-ish license, NO WARRANTY. Copies must retain this block. License, originals, details: http://www.mibsoftware.com/librock/ */ /*-------------------------------------------*/ struct librock_FSIL_s librock_PTR *next; while(m) { next = m->flink; free(m); m = next; } } /**************************************************************/ #endif /* NOIMP section */ #ifndef librock_NOIMPL_FSILfindsegment /**************************************************************/ librock_PRIVATE struct librock_FSIL_s librock_PTR *librock_body_FSILfindsegment(struct librock_FSIL_s librock_PTR *walk,long librock_PTR *index) { if (*index < 0) { return 0; } while(walk) { if (walk->inseg > *index) { /* It is here. */ return walk; } if ((walk->inseg == *index)&&(!walk->flink)) { return walk; } *index -= walk->inseg; /* Advance to next. */ walk = walk->flink; } return walk; } /* findFSILsegment */ /**************************************************************/ #endif /* NOIMP section */ #ifndef librock_NOIMPL_FSILshrink /**************************************************************/ librock_PRIVATE void librock_body_FSILshrink(struct librock_FSIL_s librock_PTR *m) { /* shrink/combine */ /* Try to ensure that there are fewer than shrink blocks extra. */ /* First see how much space is available */ int space = 0; struct librock_FSIL_s librock_PTR *walk = m; int cSeg = 0; struct librock_FSIL_s librock_PTR **pSeg; int iSw; if (!m->shrink) { return; /* Do not shrink */ } while(walk) { if (walk->grow - walk->inseg > m->shrink) { space += walk->grow - walk->inseg - m->shrink; } walk = walk->flink; cSeg++; } if (space < m->grow) { return; /* Don't bother. Coalescing will not result in an empty segment */ } /* Create a list for fast index */ pSeg = malloc(cSeg * sizeof(walk)); if (!pSeg) { return; } walk = m; iSw = 0; while(walk) { pSeg[iSw] = walk; walk = walk->flink; iSw++; } iSw = 0; while(iSw < cSeg) { int iSr = iSw+1; int ir = 0; walk = pSeg[iSw]; if (!walk->flink) { goto done; } if (!walk->flink->inseg) { walk->flink = walk->flink->flink; free(pSeg[iSw+1]); goto done; } if (walk->grow - walk->inseg > m->shrink) { int cCopy = walk->grow - walk->inseg - m->shrink; /* Copy in, from iSr,ir */ if (ir + cCopy > pSeg[iSr]->inseg) { cCopy = pSeg[iSr]->inseg - ir; } memmove((char *) (walk+1)+walk->inseg*walk->isize, (char *) (pSeg[iSr]+1)+ir*walk->isize, cCopy * walk->isize); ir += cCopy; walk->inseg += cCopy; if (ir == pSeg[iSr]->inseg) { /* segment following is empty */ pSeg[iSr-1]->flink = pSeg[iSr]->flink; free(pSeg[iSr]); goto done; } } if (ir) { /* Fix iSr, where some items were copied out */ walk = pSeg[iSr]; memmove((char *) (walk+1),(char *) (walk+1)+ir*walk->isize,(walk->inseg - ir) *walk->isize); walk->inseg -= ir; } iSw++; } done:; free(pSeg); } /* FSILshrink */ /**************************************************************/ #endif /* NOIMP section */ #ifndef librock_NOIMPL_FSILpoint /**************************************************************/ void librock_PTR *librock_body_FSILpoint(struct librock_FSIL_s librock_PTR *m,long index) { /* Copyright 1998-2001, Forrest J. Cavalier III d-b-a Mib Software Licensed under BSD-ish license, NO WARRANTY. Copies must retain this block. License, originals, details: http://www.mibsoftware.com/librock/ */ struct librock_FSIL_s librock_PTR *walk; walk = librock_FSILfindsegment(m,&index); if (!walk || (index >= walk->inseg)) { return 0; } return (char librock_PTR *) (walk + 1) + index * walk->isize; } /* FSILpoint */ /**************************************************************/ #endif /* NOIMP section */ #ifndef librock_NOIMPL_FSILdeleteAt /**************************************************************/ int librock_body_FSILdeleteAt(struct librock_FSIL_s librock_PTR *m,long index) { /* Copyright 1998-2001, Forrest J. Cavalier III d-b-a Mib Software Licensed under BSD-ish license, NO WARRANTY. Copies must retain this block. License, originals, details: http://www.mibsoftware.com/librock/ */ struct librock_FSIL_s librock_PTR *walk; char librock_PTR *ptr; walk = librock_FSILfindsegment(m,&index); if (!walk) { return -1; } /* Copy the items backwards */ ptr = (char librock_PTR *) (walk + 1) + index * walk->isize; if (index < walk->inseg) { memmove(ptr,ptr + walk->isize, (int) (walk->inseg - index) * walk->isize); } walk->inseg--; if (walk->grow - walk->inseg >= walk->shrink) { librock_FSILshrink(m); } return 0; } /* FSILdelete */ /**************************************************************/ #endif /* NOIMP section */ #ifndef librock_NOIMPL_FSILsplit /**************************************************************/ librock_PRIVATE void librock_body_FSILsplit(struct librock_FSIL_s librock_PTR *walk) { /* Helper function for FSILinsert */ struct librock_FSIL_s librock_PTR *newf; int half; newf = librock__NewFSIL(walk,walk->isize,walk->grow,walk->shrink); if (!newf) { return; /* Mem alloc error */ } newf->flink = walk->flink; walk->flink = newf; /* Copy half */ half = walk->inseg/2; memmove((char librock_PTR *) (newf + 1), (char librock_PTR *) (walk + 1) + (long) half * walk->isize, (int) (walk->inseg - half) * walk->isize); walk->inseg -= half; newf->inseg = half; } /* splitFSIL */ /**************************************************************/ #endif /* NOIMP section */ #ifndef librock_NOIMPL_FSILinsertAt /**************************************************************/ void librock_PTR *librock_body_FSILinsertAt(struct librock_FSIL_s librock_PTR *m,long index) { /* Call with -1 to insert at end */ /* Copyright 1998-2001, Forrest J. Cavalier III d-b-a Mib Software Licensed under BSD-ish license, NO WARRANTY. Copies must retain this block. License, originals, details: http://www.mibsoftware.com/librock/ */ struct librock_FSIL_s librock_PTR *walk; char librock_PTR *ptr; long ind; if (index == -1) { index =0; walk = m; while(walk) { index += walk->inseg; walk = walk->flink; } } ind = index; walk = librock_FSILfindsegment(m,&ind); if (!walk) { return 0; } /* If there is no room, then must split */ if (walk->inseg >= walk->grow) { librock_FSILsplit(walk); ind = index; walk = librock_FSILfindsegment(m,&ind); if (!walk || (walk->inseg >= walk->grow)) { return 0; /* mem alloc error */ } } /* copy to make room */ ptr = (char librock_PTR *) (walk + 1) + (long) walk->isize * ind; if (ind < walk->inseg) { /* Added test 6-5-95 */ memmove(ptr + walk->isize,ptr,(walk->inseg - (int) ind) * walk->isize); } walk->inseg++; return ptr; } /* FSILinsertAt */ /**************************************************************/ #endif /* NOIMP section */ #ifndef librock_NOIMPL_FSILinsertcopyAt /**************************************************************/ void librock_PTR *librock_body_FSILinsertcopyAt(struct librock_FSIL_s librock_PTR *m, long index,void librock_PTR *init) {/* Copyright 1998-2001, Forrest J. Cavalier III d-b-a Mib Software Licensed under BSD-ish license, NO WARRANTY. Copies must retain this block. License, originals, details: http://www.mibsoftware.com/librock/ */ char librock_PTR *ptr; ptr = (char librock_PTR *) librock_FSILinsertAt(m,index); if (ptr) { memcpy(ptr,init,m->isize); } return ptr; } /* FSILinsertcopyAt */ /**************************************************************/ #endif /* NOIMP section */ #ifndef librock_NOIMPL_FSILitemcount /**************************************************************/ long librock_body_FSILitemcount(struct librock_FSIL_s librock_PTR *walk) {/* Copyright 1998-2001, Forrest J. Cavalier III d-b-a Mib Software Licensed under BSD-ish license, NO WARRANTY. Copies must retain this block. License, originals, details: http://www.mibsoftware.com/librock/ */ long ret = 0; while(walk) { ret += walk->inseg; /* Advance to next. */ walk = walk->flink; } return ret; } /**************************************************************/ #endif /* NOIMP section */ /* $Log: fsil.c,v $ Revision 1.6 2002/08/02 04:03:17 forrest@mibsoftware.com rights=#1 Use librock_assert instead of assert. (1 place) Updated TYPICAL_USE section. Added NOTLIBROCK section. Moved CVS log to end. Changed LIDESC MD5 to HC. Revision 1.5 2002/04/09 03:33:28 forrest@mibsoftware.com rights=#1 Updated LICENSE in manual. Revision 1.4 2002/02/07 17:12:56 forrest@mibsoftware.com rights=#1 Fix LIDESC Revision 1.3 2002/02/06 14:09:36 forrest@mibsoftware.com rights=#1 Standardized chg log Revision 1.2 2002/01/30 16:07:55 forrest@mibsoftware.com rights=#1 Renamed some .h files Revision 1.1 2002/01/29 14:24:37 forrest@mibsoftware.com rights=#1 initial rights#1 Copyright (c) Forrest J Cavalier III d-b-a Mib Software rights#1 License text in librock_LIDESC_HC=12440211096131f5976d36be0cddca4cd9152e45 */