dblist.c revision 4c77fe50d97a773e32a4756c79dade3adbb6a601
1/* 2 * dblist.c -- directory block list functions 3 * 4 * Copyright 1997 by Theodore Ts'o 5 * 6 * %Begin-Header% 7 * This file may be redistributed under the terms of the GNU Public 8 * License. 9 * %End-Header% 10 * 11 */ 12 13#include <stdio.h> 14#if HAVE_UNISTD_H 15#include <unistd.h> 16#endif 17#include <string.h> 18#include <time.h> 19 20#if EXT2_FLAT_INCLUDES 21#include "ext2_fs.h" 22#else 23#include <linux/ext2_fs.h> 24#endif 25 26#include "ext2fsP.h" 27 28static EXT2_QSORT_TYPE dir_block_cmp(const void *a, const void *b); 29 30/* 31 * Returns the number of directories in the filesystem as reported by 32 * the group descriptors. Of course, the group descriptors could be 33 * wrong! 34 */ 35errcode_t ext2fs_get_num_dirs(ext2_filsys fs, ino_t *ret_num_dirs) 36{ 37 int i; 38 ino_t num_dirs, max_dirs; 39 40 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 41 42 num_dirs = 0; 43 max_dirs = fs->super->s_inodes_per_group; 44 for (i = 0; i < fs->group_desc_count; i++) { 45 if (fs->group_desc[i].bg_used_dirs_count > max_dirs) 46 num_dirs += max_dirs / 8; 47 else 48 num_dirs += fs->group_desc[i].bg_used_dirs_count; 49 } 50 if (num_dirs > fs->super->s_inodes_count) 51 num_dirs = fs->super->s_inodes_count; 52 53 *ret_num_dirs = num_dirs; 54 55 return 0; 56} 57 58/* 59 * helper function for making a new directory block list (for 60 * initialize and copy). 61 */ 62static errcode_t make_dblist(ext2_filsys fs, ino_t size, ino_t count, 63 struct ext2_db_entry *list, 64 ext2_dblist *ret_dblist) 65{ 66 ext2_dblist dblist; 67 errcode_t retval; 68 size_t len; 69 70 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 71 72 if ((ret_dblist == 0) && fs->dblist && 73 (fs->dblist->magic == EXT2_ET_MAGIC_DBLIST)) 74 return 0; 75 76 retval = ext2fs_get_mem(sizeof(struct ext2_struct_dblist), 77 (void **) &dblist); 78 if (retval) 79 return retval; 80 memset(dblist, 0, sizeof(struct ext2_struct_dblist)); 81 82 dblist->magic = EXT2_ET_MAGIC_DBLIST; 83 dblist->fs = fs; 84 if (size) 85 dblist->size = size; 86 else { 87 retval = ext2fs_get_num_dirs(fs, &dblist->size); 88 if (retval) 89 goto cleanup; 90 dblist->size = (dblist->size * 2) + 12; 91 } 92 len = (size_t) sizeof(struct ext2_db_entry) * dblist->size; 93 dblist->count = count; 94 retval = ext2fs_get_mem(len, (void **) &dblist->list); 95 if (retval) 96 goto cleanup; 97 98 if (list) 99 memcpy(dblist->list, list, len); 100 else 101 memset(dblist->list, 0, len); 102 *ret_dblist = dblist; 103 return 0; 104cleanup: 105 if (dblist) 106 ext2fs_free_mem((void **) &dblist); 107 return retval; 108} 109 110/* 111 * Initialize a directory block list 112 */ 113errcode_t ext2fs_init_dblist(ext2_filsys fs, ext2_dblist *ret_dblist) 114{ 115 ext2_dblist dblist; 116 errcode_t retval; 117 118 retval = make_dblist(fs, 0, 0, 0, &dblist); 119 if (retval) 120 return retval; 121 122 dblist->sorted = 1; 123 if (ret_dblist) 124 *ret_dblist = dblist; 125 else 126 fs->dblist = dblist; 127 128 return 0; 129} 130 131/* 132 * Copy a directory block list 133 */ 134errcode_t ext2fs_copy_dblist(ext2_dblist src, ext2_dblist *dest) 135{ 136 ext2_dblist dblist; 137 errcode_t retval; 138 139 retval = make_dblist(src->fs, src->size, src->count, src->list, 140 &dblist); 141 if (retval) 142 return retval; 143 dblist->sorted = src->sorted; 144 *dest = dblist; 145 return 0; 146} 147 148/* 149 * Close a directory block list 150 * 151 * (moved to closefs.c) 152 */ 153 154 155/* 156 * Add a directory block to the directory block list 157 */ 158errcode_t ext2fs_add_dir_block(ext2_dblist dblist, ino_t ino, blk_t blk, 159 int blockcnt) 160{ 161 struct ext2_db_entry *new_entry; 162 errcode_t retval; 163 unsigned long old_size; 164 165 EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); 166 167 if (dblist->count >= dblist->size) { 168 old_size = dblist->size * sizeof(struct ext2_db_entry); 169 dblist->size += 100; 170 retval = ext2fs_resize_mem(old_size, (size_t) dblist->size * 171 sizeof(struct ext2_db_entry), 172 (void **) &dblist->list); 173 if (retval) { 174 dblist->size -= 100; 175 return retval; 176 } 177 } 178 new_entry = dblist->list + ( (int) dblist->count++); 179 new_entry->blk = blk; 180 new_entry->ino = ino; 181 new_entry->blockcnt = blockcnt; 182 183 dblist->sorted = 0; 184 185 return 0; 186} 187 188/* 189 * Change the directory block to the directory block list 190 */ 191errcode_t ext2fs_set_dir_block(ext2_dblist dblist, ino_t ino, blk_t blk, 192 int blockcnt) 193{ 194 int i; 195 196 EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); 197 198 for (i=0; i < dblist->count; i++) { 199 if ((dblist->list[i].ino != ino) || 200 (dblist->list[i].blockcnt != blockcnt)) 201 continue; 202 dblist->list[i].blk = blk; 203 dblist->sorted = 0; 204 return 0; 205 } 206 return EXT2_ET_DB_NOT_FOUND; 207} 208 209/* 210 * This function iterates over the directory block list 211 */ 212errcode_t ext2fs_dblist_iterate(ext2_dblist dblist, 213 int (*func)(ext2_filsys fs, 214 struct ext2_db_entry *db_info, 215 void *priv_data), 216 void *priv_data) 217{ 218 ino_t i; 219 int ret; 220 221 EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); 222 223 if (!dblist->sorted) { 224 qsort(dblist->list, (size_t) dblist->count, 225 sizeof(struct ext2_db_entry), dir_block_cmp); 226 dblist->sorted = 1; 227 } 228 for (i=0; i < dblist->count; i++) { 229 ret = (*func)(dblist->fs, &dblist->list[(int)i], priv_data); 230 if (ret & DBLIST_ABORT) 231 return 0; 232 } 233 return 0; 234} 235 236 237static EXT2_QSORT_TYPE dir_block_cmp(const void *a, const void *b) 238{ 239 const struct ext2_db_entry *db_a = 240 (const struct ext2_db_entry *) a; 241 const struct ext2_db_entry *db_b = 242 (const struct ext2_db_entry *) b; 243 244 if (db_a->blk != db_b->blk) 245 return (int) (db_a->blk - db_b->blk); 246 247 if (db_a->ino != db_b->ino) 248 return (int) (db_a->ino - db_b->ino); 249 250 return (int) (db_a->blockcnt - db_b->blockcnt); 251} 252 253int ext2fs_dblist_count(ext2_dblist dblist) 254{ 255 return (int) dblist->count; 256} 257