# jh_static_set

**Repository Path**: arrco/jh_static_set

## Basic Information

- **Project Name**: jh_static_set
- **Description**: jh_static_set 是一个基于AVL树和静态链表实现的集合(set)。
- **Primary Language**: C
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2022-09-04
- **Last Updated**: 2022-10-14

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# jh_static_set

## 介绍

jh_static_set 是一个基于AVL树和静态链表实现的集合(set)。实现一个类似于 C++ STL set容器，实现任意数据结构任意排序方式的集合，本身没有内存的申请与释放，集合的空间由外部提供。

## 使用说明

只需要包含 jh_static_set.c 和 jh_static_set.h 两个文件即可使用。

## 接口函数

提供以下接口用于集合的使用：

```c
/*在集合中查找第一个数据节点*/
jh_static_set_node_type jh_static_set_begin(jh_static_set_t* set);
/*在集合中查找最后一个数据节点*/
jh_static_set_node_type jh_static_set_end(jh_static_set_t* set);
/*获取集合的数据数量*/
size_t jh_static_set_count(jh_static_set_t* set);
/*判断集合是否为空*/
int jh_static_set_is_empty(jh_static_set_t* set);
/*判断集合是否已满*/
int jh_static_set_is_full(jh_static_set_t* set);
/*在集合中查找数据*/
jh_static_set_node_type jh_static_set_find(jh_static_set_t* set, void* value);
/*在集合中插入数据*/
int jh_static_set_insert(jh_static_set_t* set, void* value);
/*删除集合中的数据*/
int jh_static_set_erase(jh_static_set_t* set, void* value);
/*清空集合*/
int jh_static_set_clear(jh_static_set_t* set);
/*集合初始化*/
int jh_static_set_init(jh_static_set_t* set, void* base, size_t num, size_t size, size_t offset, size_t datasize, size_t dataoffset, int (*compare)(const void*, const void*));
```

另外还提供两个宏接口用于数据迭代：

```c
/*集合数据迭代*/
JH_STATIC_SET_ITER(jh_static_set_t* set, jh_static_set_node_type usernode, void* value)
/*集合数据反向迭代*/
JH_STATIC_SET_ITER_REVERSE(jh_static_set_t* set, jh_static_set_node_type usernode, void* value)
```

## 接口使用说明

### 1.集合初始化

调用接口`jh_static_set_init`初始化集合。

```c
/*集合初始化*/
int jh_static_set_init(jh_static_set_t* set, void* base, size_t num, size_t size, size_t offset, size_t datasize, size_t dataoffset, int (*compare)(const void*, const void*));
```

函数参数含义：

| 参数       | 含义                                       |
| ---------- | ------------------------------------------ |
| set        | 集合对象，需要定义一个类型为jh_set_t的参数 |
| base       | 指向用于集合的数组                         |
| num        | 数组中能存放的数据项数量                   |
| size       | 每个数据项的大小                           |
| offset     | 数据项的地址偏移                           |
| datasize   | 每个用户数据的大小                         |
| dataoffset | 用户数据的地址偏移                         |
| compare    | 指向用于比较两个数据的函数指针             |

函数返回值：

| 返回值 | 含义 |
| ------ | ---- |
| 0      | 成功 |
| -1     | 失败 |

使用示例：

```c
//定义用户的数据类型，同时将集合的数据结构放入结构体当中
typedef struct {
    unsigned int data;
    jh_static_set_node_t set;
} mystruct;

//定义用户数据数组
mystruct test[64];

//定义集合
jh_static_set_t static_set;

//集合初始化 
jh_static_set_init(&static_set, test, sizeof(test)/sizeof(mystruct), sizeof(mystruct), JH_STATIC_SET_OFFSETOF(mystruct, set), sizeof(unsigned int), JH_STATIC_SET_OFFSETOF(mystruct, data), compare);
```

**注意**：初始化时传入值`num`，但实际可用于放入集合的数据数量为`num - 1`。例如上述的示例，定义用于存放数据的数组长度为64，但实际可以用于放入集合的数据数量为63。

#### 定义compare函数

需要定义一个用于比较两个数据项的compare函数。这个函数的实现方式影响着这个集合会以什么样的方式进行排序。

函数的类型为`int (*compare)(const void* p1, const void* p2)`。

函数返回值：

| 返回值 | 含义                                   |
| ------ | -------------------------------------- |
| 小于0  | p1指向的数据项排在在p2指向的数据项之前 |
| 大于0  | p1指向的数据项排在在p2指向的数据项之后 |
| 等于0  | p1指向的数据项与p2指向的数据项相同     |

使用示例，假设保存的数据类型为int，按从小到大的方式排序：

```c
int compare(const void * p1, const void * p2)
{
    return ( *(int*)p1 - *(int*)p2 );
}
```

### 2.在集合中插入数据

调用接口`jh_static_set_insert`将数据放入集合中。

```c
/*在集合中插入数据*/
int jh_static_set_insert(jh_static_set_t* set, void* value);
```

函数参数含义：

| 参数  | 含义                 |
| ----- | -------------------- |
| set   | 集合                 |
| value | 要放入集合中的数据项 |

函数返回值：

| 返回值 | 含义 |
| ------ | ---- |
| 0      | 成功 |
| -1     | 失败 |

### 3.删除集合中的数据

调用接口`jh_static_set_erase`将数据从集合中删除。

```c
/*删除集合中的数据*/
int jh_static_set_erase(jh_static_set_t* set, void* value);
```

函数参数含义：

| 参数  | 含义                   |
| ----- | ---------------------- |
| set   | 集合                   |
| value | 要从集合中删除的数据项 |

函数返回值：

| 返回值 | 含义 |
| ------ | ---- |
| 0      | 成功 |
| -1     | 失败 |

### 4.在集合中查找数据

调用接口`jh_static_set_find`在集合中查找数据。

```c
/*在集合中查找数据*/
jh_static_set_node_type jh_static_set_find(jh_static_set_t* set, void* value);
```

函数参数含义：

| 参数  | 含义                   |
| ----- | ---------------------- |
| set   | 集合                   |
| value | 要在集合中查找的数据项 |

函数返回值：

| 返回值 | 含义                                                         |
| ------ | ------------------------------------------------------------ |
| 非0    | 成功，数据存在，返回值表示该数据所在的数据结点， 可用于集合数据迭代 |
| 0      | 失败                                                         |

### 5.获取集合的数据数量

调用接口`jh_static_set_count`查看集合中已有的数据数量。

```c
/*获取集合的数据数量*/
size_t jh_static_set_count(jh_static_set_t* set);
```

函数参数含义：

| 参数 | 含义 |
| ---- | ---- |
| set  | 集合 |

函数返回值：

| 返回值 | 含义           |
| ------ | -------------- |
| >=0    | 集合的数据数量 |

### 6.判断集合是否为空

调用接口`jh_static_set_is_empty`判断集合是否为空。

```c
/*判断集合是否为空*/
int jh_static_set_is_empty(jh_static_set_t* set);
```

函数参数含义：

| 参数 | 含义 |
| ---- | ---- |
| set  | 集合 |

函数返回值：

| 返回值 | 含义       |
| ------ | ---------- |
| 1      | 集合为空   |
| 0      | 集合不为空 |
| -1     | 失败       |



### 7.判断集合是否已满

调用接口`jh_static_set_is_full`判断集合是否已满。

```c
/*判断集合是否已满*/
int jh_static_set_is_full(jh_static_set_t* set);
```

函数参数含义：

| 参数 | 含义 |
| ---- | ---- |
| set  | 集合 |

函数返回值：

| 返回值 | 含义     |
| ------ | -------- |
| 1      | 集合已满 |
| 0      | 集合未满 |
| -1     | 失败     |



### 8.清空集合

调用接口`jh_static_set_clear`清空集合。

```c
/*清空集合*/
int jh_static_set_clear(jh_static_set_t* set);
```

函数参数含义：

| 参数 | 含义 |
| ---- | ---- |
| set  | 集合 |

函数返回值：

| 返回值 | 含义 |
| ------ | ---- |
| 0      | 成功 |
| -1     | 失败 |



### 9.集合数据迭代

调用接口`JH_STATIC_SET_ITER`进行数据迭代。

```c
/*集合数据迭代*/
JH_STATIC_SET_ITER(jh_static_set_t* set, jh_static_set_node_type usernode, void* value)
```

函数参数含义：

| 参数     | 含义                                                         |
| -------- | ------------------------------------------------------------ |
| set      | 集合                                                         |
| usernode | 数据结点， 通过 `jh_static_set_find`, `jh_static_set_begin`接口获取 |
| value    | 数据项                                                       |

使用示例，从第一个数据开始打印出当前集合中的所有数据：

```c
jh_static_set_node_type usernode = jh_static_set_begin(&static_set);
JH_STATIC_SET_ITER(&static_set, usernode, &val) {
    printf("%d ", val);
}
printf("\n");
```



### 10.集合数据反向迭代

调用接口`JH_STATIC_SET_ITER_REVERSE`进行数据反向迭代。

```c
/*集合数据反向迭代*/
JH_STATIC_SET_ITER_REVERSE(jh_static_set_t* set, jh_static_set_node_type usernode, void* value)
```

函数参数含义：

| 参数     | 含义                                                         |
| -------- | ------------------------------------------------------------ |
| set      | 集合                                                         |
| usernode | 数据结点， 通过 `jh_static_set_find`,  `jh_static_set_end`接口获取 |
| value    | 数据项                                                       |

使用示例，从最后一个数据开始打印出当前集合中的所有数据：

```c
jh_static_set_node_type usernode = jh_static_set_end(&static_set);
JH_STATIC_SET_ITER_REVERSE(&static_set, usernode, &val) {
    printf("%d ", val);
}
printf("\n");
```



### 11.在集合中查找第一个数据节点

调用接口`jh_static_set_begin`在集合中查找第一个数据节点。

```c
/*在集合中查找第一个数据节点*/
jh_static_set_node_type jh_static_set_begin(jh_static_set_t* set);
```

函数参数含义：

| 参数 | 含义 |
| ---- | ---- |
| set  | 集合 |

函数返回值：

| 返回值 | 含义                                                  |
| ------ | ----------------------------------------------------- |
| 非0    | 成功，表示第一个数据所在的数据结点， 用于集合数据迭代 |
| 0      | 失败                                                  |



### 12.在集合中查找最后一个数据节点

调用接口`jh_static_set_end`在集合中查找最后一个数据节点。

```c
/*在集合中查找最后一个数据节点*/
jh_static_set_node_type jh_static_set_end(jh_static_set_t* set);
```

函数参数含义：

| 参数 | 含义 |
| ---- | ---- |
| set  | 集合 |

函数返回值：

| 返回值 | 含义                                                    |
| ------ | ------------------------------------------------------- |
| 非0    | 成功，表示最后一个数据所在的数据结点， 用于集合数据迭代 |
| 0      | 失败                                                    |

## 注意事项

1. 存储的数据不能修改，如果要修改数据则需要先删除该数据，再添加一个修改后的数据。

2. 不支持存储多个相同的数据，也就是说每个数据都需要是不相同的。

## 使用示例

集合的基础用法：

```c
//数据类型为int，按从小到大的方式排序：
int compare(const void* a, const void* b) {
     return ( *(int*)a - *(int*)b );
}

void test1(void) {
    //定义用户的数据类型，同时将集合的数据结构放入结构体当中
    typedef struct {
        unsigned int data;
        jh_static_set_node_t set;
    } mystruct;
    
    //定义用户数据数组
    mystruct test[64];
    
    //定义集合
    jh_static_set_t static_set;
    
    //集合初始化 
    jh_static_set_init(&static_set, test, sizeof(test)/sizeof(mystruct),\
                        sizeof(mystruct), JH_STATIC_SET_OFFSETOF(mystruct, set),\
                        sizeof(unsigned int), JH_STATIC_SET_OFFSETOF(mystruct, data), compare);
    
    //定义测试数据
    int buf[] = {7, 5, 8, 2, 3, 1, 0, 9, 4, 6};
    
    //在集合中插入数据
    for(int i = 0; i < sizeof(buf)/sizeof(int); i++) {
        jh_static_set_insert(&static_set, &buf[i]);
    }
    
    int val;
    jh_static_set_node_type usernode;
    //在集合中查找第一个数据节点
    usernode = jh_static_set_begin(&static_set);
    //正向遍历打印出所有数据，会按照从小到大的顺序打印出来
    JH_STATIC_SET_ITER(&static_set, usernode, &val) {
        printf("%d ", val);
    }
    printf("\n");
    
    val = 5;
    //在集合中查找数据5
    usernode = jh_static_set_find(&static_set, &val);
    //从数据5开始正向遍历打印出后续的数据
    JH_STATIC_SET_ITER(&static_set, usernode, &val) {
        printf("%d ", val);
    }
    printf("\n");
    
    //在集合中查找最后一个数据节点
    usernode = jh_static_set_end(&static_set);
    //反向遍历打印出所有数据，会按照从大到小的顺序打印出来
    JH_STATIC_SET_ITER_REVERSE(&static_set, usernode, &val) {
        printf("%d ", val);
    }
    printf("\n");
      
    //获取集合的数据数量与判断集合是否为空
    printf("count %zu, set %s empty\n", jh_static_set_count(&static_set), jh_static_set_is_empty(&static_set) ? "is" : "isn't");
    
    //删除集合中的部分数据
    jh_static_set_erase(&static_set, &buf[2]);
    jh_static_set_erase(&static_set, &buf[1]);
    jh_static_set_erase(&static_set, &buf[0]);
    
    //获取集合的数据数量与判断集合是否为空
    printf("count %zu, set %s empty\n", jh_static_set_count(&static_set), jh_static_set_is_empty(&static_set) ? "is" : "isn't");
    
    //在集合中查找第一个数据节点
    usernode = jh_static_set_begin(&static_set);
    //正向遍历打印出所有数据
    JH_STATIC_SET_ITER(&static_set, usernode, &val) {
        printf("%d ", val);
    }
    printf("\n");
    
    //清空集合
    jh_static_set_clear(&static_set);
    
    //获取集合的数据数量与判断集合是否为空
    printf("count %zu, set %s empty\n", jh_static_set_count(&static_set), jh_static_set_is_empty(&static_set) ? "is" : "isn't");
}
```

运行结果如下：

```shell
0 1 2 3 4 5 6 7 8 9
5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
count 10, set isn't empty
count 7, set isn't empty
0 1 2 3 4 6 9
count 0, set is empty
```

## License

MIT License

Copyright (c) 2022 Hong Jiahua

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.