]>
git.ipfire.org Git - thirdparty/squid.git/blob - src/filemap.cc
3 * $Id: filemap.cc,v 1.36 2000/10/13 08:45:07 wessels Exp $
5 * DEBUG: section 8 Swap File Bitmap
6 * AUTHOR: Harvest Derived
8 * SQUID Internet Object Cache http://squid.nlanr.net/Squid/
9 * ----------------------------------------------------------
11 * Squid is the result of efforts by numerous individuals from the
12 * Internet community. Development is led by Duane Wessels of the
13 * National Laboratory for Applied Network Research and funded by the
14 * National Science Foundation. Squid is Copyrighted (C) 1998 by
15 * the Regents of the University of California. Please see the
16 * COPYRIGHT file for full details. Squid incorporates software
17 * developed and/or copyrighted by other sources. Please see the
18 * CREDITS file for full details.
20 * This program is free software; you can redistribute it and/or modify
21 * it under the terms of the GNU General Public License as published by
22 * the Free Software Foundation; either version 2 of the License, or
23 * (at your option) any later version.
25 * This program is distributed in the hope that it will be useful,
26 * but WITHOUT ANY WARRANTY; without even the implied warranty of
27 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
28 * GNU General Public License for more details.
30 * You should have received a copy of the GNU General Public License
31 * along with this program; if not, write to the Free Software
32 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
38 /* Number of bits in a long */
40 #define LONG_BIT_SHIFT 6
41 #define BITS_IN_A_LONG 0x40
42 #define LONG_BIT_MASK 0x3F
43 #define ALL_ONES (unsigned long) 0xFFFFFFFFFFFFFFFF
44 #elif SIZEOF_LONG == 4
45 #define LONG_BIT_SHIFT 5
46 #define BITS_IN_A_LONG 0x20
47 #define LONG_BIT_MASK 0x1F
48 #define ALL_ONES (unsigned long) 0xFFFFFFFF
50 #define LONG_BIT_SHIFT 5
51 #define BITS_IN_A_LONG 0x20
52 #define LONG_BIT_MASK 0x1F
53 #define ALL_ONES (unsigned long) 0xFFFFFFFF
56 #define FM_INITIAL_NUMBER (1<<14)
61 fileMap
*fm
= xcalloc(1, sizeof(fileMap
));
62 fm
->max_n_files
= FM_INITIAL_NUMBER
;
63 fm
->nwords
= fm
->max_n_files
>> LONG_BIT_SHIFT
;
64 debug(8, 3) ("file_map_create: creating space for %d files\n", fm
->max_n_files
);
65 debug(8, 5) ("--> %d words of %d bytes each\n",
66 fm
->nwords
, sizeof(*fm
->file_map
));
67 fm
->file_map
= xcalloc(fm
->nwords
, sizeof(*fm
->file_map
));
68 /* XXX account fm->file_map */
73 file_map_grow(fileMap
* fm
)
75 int old_sz
= fm
->nwords
* sizeof(*fm
->file_map
);
76 void *old_map
= fm
->file_map
;
77 fm
->max_n_files
<<= 1;
78 assert(fm
->max_n_files
<= (1 << 30));
79 fm
->nwords
= fm
->max_n_files
>> LONG_BIT_SHIFT
;
80 debug(8, 3) ("file_map_grow: creating space for %d files\n", fm
->max_n_files
);
81 fm
->file_map
= xcalloc(fm
->nwords
, sizeof(*fm
->file_map
));
82 debug(8, 3) ("copying %d old bytes\n", old_sz
);
83 xmemcpy(fm
->file_map
, old_map
, old_sz
);
85 /* XXX account fm->file_map */
89 file_map_bit_set(fileMap
* fm
, int file_number
)
91 unsigned long bitmask
= (1L << (file_number
& LONG_BIT_MASK
));
92 while (file_number
>= fm
->max_n_files
)
94 fm
->file_map
[file_number
>> LONG_BIT_SHIFT
] |= bitmask
;
100 * WARNING: file_map_bit_reset does not perform array bounds
101 * checking! It assumes that 'file_number' is valid, and that the
102 * bit is already set. The caller must verify both of those
103 * conditions by calling file_map_bit_test() first.
106 file_map_bit_reset(fileMap
* fm
, int file_number
)
108 unsigned long bitmask
= (1L << (file_number
& LONG_BIT_MASK
));
109 fm
->file_map
[file_number
>> LONG_BIT_SHIFT
] &= ~bitmask
;
110 fm
->n_files_in_map
--;
114 file_map_bit_test(fileMap
* fm
, int file_number
)
116 unsigned long bitmask
= (1L << (file_number
& LONG_BIT_MASK
));
117 if (file_number
>= fm
->max_n_files
)
119 /* be sure the return value is an int, not a u_long */
120 return (fm
->file_map
[file_number
>> LONG_BIT_SHIFT
] & bitmask
? 1 : 0);
124 file_map_allocate(fileMap
* fm
, int suggestion
)
129 if (suggestion
>= fm
->max_n_files
)
131 if (!file_map_bit_test(fm
, suggestion
))
133 word
= suggestion
>> LONG_BIT_SHIFT
;
134 for (count
= 0; count
< fm
->nwords
; count
++) {
135 if (fm
->file_map
[word
] != ALL_ONES
)
137 word
= (word
+ 1) % fm
->nwords
;
139 for (bit
= 0; bit
< BITS_IN_A_LONG
; bit
++) {
140 suggestion
= ((unsigned long) word
<< LONG_BIT_SHIFT
) | bit
;
141 if (!file_map_bit_test(fm
, suggestion
)) {
145 debug(8, 3) ("growing from file_map_allocate\n");
147 return file_map_allocate(fm
, fm
->max_n_files
>> 1);
151 filemapFreeMemory(fileMap
* fm
)
153 safe_free(fm
->file_map
);
159 #define TEST_SIZE 1<<16
164 fm
= file_map_create(TEST_SIZE
);
166 for (i
= 0; i
< TEST_SIZE
; ++i
) {
168 assert(file_map_bit_test(i
));
169 file_map_bit_reset(i
);