2 * dblist.c -- directory block list functions
4 * Copyright 1997 by Theodore Ts'o
7 * This file may be redistributed under the terms of the GNU Library
8 * General Public License, version 2.
23 static EXT2_QSORT_TYPE dir_block_cmp(const void *a, const void *b);
24 static EXT2_QSORT_TYPE dir_block_cmp2(const void *a, const void *b);
25 static EXT2_QSORT_TYPE (*sortfunc32)(const void *a, const void *b);
28 * Returns the number of directories in the filesystem as reported by
29 * the group descriptors. Of course, the group descriptors could be
32 errcode_t ext2fs_get_num_dirs(ext2_filsys fs, ext2_ino_t *ret_num_dirs)
35 ext2_ino_t num_dirs, max_dirs;
37 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
40 max_dirs = fs->super->s_inodes_per_group;
41 for (i = 0; i < fs->group_desc_count; i++) {
42 if (ext2fs_bg_used_dirs_count(fs, i) > max_dirs)
43 num_dirs += max_dirs / 8;
45 num_dirs += ext2fs_bg_used_dirs_count(fs, i);
47 if (num_dirs > fs->super->s_inodes_count)
48 num_dirs = fs->super->s_inodes_count;
50 *ret_num_dirs = num_dirs;
56 * helper function for making a new directory block list (for
57 * initialize and copy).
59 static errcode_t make_dblist(ext2_filsys fs, ext2_ino_t size,
61 struct ext2_db_entry2 *list,
62 ext2_dblist *ret_dblist)
64 ext2_dblist dblist = NULL;
69 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
71 if ((ret_dblist == 0) && fs->dblist &&
72 (fs->dblist->magic == EXT2_ET_MAGIC_DBLIST))
75 retval = ext2fs_get_mem(sizeof(struct ext2_struct_dblist), &dblist);
78 memset(dblist, 0, sizeof(struct ext2_struct_dblist));
80 dblist->magic = EXT2_ET_MAGIC_DBLIST;
85 retval = ext2fs_get_num_dirs(fs, &num_dirs);
88 dblist->size = (num_dirs * 2) + 12;
90 len = (size_t) sizeof(struct ext2_db_entry2) * dblist->size;
91 dblist->count = count;
92 retval = ext2fs_get_array(dblist->size, sizeof(struct ext2_db_entry2),
98 memcpy(dblist->list, list, len);
100 memset(dblist->list, 0, len);
102 *ret_dblist = dblist;
108 ext2fs_free_mem(&dblist);
113 * Initialize a directory block list
115 errcode_t ext2fs_init_dblist(ext2_filsys fs, ext2_dblist *ret_dblist)
120 retval = make_dblist(fs, 0, 0, 0, &dblist);
126 *ret_dblist = dblist;
134 * Copy a directory block list
136 errcode_t ext2fs_copy_dblist(ext2_dblist src, ext2_dblist *dest)
141 retval = make_dblist(src->fs, src->size, src->count, src->list,
145 dblist->sorted = src->sorted;
151 * Close a directory block list
153 * (moved to closefs.c)
158 * Add a directory block to the directory block list
160 errcode_t ext2fs_add_dir_block2(ext2_dblist dblist, ext2_ino_t ino,
161 blk64_t blk, e2_blkcnt_t blockcnt)
163 struct ext2_db_entry2 *new_entry;
165 unsigned long old_size;
167 EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
169 if (dblist->count >= dblist->size) {
170 old_size = dblist->size * sizeof(struct ext2_db_entry2);
171 dblist->size += dblist->size > 200 ? dblist->size / 2 : 100;
172 retval = ext2fs_resize_mem(old_size, (size_t) dblist->size *
173 sizeof(struct ext2_db_entry2),
176 dblist->size = old_size / sizeof(struct ext2_db_entry2);
180 new_entry = dblist->list + ( dblist->count++);
181 new_entry->blk = blk;
182 new_entry->ino = ino;
183 new_entry->blockcnt = blockcnt;
191 * Change the directory block to the directory block list
193 errcode_t ext2fs_set_dir_block2(ext2_dblist dblist, ext2_ino_t ino,
194 blk64_t blk, e2_blkcnt_t blockcnt)
198 EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
200 for (i=0; i < dblist->count; i++) {
201 if ((dblist->list[i].ino != ino) ||
202 (dblist->list[i].blockcnt != blockcnt))
204 dblist->list[i].blk = blk;
208 return EXT2_ET_DB_NOT_FOUND;
211 void ext2fs_dblist_sort2(ext2_dblist dblist,
212 EXT2_QSORT_TYPE (*sortfunc)(const void *,
216 sortfunc = dir_block_cmp2;
217 qsort(dblist->list, (size_t) dblist->count,
218 sizeof(struct ext2_db_entry2), sortfunc);
223 * This function iterates over the directory block list
225 errcode_t ext2fs_dblist_iterate2(ext2_dblist dblist,
226 int (*func)(ext2_filsys fs,
227 struct ext2_db_entry2 *db_info,
231 unsigned long long i;
234 EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
237 ext2fs_dblist_sort2(dblist, 0);
238 for (i=0; i < dblist->count; i++) {
239 ret = (*func)(dblist->fs, &dblist->list[i], priv_data);
240 if (ret & DBLIST_ABORT)
246 static EXT2_QSORT_TYPE dir_block_cmp2(const void *a, const void *b)
248 const struct ext2_db_entry2 *db_a =
249 (const struct ext2_db_entry2 *) a;
250 const struct ext2_db_entry2 *db_b =
251 (const struct ext2_db_entry2 *) b;
253 if (db_a->blk != db_b->blk)
254 return (int) (db_a->blk - db_b->blk);
256 if (db_a->ino != db_b->ino)
257 return (int) (db_a->ino - db_b->ino);
259 return (db_a->blockcnt - db_b->blockcnt);
262 blk64_t ext2fs_dblist_count2(ext2_dblist dblist)
264 return dblist->count;
267 errcode_t ext2fs_dblist_get_last2(ext2_dblist dblist,
268 struct ext2_db_entry2 **entry)
270 EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
272 if (dblist->count == 0)
273 return EXT2_ET_DBLIST_EMPTY;
276 *entry = dblist->list + ( dblist->count-1);
280 errcode_t ext2fs_dblist_drop_last(ext2_dblist dblist)
282 EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
284 if (dblist->count == 0)
285 return EXT2_ET_DBLIST_EMPTY;
292 * Legacy 32-bit versions
296 * Add a directory block to the directory block list
298 errcode_t ext2fs_add_dir_block(ext2_dblist dblist, ext2_ino_t ino, blk_t blk,
301 return ext2fs_add_dir_block2(dblist, ino, blk, blockcnt);
305 * Change the directory block to the directory block list
307 errcode_t ext2fs_set_dir_block(ext2_dblist dblist, ext2_ino_t ino, blk_t blk,
310 return ext2fs_set_dir_block2(dblist, ino, blk, blockcnt);
313 void ext2fs_dblist_sort(ext2_dblist dblist,
314 EXT2_QSORT_TYPE (*sortfunc)(const void *,
318 sortfunc32 = sortfunc;
319 sortfunc = dir_block_cmp;
321 sortfunc = dir_block_cmp2;
322 qsort(dblist->list, (size_t) dblist->count,
323 sizeof(struct ext2_db_entry2), sortfunc);
328 * This function iterates over the directory block list
330 struct iterate_passthrough {
331 int (*func)(ext2_filsys fs,
332 struct ext2_db_entry *db_info,
337 static int passthrough_func(ext2_filsys fs,
338 struct ext2_db_entry2 *db_info,
341 struct iterate_passthrough *p = priv_data;
342 struct ext2_db_entry db;
345 db.ino = db_info->ino;
346 db.blk = (blk_t) db_info->blk;
347 db.blockcnt = (int) db_info->blockcnt;
348 ret = (p->func)(fs, &db, p->priv_data);
349 db_info->ino = db.ino;
350 db_info->blk = db.blk;
351 db_info->blockcnt = db.blockcnt;
355 errcode_t ext2fs_dblist_iterate(ext2_dblist dblist,
356 int (*func)(ext2_filsys fs,
357 struct ext2_db_entry *db_info,
361 struct iterate_passthrough pass;
363 EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
365 pass.priv_data = priv_data;
367 return ext2fs_dblist_iterate2(dblist, passthrough_func, &pass);
370 static EXT2_QSORT_TYPE dir_block_cmp(const void *a, const void *b)
372 const struct ext2_db_entry2 *db_a =
373 (const struct ext2_db_entry2 *) a;
374 const struct ext2_db_entry2 *db_b =
375 (const struct ext2_db_entry2 *) b;
377 struct ext2_db_entry a32, b32;
379 a32.ino = db_a->ino; a32.blk = db_a->blk;
380 a32.blockcnt = db_a->blockcnt;
382 b32.ino = db_b->ino; b32.blk = db_b->blk;
383 b32.blockcnt = db_b->blockcnt;
385 return sortfunc32(&a32, &b32);
388 int ext2fs_dblist_count(ext2_dblist dblist)
390 return dblist->count;
393 errcode_t ext2fs_dblist_get_last(ext2_dblist dblist,
394 struct ext2_db_entry **entry)
396 EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
397 static struct ext2_db_entry ret_entry;
398 struct ext2_db_entry2 *last;
400 if (dblist->count == 0)
401 return EXT2_ET_DBLIST_EMPTY;
406 last = dblist->list + dblist->count -1;
408 ret_entry.ino = last->ino;
409 ret_entry.blk = last->blk;
410 ret_entry.blockcnt = last->blockcnt;