Changeset a4419e7 in mainline

Timestamp:

2012-03-20T20:33:44Z (13 years ago)

Author:

Frantisek Princ <frantisek.princ@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

6514d1f

Parents:

9104bb5

Message:

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

File:

• uspace/lib/ext4/libext4_extent.c (modified) (2 diffs)

uspace/lib/ext4/libext4_extent.c

@@ -171 +171 @@
 //}
 //
-//static void ext4_extent_binsearch(ext4_extent_path_t *path, uint32_t iblock)
-//{
-//      ext4_extent_header_t *header = path->header;
-//      ext4_extent_t *r, *l, *m;
-//
-//      uint16_t entries_count = ext4_extent_header_get_entries_count(header);
-//
-//      if (entries_count == 0) {
-//              // this leaf is empty
-//              return;
-//      }
-//
-//      l = EXT4_EXTENT_FIRST(header) + 1;
-//      r = l + entries_count - 1;
-//
-//      while (l <= r) {
-//              m = l + (r - l) / 2;
-//              uint32_t block = ext4_extent_get_first_block(m);
-//              if (iblock < block) {
-//                              r = m - 1;
-//              } else {
-//                              l = m + 1;
-//              }
-//      }
-//
-//      path->extent = l - 1;
-//
-//}
-
-static int ext4_extent_find_extent(ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, uint32_t iblock, ext4_extent_t **ret_extent)
+static void ext4_extent_binsearch(ext4_extent_path_t *path, uint32_t iblock)
+{
+        ext4_extent_header_t *header = path->header;
+        ext4_extent_t *r, *l, *m;
+
+        uint16_t entries_count = ext4_extent_header_get_entries_count(header);
+
+        if (entries_count == 0) {
+                // this leaf is empty
+                return;
+        }
+
+        l = EXT4_EXTENT_FIRST(header) + 1;
+        r = l + entries_count - 1;
+
+        while (l <= r) {
+                m = l + (r - l) / 2;
+                uint32_t block = ext4_extent_get_first_block(m);
+                if (iblock < block) {
+                                r = m - 1;
+                } else {
+                                l = m + 1;
+                }
+        }
+
+        path->extent = l - 1;
+
+}
+
+static int ext4_extent_find_extent(ext4_filesystem_t *fs,
+                ext4_inode_ref_t *inode_ref, uint32_t iblock, ext4_extent_t **ret_extent)
 {
         int rc;
@@ -231 +232 @@
         }
 
-        ext4_extent_t *extent = EXT4_EXTENT_FIRST(header);
-//      uint64_t phys_block = 0;
-
-        for (uint16_t i = 0; i < ext4_extent_header_get_entries_count(header); ++i) {
-
-                uint32_t first_block = ext4_extent_get_first_block(extent);
-                uint16_t block_count = ext4_extent_get_block_count(extent);
-
-                if ((iblock >= first_block) && (iblock < first_block + block_count)) {
-                        break;
-                }
-                // Go to the next extent
-                ++extent;
-        }
-
-        *ret_extent = extent;
+
+        ext4_extent_path_t path;
+
+        path.header = header;
+        path.extent = NULL;
+
+        ext4_extent_binsearch(&path, iblock);
+
+        *ret_extent = path.extent;
+
+//      for (uint16_t i = 0; i < ext4_extent_header_get_entries_count(header); ++i) {
+//
+//              uint32_t first_block = ext4_extent_get_first_block(extent);
+//              uint16_t block_count = ext4_extent_get_block_count(extent);
+//
+//              if ((iblock >= first_block) && (iblock < first_block + block_count)) {
+//                      break;
+//              }
+//              // Go to the next extent
+//              ++extent;
+//      }
+//
+//      *ret_extent = extent;
 
         return EOK;