# 共享内存下链队列操作

**Repository Path**: luke_guangzhong/LinkQueue_shm.ver

## Basic Information

- **Project Name**: 共享内存下链队列操作
- **Description**: 共享内存下的链队列操作，实际上并不好用，而且容易造成内存快速消耗，仅仅用于技术试验。
- **Primary Language**: C
- **License**: GPL-3.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2022-01-19
- **Last Updated**: 2022-07-18

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 一个共享内存中的链表

[TOC]

## Abbreviations

| 缩写              | 全称                               | 备注                               |
| :---------------- | :--------------------------------- | :--------------------------------- |
| `QNode`           | Queue Node                         | 队列节点                           |
| `QNodeID`         | Queue Node Share Memory ID         | 存储有队列节点的共享内存唯一标识符 |
| `QNodePtr`        | Queue Node Pointer                 | 队列节点指针                       |
| `QData`           | Queue Node Data domain             | 队列节点数据域                     |
| `QDataCmp`        | Queue Node Data domain compare     | 比较两个节点数据域                 |
| `createShm_Node`  | create share memory for Queue Node | 给队列节点创建共享内存             |
| `getShm_Node`     | get share memory for Queue Node    | 获取存有队列节点的共享内存         |
| `detShm_Node`     | detach share memory for Queue Node | 分离存有队列节点的共享内存         |
| `createShm_Queue` | create share memory for Queue      | 给队列头创建共享内存               |
| `getShm_Queue`    | get share memory for Queue         | 获取存有队列头的共享内存           |
| `detShm_Queue`    | detach share memory for Queue      | 分离存有队列头的共享内存           |
| `relShm`          | release share memory               | 根据共享内存唯一标识符释放共享内存 |
| `rmQNode`         | remove Queue Node from Queue       | 根据数据域从链队列中摘除队列节点   |

## 函数列表

## 概述

编写环境 Ubuntu 20.04

该仓库中的函数是为了向共享内存中添加一个链表而制作的。

共享内存作为 Linux IPC 中最快的一种拥有诸多优势。其基本原理在此不做赘述。

本仓库中的大部分基于以下文章中的内容：[共享内存的动态扩展问题](https://blog.csdn.net/BLUCEJIE/article/details/109540341)

虽然在该文中并没有提供完整的代码，但是其中，用共享内存分配代替 malloc 的思路很有意义。

简单的说，shmget 分配共享内存时是连续分配，然而链队列是离散分配内存空间。由于我们不知道链队列最后需要多少空间，所以无法准确的创建大小合适的共享内存。

但是如果换成单个节点的话就不一样了。单个节点的内存结构是连续的，使用 malloc 来获取内存空间。shmget 也是连续的。那么对于用户来说，shmget 分配的连续空间和 malloc 分配的连续空间两者并没有区别。

所以我们可以用 shmget 来代替 malloc 创建节点内存空间。

另外，节点数据结构也需要作出修改。以往，指针域是由节点类型的指针担任，换成共享内存以后，如果不提前与共享内存关联，我们存在节点中的指针是毫无意义的。为了减少野指针的出现，指针域换成共享内存标识符（int 型）。

由于指针域的变化，我们也需要一个新的函数：它能根据共享内存标识符连接共享内存，并获取返回的地址。

## 数据结构说明

```c
/*******Struct*******/
typedef int QNodeID;
typedef int QueueID;

typedef struct QData {
    int data;
} QData;

typedef struct QNode {
    QData data;
    QNodeID next;
} QNode, *QNodePtr;

typedef struct LinkQueue {
    QNodeID head;
    QNodeID tail;
    int length;
} LinkQueue
```

前两个是对 int 型数据的类型定义，便于提高代码的可读性。

QData 是链节点的数据域，对此处做修改需要同时修改所有与数据域相关的函数

QNode 是链节点的数据结构，包含有数据域和指针域，由于我们在这里用于标记下一个节点的是 shmid, 所以这里使用 int 型数据。

LinkQueue 是链头的数据结构，一个链头实例代表一个链队列。其中，head 部分表示链队列头节点的位置，tail 代表链队列尾节点的位置。

在此，我们使用的是带头节点（哨兵）的单链链队列。

## 函数功能与参数说明

### LinkQueue.h

```c
/*******Internal Functions*******/
static LStatus QDataCmp(QData elem, QData elem2);
static LStatus printQData(QData elem);
```

以上为内部函数，主要是数据域的函数，也是如果发生数据域修改就要跟随修改的函数。

QDataCmp 主要是对数据域的等值比较，如果值相同返回 OK，否则返回 ERROR

printQData 主要是为了将数据域通过 console 打印的函数，只会返回 OK，如果发生错误，可能会触发信号。需要对信号进行捕捉处理。

```c
/*******Share Memory Functions*******/
static LinkQueue *createShm_Queue(QueueID *shmidPtr, key_t key);
static LinkQueue *getShm_Queue(QueueID *shmidPtr, key_t key);
static LStatus detShm_Queue(LinkQueue *Q);
static LStatus relShm(int shmid);
```
createShm_Queue 是为了创建链头的共享内存空间。shmidPtr 参数用于输出，便于获取链头的共享内存标识符。key 用于创建共享内存，建议预定义。

getShm_Queue 是根据 key 值获取共享内存空间地址的函数。在这个函数中只能获取已经创建好共享内存空间的地址。否则返回 NULL。

detShm_Queue 是根据地址解除与共享内存的关联。

relShm 是根据共享内存标识符释放共享内存。

```c
/*******External Functions*******/
#define LStatus int
LStatus initQueue(LinkQueue *Q);
LStatus destroyQueue(LinkQueue **QPtr, QueueID Qid);
LStatus clearQueue(LinkQueue *Q, QueueID *Qid);
bool QueueEmpty(LinkQueue *Q);
int QueueLength(LinkQueue *Q);
LStatus enQueue(LinkQueue *Q, QData elem);
LStatus deQueue(LinkQueue *Q, QData *elemPtr);
int QueueTraverse(LinkQueue *Q, void(*visit)(QNodePtr));
```
initQueue 初始化链队列。

destroyQueue 销毁链队列，因为内部包含共享内存的释放函数，需要一并提供共享内存标识符和链头的二级指针。

clearQueue 清空链队列，因为清空的内部逻辑是先销毁，后创建，所以也需要共享内存标识符。

QueueEmpty 判断队列是否为空。判断逻辑：头节点和尾节点指向同一个节点。

QueueLength 返回节点长度。

enQueue 节点入队。参数 elem 只需要进行值传递，所以调用该函数前请想创建 QData 。

deQueue 节点出队。参数 elemPtr 是地址传递，目的是为了获取出队的节点数据。

QueueTraverse 节点遍历操作。（未完成）

```c
/*******Custom Functions*******/
LStatus rmQNode(LinkQueue *Q, QData elem);
LStatus printQueue(LinkQueue *Q);
```
rmQNode 根据节点数值域删除链节点。首先遍历，没一个节点，比较两者的数据域，如果相等，就把这个节点从队列中取出来。

printQueue 打印链队列。