快速上手：二叉树实现高性能共享内存

开篇

  之前看过一段时间Android property源码，发现其中对共享内存的使用方式挺优秀，对于实际的工作开发也有借鉴意义。于是乎参考其设计思想，个人用C++也完成一篇共享内存的使用代码。共享内存的使用可参考进程间通信 共享内存, 本篇记录一种比较优雅的共享内存使用方式。

常见的使用方案

  在项目初期，由于需要存储的属性相对较少，对于共享内存的使用，没有很好的规划，常见的使用共享内存的方式大致两种：
① 声明一个结构体，成员对应需要存储的属性值，然后将这个结构体指针指向共享内存，通过增加成员实现增加属性的存储。
② 定义一个固对结构体数组，每个结构体包含属性名和属性值，将此数组映射到共享内存中，通过遍历共享内存匹配属性名称进而获取属性值。

  上述方案都有不好的地方：第①种方案随着项目迭代，存储的属性不断增加，结构体会变的越来越臃肿，不利于项目维护；第二种方案当需要存储的属性越来越庞大，搜索性能就会存在问题。

二叉树优化方案

针对上述问题，Android property对共享内存的使用有很大的参考价值：

• 呈现形式：与第二种方案一样，对于属性值采用键值对的方式保存，声明一个结构体，分别包含键（属性名称）和值（属性值）。
• 存储方式：对于键值对的保存，采用二叉树的方式，在键值对结构体增加左、右指针。二叉树的原理很简单，这里不细说了。
• 对外封装：对于外部的使用，只需封装set和get接口，实现细节使用者无需关心。
• 溢出管控：在使用共享内存过程中，可能会出现存储量超过共享内存的最大范围， 因此在共享内存头部固定几个字节用于存储当前共享内存的使用大小，在使用时比较使用的大小和最大范围。
• 其他：另外考虑到多进程、多线程的使用，对于共享内存这个共享资源采用信号量的方式进行保护，避免进程或线程同时访问出现不可预知问题。
    此方案避免了项目迭代需要不断修改共享内存的代码，对于使用者来说只需要定义好属性名和属性值即可；同时二叉树的形式也解决了搜索性能问题，即使后续需要更换更优秀的存储数据结构，也不会影响到使用代码。

源码实现

编程环境

1. 编译环境: Linux环境
2. 语言: C++语言
3. 编译命令: make

工程结构

.
├── main.cc
├── Makefile
├── shared_memory.cc
└── shared_memory.h

使用接口

class SharedMemory
{
public:
    SharedMemory(const char* pFilename, size_t size);
    ~SharedMemory();

    int getValue(int key, std::string& value);
    int setValue(int key, const std::string& value);

private:
    const char* mFilename;
    size_t mSize;
    size_t mCurUsedSize;
    void* mRoot;
    Node* mFirstNode;
    int mFd;
    sem_t mSemaphore;

    Node* getNode(void* pAddr);
    Node* createNode();
    Node* createNode(int key, const std::string& value);
    int openAndCreateFile(const char* pFilename, size_t size);
    void deleteFile(const char* pFilename);
    void* mapFile(int fd, size_t size);
    void unmapFile(void* pRoot, size_t size);
    void setString(char* pDest, const std::string& src);
};

setValue和getValue为对外接口，使用者只需要关心属性名称和属性值即可。一般情况下，会再封装一层仅暴露set和get接口,实现接口对外部不可见。

二叉树数据结构

struct Node
{
    int key;
    char value[MAX_LENGTH_VALUE];

    Node* left;
    Node* right;
};

Node为二叉树的节点数据结构，这里key定义为int类型，也可以优化为字符串。left为左节点指针，right为右节点指针。

主要实现

int SharedMemory::getValue(int key, string& value)
{
    sem_wait(&mSemaphore);
    Node* pNode = mFirstNode;

    while (pNode != nullptr) {
        if (key == pNode->key) {
            value = pNode->value;
            sem_post(&mSemaphore);
            return 0;
        } else if (key < pNode->key) {
            pNode = pNode->left;
        } else {
            pNode = pNode->right;
        }
    }

    sem_post(&mSemaphore);
    return -1;
}

int SharedMemory::setValue(int key, const string& value)
{
    sem_wait(&mSemaphore);

    Node* pNode = mFirstNode;
    if (pNode == nullptr) {
        LOGE("pNode is nullptr! \n");
        sem_post(&mSemaphore);
        return -1;
    }

    Node* pPrev = nullptr;
    while (pNode != nullptr) {
        if (key == pNode->key) {
            setString(pNode->value, value);
            sem_post(&mSemaphore);
            return 0;
        }

        pPrev = pNode;
        pNode = (key < pNode->key) ? pNode->left : pNode->right;
    }

    // 更新共享内存使用大小
    mCurUsedSize += sizeof(Node);
    if (mCurUsedSize > mSize)
    {
        LOGE("Resource exhaustion! mCurUsedSize = %ld, mSize = %ld", mCurUsedSize, mSize);
        return -1;
    }
 
    Node* pNewNode = createNode(key, value);
    if (pNewNode == nullptr) {
        LOGE("pNewNode is nullptr! \n");
        mCurUsedSize -= sizeof(Node);
        sem_post(&mSemaphore);
        return -1;
    }

    *reinterpret_cast<size_t*>(mRoot) = mCurUsedSize;

    if (key < pPrev->key) {
        pPrev->left = pNewNode;
    } else {
        pPrev->right = pNewNode;
    }

    sem_post(&mSemaphore);
    return 0;
}

• getValue主要为二叉树查找，在使用前内部用信号量保护，避免多个进程或线程同时对共享资源进行操作。
• setValue实现属性存在更新，不存在则插入；插入时检查共享内存资源是否耗尽。同样在使用时用信号量保护共享资源。

测试代码

int main(int argc, char * argv[])
{
    SharedMemory theSharedMemory = SharedMemory(SHARED_MEMORY_PATH, MAX_SIZE_SHM_TEST);
    
    for (int i = 0; i < 10; i++)
    {
        string value = "value" + to_string(i);
        theSharedMemory.setValue(i, value);
    }

    for (int i = 0; i < 10; i++)
    {
        string value;
        theSharedMemory.getValue(i, value);
        LOGD("key = %d, value = %s\n", i, value.c_str());
    }

    return 0;
}

篇幅有限，这里只测试10个存储值。如需测试更多值，可下载本代码自行修改。

测试效果

$ ./exe 
56 Main D: key = 0, value = value0
56 Main D: key = 1, value = value1
56 Main D: key = 2, value = value2
56 Main D: key = 3, value = value3
56 Main D: key = 4, value = value4
56 Main D: key = 5, value = value5
56 Main D: key = 6, value = value6
56 Main D: key = 7, value = value7
56 Main D: key = 8, value = value8
56 Main D: key = 9, value = value9

测试效果满足预期。

总结

• 使用二叉树管理共享内存优势很明显，搜索更快，封装出的共享内存接口使用也更简单。
• 本代码还存在优化点，例如key值可以换成字符串; key属性也可以增加掉电存储、掉电不存储等属性。
• 基于此代码，可以做一些项目上的通用功能，例如项目配置、进程间通信等功能。