美文网首页C语言
C链表

C链表

作者: Mr_Me | 来源:发表于2017-07-20 11:52 被阅读15次
  • 互斥锁：链表用在多线程中保证顺序，多个线程会操作同一个链表，互斥锁保证多线程操作的安全，互斥锁分情况使用，链表并不一定需要互斥锁。
typedef struct SDL_mutex {
    pthread_mutex_t id;
} SDL_mutex;

typedef struct SDL_cond {
    pthread_cond_t id;
} SDL_cond;
  • 互斥锁的操作
SDL_mutex *SDL_CreateMutex(void)
{
    SDL_mutex *mutex;
    mutex = (SDL_mutex *) mallocz(sizeof(SDL_mutex));
    if (!mutex)
        return NULL;

    if (pthread_mutex_init(&mutex->id, NULL) != 0) {
        free(mutex);
        return NULL;
    }

    return mutex;
}

void SDL_DestroyMutex(SDL_mutex *mutex)
{
    if (mutex) {
        pthread_mutex_destroy(&mutex->id);
        free(mutex);
    }
}

void SDL_DestroyMutexP(SDL_mutex **mutex)
{
    if (mutex) {
        SDL_DestroyMutex(*mutex);
        *mutex = NULL;
    }
}

int SDL_LockMutex(SDL_mutex *mutex)
{
    assert(mutex);
    if (!mutex)
        return -1;

    return pthread_mutex_lock(&mutex->id);
}

int SDL_UnlockMutex(SDL_mutex *mutex)
{
    assert(mutex);
    if (!mutex)
        return -1;

    return pthread_mutex_unlock(&mutex->id);
}

SDL_cond *SDL_CreateCond(void)
{
    SDL_cond *cond;
    cond = (SDL_cond *) mallocz(sizeof(SDL_cond));
    if (!cond)
        return NULL;

    if (pthread_cond_init(&cond->id, NULL) != 0) {
        free(cond);
        return NULL;
    }

    return cond;
}

void SDL_DestroyCond(SDL_cond *cond)
{
    if (cond) {
        pthread_cond_destroy(&cond->id);
        free(cond);
    }
}

void SDL_DestroyCondP(SDL_cond **cond)
{

    if (cond) {
        SDL_DestroyCond(*cond);
        *cond = NULL;
    }
}

int SDL_CondSignal(SDL_cond *cond)
{
    assert(cond);
    if (!cond)
        return -1;

    return pthread_cond_signal(&cond->id);
}
  • 链表和节点的定义声明
typedef struct Queue{
    node *phead, *first_node, *last_node;
    int count;
    SDL_mutex *mutex;
    SDL_mutex *ex_mutex;
    SDL_cond *cond;
}queue;

typedef struct queue_node {
    struct queue_node* prev;
    struct queue_node* next;
    void *para;
} node;
  • 链表的逻辑结构
/**
双向链表 创建一个节点

 @param para 要保存到链表的内容
 @return 返回创建的这个节点
 */
static node* create_node(void *para)
{
    node *pnode = NULL;
    pnode = (node *) malloc(sizeof(node));
    if (pnode)
    {
        pnode->prev = pnode->next = pnode;
        pnode->para = para;
    }
    return pnode;
}

/**
 创建链表的phead

 @param q 链表
 @return success return 0, fail return -1
 */
int create_queue(queue *q)
{
    q->phead = create_node(NULL);
    if (!q->phead)
        return -1;
    return 0;
}

/**
 初始化一个链表

 @param q 链表
 @return 链表的头
 */
static int queue_init(queue *q)
{
    memset(q, 0, sizeof(queue));
    
    q->phead = NULL;
    q->last_node = NULL;
    q->first_node = NULL;
    q->count = 0;
    q->mutex = SDL_CreateMutex();
    if (!q->mutex)
    {
        av_log(NULL, AV_LOG_FATAL, "SDL_CreateMutex(): %s\n", SDL_GetError());
        return AVERROR(ENOMEM);
    }
    q->ex_mutex = SDL_CreateMutex();
    if (!q->ex_mutex)
    {
        av_log(NULL, AV_LOG_FATAL, "SDL_CreateMutex(): %s\n", SDL_GetError());
        return AVERROR(ENOMEM);
    }
    q->cond = SDL_CreateCond();
    if (!q->cond)
    {
        av_log(NULL, AV_LOG_FATAL, "SDL_CreateCond(): %s\n", SDL_GetError());
        return AVERROR(ENOMEM);
    }
    return create_queue(q);
}

/**
 判断链表是否为空

 @param q 链表
 @return 空：return 1，不是空：return 0
 */
int queue_is_empty(queue *q)
{
    return q->count == 0;
}

/**
 获取链表长度

 @param q 链表
 @return 链表中元素的个数
 */
int queue_size(queue *q)
{
    return q->count;
}

/**
 根据index获取链表的节点

 @param q 链表
 @param index 链表元素下标
 @return 该下标的链表元素节点。
 */
static node* get_node(queue *q,int index)
{
    if (index < 0 || index >= q->count)
        return NULL;
    
    if (index <= (q->count / 2))
    {
        int i = 0;
        node *pnode = q->phead->next;
        while ((i++) < index)
            pnode = pnode->next;
        return pnode;
    }
    int j = 0;
    int rindex = q->count - index - 1;
    node *rnode = q->phead->prev;
    while ((j++) < rindex)
        rnode = rnode->prev;

    return rnode;
}

/**
 根据index获取改链表节点里面的存储内容

 @param q 链表
 @param index 链表节点下标
 @return 该下标元素节点中存储的内容
 */
void* queue_get(queue *q,int index)
{
    SDL_LockMutex(q->mutex);
    node *pindex = get_node(q,index);
    if (!pindex)
    {
        SDL_UnlockMutex(q->mutex);
        return NULL;
    }
    SDL_UnlockMutex(q->mutex);
    return pindex->para;
}

/**
 获取该链表第一个节点存储的内容

 @param q 链表
 @return 该链表的某个节点内容
 */
void* queue_get_first(queue *q)
{
    return queue_get(q,0);
}

/**
 获取该链表最后一个节点存储的内容

 @param q 链表
 @return 该链表的某个节点内容
 */
void* queue_get_last(queue *q)
{
    return queue_get(q,q->count - 1);
}

/**
 存储一个元素到链表

 @param q 要存储到的链表
 @param para 要存储的内容
 @return success return 0 ，fail return -1
 */
int queue_append_last(queue *q,void *para)
{
    SDL_LockMutex(q->mutex);
    node *pnode = create_node(para);
    if (!pnode)
    {
        SDL_UnlockMutex(q->mutex);
        return -1;
    }
    pnode->next = q->phead;
    pnode->prev = q->phead->prev;
    q->phead->prev->next = pnode;
    q->phead->prev = pnode;
    q->last_node = pnode;
    q->count++;
    SDL_UnlockMutex(q->mutex);
    return 0;
}

/**
 根据index 删除链表的元素节点

 @param q 链表
 @param index 要删除的节点下标
 @return success return 0 ，fail return -1
 */
int queue_delete(queue *q,int index)
{
    SDL_LockMutex(q->mutex);
    node *pindex = get_node(q,index);
    if (!pindex)
    {
        SDL_UnlockMutex(q->mutex);
        return -1;
    }
    pindex->next->prev = pindex->prev;
    pindex->prev->next = pindex->next;
    free(pindex);
    q->count--;
    SDL_UnlockMutex(q->mutex);
    return 0;
}

/**
 删除该链表第一个节点

 @param q 链表
 @return success return 0 ，fail return -1
 */
int queue_delete_first(queue *q)
{
    return queue_delete(q,0);
}
/**
 删除该链表最后一个节点
 
 @param q 链表
 @return success return 0 ，fail return -1
 */
int queue_delete_last(queue *q)
{
    return queue_delete(q, q->count - 1);
}

/**
 销毁链表

 @param q 链表
 @return success return 0 ，fail return -1
 */
int destroy_queue(queue *q)
{
    SDL_LockMutex(q->mutex);
    if (!q->phead)
    {
        SDL_UnlockMutex(q->mutex);
        return -1;
    }
    node *pnode = q->phead->next;
    node *ptmp = NULL;
    while (pnode != q->phead)
    {
        ptmp = pnode;
        pnode = pnode->next;
        free(ptmp);
    }
    free(q->phead);
    q->phead = NULL;
    q->last_node = NULL;
    q->first_node = NULL;
    q->count = 0;
    SDL_UnlockMutex(q->mutex);
    SDL_DestroyMutex(q->mutex);
    SDL_DestroyCond(q->cond);
    return 0;
}

相关文章

  • 链表

    单链表 C实现 Java实现 双链表 C实现 Java实现

  • C# 链表

    链表介绍 Unity 用C#写的链表类 简述链表和数组的区别 Unity--链表实现贪吃蛇

  • LeetCode 141 环形链表 Linked List Cy

    有关链表的LeetCode做题笔记合集，Python实现 链表定义 141. 环形链表 Linked List C...

  • C链表

    互斥锁：链表用在多线程中保证顺序，多个线程会操作同一个链表，互斥锁保证多线程操作的安全，互斥锁分情况使用，链表并不...

  • 容器(2) - LinkedList

    LinkedList 基本实现 LinkedList 类似 C/C++ 的双向链表，这种链表中任意一个存储单元都可...

  • 关于单链表、双向列表的一些算法

    首先给出数据定义的结构 单链表 1.单链表的逆序反转 单链表相邻节点反转 A-B-C-D 输出 B-A-D-C 双...

  • LeetCode 21.合并两个有序链表

    将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 C_非递归合并 C_...

  • 单链表 C++

    单链表 C++ 题目 1、创建单链表2、初始化单链表3、释放单链表4、获取单链表中元素的数量5、输出单链表中的所有...

  • Redis的数据结构(二)：链表

    链表在redis的应用 由于redis的c语言没有内置链表结构类型，因此redis自身实现了一套链表结构。链表主要...

  • C++实现双向循环链表

    本次博文是关于利用C++模板的方式实现的双向循环链表以及双向循环链表的基本操作，在之前的博文C++语言实现双向链表...

网友评论

    本文标题：C链表

    本文链接：https://www.haomeiwen.com/subject/pnpdkxtx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    C语言

    关于我们|服务条款|联系我们|C链表|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！