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