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 22static 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 */ 29errcode_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 */ 56static 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; 101cleanup: 102 if (dblist) 103 ext2fs_free_mem(&dblist); 104 return retval; 105} 106 107/* 108 * Initialize a directory block list 109 */ 110errcode_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 */ 131errcode_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 */ 155errcode_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 */ 188errcode_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 206void 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 */ 220errcode_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 241static 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 257int ext2fs_dblist_count(ext2_dblist dblist) 258{ 259 return (int) dblist->count; 260} 261 262errcode_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 275errcode_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