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 libraries 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 *fcb, Bytearray *isfhandle)
  79 {
  80     int                 hashval = _hashisfhandle(isfhandle);
  81     register int        ind;
  82     int                 ntries;
  83
  84     /* Try to find an unused entry in the hash table. */
  85     ind = hashval;
  86     for (ntries = 0; ntries < FCBHASHSIZE; ntries++) {
  87         if (unused(hashtable[ind]))
  88             break;
  89         if (++ind == FCBHASHSIZE)
  90             ind = 0;                         /* Wrap the table */
  91     }
  92
  93     if (ntries == FCBHASHSIZE) {
  94         _isfatal_error("FCB hash table overflow");
  95     }
  96
  97     /*
  98      * Create an entry at the index ind.
  99      * Duplicate the file handle and mark the entry with the current stamp.
 100      */
 101     hashtable[ind].isfhandle = _bytearr_dup(isfhandle);
 102     hashtable[ind].fcb = fcb;
 103     hashtable[ind].mrused = mrused_last++;
 104 }
 105
 106
 107 /*
 108  * fcb = _mngfcb_find(isfhandle)
 109  *
 110  * Return a pointer to the FCB, or NULL if the FCB is not found.
 111  * If the FCB is found, it is "touched" for the LRU algorithm purpose.
 112  */
 113
 114 Fcb *
 115 _mngfcb_find(Bytearray *isfhandle)
 116 {
 117     int                 hashval = _hashisfhandle(isfhandle);
 118     register int        ind;
 119     int                 ntries;
 120
 121     /* Find the entry. */
 122     ind = hashval;
 123     for (ntries = 0; ntries < FCBHASHSIZE; ntries++) {
 124         if (_bytearr_cmp(&hashtable[ind].isfhandle, isfhandle) == 0)
 125             break;
 126         if (++ind == FCBHASHSIZE)
 127             ind = 0;                         /* Wrap the table */
 128     }
 129
 130     if (ntries == FCBHASHSIZE) {
 131         return (NULL);                       /* Not found */
 132     }
 133     else {
 134
 135         /*
 136          * Mark the entry with the current stamp.
 137          */
 138         hashtable[ind].mrused = mrused_last++;
 139         return hashtable[ind].fcb;
 140     }
 141 }
 142
 143 /*
 144  * _mngfcb_delete(isfname)
 145  *
 146  * Delete an entry.
 147  */
 148
 149 void
 150 _mngfcb_delete(Bytearray *isfhandle)
 151 {
 152     int                 hashval = _hashisfhandle(isfhandle);
 153     register int        ind;
 154     int                 ntries;
 155
 156     /* Find the entry */
 157     ind = hashval;
 158     for (ntries = 0; ntries < FCBHASHSIZE; ntries++) {
 159         if (_bytearr_cmp(&hashtable[ind].isfhandle, isfhandle) == 0)
 160             break;
 161         if (++ind == FCBHASHSIZE)
 162             ind = 0;                         /* Wrap the table */
 163     }
 164
 165     if (ntries == FCBHASHSIZE) {
 166         _isfatal_error("_mngfcb_delete cannot find entry");
 167     }
 168     else {
 169
 170         /*
 171          * Clear the entry.
 172          */
 173         _bytearr_free(&hashtable[ind].isfhandle);
 174         memset ((char *) &hashtable[ind], 0, sizeof(hashtable[ind]));
 175     }
 176 }
 177
 178
 179 /*
 180  * isfhandle = _mngfcb_victim()
 181  *
 182  * Find LRU used FCB.
 183  */
 184
 185 Bytearray *
 186 _mngfcb_victim(void)
 187 {
 188     int                 victim_ind = -1;
 189     long                victim_time = 0;     /* Assign to shut up lint */
 190     register int        i;
 191
 192     for (i = 0; i < FCBHASHSIZE; i++) {
 193
 194         if (unused(hashtable[i]))            /* Skip empty slots in table */
 195             continue;
 196
 197         if (victim_ind == -1 || victim_time > hashtable[i].mrused) {
 198             victim_ind = i;
 199             victim_time = hashtable[i].mrused;
 200         }
 201     }
 202     return ((victim_ind == -1) ? NULL : &hashtable[victim_ind].isfhandle);
 203 }
 204
 205
 206 /*
 207  * _hashisfhandle(isfhandle)
 208  *
 209  * Hash isfhandle into an integer.
 210  */
 211
 212 Static int
 213 _hashisfhandle(Bytearray *isfhandle)
 214 {
 215     register char       *p;
 216     register unsigned   h, g;
 217     register int        len;
 218
 219     len = isfhandle->length;
 220     p = isfhandle->data;
 221     h = 0;
 222
 223     while (len-- > 0) {
 224         h = (h << 4) + (*p++);
 225         if (g = h&0xf0000000) {
 226             h = h ^ (g >> 24);
 227             h = h ^ g;
 228         }
 229     }
 230     return (h % FCBHASHSIZE);
 231 }