cde/lib/tt/mini_isam/ismngfcb.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /*%%  (c) Copyright 1993, 1994 Hewlett-Packard Company                   */
  24 /*%%  (c) Copyright 1993, 1994 International Business Machines Corp.     */
  25 /*%%  (c) Copyright 1993, 1994 Sun Microsystems, Inc.                    */
  26 /*%%  (c) Copyright 1993, 1994 Novell, Inc.                              */
  27 /*%%  $XConsortium: ismngfcb.c /main/3 1995/10/23 11:42:28 rswiston $                                                    */
  28 #ifndef lint
  29 static char sccsid[] = "@(#)ismngfcb.c 1.4 89/07/17 Copyr 1988 Sun Micro";
  30 #endif
  31 /*
  32  * Copyright (c) 1988 by Sun Microsystems, Inc.
  33  */
  34
  35 /*
  36  * ismngfcb.c
  37  *
  38  * Description:
  39  *      Manager of open FCB blocks.
  40  *
  41  * This module keeps track of usage of the FCB blocks and finds a victim
  42  * on LRU basis.
  43  * It also provides associative access to the FCB by their isfhandles.
  44  *
  45  */
  46 #include "isam_impl.h"
  47
  48
  49 #define FCBHASHSIZE     101                  /* Should be a prime for best hash */
  50
  51 #if  (MAXFCB_UNIXFD > FCBHASHSIZE)
  52 /*
  53  * Cause a syntax error. FCBHASHSIZE must be increased to be > MAXFCB_UNIXFD.
  54  * A good estimate is a prime approximately equal (2 * MAXFCB_UNIXFD).
  55  */
  56 MUST INCREASE FCBHASHSIZE
  57 #endif
  58
  59 struct hashtable {
  60     Bytearray   isfhandle;
  61     Fcb         *fcb;
  62     long        mrused;
  63 } hashtable [FCBHASHSIZE];
  64 #define unused(entry) ((entry).fcb == NULL)
  65
  66 static int _hashisfhandle();
  67
  68 static mrused_last = 0;                      /* stamp generator */
  69
  70
  71 /*
  72  * _mngfcb_insert(fcb, isfhandle)
  73  *
  74  * Insert new FCB entry.
  75  */
  76
  77 void
  78 _mngfcb_insert(fcb, isfhandle)
  79     Fcb         *fcb;
  80     Bytearray   *isfhandle;
  81 {
  82     int                 hashval = _hashisfhandle(isfhandle);
  83     register int        ind;
  84     int                 ntries;
  85
  86     /* Try to find an unused entry in the hash table. */
  87     ind = hashval;
  88     for (ntries = 0; ntries < FCBHASHSIZE; ntries++) {
  89         if (unused(hashtable[ind]))
  90             break;
  91         if (++ind == FCBHASHSIZE)
  92             ind = 0;                         /* Wrap the table */
  93     }
  94
  95     if (ntries == FCBHASHSIZE) {
  96         _isfatal_error("FCB hash table overflow");
  97     }
  98
  99     /*
 100      * Create an entry at the index ind.
 101      * Duplicate the file handle and mark the entry with the current stamp.
 102      */
 103     hashtable[ind].isfhandle = _bytearr_dup(isfhandle);
 104     hashtable[ind].fcb = fcb;
 105     hashtable[ind].mrused = mrused_last++;
 106 }
 107
 108
 109 /*
 110  * fcb = _mngfcb_find(isfhandle)
 111  *
 112  * Return a pointer to the FCB, or NULL if the FCB is not found.
 113  * If the FCB is found, it is "touched" for the LRU algorithm purpose.
 114  */
 115
 116 Fcb *
 117 _mngfcb_find(isfhandle)
 118     Bytearray   *isfhandle;
 119 {
 120     int                 hashval = _hashisfhandle(isfhandle);
 121     register int        ind;
 122     int                 ntries;
 123
 124     /* Find the entry. */
 125     ind = hashval;
 126     for (ntries = 0; ntries < FCBHASHSIZE; ntries++) {
 127         if (_bytearr_cmp(&hashtable[ind].isfhandle, isfhandle) == 0)
 128             break;
 129         if (++ind == FCBHASHSIZE)
 130             ind = 0;                         /* Wrap the table */
 131     }
 132
 133     if (ntries == FCBHASHSIZE) {
 134         return (NULL);                       /* Not found */
 135     }
 136     else {
 137
 138         /*
 139          * Mark the entry with the current stamp.
 140          */
 141         hashtable[ind].mrused = mrused_last++;
 142         return hashtable[ind].fcb;
 143     }
 144 }
 145
 146 /*
 147  * _mngfcb_delete(isfname)
 148  *
 149  * Delete an entry.
 150  */
 151
 152 void
 153 _mngfcb_delete(isfhandle)
 154     Bytearray   *isfhandle;
 155 {
 156     int                 hashval = _hashisfhandle(isfhandle);
 157     register int        ind;
 158     int                 ntries;
 159
 160     /* Find the entry */
 161     ind = hashval;
 162     for (ntries = 0; ntries < FCBHASHSIZE; ntries++) {
 163         if (_bytearr_cmp(&hashtable[ind].isfhandle, isfhandle) == 0)
 164             break;
 165         if (++ind == FCBHASHSIZE)
 166             ind = 0;                         /* Wrap the table */
 167     }
 168
 169     if (ntries == FCBHASHSIZE) {
 170         _isfatal_error("_mngfcb_delete cannot find entry");
 171     }
 172     else {
 173
 174         /*
 175          * Clear the entry.
 176          */
 177         _bytearr_free(&hashtable[ind].isfhandle);
 178         memset ((char *) &hashtable[ind], 0, sizeof(hashtable[ind]));
 179     }
 180 }
 181
 182
 183 /*
 184  * isfhandle = _mngfcb_victim()
 185  *
 186  * Find LRU used FCB.
 187  */
 188
 189 Bytearray *
 190 _mngfcb_victim()
 191 {
 192     int                 victim_ind = -1;
 193     long                victim_time = 0;     /* Assign to shut up lint */
 194     register int        i;
 195
 196     for (i = 0; i < FCBHASHSIZE; i++) {
 197
 198         if (unused(hashtable[i]))            /* Skip empty slots in table */
 199             continue;
 200
 201         if (victim_ind == -1 || victim_time > hashtable[i].mrused) {
 202             victim_ind = i;
 203             victim_time = hashtable[i].mrused;
 204         }
 205     }
 206     return ((victim_ind == -1) ? NULL : &hashtable[victim_ind].isfhandle);
 207 }
 208
 209
 210 /*
 211  * _hashisfhandle(isfhandle)
 212  *
 213  * Hash isfhandle into an integer.
 214  */
 215
 216 Static int
 217 _hashisfhandle(isfhandle)
 218     Bytearray           *isfhandle;
 219 {
 220     register char       *p;
 221     register unsigned   h, g;
 222     register int        len;
 223
 224     len = isfhandle->length;
 225     p = isfhandle->data;
 226     h = 0;
 227
 228     while (len-- > 0) {
 229         h = (h << 4) + (*p++);
 230         if (g = h&0xf0000000) {
 231             h = h ^ (g >> 24);
 232             h = h ^ g;
 233         }
 234     }
 235     return (h % FCBHASHSIZE);
 236 }