大于或等于0时代表可供并发进程使用的资源实体数；
小于0时代表正在等待使用临界区的进程数；
用于互斥的信号量初始值应大于0；
只能通过P、V原语操作而改变；
信号量元素组成：
1、表示信号量元素的值；
2、最后操作信号量元素的进程ID
3、等待信号量元素值+1的进程数；
4、等待信号量元素值为0的进程数；
二、主要函数
1.1 创建信号量
int semget(
key_t key, //标识信号量的关键字，有三种方法：1、使用IPC——PRIVATE让系统产生，
// 2、挑选一个随机数，3、使用ftok从文件路径名中产生
int nSemes, //信号量集中元素个数
int flag //IPC_CREAT；IPC_EXCL 只有在信号量集不存在时创建
)
成功：返回信号量句柄
失败：返回-1
1.2 使用ftok函数根据文件路径名产生一个关键字
key_t ftok(const char *pathname,int proj_id)
路径名称必须有相应权限
1.3 控制信号量
int semctl(
int semid, //信号量集的句柄
int semnum, //信号量集的元素数
int cmd, //命令
/*union senum arg */... //
)
成功：返回相应的值
失败：返回-1
命令详细说明:
cmd: IPC_RMID 删除一个信号量
IPC_EXCL 只有在信号量集不存在时创建
IPC_SET 设置信号量的许可权
SETVAL 设置指定信号量的元素的值为 agc.val
GETVAL 获得一个指定信号量的值
GETPID 获得最后操纵此元素的最后进程ID
GETNCNT 获得等待元素变为1的进程数
GETZCNT 获得等待元素变为0的进程数
union senum 定义如下：
union senum{
int val
struct semid_ds *buf
unsigned short * array
}agc
其中 semid_ds 定义如下：
struct semid_ds{
struct ipc_pem sem_pem //operation pemission struct
time_t sem_otime //last semop()time
time_t sem_ctime //last time changed by semctl()
struct sem *sembase //ptr to first semaphore in array
struct sem_queue *sem_pending//pending operations
struct sem_queue *sem_pending_last//last pending operations
struct sem_undo *undo //undo requests on this arrary
unsigned short int sem_nsems//number of semaphores in set
}
1.4 对信号量 +1 或 -1 或测试是否为0
int semop(
int semid,
struct sembuf *sops, //指向元素操作数组
unsigned short nsops //数组中元素操作的个数
)
结构 sembuf 定义
sembuf{
short int sem_num//semaphore number
short int sem_op//semaphore operaion
short int sem_flg //operation flag
}
三、例子:
2.1 服务器
#include <sys/sem.h>
#include <sys/ipc.h>
#define SEGSIZE 1024
#define READTIME 1
union semun {
int val
struct semid_ds *buf
unsigned short *array
} arg
//生成信号量
int sem_creat(key_t key)
{
union semun sem
int semid
sem.val = 0
semid = semget(key,1,IPC_CREAT|0666)
if (-1 == semid){
printf("create semaphore error\n")
exit(-1)
}
semctl(semid,0,SETVAL,sem)
return semid
}
//删除信号量
void del_sem(int semid)
{
union semun sem
sem.val = 0
semctl(semid,0,IPC_RMID,sem)
}
//p
int p(int semid)
{
struct sembuf sops={0,+1,IPC_NOWAIT}
return (semop(semid,&sops,1))
}
//v
int v(int semid)
{
struct sembuf sops={0,-1,IPC_NOWAIT}
return (semop(semid,&sops,1))
}
int main()
{
key_t key
int shmid,semid
char *shm
char msg[7] = "-data-"
char i
struct semid_ds buf
key = ftok("/",0)
shmid = shmget(key,SEGSIZE,IPC_CREAT|0604)
if (-1 == shmid){
printf(" create shared memory error\n")
return -1
}
shm = (char *)shmat(shmid,0,0)
if (-1 == (int)shm){
printf(" attach shared memory error\n")
return -1
}
semid = sem_creat(key)
for (i = 0i <= 3i++){
sleep(1)
p(semid)
sleep(READTIME)
msg[5] = '0' + i
memcpy(shm,msg,sizeof(msg))
sleep(58)
v(semid)
}
shmdt(shm)
shmctl(shmid,IPC_RMID,&buf)
del_sem(semid)
return 0
//gcc -o shm shm.c -g
}
2.2 客户端
#include <sys/sem.h>
#include <time.h>
#include <sys/ipc.h>
#define SEGSIZE 1024
#define READTIME 1
union semun {
int val
struct semid_ds *buf
unsigned short *array
} arg
// 打印程序执行时间
void out_time(void)
{
static long start = 0
time_t tm
if (0 == start){
tm = time(NULL)
start = (long)tm
printf(" now start ...\n")
}
printf(" second: %ld \n",(long)(time(NULL)) - start)
}
//创建信号量
int new_sem(key_t key)
{
union semun sem
int semid
sem.val = 0
semid = semget(key,0,0)
if (-1 == semid){
printf("create semaphore error\n")
exit(-1)
}
return semid
}
//等待信号量变成0
void wait_v(int semid)
{
struct sembuf sops={0,0,0}
semop(semid,&sops,1)
}
int main(void)
{
key_t key
int shmid,semid
char *shm
char msg[100]
char i
key = ftok("/",0)
shmid = shmget(key,SEGSIZE,0)
if(-1 == shmid){
printf(" create shared memory error\n")
return -1
}
shm = (char *)shmat(shmid,0,0)
if (-1 == (int)shm){
printf(" attach shared memory error\n")
return -1
}
semid = new_sem(key)
for (i = 0i <3i ++){
sleep(2)
wait_v(semid)
printf("Message geted is: %s \n",shm + 1)
out_time()
}
shmdt(shm)
return 0
// gcc -o shmc shmC.c -g
}
通用有序平衡二叉树接口描述这套代码对用户屏蔽了复杂的二叉树的旋转操作，不区分用户的数据类型，任何数
据都可以用有序平衡二叉树来存放。我还对平衡二叉树进行了一点点扩展，在树结构里
面增加了保持线行递增（或递减）顺序的双向链表，方便使用者能够快速按序遍历所有
树节点。
这套代码需要用户直接参与的部分都用注册函数来实现，让使用者完全不需要了解
有序平衡二叉树的添加、删除或查找的过程，能够做到傻瓜式的使用。至于性能，我添
加过300万个树节点之后，树高只有22层，查找任意一个节点最多只需要22次匹配操作。
比HASH表快了很多。
这套代码还针对vxworks操作系统做了一点点扩展，其实就是判断一下当前操作系统
是否是vxworks，如果是的话就创建一个二进制信号量，如果不是就什么信号量也不创建。
目前此版本提供了如下通用接口：
1、数据结构定义
1.1、树的结构定义
typedef struct _AVL_TREE_HEADER
{
TREE_NODE *pTreeHeader
#ifdef ORDER_LIST_WANTED
TREE_NODE *pListHeader
TREE_NODE *pListTail
#endif
unsigned int count/*AVL树里的节点总数*/
int (*keyCompare)(TREE_NODE * , TREE_NODE *)
int (*free)(TREE_NODE *)
#if OS==3||OS==4 /*#if OS == VXWORKS || OS == VXWORKS_M*/
SEM_ID sem
#endif
} tAVLTree
1.2、树节点的结构定义
typedef struct _AVL_TREE_NODE
{
#ifdef ORDER_LIST_WANTED
struct _AVL_TREE_NODE *prev
struct _AVL_TREE_NODE *next
#endif
struct _AVL_TREE_NODE *tree_root
struct _AVL_TREE_NODE *left_child
struct _AVL_TREE_NODE *right_child
int bf /*平衡因子；当平衡因子的绝对值大于或等于2的时候就表示树不平衡(balance_factor)*/
}TREE_NODE
2、通用函数接口定义
2.1、avlTreeCreate
函数原型：tAVLTree *avlTreeCreate(int *keyCompareFunc,int *freeFunc)
参数描述：keyCompareFunc - 节点大小比较函数的指针，此函数需要用户自己提供，
比较函数的返回值应该是-1、0、1，(*keyCompareFunc)函数有两个参数，
分别是两个树节点，如果第二个参数所指向的树节点的值比第一个的小，
那么比较函数就应该返回-1，如果相等就是返回0，否则就是1。具体的比
较规则由用户根据所存储的数据里面的关键字来指定（当然，关键字有可
能有多个）。
freeFunc - (*freeFunc)只有一个参数，就是需要释放内存的节点的指
针，填写这个注册函数的目的是为了实现avlTreeDestroy和avlTreeFlush
这两个函数。
返回值 ：成功 - 返回指向一个树的指针
失败 - NULL
函数描述：创建一棵空的平衡二叉树，如果是vxworks操作系统的话还创建一个跟树
相关的一个二进制信号量。初始化所有指针为空指针。
2.2、avlTreeDestroy
函数原型：int avlTreeDestroy(tAVLTree *pTree)
参数描述：pTree - 指向一棵平衡二叉树的指针
返回值 ：成功 - 1
失败 - 0
函数描述：摧毁一颗平衡二叉树，释放所有树节点的内存，并且释放信号量（如果是
vxworks操作系统的话），释放pTree所指向的二叉树所占用的内存。
2.3、avlTreeFlush
函数原型：int avlTreeFlush(tAVLTree *pTree)
参数描述：pTree - 指向一棵平衡二叉树的指针
返回值 ：成功 - 1
失败 - 0
函数描述：清空一颗平衡二叉树，释放所有树节点的内存，但是并不删除平衡二叉树
2.4、avlTreeAdd
函数原型：int avlTreeAdd(tAVLTree *pTree , TREE_NODE *pInsertNode)
参数描述：pTree - 指向一棵平衡二叉树的指针
pInsertNode - 待插入的节点的指针
返回值 ：成功 - 1
失败 - 0
函数描述：往平衡二叉树中添加一个成员节点
2.5、avlTreeDel
函数原型：int avlTreeAdd(tAVLTree *pTree , TREE_NODE *pDelNode)
参数描述：pTree - 指向一棵平衡二叉树的指针
pDelNode - 待插入的节点的指针
返回值 ：成功 - 1
失败 - 0
函数描述：从平衡二叉树中删除一个树节点
2.6、avlTreeFind
函数原型：TREE_NODE *avlTreeFind(tAVLTree *pTree,TREE_NODE *pKeyNode)
参数描述：pTree - 指向一棵平衡二叉树的指针
pKeyNode - 待查找的节点的关键字
返回值 ：成功 - 查找到的节点指针
失败 - NULL
函数描述：查找一个节点
2.7、avlTreeCount
函数原型：int avlTreeCount(tAVLTree *pTree)
参数描述：pTree - 指向一棵平衡二叉树的指针
返回值 ：成功 - 当前平衡二叉树里的节点总数
失败 - 0
函数描述：获取当前树里面的所有成员节点总数
2.8、avlTreeFirst
函数原型：TREE_NODE *avlTreeFirst(tAVLTree *pTree)
参数描述：pTree - 指向一棵平衡二叉树的指针
返回值 ：成功 - 当前平衡二叉树里面的最小的成员节点的指针
失败 - NULL，只有树是空的时候才会返回NULL
函数描述：获取当前平衡二叉树里面第一个成员节点，即最小的成员节点
2.9、avlTreeLast
函数原型：TREE_NODE *avlTreeLast(tAVLTree *pTree)
参数描述：pTree - 指向一棵平衡二叉树的指针
返回值 ：成功 - 当前平衡二叉树里面的最大的成员节点的指针
失败 - NULL，只有树是空的时候才会返回NULL
函数描述：获取当前平衡二叉树里面最后一个成员节点，即最大的成员节点
2.10、avlTreeNext
函数原型：TREE_NODE *avlTreeNext(TREE_NODE *pNode)
参数描述：pTree - 指向一棵平衡二叉树的指针
返回值 ：成功 - 下一个成员节点的指针
失败 - NULL
函数描述：获取当前节点的下一个节点
2.11、avlTreePrev
函数原型：TREE_NODE *avlTreePrev(TREE_NODE *pNode)
参数描述：pTree - 指向一棵平衡二叉树的指针
返回值 ：成功 - 前一个成员节点的指针
失败 - NULL
函数描述：获取当前节点的前一个节点
2.12、AVL_TREE_LOCK
函数原型：void AVL_TREE_LOCK(tAVLTree *pTree,int timeout)
参数描述：pTree - 指向一棵平衡二叉树的指针
timeout - 等待时间
返回值 ：N/A
函数描述：此函数只有是vxworks系统才有效，目的是对树进行互斥操作，防止
多任务同时操作链表。
2.13、AVL_TREE_UNLOCK
函数原型：void AVL_TREE_UNLOCK(tAVLTree *pTree)
参数描述：pTree - 指向一棵平衡二叉树的指针
返回值 ：N/A
函数描述：此函数只有是vxworks系统才有效，目的是对树进行解除互斥操作
2.13、AVL_TREENODE_FREE
函数原型：void AVL_TREENODE_FREE(tAVLTree *pTree,TREE_NODE *pNode)
参数描述：pTree - 指向一棵平衡二叉树的指针
pNode - 需要释放的节点的指针
返回值 ：N/A
函数描述：此函数释放内存的过程采用的是注册的释放函数，释放不仅仅
只有free函数，对于一些复杂的结构设计，可能需要释放多个
不同的内存。
3、应用举例
> typedef struct _testStruct{
> TREE_NODE node /*树节点的结构一定要放在用户自定义结构的最前面，注意!*/
> int keyA /*关键字A*/
> int keyB /*关键字B*/
> int keyC /*关键字C，比方说此结构有3个关键字*/
> int userData[200]/*用户的实际数据区*/
> }tTestStruct
>
> int keyCompareFunc(TREE_NODE *p , TREE_NODE *p1)
> {
> tTestStruct *T1=NULL,*T2=NULL
>
> T1=(tTestStruct *)p
> T2=(tTestStruct *)p1
>
> if(T1->keyA <T2->keyA) return 1
> if(T1->keyA >T2->keyA) return -1
>
> if(T1->keyB <T2->keyB) return 1
> if(T1->keyB >T2->keyB) return -1
>
> if(T1->keyC <T2->keyC) return 1
> if(T1->keyC >T2->keyC) return -1
>
> return 0
> }
>
> int freeFunc(TREE_NODE *pNode)
> {
> free((void *)pNode)
> return 1
> }
>
> tAVLTree *pTree = NULL
> int main()
> {
> tTestStruct *pTest = NULL
> tTestStruct key
> int count = 0
> pTree = (tAVLTree *)avlTreeCreate
> (
> (void*)keyCompareFunc ,
> (void *)freeFunc
> )
> if(!pTree)
> {
> printf("\r\n 创建平衡二叉树失败")
> return 0
> }
>
> /*添加一个节点*/
> pTest = (tTestStruct *)malloc(sizeof(tTestStruct))
> if(!pTest)
> {
> printf("\r\n 创建树节点失败")
> return 0
> }
>
> pTest->keyA = 1
> pTest->keyB = 2
> pTest->keyC = 3
> if(!avlTreeAdd(pTree , (TREE_NODE *)pTest))
> {
> printf("\r\n 已经存在相同节点，添加失败!关键字完全匹配就表示节点完全相同")
> return 1
> }
>
> /*再添加一个节点*/
> pTest = (tTestStruct *)malloc(sizeof(tTestStruct))
> if(!pTest)
> {
> printf("\r\n 创建树节点又失败")
> return 0
> }
>
> pTest->keyA = 1
> pTest->keyB = 1
> pTest->keyC = 3 /*第二次添加的节点的关键字比较大家可以算一算*/
> if(!avlTreeAdd(pTree , (TREE_NODE *)pTest))
> {
> printf("\r\n 已经存在相同节点，添加失败!关键字完全匹配就表示节点完全相同")
> return 1
> }
>
> /*遍历有序平衡二叉树 -- 从小到大*/
> pTest = (tTestStruct *)avlTreeFirst(pTree)
> while(pTest)
> {
> /**************************
> *这里你想干嘛干嘛
> *处理pTest->userData?
> ***************************/
> pTest = (tTestStruct *)avlTreeNext(pTree)
> }
>
> /*遍历有序平衡二叉树 -- 从大到小*/
> pTest = (tTestStruct *)avlTreeLast(pTree)
> while(pTest)
> {
> /**************************
> *这里你想干嘛干嘛
> *处理pTest->userData?
> ***************************/
> pTest = (tTestStruct *)avlTreePrev(pTree)
> }
>
> /*查找某个节点*/
> key->keyA = 1
> key->keyB = 1
> key->keyC = 3
> pTest = (tTestStruct *)avlTreeFind(pTree , (TREE_NODE *)&key)
> if(pTest)
> printf("\r\n 这里应该可以查找到一条记录，就是第二个插入的节点")
>
> /*删除一个节点，我们就将上面查找到的节点删除*/
> if(!avlTreeCount(pTree , (TREE_NODE *)pTest))
> {
> printf("\r\n 如果删除失败，只能说明一个问题，树里面不存在这个节点")
> return 0
> }
>
> /*获取树的总的节点数*/
> count = avlTreeCount(pTree)
> printf("\r\n 我想现在count应该等于1，刚才我们删掉了一个节点")
>
> /*清空整棵树*/
> avlTreeFlush(pTree)
>
> /*删除整棵树，其实现在只有一颗裸树了，因为树节点都被flush掉了*/
> avlTreeDestroy(pTree)
> pTree = NULL
>
> return 1
> }
欢迎分享，转载请注明来源：夏雨云
微信扫一扫
支付宝扫一扫
评论列表（0条）