]>
git.ipfire.org Git - thirdparty/squid.git/blob - src/filemap.cc
4 * DEBUG: section 08 Swap File Bitmap
5 * AUTHOR: Harvest Derived
7 * SQUID Web Proxy Cache http://www.squid-cache.org/
8 * ----------------------------------------------------------
10 * Squid is the result of efforts by numerous individuals from
11 * the Internet community; see the CONTRIBUTORS file for full
12 * details. Many organizations have provided support for Squid's
13 * development; see the SPONSORS file for full details. Squid is
14 * Copyrighted (C) 2001 by the Regents of the University of
15 * California; see the COPYRIGHT file for full details. Squid
16 * incorporates software developed and/or copyrighted by other
17 * sources; see the CREDITS file for full details.
19 * This program is free software; you can redistribute it and/or modify
20 * it under the terms of the GNU General Public License as published by
21 * the Free Software Foundation; either version 2 of the License, or
22 * (at your option) any later version.
24 * This program is distributed in the hope that it will be useful,
25 * but WITHOUT ANY WARRANTY; without even the implied warranty of
26 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
27 * GNU General Public License for more details.
29 * You should have received a copy of the GNU General Public License
30 * along with this program; if not, write to the Free Software
31 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
37 /* Number of bits in a long */
39 #define LONG_BIT_SHIFT 6
40 #define BITS_IN_A_LONG 0x40
41 #define LONG_BIT_MASK 0x3F
42 #define ALL_ONES (unsigned long) 0xFFFFFFFFFFFFFFFF
43 #elif SIZEOF_LONG == 4
44 #define LONG_BIT_SHIFT 5
45 #define BITS_IN_A_LONG 0x20
46 #define LONG_BIT_MASK 0x1F
47 #define ALL_ONES (unsigned long) 0xFFFFFFFF
49 #define LONG_BIT_SHIFT 5
50 #define BITS_IN_A_LONG 0x20
51 #define LONG_BIT_MASK 0x1F
52 #define ALL_ONES (unsigned long) 0xFFFFFFFF
55 #define FM_INITIAL_NUMBER (1<<14)
60 fileMap
*fm
= (fileMap
*)xcalloc(1, sizeof(fileMap
));
61 fm
->max_n_files
= FM_INITIAL_NUMBER
;
62 fm
->nwords
= fm
->max_n_files
>> LONG_BIT_SHIFT
;
63 debugs(8, 3, "file_map_create: creating space for " << fm
->max_n_files
<< " files");
64 debugs(8, 5, "--> " << fm
->nwords
<< " words of " << sizeof(*fm
->file_map
) << " bytes each");
65 fm
->file_map
= (unsigned long *)xcalloc(fm
->nwords
, sizeof(*fm
->file_map
));
66 /* XXX account fm->file_map */
71 file_map_grow(fileMap
* fm
)
73 int old_sz
= fm
->nwords
* sizeof(*fm
->file_map
);
74 void *old_map
= fm
->file_map
;
75 fm
->max_n_files
<<= 1;
76 assert(fm
->max_n_files
<= (1 << 24)); /* swap_filen is 25 bits, signed */
77 fm
->nwords
= fm
->max_n_files
>> LONG_BIT_SHIFT
;
78 debugs(8, 3, "file_map_grow: creating space for " << fm
->max_n_files
<< " files");
79 fm
->file_map
= (unsigned long *)xcalloc(fm
->nwords
, sizeof(*fm
->file_map
));
80 debugs(8, 3, "copying " << old_sz
<< " old bytes");
81 memcpy(fm
->file_map
, old_map
, old_sz
);
83 /* XXX account fm->file_map */
87 file_map_bit_set(fileMap
* fm
, int file_number
)
89 unsigned long bitmask
= (1L << (file_number
& LONG_BIT_MASK
));
91 while (file_number
>= fm
->max_n_files
)
94 fm
->file_map
[file_number
>> LONG_BIT_SHIFT
] |= bitmask
;
102 * WARNING: file_map_bit_reset does not perform array bounds
103 * checking! It assumes that 'file_number' is valid, and that the
104 * bit is already set. The caller must verify both of those
105 * conditions by calling file_map_bit_test() first.
108 file_map_bit_reset(fileMap
* fm
, int file_number
)
110 unsigned long bitmask
= (1L << (file_number
& LONG_BIT_MASK
));
111 fm
->file_map
[file_number
>> LONG_BIT_SHIFT
] &= ~bitmask
;
112 fm
->n_files_in_map
--;
116 file_map_bit_test(fileMap
* fm
, int file_number
)
118 unsigned long bitmask
= (1L << (file_number
& LONG_BIT_MASK
));
120 if (file_number
>= fm
->max_n_files
)
123 /* be sure the return value is an int, not a u_long */
124 return (fm
->file_map
[file_number
>> LONG_BIT_SHIFT
] & bitmask
? 1 : 0);
128 file_map_allocate(fileMap
* fm
, int suggestion
)
134 if (suggestion
>= fm
->max_n_files
)
137 if (!file_map_bit_test(fm
, suggestion
))
140 word
= suggestion
>> LONG_BIT_SHIFT
;
142 for (count
= 0; count
< fm
->nwords
; count
++) {
143 if (fm
->file_map
[word
] != ALL_ONES
)
146 word
= (word
+ 1) % fm
->nwords
;
149 for (bit
= 0; bit
< BITS_IN_A_LONG
; bit
++) {
150 suggestion
= ((unsigned long) word
<< LONG_BIT_SHIFT
) | bit
;
152 if (!file_map_bit_test(fm
, suggestion
)) {
157 debugs(8, 3, "growing from file_map_allocate");
159 return file_map_allocate(fm
, fm
->max_n_files
>> 1);
163 filemapFreeMemory(fileMap
* fm
)
165 safe_free(fm
->file_map
);
171 #define TEST_SIZE 1<<16
176 fm
= file_map_create(TEST_SIZE
);
178 for (i
= 0; i
< TEST_SIZE
; ++i
) {
180 assert(file_map_bit_test(i
));
181 file_map_bit_reset(i
);