基于二分查找实现Flash内存空闲/已用地址快速定位求助

在Flash内存中存储4字节数字，为减少擦写次数，预留一整页作为计数器存储区：每次写入时将数字写入下一个4字节位置，整页写满后擦除页面再从头写入。需要实现两个核心功能：

• 找到下一个可写入的空闲地址：即首个值为0xFFFFFFFF的地址（存储的数字永远不会是0xFFFFFFFF）
• 找到最后一个已写入的地址：即最后一个值不为0xFFFFFFFF的地址

原逐4字节遍历方法因Flash读取速度过慢改用二分查找，但现有FindNextFreeAddress函数存在问题：当内存全为0xFFFFFFFF（刚擦除状态）时无法找到第一个空闲地址；同时FindLastOccupiedAddress函数尚未实现。

原函数未处理全内存空闲的边界场景，以下是修复后的代码：

u32 FindNextFreeAddress(u32* arr, s32 l, s32 r, u32* address)
{
    if (!arr || !address) {
        return 1; // 参数非法
    }

    while (l <= r) {
        s32 m = l + ((r - l) / 2); // 避免溢出的二分中点计算
        if (arr[m] == 0xFFFFFFFF) {
            // 当前位置是空闲的，检查是否是第一个空闲位置
            if (m == 0 || arr[m-1] != 0xFFFFFFFF) {
                *address = (u32)&arr[m];
                return 0; // 找到有效地址，返回成功
            }
            // 左边还有连续空闲位置，继续向左找
            r = m - 1;
        } else {
            // 当前位置已被占用，向右找空闲区域
            l = m + 1;
        }
    }

    // 循环结束后，处理全空闲场景
    if (l == 0) {
        *address = (u32)&arr[0];
        return 0;
    }
    // 所有位置都被占用，无空闲地址
    return 1;
}

修复说明 #

• 新增m == 0的边界判断，直接识别首个位置为空闲的场景
• 循环结束后补充全内存空闲的处理逻辑，返回起始地址
• 保留溢出安全的中点计算和参数合法性检查

该函数通过二分查找定位最右侧的非0xFFFFFFFF元素，代码如下：

u32 FindLastOccupiedAddress(u32* arr, s32 l, s32 r, u32* address)
{
    if (!arr || !address) {
        return 1; // 参数非法
    }

    s32 lastValid = -1; // 记录最后一个有效地址的索引
    while (l <= r) {
        s32 m = l + ((r - l) / 2);
        if (arr[m] != 0xFFFFFFFF) {
            // 当前位置有效，记录后继续向右搜索更晚的有效位置
            lastValid = m;
            l = m + 1;
        } else {
            // 当前位置空闲，向左查找有效区域
            r = m - 1;
        }
    }

    if (lastValid != -1) {
        *address = (u32)&arr[lastValid];
        return 0; // 找到有效地址，返回成功
    }
    // 所有位置都是空闲的，无已写入地址
    return 1;
}

逻辑说明 #

• 用lastValid变量跟踪遍历过程中找到的有效位置
• 遇到有效元素时不直接返回，继续向右搜索以确保找到最后一个有效位置
• 循环结束后判断是否存在有效元素，不存在则返回错误

内容的提问来源于stack exchange，提问作者Korsarq