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