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

Changeset a4419e7 in mainline


Ignore:
Timestamp:
2012-03-20T20:33:44Z (10 years ago)
Author:
Frantisek Princ <frantisek.princ@…>
Branches:
lfn, master
Children:
6514d1f
Parents:
9104bb5
Message:

binary search for extent (not for extent index !!!)

File:
1 edited

Legend:

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

    r9104bb5 ra4419e7  
    171171//}
    172172//
    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 static int ext4_extent_find_extent(ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, uint32_t iblock, ext4_extent_t **ret_extent)
     173static 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
     202static int ext4_extent_find_extent(ext4_filesystem_t *fs,
     203                ext4_inode_ref_t *inode_ref, uint32_t iblock, ext4_extent_t **ret_extent)
    203204{
    204205        int rc;
     
    231232        }
    232233
    233         ext4_extent_t *extent = EXT4_EXTENT_FIRST(header);
    234 //      uint64_t phys_block = 0;
    235 
    236         for (uint16_t i = 0; i < ext4_extent_header_get_entries_count(header); ++i) {
    237 
    238                 uint32_t first_block = ext4_extent_get_first_block(extent);
    239                 uint16_t block_count = ext4_extent_get_block_count(extent);
    240 
    241                 if ((iblock >= first_block) && (iblock < first_block + block_count)) {
    242                         break;
    243                 }
    244                 // Go to the next extent
    245                 ++extent;
    246         }
    247 
    248         *ret_extent = extent;
     234
     235        ext4_extent_path_t path;
     236
     237        path.header = header;
     238        path.extent = NULL;
     239
     240        ext4_extent_binsearch(&path, iblock);
     241
     242        *ret_extent = path.extent;
     243
     244//      for (uint16_t i = 0; i < ext4_extent_header_get_entries_count(header); ++i) {
     245//
     246//              uint32_t first_block = ext4_extent_get_first_block(extent);
     247//              uint16_t block_count = ext4_extent_get_block_count(extent);
     248//
     249//              if ((iblock >= first_block) && (iblock < first_block + block_count)) {
     250//                      break;
     251//              }
     252//              // Go to the next extent
     253//              ++extent;
     254//      }
     255//
     256//      *ret_extent = extent;
    249257
    250258        return EOK;
Note: See TracChangeset for help on using the changeset viewer.