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 <KernelExport.h>
23
24#include <stdlib.h>
25#include <string.h>
26
27#include "dosfs.h"
28#include "dlist.h"
29#include "util.h"
30#include "vcache.h"
31
32#if DEBUG
33	#define DLIST_ENTRY_QUANTUM 1
34#else
35	#define DLIST_ENTRY_QUANTUM 0x20
36#endif
37
38
39status_t
40dlist_init(nspace *vol)
41{
42	DPRINTF(0, ("dlist_init called\n"));
43
44	vol->dlist.entries = 0;
45	vol->dlist.allocated = DLIST_ENTRY_QUANTUM;
46	vol->dlist.vnid_list = malloc(sizeof(ino_t) * vol->dlist.allocated);
47	if (vol->dlist.vnid_list == NULL) {
48		vol->dlist.allocated = 0;
49		dprintf("dlist_init: out of core\n");
50		return ENOMEM;
51	}
52
53	return B_OK;
54}
55
56
57status_t
58dlist_uninit(nspace *vol)
59{
60	DPRINTF(0, ("dlist_uninit called\n"));
61
62	if (vol->dlist.vnid_list)
63		free(vol->dlist.vnid_list);
64	vol->dlist.entries = vol->dlist.allocated = 0;
65	vol->dlist.vnid_list = NULL;
66
67	return B_OK;
68}
69
70
71static status_t
72dlist_realloc(nspace *vol, uint32 allocate)
73{
74	ino_t *vnid_list;
75
76	DPRINTF(0, ("dlist_realloc %lx -> %lx\n", vol->dlist.allocated, allocate));
77
78	ASSERT(allocate != vol->dlist.allocated);
79	ASSERT(allocate > vol->dlist.entries);
80
81	vnid_list = malloc(sizeof(ino_t) * allocate);
82	if (vnid_list == NULL) {
83		dprintf("dlist_realloc: out of core\n");
84		return ENOMEM;
85	}
86
87	memcpy(vnid_list, vol->dlist.vnid_list, sizeof(ino_t) * vol->dlist.entries);
88	free(vol->dlist.vnid_list);
89	vol->dlist.vnid_list = vnid_list;
90	vol->dlist.allocated = allocate;
91
92	return B_OK;
93}
94
95
96status_t
97dlist_add(nspace *vol, ino_t vnid)
98{
99	DPRINTF(0, ("dlist_add vnid %Lx\n", vnid));
100
101	ASSERT(IS_DIR_CLUSTER_VNID(vnid) || IS_ARTIFICIAL_VNID(vnid));
102	ASSERT(vnid != 0);
103	// XXX: check for duplicate entries
104
105	if (vol->dlist.entries == vol->dlist.allocated) {
106		if (dlist_realloc(vol, vol->dlist.allocated + DLIST_ENTRY_QUANTUM) < 0)
107			return B_ERROR;
108	}
109	vol->dlist.vnid_list[vol->dlist.entries++] = vnid;
110
111	return B_OK;
112}
113
114
115status_t
116dlist_remove(nspace *vol, ino_t vnid)
117{
118	uint32 i;
119
120	DPRINTF(0, ("dlist_remove vnid %Lx\n", vnid));
121
122	for (i=0;i<vol->dlist.entries;i++)
123		if (vol->dlist.vnid_list[i] == vnid)
124			break;
125	ASSERT(i < vol->dlist.entries);
126	if (i == vol->dlist.entries)
127		return ENOENT;
128	for (;i<vol->dlist.entries-1;i++)
129		vol->dlist.vnid_list[i] = vol->dlist.vnid_list[i+1];
130	vol->dlist.entries--;
131
132	if (vol->dlist.allocated - vol->dlist.entries > 2*DLIST_ENTRY_QUANTUM)
133		return dlist_realloc(vol, vol->dlist.allocated - DLIST_ENTRY_QUANTUM);
134
135	return B_OK;
136}
137
138
139ino_t
140dlist_find(nspace *vol, uint32 cluster)
141{
142	uint32 i;
143
144	DPRINTF(1, ("dlist_find cluster %lx\n", cluster));
145
146	ASSERT(((cluster >= 2) && (cluster < vol->total_clusters + 2)) || (cluster == 1));
147
148	for (i = 0; i < vol->dlist.entries; i++) {
149		ino_t loc;
150
151		if (vcache_vnid_to_loc(vol, vol->dlist.vnid_list[i], &loc) < B_OK)
152			loc = vol->dlist.vnid_list[i];
153		ASSERT(IS_DIR_CLUSTER_VNID(loc));
154		if (CLUSTER_OF_DIR_CLUSTER_VNID(loc) == cluster)
155			return vol->dlist.vnid_list[i];
156	}
157
158	DPRINTF(1, ("dlist_find cluster %lx not found\n", cluster));
159
160	return -1LL;
161}
162
163
164void
165dlist_dump(nspace *vol)
166{
167	uint32 i;
168
169	dprintf("%lx/%lx dlist entries filled, QUANTUM = %x\n",
170		vol->dlist.entries, vol->dlist.allocated, DLIST_ENTRY_QUANTUM);
171
172	for (i = 0; i < vol->dlist.entries; i++)
173		dprintf("%s %Lx", ((i == 0) ? "entries:" : ","), vol->dlist.vnid_list[i]);
174
175	dprintf("\n");
176}
177