Changeset e2629b08 in mainline for uspace/lib/ext4/libext4_extent.c
- Timestamp:
- 2012-03-07T10:11:41Z (12 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 9093c61
- Parents:
- b53a733
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/ext4/libext4_extent.c
rb53a733 re2629b08 37 37 38 38 #include <byteorder.h> 39 #include "libext4_extent.h" 39 #include <errno.h> 40 #include <malloc.h> 41 #include "libext4.h" 40 42 41 43 uint32_t ext4_extent_get_first_block(ext4_extent_t *extent) … … 145 147 { 146 148 header->generation = host2uint32_t_le(generation); 149 } 150 151 static void ext4_extent_binsearch_idx(ext4_extent_path_t *path, uint32_t iblock) 152 { 153 ext4_extent_header_t *header = path->header; 154 ext4_extent_index_t *r, *l, *m; 155 156 uint16_t entries_count = ext4_extent_header_get_entries_count(header); 157 l = EXT4_EXTENT_FIRST_INDEX(header) + 1; 158 r = l + entries_count - 1; 159 160 while (l <= r) { 161 m = l + (r - l) / 2; 162 uint32_t block = ext4_extent_index_get_first_block(m); 163 if (iblock < block) { 164 r = m - 1; 165 } else { 166 l = m + 1; 167 } 168 } 169 170 path->index = l - 1; 171 } 172 173 static void ext4_extent_binsearch(ext4_extent_path_t *path, uint32_t iblock) 174 { 175 ext4_extent_header_t *header = path->header; 176 ext4_extent_t *r, *l, *m; 177 178 uint16_t entries_count = ext4_extent_header_get_entries_count(header); 179 180 if (entries_count == 0) { 181 // this leaf is empty 182 return; 183 } 184 185 l = EXT4_EXTENT_FIRST(header) + 1; 186 r = l + entries_count - 1; 187 188 while (l <= r) { 189 m = l + (r - l) / 2; 190 uint32_t block = ext4_extent_get_first_block(m); 191 if (iblock < block) { 192 r = m - 1; 193 } else { 194 l = m + 1; 195 } 196 } 197 198 path->extent = l - 1; 199 200 } 201 202 int ext4_extent_find_block(ext4_filesystem_t *fs, ext4_extent_path_t **path, 203 ext4_extent_header_t *header, uint32_t iblock) 204 { 205 int rc; 206 207 uint16_t depth = ext4_extent_header_get_depth(header); 208 209 ext4_extent_header_t *eh = header; 210 211 ext4_extent_path_t *tmp_path; 212 213 // Added 2 for possible tree growing 214 tmp_path = malloc(sizeof(ext4_extent_path_t) * (depth + 2)); 215 if (tmp_path == NULL) { 216 *path = NULL; 217 return ENOMEM; 218 } 219 220 tmp_path[0].block = NULL; 221 tmp_path[0].header = eh; 222 223 uint16_t pos = 0, idx = depth; 224 while (idx > 0) { 225 226 ext4_extent_binsearch_idx(tmp_path + pos, iblock); 227 228 tmp_path[pos].depth = idx; 229 tmp_path[pos].extent = NULL; 230 231 uint64_t fblock = ext4_extent_index_get_leaf(tmp_path[pos].index); 232 block_t *block; 233 rc = block_get(&block, fs->device, fblock, BLOCK_FLAGS_NONE); 234 if (rc != EOK) { 235 // TODO cleanup 236 } 237 238 eh = (ext4_extent_header_t *)tmp_path[pos].block->data; 239 pos++; 240 241 tmp_path[pos].block = block; 242 tmp_path[pos].header = eh; 243 244 idx--; 245 246 } 247 248 tmp_path[pos].depth = idx; 249 tmp_path[pos].extent = NULL; 250 tmp_path[pos].index = NULL; 251 252 /* find extent */ 253 ext4_extent_binsearch(tmp_path + pos, iblock); 254 255 /* if not an empty leaf */ 256 if (tmp_path[pos].extent) { 257 uint64_t fblock = ext4_extent_get_start(tmp_path[pos].extent); 258 block_t *block; 259 rc = block_get(&block, fs->device, fblock, BLOCK_FLAGS_NONE); 260 if (rc != EOK) { 261 // TODO cleanup 262 } 263 tmp_path[pos].block = block; 264 } 265 266 return EOK; 147 267 } 148 268
Note:
See TracChangeset
for help on using the changeset viewer.