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