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 "config.h"
13#include <stdio.h>
14#if HAVE_UNISTD_H
15#include <unistd.h>
16#endif
17#include <string.h>
18#include <time.h>
19
20#include "ext2_fs.h"
21#include "ext2fsP.h"
22
23static EXT2_QSORT_TYPE dir_block_cmp(const void *a, const void *b);
24static EXT2_QSORT_TYPE dir_block_cmp2(const void *a, const void *b);
25static EXT2_QSORT_TYPE (*sortfunc32)(const void *a, const void *b);
26
27/*
28 * helper function for making a new directory block list (for
29 * initialize and copy).
30 */
31static errcode_t make_dblist(ext2_filsys fs, ext2_ino_t size,
32			     ext2_ino_t count,
33			     struct ext2_db_entry2 *list,
34			     ext2_dblist *ret_dblist)
35{
36	ext2_dblist	dblist = NULL;
37	errcode_t	retval;
38	ext2_ino_t	num_dirs;
39	size_t		len;
40
41	EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
42
43	if ((ret_dblist == 0) && fs->dblist &&
44	    (fs->dblist->magic == EXT2_ET_MAGIC_DBLIST))
45		return 0;
46
47	retval = ext2fs_get_mem(sizeof(struct ext2_struct_dblist), &dblist);
48	if (retval)
49		goto cleanup;
50	memset(dblist, 0, sizeof(struct ext2_struct_dblist));
51
52	dblist->magic = EXT2_ET_MAGIC_DBLIST;
53	dblist->fs = fs;
54	if (size)
55		dblist->size = size;
56	else {
57		retval = ext2fs_get_num_dirs(fs, &num_dirs);
58		if (retval)
59			goto cleanup;
60		dblist->size = (num_dirs * 2) + 12;
61	}
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),
65		&dblist->list);
66	if (retval)
67		goto cleanup;
68
69	if (list)
70		memcpy(dblist->list, list, len);
71	else
72		memset(dblist->list, 0, len);
73	if (ret_dblist)
74		*ret_dblist = dblist;
75	else
76		fs->dblist = dblist;
77	return 0;
78cleanup:
79	if (dblist)
80		ext2fs_free_mem(&dblist);
81	return retval;
82}
83
84/*
85 * Initialize a directory block list
86 */
87errcode_t ext2fs_init_dblist(ext2_filsys fs, ext2_dblist *ret_dblist)
88{
89	ext2_dblist	dblist;
90	errcode_t	retval;
91
92	retval = make_dblist(fs, 0, 0, 0, &dblist);
93	if (retval)
94		return retval;
95
96	dblist->sorted = 1;
97	if (ret_dblist)
98		*ret_dblist = dblist;
99	else
100		fs->dblist = dblist;
101
102	return 0;
103}
104
105/*
106 * Copy a directory block list
107 */
108errcode_t ext2fs_copy_dblist(ext2_dblist src, ext2_dblist *dest)
109{
110	ext2_dblist	dblist;
111	errcode_t	retval;
112
113	retval = make_dblist(src->fs, src->size, src->count, src->list,
114			     &dblist);
115	if (retval)
116		return retval;
117	dblist->sorted = src->sorted;
118	*dest = dblist;
119	return 0;
120}
121
122/*
123 * Close a directory block list
124 *
125 * (moved to closefs.c)
126 */
127
128
129/*
130 * Add a directory block to the directory block list
131 */
132errcode_t ext2fs_add_dir_block2(ext2_dblist dblist, ext2_ino_t ino,
133				blk64_t blk, e2_blkcnt_t blockcnt)
134{
135	struct ext2_db_entry2 	*new_entry;
136	errcode_t		retval;
137	unsigned long		old_size;
138
139	EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
140
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),
146					   &dblist->list);
147		if (retval) {
148			dblist->size = old_size / sizeof(struct ext2_db_entry2);
149			return retval;
150		}
151	}
152	new_entry = dblist->list + ( dblist->count++);
153	new_entry->blk = blk;
154	new_entry->ino = ino;
155	new_entry->blockcnt = blockcnt;
156
157	dblist->sorted = 0;
158
159	return 0;
160}
161
162/*
163 * Change the directory block to the directory block list
164 */
165errcode_t ext2fs_set_dir_block2(ext2_dblist dblist, ext2_ino_t ino,
166				blk64_t blk, e2_blkcnt_t blockcnt)
167{
168	dgrp_t			i;
169
170	EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
171
172	for (i=0; i < dblist->count; i++) {
173		if ((dblist->list[i].ino != ino) ||
174		    (dblist->list[i].blockcnt != blockcnt))
175			continue;
176		dblist->list[i].blk = blk;
177		dblist->sorted = 0;
178		return 0;
179	}
180	return EXT2_ET_DB_NOT_FOUND;
181}
182
183void ext2fs_dblist_sort2(ext2_dblist dblist,
184			 EXT2_QSORT_TYPE (*sortfunc)(const void *,
185						     const void *))
186{
187	if (!sortfunc)
188		sortfunc = dir_block_cmp2;
189	qsort(dblist->list, (size_t) dblist->count,
190	      sizeof(struct ext2_db_entry2), sortfunc);
191	dblist->sorted = 1;
192}
193
194/*
195 * This function iterates over the directory block list
196 */
197errcode_t ext2fs_dblist_iterate3(ext2_dblist dblist,
198				 int (*func)(ext2_filsys fs,
199					     struct ext2_db_entry2 *db_info,
200					     void	*priv_data),
201				 unsigned long long start,
202				 unsigned long long count,
203				 void *priv_data)
204{
205	unsigned long long	i, end;
206	int		ret;
207
208	EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
209
210	end = start + count;
211	if (!dblist->sorted)
212		ext2fs_dblist_sort2(dblist, 0);
213	if (end > dblist->count)
214		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)
218			return 0;
219	}
220	return 0;
221}
222
223errcode_t ext2fs_dblist_iterate2(ext2_dblist dblist,
224				 int (*func)(ext2_filsys fs,
225					     struct ext2_db_entry2 *db_info,
226					     void	*priv_data),
227				 void *priv_data)
228{
229	return ext2fs_dblist_iterate3(dblist, func, 0, dblist->count,
230				      priv_data);
231}
232
233static EXT2_QSORT_TYPE dir_block_cmp2(const void *a, const void *b)
234{
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;
239
240	if (db_a->blk != db_b->blk)
241		return (int) (db_a->blk - db_b->blk);
242
243	if (db_a->ino != db_b->ino)
244		return (int) (db_a->ino - db_b->ino);
245
246	return (db_a->blockcnt - db_b->blockcnt);
247}
248
249blk64_t ext2fs_dblist_count2(ext2_dblist dblist)
250{
251	return dblist->count;
252}
253
254errcode_t ext2fs_dblist_get_last2(ext2_dblist dblist,
255				  struct ext2_db_entry2 **entry)
256{
257	EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
258
259	if (dblist->count == 0)
260		return EXT2_ET_DBLIST_EMPTY;
261
262	if (entry)
263		*entry = dblist->list + ( dblist->count-1);
264	return 0;
265}
266
267errcode_t ext2fs_dblist_drop_last(ext2_dblist dblist)
268{
269	EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
270
271	if (dblist->count == 0)
272		return EXT2_ET_DBLIST_EMPTY;
273
274	dblist->count--;
275	return 0;
276}
277
278/*
279 * Legacy 32-bit versions
280 */
281
282/*
283 * Add a directory block to the directory block list
284 */
285errcode_t ext2fs_add_dir_block(ext2_dblist dblist, ext2_ino_t ino, blk_t blk,
286			       int blockcnt)
287{
288	return ext2fs_add_dir_block2(dblist, ino, blk, blockcnt);
289}
290
291/*
292 * Change the directory block to the directory block list
293 */
294errcode_t ext2fs_set_dir_block(ext2_dblist dblist, ext2_ino_t ino, blk_t blk,
295			       int blockcnt)
296{
297	return ext2fs_set_dir_block2(dblist, ino, blk, blockcnt);
298}
299
300void ext2fs_dblist_sort(ext2_dblist dblist,
301			EXT2_QSORT_TYPE (*sortfunc)(const void *,
302						    const void *))
303{
304	if (sortfunc) {
305		sortfunc32 = sortfunc;
306		sortfunc = dir_block_cmp;
307	} else
308		sortfunc = dir_block_cmp2;
309	qsort(dblist->list, (size_t) dblist->count,
310	      sizeof(struct ext2_db_entry2), sortfunc);
311	dblist->sorted = 1;
312}
313
314/*
315 * This function iterates over the directory block list
316 */
317struct iterate_passthrough {
318	int (*func)(ext2_filsys fs,
319		    struct ext2_db_entry *db_info,
320		    void	*priv_data);
321	void *priv_data;
322};
323
324static int passthrough_func(ext2_filsys fs,
325			    struct ext2_db_entry2 *db_info,
326			    void	*priv_data)
327{
328	struct iterate_passthrough *p = priv_data;
329	struct ext2_db_entry db;
330	int ret;
331
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;
339	return ret;
340}
341
342errcode_t ext2fs_dblist_iterate(ext2_dblist dblist,
343				int (*func)(ext2_filsys fs,
344					    struct ext2_db_entry *db_info,
345					    void	*priv_data),
346				void *priv_data)
347{
348	struct iterate_passthrough pass;
349
350	EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
351	pass.func = func;
352	pass.priv_data = priv_data;
353
354	return ext2fs_dblist_iterate2(dblist, passthrough_func, &pass);
355}
356
357static EXT2_QSORT_TYPE dir_block_cmp(const void *a, const void *b)
358{
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;
363
364	struct ext2_db_entry a32, b32;
365
366	a32.ino = db_a->ino;  a32.blk = db_a->blk;
367	a32.blockcnt = db_a->blockcnt;
368
369	b32.ino = db_b->ino;  b32.blk = db_b->blk;
370	b32.blockcnt = db_b->blockcnt;
371
372	return sortfunc32(&a32, &b32);
373}
374
375int ext2fs_dblist_count(ext2_dblist dblist)
376{
377	return dblist->count;
378}
379
380errcode_t ext2fs_dblist_get_last(ext2_dblist dblist,
381				 struct ext2_db_entry **entry)
382{
383	static struct ext2_db_entry ret_entry;
384	struct ext2_db_entry2 *last;
385
386	EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
387
388	if (dblist->count == 0)
389		return EXT2_ET_DBLIST_EMPTY;
390
391	if (!entry)
392		return 0;
393
394	last = dblist->list + dblist->count -1;
395
396	ret_entry.ino = last->ino;
397	ret_entry.blk = last->blk;
398	ret_entry.blockcnt = last->blockcnt;
399	*entry = &ret_entry;
400
401	return 0;
402}
403
404