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