/* * CDE - Common Desktop Environment * * Copyright (c) 1993-2012, The Open Group. All rights reserved. * * These libraries and programs are free software; you can * redistribute them and/or modify them under the terms of the GNU * Lesser General Public License as published by the Free Software * Foundation; either version 2 of the License, or (at your option) * any later version. * * These libraries and programs are distributed in the hope that * they will be useful, but WITHOUT ANY WARRANTY; without even the * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR * PURPOSE. See the GNU Lesser General Public License for more * details. * * You should have received a copy of the GNU Lesser General Public * License along with these libraries and programs; if not, write * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth * Floor, Boston, MA 02110-1301 USA */ /* * COMPONENT_NAME: austext * * FUNCTIONS: add_free_space * find_free_space * init_header * * ORIGINS: 27 * * (C) COPYRIGHT International Business Machines Corp. 1993,1995 * All Rights Reserved * US Government Users Restricted Rights - Use, duplication or * disclosure restricted by GSA ADP Schedule Contract with IBM Corp. */ /******************* FILEMAN.C ********************** * $XConsortium: fileman.c /main/8 1996/11/25 18:47:12 drk $ * September 1993. * Garbage collection algorithm: Fileman maintains * 2 tables at the front of the d99. They keep track of * small sized 'holes' (unique words that appear only * once in a record)and large holes of free space. * Only the N largest holes in each table are saved, * so some fragmentation still exists. This happens * particularly when a huge database is built from scratch. * As the size grows, more and more holes are discarded * because they are too small to handle any words as * the database grows. For this reason, mrclean should * be run at least once after the database grows to a * fairly good size, to recover the wasted space. Once the * database reaches its nominal size, the 2 tables are very * effective at recycling holes, so mrclean need not be * run for compression purposes. * * $Log$ * Revision 2.2 1995/10/24 22:09:25 miker * Add prolog. * * Revision 2.1 1995/09/22 20:05:50 miker * Freeze DtSearch 0.1, AusText 2.1.8 * * Revision 1.3 1995/09/05 17:27:37 miker * Names changes for DtSearch. */ #include "SearchP.h" #include #include #define PROGNAME "FILEMAN" #define HOLE_SIZE_LIMIT 500 DtSrINT32 batch_size = 0; /************************/ /* */ /* Init Header */ /* */ /************************/ /* Initialize file_header data, and write it at the beginning of a new file */ void init_header (FILE * fp, FILE_HEADER * flh) { memset (flh, 0, sizeof(FILE_HEADER)); fseek (fp, 0L, SEEK_SET); fwrite (flh, sizeof(FILE_HEADER), (size_t)1, fp); return; } /* init_header() */ /********************************/ /* */ /* fread_d99_header */ /* */ /********************************/ /* Reads d99 header structure from front of passed d99 file. * Performs byte swap as necessary IN PASSED BUFFER. * Returns TRUE if successful, else FALSE. */ int fread_d99_header (FILE_HEADER *flh, FILE *fp) { int i; errno = 0; fseek (fp, 0L, SEEK_SET); if (fread (flh, sizeof(FILE_HEADER), (size_t)1, fp) != 1L) return FALSE; NTOHL (flh->hole_count[0]); NTOHL (flh->hole_count[1]); for (i = 0; i < NUM_HOLES; i++) { NTOHL (flh->hole_array[0][i].hole_size); NTOHL (flh->hole_array[0][i].offset); NTOHL (flh->hole_array[1][i].hole_size); NTOHL (flh->hole_array[1][i].offset); } return TRUE; } /* fread_d99_header() */ /********************************/ /* */ /* fwrite_d99_header */ /* */ /********************************/ /* Writes d99 header structure to front of passed d99 file. * Performs byte swap as necessary IN PASSED BUFFER. * Returns TRUE if successful, else FALSE. */ int fwrite_d99_header (FILE_HEADER *flh, FILE *fp) { int i; HTONL (flh->hole_count[0]); HTONL (flh->hole_count[1]); for (i = 0; i < NUM_HOLES; i++) { HTONL (flh->hole_array[0][i].hole_size); HTONL (flh->hole_array[0][i].offset); HTONL (flh->hole_array[1][i].hole_size); HTONL (flh->hole_array[1][i].offset); } errno = 0; fseek (fp, 0L, SEEK_SET); if (fwrite (flh, sizeof(FILE_HEADER), (size_t)1, fp) == 1L) return TRUE; else return FALSE; } /* fwrite_d99_header() */ /************************/ /* */ /* Find Free Space */ /* */ /************************/ /* Find free space that is big enough to hold a new record. On success - return pointer to the FREE_SPACE_STR. On failure - return NULL. */ FREE_SPACE_STR *find_free_space (DtSrINT32 req_size, FILE_HEADER * flh) { static FREE_SPACE_STR space_found; FREE_SPACE_STR del_rec; int i, j, k; DtSrINT32 hole_check_size; float coeff; j = -1; if (req_size <= HOLE_SIZE_LIMIT) { k = 0; coeff = 1.1; } else { k = 1; coeff = 1.2; } for (i = 0; i < flh->hole_count[k]; i++) { if (flh->hole_array[k][i].hole_size >= req_size) { if (j < 0) { j = i; } else { /** check if it's the smallest one of the free space available ***/ if (flh->hole_array[k][i].hole_size < flh->hole_array[k][j].hole_size) { j = i; } } } } /* if big enough free space not found, return NULL */ if (j < 0) { return NULL; } if (flh->hole_array[k][j].hole_size == req_size) { space_found.hole_size = flh->hole_array[k][j].hole_size; space_found.offset = flh->hole_array[k][j].offset; /* compact the hole_array */ if (j == NUM_HOLES - 1) { (flh->hole_count[k])--; flh->hole_array[k][j].hole_size = 0; return &space_found; } for (i = j; i < (flh->hole_count[k] - 1); i++) { flh->hole_array[k][i].hole_size = flh->hole_array[k][i + 1].hole_size; flh->hole_array[k][i].offset = flh->hole_array[k][i + 1].offset; } (flh->hole_count[k])--; } else { /* Hole size CAN NOT exceed global batch_size in borodin */ hole_check_size = (req_size * coeff < batch_size) ? req_size * coeff : batch_size; if (hole_check_size >= flh->hole_array[k][j].hole_size) { space_found.hole_size = flh->hole_array[k][j].hole_size; space_found.offset = flh->hole_array[k][j].offset; /* compact the hole_array */ if (j == NUM_HOLES - 1) { flh->hole_array[k][j].hole_size = 0; } else { for (i = j; i < (flh->hole_count[k] - 1); i++) { flh->hole_array[k][i].hole_size = flh->hole_array[k][i + 1].hole_size; flh->hole_array[k][i].offset = flh->hole_array[k][i + 1].offset; } } (flh->hole_count[k])--; } else { space_found.hole_size = req_size; space_found.offset = flh->hole_array[k][j].offset; flh->hole_array[k][j].hole_size -= req_size; flh->hole_array[k][j].offset += req_size * sizeof(DtSrINT32); if ((k == 1) && (flh->hole_array[k][j].hole_size <= HOLE_SIZE_LIMIT)) { del_rec.hole_size = flh->hole_array[k][j].hole_size; del_rec.offset = flh->hole_array[k][j].offset; add_free_space (&del_rec, flh); if (j == NUM_HOLES - 1) { (flh->hole_count[k])--; flh->hole_array[k][j].hole_size = 0; return &space_found; } for (i = j; i < (flh->hole_count[k] - 1); i++) { flh->hole_array[k][i].hole_size = flh->hole_array[k][i + 1].hole_size; flh->hole_array[k][i].offset = flh->hole_array[k][i + 1].offset; } (flh->hole_count[k])--; } } } return &space_found; } /************ end of function find_free_space ******************/ /************************/ /* */ /* Add Free Space */ /* */ /************************/ /* Adds freed space to the hole_array. If there'e no space left in the hole_array, checks if the new space is greater, than the smallest space in the hole_array. If yes - substitute it. */ void add_free_space (FREE_SPACE_STR * del_rec, FILE_HEADER * flh) { int i, j, k; DtSrINT32 min_size; if (del_rec->hole_size <= HOLE_SIZE_LIMIT) { k = 0; } else { k = 1; } j = flh->hole_count[k]; if (j < NUM_HOLES) { flh->hole_array[k][j].hole_size = del_rec->hole_size; flh->hole_array[k][j].offset = del_rec->offset; (flh->hole_count[k])++; } else { min_size = flh->hole_array[k][0].hole_size; j = 0; for (i = 1; i < NUM_HOLES; i++) { if (flh->hole_array[k][i].hole_size < min_size) { min_size = flh->hole_array[k][i].hole_size; j = i; } } if (del_rec->hole_size > flh->hole_array[k][j].hole_size) { flh->hole_array[k][j].hole_size = del_rec->hole_size; flh->hole_array[k][j].offset = del_rec->offset; } } return; } /************ end of function add_free_space ******************/