1/* vi: set sw=4 ts=4: */ 2/* 3 * dblist.c -- directory block list functions 4 * 5 * Copyright 1997 by Theodore Ts'o 6 * 7 * %Begin-Header% 8 * This file may be redistributed under the terms of the GNU Public 9 * License. 10 * %End-Header% 11 * 12 */ 13 14#include <stdio.h> 15#if HAVE_UNISTD_H 16#include <unistd.h> 17#endif 18#include <string.h> 19#include <time.h> 20 21#include "ext2_fs.h" 22#include "ext2fsP.h" 23 24static int dir_block_cmp(const void *a, const void *b); 25 26/* 27 * Returns the number of directories in the filesystem as reported by 28 * the group descriptors. Of course, the group descriptors could be 29 * wrong! 30 */ 31errcode_t ext2fs_get_num_dirs(ext2_filsys fs, ext2_ino_t *ret_num_dirs) 32{ 33 dgrp_t i; 34 ext2_ino_t num_dirs, max_dirs; 35 36 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 37 38 num_dirs = 0; 39 max_dirs = fs->super->s_inodes_per_group; 40 for (i = 0; i < fs->group_desc_count; i++) { 41 if (fs->group_desc[i].bg_used_dirs_count > max_dirs) 42 num_dirs += max_dirs / 8; 43 else 44 num_dirs += fs->group_desc[i].bg_used_dirs_count; 45 } 46 if (num_dirs > fs->super->s_inodes_count) 47 num_dirs = fs->super->s_inodes_count; 48 49 *ret_num_dirs = num_dirs; 50 51 return 0; 52} 53 54/* 55 * helper function for making a new directory block list (for 56 * initialize and copy). 57 */ 58static errcode_t make_dblist(ext2_filsys fs, ext2_ino_t size, ext2_ino_t count, 59 struct ext2_db_entry *list, 60 ext2_dblist *ret_dblist) 61{ 62 ext2_dblist dblist; 63 errcode_t retval; 64 size_t len; 65 66 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 67 68 if ((ret_dblist == 0) && fs->dblist && 69 (fs->dblist->magic == EXT2_ET_MAGIC_DBLIST)) 70 return 0; 71 72 retval = ext2fs_get_mem(sizeof(struct ext2_struct_dblist), &dblist); 73 if (retval) 74 return retval; 75 memset(dblist, 0, sizeof(struct ext2_struct_dblist)); 76 77 dblist->magic = EXT2_ET_MAGIC_DBLIST; 78 dblist->fs = fs; 79 if (size) 80 dblist->size = size; 81 else { 82 retval = ext2fs_get_num_dirs(fs, &dblist->size); 83 if (retval) 84 goto cleanup; 85 dblist->size = (dblist->size * 2) + 12; 86 } 87 len = (size_t) sizeof(struct ext2_db_entry) * dblist->size; 88 dblist->count = count; 89 retval = ext2fs_get_mem(len, &dblist->list); 90 if (retval) 91 goto cleanup; 92 93 if (list) 94 memcpy(dblist->list, list, len); 95 else 96 memset(dblist->list, 0, len); 97 if (ret_dblist) 98 *ret_dblist = dblist; 99 else 100 fs->dblist = dblist; 101 return 0; 102cleanup: 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 += 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 int (*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 int 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