2 * $Id: filemap.cc,v 1.16 1997/03/29 04:45:15 wessels Exp $
4 * DEBUG: section 8 Swap File Bitmap
5 * AUTHOR: Harvest Derived
7 * SQUID Internet Object Cache http://squid.nlanr.net/Squid/
8 * --------------------------------------------------------
10 * Squid is the result of efforts by numerous individuals from the
11 * Internet community. Development is led by Duane Wessels of the
12 * National Laboratory for Applied Network Research and funded by
13 * the National Science Foundation.
15 * This program is free software; you can redistribute it and/or modify
16 * it under the terms of the GNU General Public License as published by
17 * the Free Software Foundation; either version 2 of the License, or
18 * (at your option) any later version.
20 * This program is distributed in the hope that it will be useful,
21 * but WITHOUT ANY WARRANTY; without even the implied warranty of
22 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23 * GNU General Public License for more details.
25 * You should have received a copy of the GNU General Public License
26 * along with this program; if not, write to the Free Software
27 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
32 * Copyright (c) 1994, 1995. All rights reserved.
34 * The Harvest software was developed by the Internet Research Task
35 * Force Research Group on Resource Discovery (IRTF-RD):
37 * Mic Bowman of Transarc Corporation.
38 * Peter Danzig of the University of Southern California.
39 * Darren R. Hardy of the University of Colorado at Boulder.
40 * Udi Manber of the University of Arizona.
41 * Michael F. Schwartz of the University of Colorado at Boulder.
42 * Duane Wessels of the University of Colorado at Boulder.
44 * This copyright notice applies to software in the Harvest
45 * ``src/'' directory only. Users should consult the individual
46 * copyright notices in the ``components/'' subdirectories for
47 * copyright information about other software bundled with the
48 * Harvest source code distribution.
52 * The Harvest software may be used and re-distributed without
53 * charge, provided that the software origin and research team are
54 * cited in any use of the system. Most commonly this is
55 * accomplished by including a link to the Harvest Home Page
56 * (http://harvest.cs.colorado.edu/) from the query page of any
57 * Broker you deploy, as well as in the query result pages. These
58 * links are generated automatically by the standard Broker
59 * software distribution.
61 * The Harvest software is provided ``as is'', without express or
62 * implied warranty, and with no support nor obligation to assist
63 * in its use, correction, modification or enhancement. We assume
64 * no liability with respect to the infringement of copyrights,
65 * trade secrets, or any patents, and are not responsible for
66 * consequential damages. Proper use of the Harvest software is
67 * entirely the responsibility of the user.
71 * Users may make derivative works from the Harvest software, subject
72 * to the following constraints:
74 * - You must include the above copyright notice and these
75 * accompanying paragraphs in all forms of derivative works,
76 * and any documentation and other materials related to such
77 * distribution and use acknowledge that the software was
78 * developed at the above institutions.
80 * - You must notify IRTF-RD regarding your distribution of
81 * the derivative work.
83 * - You must clearly notify users that your are distributing
84 * a modified version and not the original Harvest software.
86 * - Any derivative product is also subject to these copyright
87 * and use restrictions.
89 * Note that the Harvest software is NOT in the public domain. We
90 * retain copyright, as specified above.
92 * HISTORY OF FREE SOFTWARE STATUS
94 * Originally we required sites to license the software in cases
95 * where they were going to build commercial products/services
96 * around Harvest. In June 1995 we changed this policy. We now
97 * allow people to use the core Harvest software (the code found in
98 * the Harvest ``src/'' directory) for free. We made this change
99 * in the interest of encouraging the widest possible deployment of
100 * the technology. The Harvest software is really a reference
101 * implementation of a set of protocols and formats, some of which
102 * we intend to standardize. We encourage commercial
103 * re-implementations of code complying to this set of standards.
109 /* Number of bits in a long */
111 #define LONG_BIT_SHIFT 6
112 #define BITS_IN_A_LONG 0x40
113 #define LONG_BIT_MASK 0x3F
114 #define ALL_ONES (unsigned long) 0xFFFFFFFFFFFFFFFF
115 #elif SIZEOF_LONG == 4
116 #define LONG_BIT_SHIFT 5
117 #define BITS_IN_A_LONG 0x20
118 #define LONG_BIT_MASK 0x1F
119 #define ALL_ONES (unsigned long) 0xFFFFFFFF
121 #define LONG_BIT_SHIFT 5
122 #define BITS_IN_A_LONG 0x20
123 #define LONG_BIT_MASK 0x1F
124 #define ALL_ONES (unsigned long) 0xFFFFFFFF
128 file_map_create(int n
)
130 fileMap
*fm
= xcalloc(1, sizeof(fileMap
));
132 fm
->nwords
= n
>> LONG_BIT_SHIFT
;
133 debug(8, 1, "file_map_create: creating space for %d files\n", n
);
134 debug(8, 5, "--> %d words of %d bytes each\n",
135 fm
->nwords
, sizeof(unsigned long));
136 fm
->file_map
= xcalloc(fm
->nwords
, sizeof(unsigned long));
137 meta_data
.misc
+= fm
->nwords
* sizeof(unsigned long);
142 file_map_bit_set(fileMap
* fm
, int file_number
)
144 unsigned long bitmask
= (1L << (file_number
& LONG_BIT_MASK
));
145 fm
->file_map
[file_number
>> LONG_BIT_SHIFT
] |= bitmask
;
146 fm
->n_files_in_map
++;
147 if (!fm
->toggle
&& (fm
->n_files_in_map
> ((fm
->max_n_files
* 7) >> 3))) {
149 debug(8, 0, "You should increment MAX_SWAP_FILE\n");
150 } else if (fm
->n_files_in_map
> (fm
->max_n_files
- 100)) {
151 debug(8, 0, "You've run out of swap file numbers. Freeing 1MB\n");
152 storeGetSwapSpace(1000000);
154 return (file_number
);
158 file_map_bit_reset(fileMap
* fm
, int file_number
)
160 unsigned long bitmask
= (1L << (file_number
& LONG_BIT_MASK
));
161 fm
->file_map
[file_number
>> LONG_BIT_SHIFT
] &= ~bitmask
;
162 fm
->n_files_in_map
--;
166 file_map_bit_test(fileMap
* fm
, int file_number
)
168 unsigned long bitmask
= (1L << (file_number
& LONG_BIT_MASK
));
169 /* be sure the return value is an int, not a u_long */
170 return (fm
->file_map
[file_number
>> LONG_BIT_SHIFT
] & bitmask
? 1 : 0);
174 file_map_allocate(fileMap
* fm
, int suggestion
)
179 if (!file_map_bit_test(fm
, suggestion
)) {
180 fm
->last_file_number_allocated
= suggestion
;
181 return file_map_bit_set(fm
, suggestion
);
183 word
= suggestion
>> LONG_BIT_SHIFT
;
184 for (count
= 0; count
< fm
->nwords
; count
++) {
185 if (fm
->file_map
[word
] != ALL_ONES
)
187 word
= (word
+ 1) % fm
->nwords
;
189 for (bit
= 0; bit
< BITS_IN_A_LONG
; bit
++) {
190 suggestion
= ((unsigned long) word
<< LONG_BIT_SHIFT
) | bit
;
191 if (!file_map_bit_test(fm
, suggestion
)) {
192 fm
->last_file_number_allocated
= suggestion
;
193 return file_map_bit_set(fm
, suggestion
);
196 fatal_dump("file_map_allocate: Exceeded filemap limit");
197 return 0; /* NOTREACHED */
201 filemapFreeMemory(fileMap
* fm
)
203 safe_free(fm
->file_map
);
209 #define TEST_SIZE 1<<16
214 fm
= file_map_create(TEST_SIZE
);
216 for (i
= 0; i
< TEST_SIZE
; ++i
) {
218 if (!file_map_bit_test(i
))
220 file_map_bit_reset(i
);