Lines Matching defs:icount
3 * icount.c --- an efficient inode count abstraction
23 * The data storage strategy used by icount relies on the observation
28 * Also, e2fsck tends to load the icount data sequentially.
57 void ext2fs_free_icount(ext2_icount_t icount)
59 if (!icount)
62 icount->magic = 0;
63 ext2fs_free_mem(&icount->list);
64 ext2fs_free_inode_bitmap(icount->single);
65 ext2fs_free_inode_bitmap(icount->multiple);
66 ext2fs_free_mem(&icount);
72 ext2_icount_t icount;
83 retval = ext2fs_get_mem(sizeof(struct ext2_icount), &icount);
86 memset(icount, 0, sizeof(struct ext2_icount));
89 &icount->single);
95 &icount->multiple);
99 icount->multiple = 0;
102 icount->size = size;
109 retval = ext2fs_get_num_dirs(fs, &icount->size);
112 icount->size += fs->super->s_inodes_count / 50;
115 bytes = (size_t) (icount->size * sizeof(struct ext2_icount_el));
116 retval = ext2fs_get_mem(bytes, &icount->list);
119 memset(icount->list, 0, bytes);
121 icount->magic = EXT2_ET_MAGIC_ICOUNT;
122 icount->count = 0;
123 icount->cursor = 0;
124 icount->num_inodes = fs->super->s_inodes_count;
128 * found in the hint icount (since those are ones which will
133 icount->list[i].ino = hint->list[i].ino;
134 icount->count = hint->count;
137 *ret = icount;
141 ext2fs_free_icount(icount);
156 static struct ext2_icount_el *insert_icount_el(ext2_icount_t icount,
164 if (icount->count >= icount->size) {
165 if (icount->count) {
166 new_size = icount->list[(unsigned)icount->count-1].ino;
167 new_size = (ext2_ino_t) (icount->count *
168 ((float) icount->num_inodes / new_size));
170 if (new_size < (icount->size + 100))
171 new_size = icount->size + 100;
172 retval = ext2fs_resize_mem((size_t) icount->size *
176 &icount->list);
179 icount->size = new_size;
181 num = (int) icount->count - pos;
185 memmove(&icount->list[pos+1], &icount->list[pos],
188 icount->count++;
189 el = &icount->list[pos];
196 * get_icount_el() --- given an inode number, try to find icount
200 static struct ext2_icount_el *get_icount_el(ext2_icount_t icount,
207 if (!icount || !icount->list)
210 if (create && ((icount->count == 0) ||
211 (ino > icount->list[(unsigned)icount->count-1].ino))) {
212 return insert_icount_el(icount, ino, (unsigned) icount->count);
214 if (icount->count == 0)
217 if (icount->cursor >= icount->count)
218 icount->cursor = 0;
219 if (ino == icount->list[icount->cursor].ino)
220 return &icount->list[icount->cursor++];
222 high = (int) icount->count-1;
228 lowval = icount->list[low].ino;
229 highval = icount->list[high].ino;
240 if (ino == icount->list[mid].ino) {
241 icount->cursor = mid+1;
242 return &icount->list[mid];
244 if (ino < icount->list[mid].ino)
254 return insert_icount_el(icount, ino, low);
258 errcode_t ext2fs_icount_validate(ext2_icount_t icount, FILE *out)
262 const char *bad = "bad icount";
264 EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
266 if (icount->count > icount->size) {
270 for (i=1; i < icount->count; i++) {
271 if (icount->list[i-1].ino >= icount->list[i].ino) {
273 bad, i-1, icount->list[i-1].ino,
274 i, icount->list[i].ino);
281 errcode_t ext2fs_icount_fetch(ext2_icount_t icount, ext2_ino_t ino, __u16 *ret)
285 EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
287 if (!ino || (ino > icount->num_inodes))
290 if (ext2fs_test_inode_bitmap(icount->single, ino)) {
294 if (icount->multiple &&
295 !ext2fs_test_inode_bitmap(icount->multiple, ino)) {
299 el = get_icount_el(icount, ino, 0);
308 errcode_t ext2fs_icount_increment(ext2_icount_t icount, ext2_ino_t ino,
313 EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
315 if (!ino || (ino > icount->num_inodes))
318 if (ext2fs_test_inode_bitmap(icount->single, ino)) {
323 el = get_icount_el(icount, ino, 1);
326 ext2fs_unmark_inode_bitmap(icount->single, ino);
328 } else if (icount->multiple) {
331 * inode is set in icount->multiple, then there should
335 if (ext2fs_test_inode_bitmap(icount->multiple, ino)) {
336 el = get_icount_el(icount, ino, 1);
346 ext2fs_mark_inode_bitmap(icount->single, ino);
356 el = get_icount_el(icount, ino, 0);
361 el = get_icount_el(icount, ino, 1);
366 if (icount->multiple)
367 ext2fs_mark_inode_bitmap(icount->multiple, ino);
373 errcode_t ext2fs_icount_decrement(ext2_icount_t icount, ext2_ino_t ino,
378 if (!ino || (ino > icount->num_inodes))
381 EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
383 if (ext2fs_test_inode_bitmap(icount->single, ino)) {
384 ext2fs_unmark_inode_bitmap(icount->single, ino);
385 if (icount->multiple)
386 ext2fs_unmark_inode_bitmap(icount->multiple, ino);
388 el = get_icount_el(icount, ino, 0);
397 if (icount->multiple &&
398 !ext2fs_test_inode_bitmap(icount->multiple, ino))
401 el = get_icount_el(icount, ino, 0);
407 ext2fs_mark_inode_bitmap(icount->single, ino);
408 if ((el->count == 0) && icount->multiple)
409 ext2fs_unmark_inode_bitmap(icount->multiple, ino);
416 errcode_t ext2fs_icount_store(ext2_icount_t icount, ext2_ino_t ino,
421 if (!ino || (ino > icount->num_inodes))
424 EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
427 ext2fs_mark_inode_bitmap(icount->single, ino);
428 if (icount->multiple)
429 ext2fs_unmark_inode_bitmap(icount->multiple, ino);
433 ext2fs_unmark_inode_bitmap(icount->single, ino);
434 if (icount->multiple) {
436 * If the icount->multiple bitmap is enabled,
439 ext2fs_unmark_inode_bitmap(icount->multiple, ino);
441 el = get_icount_el(icount, ino, 0);
449 * Get the icount element
451 el = get_icount_el(icount, ino, 1);
455 ext2fs_unmark_inode_bitmap(icount->single, ino);
456 if (icount->multiple)
457 ext2fs_mark_inode_bitmap(icount->multiple, ino);
461 ext2_ino_t ext2fs_get_icount_size(ext2_icount_t icount)
463 if (!icount || icount->magic != EXT2_ET_MAGIC_ICOUNT)
466 return icount->size;