Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changeset 47faec1 in mainline


Ignore:
Timestamp:
2012-03-26T09:42:16Z (10 years ago)
Author:
Frantisek Princ <frantisek.princ@…>
Branches:
lfn, master
Children:
fffb061
Parents:
9463b245
Message:

introduced binary search in extent index node

File:
1 edited

Legend:

Unmodified
Added
Removed
  • uspace/lib/ext4/libext4_extent.c

    r9463b245 r47faec1  
    149149}
    150150
    151 //static void ext4_extent_binsearch_idx(ext4_extent_header_t *header,
    152 //      ext4_extent_index_t **index, uint32_t iblock)
    153 //{
    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 //      *index = l - 1;
    171 //}
    172 //
    173 static void ext4_extent_binsearch(ext4_extent_header_t *header,
    174                 ext4_extent_t **extent, uint32_t iblock)
    175 {
    176         ext4_extent_t *r, *l, *m;
     151static void ext4_extent_binsearch_idx(ext4_extent_header_t *header,
     152        ext4_extent_index_t **index, uint32_t iblock)
     153{
     154        ext4_extent_index_t *r, *l, *m;
    177155
    178156        uint16_t entries_count = ext4_extent_header_get_entries_count(header);
    179157
    180         if (entries_count == 0) {
    181                 // this leaf is empty
     158        if (entries_count == 1) {
     159                *index = EXT4_EXTENT_FIRST_INDEX(header);
    182160                return;
    183161        }
    184162
    185         l = EXT4_EXTENT_FIRST(header) + 1;
     163        l = EXT4_EXTENT_FIRST_INDEX(header) + 1;
    186164        r = l + entries_count - 1;
    187165
    188166        while (l <= r) {
    189167                m = l + (r - l) / 2;
    190                 uint32_t block = ext4_extent_get_first_block(m);
    191                 if (iblock < block) {
     168                uint32_t first_block = ext4_extent_index_get_first_block(m);
     169                if (iblock < first_block) {
    192170                                r = m - 1;
    193171                } else {
     
    196174        }
    197175
     176        *index = l - 1;
     177}
     178
     179static void ext4_extent_binsearch(ext4_extent_header_t *header,
     180                ext4_extent_t **extent, uint32_t iblock)
     181{
     182        ext4_extent_t *r, *l, *m;
     183
     184        uint16_t entries_count = ext4_extent_header_get_entries_count(header);
     185
     186        if (entries_count == 0) {
     187                // this leaf is empty
     188                EXT4FS_DBG("EMPTY LEAF");
     189                *extent = NULL;
     190                return;
     191        }
     192
     193        if (entries_count == 1) {
     194                *extent = EXT4_EXTENT_FIRST(header);
     195                return;
     196        }
     197
     198        l = EXT4_EXTENT_FIRST(header) + 1;
     199        r = l + entries_count - 1;
     200
     201        while (l <= r) {
     202                m = l + (r - l) / 2;
     203                uint32_t first_block = ext4_extent_get_first_block(m);
     204                if (iblock < first_block) {
     205                                r = m - 1;
     206                } else {
     207                                l = m + 1;
     208                }
     209        }
     210
    198211        *extent = l - 1;
    199 
    200212}
    201213
     
    210222        while (ext4_extent_header_get_depth(header) != 0) {
    211223
    212 //              ext4_extent_path_t path2;
    213 //              path2.header = header;
    214 //              path2.index = NULL;
    215 //              ext4_extent_binsearch_idx(header, &path2.index, iblock);
    216 //
    217 //              uint64_t child = ext4_extent_index_get_leaf(path2.index);
    218 //              if (block != NULL) {
    219 //                      block_put(block);
    220 //              }
    221 //
    222 //              rc = block_get(&block, fs->device, child, BLOCK_FLAGS_NONE);
    223 //              if (rc != EOK) {
    224 //                      return rc;
    225 //              }
    226 //
    227 //              header = block->data;
    228 //              break;
    229 
    230 
    231                 ext4_extent_index_t *extent_index = EXT4_EXTENT_FIRST_INDEX(header);
    232 
    233                 for (uint16_t i = 0; i < ext4_extent_header_get_entries_count(header); ++i, extent_index++) {
    234                         if (iblock >= ext4_extent_index_get_first_block(extent_index)) {
    235 
    236                                 uint64_t child = ext4_extent_index_get_leaf(extent_index);
    237 
    238                                 if (block != NULL) {
    239                                         block_put(block);
    240                                 }
    241 
    242                                 rc = block_get(&block, fs->device, child, BLOCK_FLAGS_NONE);
    243                                 if (rc != EOK) {
    244                                         return rc;
    245                                 }
    246 
    247                                 header = (ext4_extent_header_t *)block->data;
    248                                 break;
    249                         }
     224                ext4_extent_index_t *index;
     225                ext4_extent_binsearch_idx(header, &index, iblock);
     226
     227                uint64_t child = ext4_extent_index_get_leaf(index);
     228
     229                if (block != NULL) {
     230                        block_put(block);
    250231                }
    251         }
    252 
    253 
    254         ext4_extent_path_t path;
    255 
    256         path.header = header;
    257         path.extent = NULL;
    258 
    259         ext4_extent_binsearch(path.header, &path.extent, iblock);
    260 
    261         *ret_extent = path.extent;
     232
     233                rc = block_get(&block, fs->device, child, BLOCK_FLAGS_NONE);
     234                if (rc != EOK) {
     235                        return rc;
     236                }
     237
     238                header = (ext4_extent_header_t *)block->data;
     239        }
     240
     241
     242        ext4_extent_t *extent = NULL;
     243        ext4_extent_binsearch(header, &extent, iblock);
     244        *ret_extent = extent;
    262245
    263246        return EOK;
Note: See TracChangeset for help on using the changeset viewer.