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 * helper function for making a new directory block list (for
29 * initialize and copy).
31 static errcode_t
make_dblist(ext2_filsys fs
, ext2_ino_t size
,
33 struct ext2_db_entry2
*list
,
34 ext2_dblist
*ret_dblist
)
36 ext2_dblist dblist
= NULL
;
41 EXT2_CHECK_MAGIC(fs
, EXT2_ET_MAGIC_EXT2FS_FILSYS
);
43 if ((ret_dblist
== 0) && fs
->dblist
&&
44 (fs
->dblist
->magic
== EXT2_ET_MAGIC_DBLIST
))
47 retval
= ext2fs_get_mem(sizeof(struct ext2_struct_dblist
), &dblist
);
50 memset(dblist
, 0, sizeof(struct ext2_struct_dblist
));
52 dblist
->magic
= EXT2_ET_MAGIC_DBLIST
;
57 retval
= ext2fs_get_num_dirs(fs
, &num_dirs
);
60 dblist
->size
= (num_dirs
* 2) + 12;
62 len
= (size_t) sizeof(struct ext2_db_entry2
) * dblist
->size
;
63 dblist
->count
= count
;
64 retval
= ext2fs_get_array(dblist
->size
, sizeof(struct ext2_db_entry2
),
70 memcpy(dblist
->list
, list
, len
);
72 memset(dblist
->list
, 0, len
);
80 ext2fs_free_mem(&dblist
);
85 * Initialize a directory block list
87 errcode_t
ext2fs_init_dblist(ext2_filsys fs
, ext2_dblist
*ret_dblist
)
92 retval
= make_dblist(fs
, 0, 0, 0, &dblist
);
106 * Copy a directory block list
108 errcode_t
ext2fs_copy_dblist(ext2_dblist src
, ext2_dblist
*dest
)
113 retval
= make_dblist(src
->fs
, src
->size
, src
->count
, src
->list
,
117 dblist
->sorted
= src
->sorted
;
123 * Close a directory block list
125 * (moved to closefs.c)
130 * Add a directory block to the directory block list
132 errcode_t
ext2fs_add_dir_block2(ext2_dblist dblist
, ext2_ino_t ino
,
133 blk64_t blk
, e2_blkcnt_t blockcnt
)
135 struct ext2_db_entry2
*new_entry
;
137 unsigned long old_size
;
139 EXT2_CHECK_MAGIC(dblist
, EXT2_ET_MAGIC_DBLIST
);
141 if (dblist
->count
>= dblist
->size
) {
142 old_size
= dblist
->size
* sizeof(struct ext2_db_entry2
);
143 dblist
->size
+= dblist
->size
> 200 ? dblist
->size
/ 2 : 100;
144 retval
= ext2fs_resize_mem(old_size
, (size_t) dblist
->size
*
145 sizeof(struct ext2_db_entry2
),
148 dblist
->size
= old_size
/ sizeof(struct ext2_db_entry2
);
152 new_entry
= dblist
->list
+ ( dblist
->count
++);
153 new_entry
->blk
= blk
;
154 new_entry
->ino
= ino
;
155 new_entry
->blockcnt
= blockcnt
;
163 * Change the directory block to the directory block list
165 errcode_t
ext2fs_set_dir_block2(ext2_dblist dblist
, ext2_ino_t ino
,
166 blk64_t blk
, e2_blkcnt_t blockcnt
)
170 EXT2_CHECK_MAGIC(dblist
, EXT2_ET_MAGIC_DBLIST
);
172 for (i
=0; i
< dblist
->count
; i
++) {
173 if ((dblist
->list
[i
].ino
!= ino
) ||
174 (dblist
->list
[i
].blockcnt
!= blockcnt
))
176 dblist
->list
[i
].blk
= blk
;
180 return EXT2_ET_DB_NOT_FOUND
;
183 void ext2fs_dblist_sort2(ext2_dblist dblist
,
184 EXT2_QSORT_TYPE (*sortfunc
)(const void *,
188 sortfunc
= dir_block_cmp2
;
189 qsort(dblist
->list
, (size_t) dblist
->count
,
190 sizeof(struct ext2_db_entry2
), sortfunc
);
195 * This function iterates over the directory block list
197 errcode_t
ext2fs_dblist_iterate3(ext2_dblist dblist
,
198 int (*func
)(ext2_filsys fs
,
199 struct ext2_db_entry2
*db_info
,
201 unsigned long long start
,
202 unsigned long long count
,
205 unsigned long long i
, end
;
208 EXT2_CHECK_MAGIC(dblist
, EXT2_ET_MAGIC_DBLIST
);
212 ext2fs_dblist_sort2(dblist
, 0);
213 if (end
> dblist
->count
)
215 for (i
= start
; i
< end
; i
++) {
216 ret
= (*func
)(dblist
->fs
, &dblist
->list
[i
], priv_data
);
217 if (ret
& DBLIST_ABORT
)
223 errcode_t
ext2fs_dblist_iterate2(ext2_dblist dblist
,
224 int (*func
)(ext2_filsys fs
,
225 struct ext2_db_entry2
*db_info
,
229 return ext2fs_dblist_iterate3(dblist
, func
, 0, dblist
->count
,
233 static EXT2_QSORT_TYPE
dir_block_cmp2(const void *a
, const void *b
)
235 const struct ext2_db_entry2
*db_a
=
236 (const struct ext2_db_entry2
*) a
;
237 const struct ext2_db_entry2
*db_b
=
238 (const struct ext2_db_entry2
*) b
;
240 if (db_a
->blk
!= db_b
->blk
)
241 return (int) (db_a
->blk
- db_b
->blk
);
243 if (db_a
->ino
!= db_b
->ino
)
244 return (int) (db_a
->ino
- db_b
->ino
);
246 return (db_a
->blockcnt
- db_b
->blockcnt
);
249 blk64_t
ext2fs_dblist_count2(ext2_dblist dblist
)
251 return dblist
->count
;
254 errcode_t
ext2fs_dblist_get_last2(ext2_dblist dblist
,
255 struct ext2_db_entry2
**entry
)
257 EXT2_CHECK_MAGIC(dblist
, EXT2_ET_MAGIC_DBLIST
);
259 if (dblist
->count
== 0)
260 return EXT2_ET_DBLIST_EMPTY
;
263 *entry
= dblist
->list
+ ( dblist
->count
-1);
267 errcode_t
ext2fs_dblist_drop_last(ext2_dblist dblist
)
269 EXT2_CHECK_MAGIC(dblist
, EXT2_ET_MAGIC_DBLIST
);
271 if (dblist
->count
== 0)
272 return EXT2_ET_DBLIST_EMPTY
;
279 * Legacy 32-bit versions
283 * Add a directory block to the directory block list
285 errcode_t
ext2fs_add_dir_block(ext2_dblist dblist
, ext2_ino_t ino
, blk_t blk
,
288 return ext2fs_add_dir_block2(dblist
, ino
, blk
, blockcnt
);
292 * Change the directory block to the directory block list
294 errcode_t
ext2fs_set_dir_block(ext2_dblist dblist
, ext2_ino_t ino
, blk_t blk
,
297 return ext2fs_set_dir_block2(dblist
, ino
, blk
, blockcnt
);
300 void ext2fs_dblist_sort(ext2_dblist dblist
,
301 EXT2_QSORT_TYPE (*sortfunc
)(const void *,
305 sortfunc32
= sortfunc
;
306 sortfunc
= dir_block_cmp
;
308 sortfunc
= dir_block_cmp2
;
309 qsort(dblist
->list
, (size_t) dblist
->count
,
310 sizeof(struct ext2_db_entry2
), sortfunc
);
315 * This function iterates over the directory block list
317 struct iterate_passthrough
{
318 int (*func
)(ext2_filsys fs
,
319 struct ext2_db_entry
*db_info
,
324 static int passthrough_func(ext2_filsys fs
,
325 struct ext2_db_entry2
*db_info
,
328 struct iterate_passthrough
*p
= priv_data
;
329 struct ext2_db_entry db
;
332 db
.ino
= db_info
->ino
;
333 db
.blk
= (blk_t
) db_info
->blk
;
334 db
.blockcnt
= (int) db_info
->blockcnt
;
335 ret
= (p
->func
)(fs
, &db
, p
->priv_data
);
336 db_info
->ino
= db
.ino
;
337 db_info
->blk
= db
.blk
;
338 db_info
->blockcnt
= db
.blockcnt
;
342 errcode_t
ext2fs_dblist_iterate(ext2_dblist dblist
,
343 int (*func
)(ext2_filsys fs
,
344 struct ext2_db_entry
*db_info
,
348 struct iterate_passthrough pass
;
350 EXT2_CHECK_MAGIC(dblist
, EXT2_ET_MAGIC_DBLIST
);
352 pass
.priv_data
= priv_data
;
354 return ext2fs_dblist_iterate2(dblist
, passthrough_func
, &pass
);
357 static EXT2_QSORT_TYPE
dir_block_cmp(const void *a
, const void *b
)
359 const struct ext2_db_entry2
*db_a
=
360 (const struct ext2_db_entry2
*) a
;
361 const struct ext2_db_entry2
*db_b
=
362 (const struct ext2_db_entry2
*) b
;
364 struct ext2_db_entry a32
, b32
;
366 a32
.ino
= db_a
->ino
; a32
.blk
= db_a
->blk
;
367 a32
.blockcnt
= db_a
->blockcnt
;
369 b32
.ino
= db_b
->ino
; b32
.blk
= db_b
->blk
;
370 b32
.blockcnt
= db_b
->blockcnt
;
372 return sortfunc32(&a32
, &b32
);
375 int ext2fs_dblist_count(ext2_dblist dblist
)
377 return dblist
->count
;
380 errcode_t
ext2fs_dblist_get_last(ext2_dblist dblist
,
381 struct ext2_db_entry
**entry
)
383 static struct ext2_db_entry ret_entry
;
384 struct ext2_db_entry2
*last
;
386 EXT2_CHECK_MAGIC(dblist
, EXT2_ET_MAGIC_DBLIST
);
388 if (dblist
->count
== 0)
389 return EXT2_ET_DBLIST_EMPTY
;
394 last
= dblist
->list
+ dblist
->count
-1;
396 ret_entry
.ino
= last
->ino
;
397 ret_entry
.blk
= last
->blk
;
398 ret_entry
.blockcnt
= last
->blockcnt
;