]>
git.ipfire.org Git - thirdparty/squid.git/blob - src/filemap.cc
3 * $Id: filemap.cc,v 1.44 2007/04/30 16:56:09 wessels Exp $
5 * DEBUG: section 8 Swap File Bitmap
6 * AUTHOR: Harvest Derived
8 * SQUID Web Proxy Cache http://www.squid-cache.org/
9 * ----------------------------------------------------------
11 * Squid is the result of efforts by numerous individuals from
12 * the Internet community; see the CONTRIBUTORS file for full
13 * details. Many organizations have provided support for Squid's
14 * development; see the SPONSORS file for full details. Squid is
15 * Copyrighted (C) 2001 by the Regents of the University of
16 * California; see the COPYRIGHT file for full details. Squid
17 * incorporates software developed and/or copyrighted by other
18 * sources; see the 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
= (fileMap
*)xcalloc(1, sizeof(fileMap
));
62 fm
->max_n_files
= FM_INITIAL_NUMBER
;
63 fm
->nwords
= fm
->max_n_files
>> LONG_BIT_SHIFT
;
64 debugs(8, 3, "file_map_create: creating space for " << fm
->max_n_files
<< " files");
65 debugs(8, 5, "--> " << fm
->nwords
<< " words of " << sizeof(*fm
->file_map
) << " bytes each");
66 fm
->file_map
= (unsigned long *)xcalloc(fm
->nwords
, sizeof(*fm
->file_map
));
67 /* XXX account fm->file_map */
72 file_map_grow(fileMap
* fm
)
74 int old_sz
= fm
->nwords
* sizeof(*fm
->file_map
);
75 void *old_map
= fm
->file_map
;
76 fm
->max_n_files
<<= 1;
77 assert(fm
->max_n_files
<= (1 << 24)); /* swap_filen is 25 bits, signed */
78 fm
->nwords
= fm
->max_n_files
>> LONG_BIT_SHIFT
;
79 debugs(8, 3, "file_map_grow: creating space for " << fm
->max_n_files
<< " files");
80 fm
->file_map
= (unsigned long *)xcalloc(fm
->nwords
, sizeof(*fm
->file_map
));
81 debugs(8, 3, "copying " << old_sz
<< " old bytes");
82 xmemcpy(fm
->file_map
, old_map
, old_sz
);
84 /* XXX account fm->file_map */
88 file_map_bit_set(fileMap
* fm
, int file_number
)
90 unsigned long bitmask
= (1L << (file_number
& LONG_BIT_MASK
));
92 while (file_number
>= fm
->max_n_files
)
95 fm
->file_map
[file_number
>> LONG_BIT_SHIFT
] |= bitmask
;
103 * WARNING: file_map_bit_reset does not perform array bounds
104 * checking! It assumes that 'file_number' is valid, and that the
105 * bit is already set. The caller must verify both of those
106 * conditions by calling file_map_bit_test() first.
109 file_map_bit_reset(fileMap
* fm
, int file_number
)
111 unsigned long bitmask
= (1L << (file_number
& LONG_BIT_MASK
));
112 fm
->file_map
[file_number
>> LONG_BIT_SHIFT
] &= ~bitmask
;
113 fm
->n_files_in_map
--;
117 file_map_bit_test(fileMap
* fm
, int file_number
)
119 unsigned long bitmask
= (1L << (file_number
& LONG_BIT_MASK
));
121 if (file_number
>= fm
->max_n_files
)
124 /* be sure the return value is an int, not a u_long */
125 return (fm
->file_map
[file_number
>> LONG_BIT_SHIFT
] & bitmask
? 1 : 0);
129 file_map_allocate(fileMap
* fm
, int suggestion
)
135 if (suggestion
>= fm
->max_n_files
)
138 if (!file_map_bit_test(fm
, suggestion
))
141 word
= suggestion
>> LONG_BIT_SHIFT
;
143 for (count
= 0; count
< fm
->nwords
; count
++) {
144 if (fm
->file_map
[word
] != ALL_ONES
)
147 word
= (word
+ 1) % fm
->nwords
;
150 for (bit
= 0; bit
< BITS_IN_A_LONG
; bit
++) {
151 suggestion
= ((unsigned long) word
<< LONG_BIT_SHIFT
) | bit
;
153 if (!file_map_bit_test(fm
, suggestion
)) {
158 debugs(8, 3, "growing from file_map_allocate");
160 return file_map_allocate(fm
, fm
->max_n_files
>> 1);
164 filemapFreeMemory(fileMap
* fm
)
166 safe_free(fm
->file_map
);
172 #define TEST_SIZE 1<<16
177 fm
= file_map_create(TEST_SIZE
);
179 for (i
= 0; i
< TEST_SIZE
; ++i
) {
181 assert(file_map_bit_test(i
));
182 file_map_bit_reset(i
);