1/*
2	Copyright 1999-2001, Be Incorporated.   All Rights Reserved.
3	This file may be used under the terms of the Be Sample Code License.
4*/
5/*
6directory vnode id list
7
8We only add to this list as we encounter directories; there is no need to
9scan through the directories ourselves since we aren't worried about preserving
10vnid's across reboots.
11
12We don't worry about aliases for directories since their cluster values will
13always be the same -- searches are performed only on the starting cluster
14number of the directories.
15
16TODO:
17	XXX: make this more efficient
18*/
19
20#define DPRINTF(a,b) if (debug_dlist > (a)) dprintf b
21
22#include "system_dependencies.h"
23
24#include "dosfs.h"
25#include "dlist.h"
26#include "util.h"
27#include "vcache.h"
28
29#if DEBUG
30	#define DLIST_ENTRY_QUANTUM 1
31#else
32	#define DLIST_ENTRY_QUANTUM 0x20
33#endif
34
35
36status_t
37dlist_init(nspace *vol)
38{
39	DPRINTF(0, ("dlist_init called\n"));
40
41	vol->dlist.entries = 0;
42	vol->dlist.allocated = DLIST_ENTRY_QUANTUM;
43	vol->dlist.vnid_list = (ino_t *)malloc(sizeof(ino_t) * vol->dlist.allocated);
44	if (vol->dlist.vnid_list == NULL) {
45		vol->dlist.allocated = 0;
46		dprintf("dlist_init: out of core\n");
47		return ENOMEM;
48	}
49
50	return B_OK;
51}
52
53
54status_t
55dlist_uninit(nspace *vol)
56{
57	DPRINTF(0, ("dlist_uninit called\n"));
58
59	if (vol->dlist.vnid_list)
60		free(vol->dlist.vnid_list);
61	vol->dlist.entries = vol->dlist.allocated = 0;
62	vol->dlist.vnid_list = NULL;
63
64	return B_OK;
65}
66
67
68static status_t
69dlist_realloc(nspace *vol, uint32 allocate)
70{
71	ino_t *vnid_list;
72
73	DPRINTF(0, ("dlist_realloc %" B_PRIu32 " -> %" B_PRIu32 "\n",
74		vol->dlist.allocated, allocate));
75
76	ASSERT(allocate != vol->dlist.allocated);
77	ASSERT(allocate > vol->dlist.entries);
78
79	vnid_list = (ino_t *)malloc(sizeof(ino_t) * allocate);
80	if (vnid_list == NULL) {
81		dprintf("dlist_realloc: out of core\n");
82		return ENOMEM;
83	}
84
85	memcpy(vnid_list, vol->dlist.vnid_list, sizeof(ino_t) * vol->dlist.entries);
86	free(vol->dlist.vnid_list);
87	vol->dlist.vnid_list = vnid_list;
88	vol->dlist.allocated = allocate;
89
90	return B_OK;
91}
92
93
94status_t
95dlist_add(nspace *vol, ino_t vnid)
96{
97	DPRINTF(0, ("dlist_add vnid %" B_PRIdINO "\n", vnid));
98
99	ASSERT(IS_DIR_CLUSTER_VNID(vnid) || IS_ARTIFICIAL_VNID(vnid));
100	ASSERT(vnid != 0);
101	// XXX: check for duplicate entries
102
103	if (vol->dlist.entries == vol->dlist.allocated) {
104		if (dlist_realloc(vol, vol->dlist.allocated + DLIST_ENTRY_QUANTUM) < 0)
105			return B_ERROR;
106	}
107	vol->dlist.vnid_list[vol->dlist.entries++] = vnid;
108
109	return B_OK;
110}
111
112
113status_t
114dlist_remove(nspace *vol, ino_t vnid)
115{
116	uint32 i;
117
118	DPRINTF(0, ("dlist_remove vnid %" B_PRIdINO "\n", vnid));
119
120	for (i=0;i<vol->dlist.entries;i++)
121		if (vol->dlist.vnid_list[i] == vnid)
122			break;
123	ASSERT(i < vol->dlist.entries);
124	if (i == vol->dlist.entries)
125		return ENOENT;
126	for (;i<vol->dlist.entries-1;i++)
127		vol->dlist.vnid_list[i] = vol->dlist.vnid_list[i+1];
128	vol->dlist.entries--;
129
130	if (vol->dlist.allocated - vol->dlist.entries > 2*DLIST_ENTRY_QUANTUM)
131		return dlist_realloc(vol, vol->dlist.allocated - DLIST_ENTRY_QUANTUM);
132
133	return B_OK;
134}
135
136
137ino_t
138dlist_find(nspace *vol, uint32 cluster)
139{
140	uint32 i;
141
142	DPRINTF(1, ("dlist_find cluster %" B_PRIu32 "\n", cluster));
143
144	ASSERT(((cluster >= 2) && (cluster < vol->total_clusters + 2)) || (cluster == 1));
145
146	for (i = 0; i < vol->dlist.entries; i++) {
147		ino_t loc;
148
149		if (vcache_vnid_to_loc(vol, vol->dlist.vnid_list[i], &loc) < B_OK)
150			loc = vol->dlist.vnid_list[i];
151		ASSERT(IS_DIR_CLUSTER_VNID(loc));
152		if (CLUSTER_OF_DIR_CLUSTER_VNID(loc) == cluster)
153			return vol->dlist.vnid_list[i];
154	}
155
156	DPRINTF(1, ("dlist_find cluster %" B_PRIu32 " not found\n", cluster));
157
158	return -1LL;
159}
160
161
162void
163dlist_dump(nspace *vol)
164{
165	uint32 i;
166
167	dprintf("%" B_PRIu32 "/%" B_PRIu32 " dlist entries filled, QUANTUM = %u\n",
168		vol->dlist.entries, vol->dlist.allocated, DLIST_ENTRY_QUANTUM);
169
170	for (i = 0; i < vol->dlist.entries; i++) {
171		dprintf("%s %" B_PRIdINO, i == 0 ? "entries:" : ",",
172			vol->dlist.vnid_list[i]);
173	}
174
175	dprintf("\n");
176}
177