From 498267851d48ee60376dc96411fb8693a5e95a3c Mon Sep 17 00:00:00 2001 From: Guido Guenther Date: Wed, 21 Nov 2007 16:55:40 +0100 Subject: remove unneeded e2fslib --- e2fslib/icount.c | 482 ------------------------------------------------------- 1 file changed, 482 deletions(-) delete mode 100644 e2fslib/icount.c (limited to 'e2fslib/icount.c') diff --git a/e2fslib/icount.c b/e2fslib/icount.c deleted file mode 100644 index 1ad3940..0000000 --- a/e2fslib/icount.c +++ /dev/null @@ -1,482 +0,0 @@ -/* - * icount.c --- an efficient inode count abstraction - * - * Copyright (C) 1997 Theodore Ts'o. - * - * %Begin-Header% - * This file may be redistributed under the terms of the GNU Public - * License. - * %End-Header% - */ - -#if HAVE_UNISTD_H -#include -#endif -#include -#include - -#include "ext2_fs.h" -#include "ext2fs.h" - -/* - * The data storage strategy used by icount relies on the observation - * that most inode counts are either zero (for non-allocated inodes), - * one (for most files), and only a few that are two or more - * (directories and files that are linked to more than one directory). - * - * Also, e2fsck tends to load the icount data sequentially. - * - * So, we use an inode bitmap to indicate which inodes have a count of - * one, and then use a sorted list to store the counts for inodes - * which are greater than one. - * - * We also use an optional bitmap to indicate which inodes are already - * in the sorted list, to speed up the use of this abstraction by - * e2fsck's pass 2. Pass 2 increments inode counts as it finds them, - * so this extra bitmap avoids searching the sorted list to see if a - * particular inode is on the sorted list already. - */ - -struct ext2_icount_el { - ext2_ino_t ino; - __u16 count; -}; - -struct ext2_icount { - errcode_t magic; - ext2fs_inode_bitmap single; - ext2fs_inode_bitmap multiple; - ext2_ino_t count; - ext2_ino_t size; - ext2_ino_t num_inodes; - int cursor; - struct ext2_icount_el *list; -}; - -void ext2fs_free_icount(ext2_icount_t icount) -{ - if (!icount) - return; - - icount->magic = 0; - if (icount->list) - ext2fs_free_mem((void **) &icount->list); - if (icount->single) - ext2fs_free_inode_bitmap(icount->single); - if (icount->multiple) - ext2fs_free_inode_bitmap(icount->multiple); - ext2fs_free_mem((void **) &icount); -} - -errcode_t ext2fs_create_icount2(ext2_filsys fs, int flags, int size, - ext2_icount_t hint, ext2_icount_t *ret) -{ - ext2_icount_t icount; - errcode_t retval; - size_t bytes; - int i; - - if (hint) { - EXT2_CHECK_MAGIC(hint, EXT2_ET_MAGIC_ICOUNT); - if (hint->size > size) - size = (size_t) hint->size; - } - - retval = ext2fs_get_mem(sizeof(struct ext2_icount), (void **) &icount); - if (retval) - return retval; - memset(icount, 0, sizeof(struct ext2_icount)); - - retval = ext2fs_allocate_inode_bitmap(fs, 0, - &icount->single); - if (retval) - goto errout; - - if (flags & EXT2_ICOUNT_OPT_INCREMENT) { - retval = ext2fs_allocate_inode_bitmap(fs, 0, - &icount->multiple); - if (retval) - goto errout; - } else - icount->multiple = 0; - - if (size) { - icount->size = size; - } else { - /* - * Figure out how many special case inode counts we will - * have. We know we will need one for each directory; - * we also need to reserve some extra room for file links - */ - retval = ext2fs_get_num_dirs(fs, &icount->size); - if (retval) - goto errout; - icount->size += fs->super->s_inodes_count / 50; - } - - bytes = (size_t) (icount->size * sizeof(struct ext2_icount_el)); -#if 0 - printf("Icount allocated %d entries, %d bytes.\n", - icount->size, bytes); -#endif - retval = ext2fs_get_mem(bytes, (void **) &icount->list); - if (retval) - goto errout; - memset(icount->list, 0, bytes); - - icount->magic = EXT2_ET_MAGIC_ICOUNT; - icount->count = 0; - icount->cursor = 0; - icount->num_inodes = fs->super->s_inodes_count; - - /* - * Populate the sorted list with those entries which were - * found in the hint icount (since those are ones which will - * likely need to be in the sorted list this time around). - */ - if (hint) { - for (i=0; i < hint->count; i++) - icount->list[i].ino = hint->list[i].ino; - icount->count = hint->count; - } - - *ret = icount; - return 0; - -errout: - ext2fs_free_icount(icount); - return(retval); -} - -errcode_t ext2fs_create_icount(ext2_filsys fs, int flags, int size, - ext2_icount_t *ret) -{ - return ext2fs_create_icount2(fs, flags, size, 0, ret); -} - -/* - * insert_icount_el() --- Insert a new entry into the sorted list at a - * specified position. - */ -static struct ext2_icount_el *insert_icount_el(ext2_icount_t icount, - ext2_ino_t ino, int pos) -{ - struct ext2_icount_el *el; - errcode_t retval; - ext2_ino_t new_size = 0; - int num; - - if (icount->count >= icount->size) { - if (icount->count) { - new_size = icount->list[(unsigned)icount->count-1].ino; - new_size = (ext2_ino_t) (icount->count * - ((float) icount->num_inodes / new_size)); - } - if (new_size < (icount->size + 100)) - new_size = icount->size + 100; -#if 0 - printf("Reallocating icount %d entries...\n", new_size); -#endif - retval = ext2fs_resize_mem((size_t) icount->size * - sizeof(struct ext2_icount_el), - (size_t) new_size * - sizeof(struct ext2_icount_el), - (void **) &icount->list); - if (retval) - return 0; - icount->size = new_size; - } - num = (int) icount->count - pos; - if (num < 0) - return 0; /* should never happen */ - if (num) { - memmove(&icount->list[pos+1], &icount->list[pos], - sizeof(struct ext2_icount_el) * num); - } - icount->count++; - el = &icount->list[pos]; - el->count = 0; - el->ino = ino; - return el; -} - -/* - * get_icount_el() --- given an inode number, try to find icount - * information in the sorted list. If the create flag is set, - * and we can't find an entry, create one in the sorted list. - */ -static struct ext2_icount_el *get_icount_el(ext2_icount_t icount, - ext2_ino_t ino, int create) -{ - float range; - int low, high, mid; - ext2_ino_t lowval, highval; - - if (!icount || !icount->list) - return 0; - - if (create && ((icount->count == 0) || - (ino > icount->list[(unsigned)icount->count-1].ino))) { - return insert_icount_el(icount, ino, (unsigned) icount->count); - } - if (icount->count == 0) - return 0; - - if (icount->cursor >= icount->count) - icount->cursor = 0; - if (ino == icount->list[icount->cursor].ino) - return &icount->list[icount->cursor++]; -#if 0 - printf("Non-cursor get_icount_el: %u\n", ino); -#endif - low = 0; - high = (int) icount->count-1; - while (low <= high) { -#if 0 - mid = (low+high)/2; -#else - if (low == high) - mid = low; - else { - /* Interpolate for efficiency */ - lowval = icount->list[low].ino; - highval = icount->list[high].ino; - - if (ino < lowval) - range = 0; - else if (ino > highval) - range = 1; - else - range = ((float) (ino - lowval)) / - (highval - lowval); - mid = low + ((int) (range * (high-low))); - } -#endif - if (ino == icount->list[mid].ino) { - icount->cursor = mid+1; - return &icount->list[mid]; - } - if (ino < icount->list[mid].ino) - high = mid-1; - else - low = mid+1; - } - /* - * If we need to create a new entry, it should be right at - * low (where high will be left at low-1). - */ - if (create) - return insert_icount_el(icount, ino, low); - return 0; -} - -errcode_t ext2fs_icount_validate(ext2_icount_t icount, FILE *out) -{ - errcode_t ret = 0; - int i; - const char *bad = "bad icount"; - - EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); - - if (icount->count > icount->size) { - fprintf(out, "%s: count > size\n", bad); - return EXT2_ET_INVALID_ARGUMENT; - } - for (i=1; i < icount->count; i++) { - if (icount->list[i-1].ino >= icount->list[i].ino) { - fprintf(out, "%s: list[%d].ino=%u, list[%d].ino=%u\n", - bad, i-1, icount->list[i-1].ino, - i, icount->list[i].ino); - ret = EXT2_ET_INVALID_ARGUMENT; - } - } - return ret; -} - -errcode_t ext2fs_icount_fetch(ext2_icount_t icount, ext2_ino_t ino, __u16 *ret) -{ - struct ext2_icount_el *el; - - EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); - - if (!ino || (ino > icount->num_inodes)) - return EXT2_ET_INVALID_ARGUMENT; - - if (ext2fs_test_inode_bitmap(icount->single, ino)) { - *ret = 1; - return 0; - } - if (icount->multiple && - !ext2fs_test_inode_bitmap(icount->multiple, ino)) { - *ret = 0; - return 0; - } - el = get_icount_el(icount, ino, 0); - if (!el) { - *ret = 0; - return 0; - } - *ret = el->count; - return 0; -} - -errcode_t ext2fs_icount_increment(ext2_icount_t icount, ext2_ino_t ino, - __u16 *ret) -{ - struct ext2_icount_el *el; - - EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); - - if (!ino || (ino > icount->num_inodes)) - return EXT2_ET_INVALID_ARGUMENT; - - if (ext2fs_test_inode_bitmap(icount->single, ino)) { - /* - * If the existing count is 1, then we know there is - * no entry in the list. - */ - el = get_icount_el(icount, ino, 1); - if (!el) - return EXT2_ET_NO_MEMORY; - ext2fs_unmark_inode_bitmap(icount->single, ino); - el->count = 2; - } else if (icount->multiple) { - /* - * The count is either zero or greater than 1; if the - * inode is set in icount->multiple, then there should - * be an entry in the list, so find it using - * get_icount_el(). - */ - if (ext2fs_test_inode_bitmap(icount->multiple, ino)) { - el = get_icount_el(icount, ino, 1); - if (!el) - return EXT2_ET_NO_MEMORY; - el->count++; - } else { - /* - * The count was zero; mark the single bitmap - * and return. - */ - zero_count: - ext2fs_mark_inode_bitmap(icount->single, ino); - if (ret) - *ret = 1; - return 0; - } - } else { - /* - * The count is either zero or greater than 1; try to - * find an entry in the list to determine which. - */ - el = get_icount_el(icount, ino, 0); - if (!el) { - /* No entry means the count was zero */ - goto zero_count; - } - el = get_icount_el(icount, ino, 1); - if (!el) - return EXT2_ET_NO_MEMORY; - el->count++; - } - if (icount->multiple) - ext2fs_mark_inode_bitmap(icount->multiple, ino); - if (ret) - *ret = el->count; - return 0; -} - -errcode_t ext2fs_icount_decrement(ext2_icount_t icount, ext2_ino_t ino, - __u16 *ret) -{ - struct ext2_icount_el *el; - - if (!ino || (ino > icount->num_inodes)) - return EXT2_ET_INVALID_ARGUMENT; - - EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); - - if (ext2fs_test_inode_bitmap(icount->single, ino)) { - ext2fs_unmark_inode_bitmap(icount->single, ino); - if (icount->multiple) - ext2fs_unmark_inode_bitmap(icount->multiple, ino); - else { - el = get_icount_el(icount, ino, 0); - if (el) - el->count = 0; - } - if (ret) - *ret = 0; - return 0; - } - - if (icount->multiple && - !ext2fs_test_inode_bitmap(icount->multiple, ino)) - return EXT2_ET_INVALID_ARGUMENT; - - el = get_icount_el(icount, ino, 0); - if (!el || el->count == 0) - return EXT2_ET_INVALID_ARGUMENT; - - el->count--; - if (el->count == 1) - ext2fs_mark_inode_bitmap(icount->single, ino); - if ((el->count == 0) && icount->multiple) - ext2fs_unmark_inode_bitmap(icount->multiple, ino); - - if (ret) - *ret = el->count; - return 0; -} - -errcode_t ext2fs_icount_store(ext2_icount_t icount, ext2_ino_t ino, - __u16 count) -{ - struct ext2_icount_el *el; - - if (!ino || (ino > icount->num_inodes)) - return EXT2_ET_INVALID_ARGUMENT; - - EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); - - if (count == 1) { - ext2fs_mark_inode_bitmap(icount->single, ino); - if (icount->multiple) - ext2fs_unmark_inode_bitmap(icount->multiple, ino); - return 0; - } - if (count == 0) { - ext2fs_unmark_inode_bitmap(icount->single, ino); - if (icount->multiple) { - /* - * If the icount->multiple bitmap is enabled, - * we can just clear both bitmaps and we're done - */ - ext2fs_unmark_inode_bitmap(icount->multiple, ino); - } else { - el = get_icount_el(icount, ino, 0); - if (el) - el->count = 0; - } - return 0; - } - - /* - * Get the icount element - */ - el = get_icount_el(icount, ino, 1); - if (!el) - return EXT2_ET_NO_MEMORY; - el->count = count; - ext2fs_unmark_inode_bitmap(icount->single, ino); - if (icount->multiple) - ext2fs_mark_inode_bitmap(icount->multiple, ino); - return 0; -} - -ext2_ino_t ext2fs_get_icount_size(ext2_icount_t icount) -{ - if (!icount || icount->magic != EXT2_ET_MAGIC_ICOUNT) - return 0; - - return icount->size; -} -- cgit v1.2.3