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