| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661 | /****************************************************************************** * 链表 * Copyright 2014, Simon * * File Name  : LinkedList.c * Description: 链表各项操作 * Last Modify: 08-jul-2013 * Virsion      : 1.1 * * modification history * -------------------- * V1.6, 21-dec-2016, Simon modify: 修改append/insert/appendnomalloc, 删除节点size形参 * V1.5, 08-sep-2016, Simon modify: 重写,删除index属性,外部免除更多链表的操作 * V1.4, 22-jul-2016, Simon modify: 移植到rt-thread * V1.3, 09-jun-2015, Simon modify: 修改结构体List_t内成员名location=>index * V1.2, 10-jun-2014, Simon modify: 减少返回错误类型 * V1.1, 17-jul-2013, Simon modify: 修改List_Append * V1.1, 08-jul-2013, Simon modify: 结点数据size从固定改为可变输入 * V1.0, 23-dec-2009, Simon written * -------------------- ******************************************************************************/#include "linkedlist.h"//#include <stdint.h>#include <stdio.h>#include <stdlib.h>#include <string.h>static int __FreeContent(void *content){    return 1;}/****************************************************************************** * List_Creat - 创建链表 * * Input: * @param max_cnt the max count of the list * Return: * @return a pointer to the new list structure * modification history * -------------------- * 23-dec-2009, Simon written * -------------------- ******************************************************************************/List_t *List_Creat(const uint32_t max_cnt){    List_t *newl = malloc(sizeof(List_t));    if(newl)    {        memset(newl, 0, sizeof(List_t));        newl->max_cnt = max_cnt;    }    else    {        return NULL;    }    return newl;}/****************************************************************************** * List_NextNode - 下一结点 * * Input: * @param plist the list to which the operation is to be applied * @param pos pointer to the current position in the list.  NULL means start from the beginning of the list * Output: This is updated on return to the same value as that returned from this function * Returns: return pointer to the current list node * modification history * -------------------- * 08-sep-2016, Simon written * -------------------- ******************************************************************************/List_Node_t* List_NextNode(List_t *plist, List_Node_t** pos){    return *pos = (*pos == NULL) ? plist->head : (*pos)->next;}/****************************************************************************** * List_PrevNode - 上一结点 * * Input: * @param plist the list to which the operation is to be applied * @param pos pointer to the current position in the list.  NULL means start from the end of the list * Output: This is updated on return to the same value as that returned from this function * Returns: return pointer to the current list node * modification history * -------------------- * 08-sep-2016, Simon written * -------------------- ******************************************************************************/List_Node_t* List_PrevNode(List_t *plist, List_Node_t** pos){    return *pos = (*pos == NULL) ? plist->tail : (*pos)->prev;}/****************************************************************************** * List_FindItem - 查找结点,查找对应内容或内容指针的结点 *                  调用内容指针或比较函数来比较 * * Input: * @param plist the list in which the search is to be conducted * @param content pointer to the content to look for * @param cmp pointer to a function which compares each node (NULL means compare by content pointer) * Output: * Returns: * @return the list node found, or NULL * modification history * -------------------- * 08-sep-2016, Simon written * -------------------- ******************************************************************************/List_Node_t* List_FindItem(List_t *plist, void *content, int(*cmp)(void*, void*)){    List_Node_t* rc = NULL;    if(!plist->size)    {        return rc;    }    if (plist->current != NULL && ((cmp == NULL && plist->current->content == content) ||        (cmp != NULL && cmp(plist->current->content, content))))    {        rc = plist->current;    }    else    {        List_Node_t* current = NULL;        /* find the content */        while (List_NextNode(plist, ¤t) != NULL)        {            if (cmp == NULL)            {                if (current->content == content)                {                    rc = current;                    break;                }            }            else            {                if (cmp(current->content, content))                {                    rc = current;                    break;                }            }        }        if (rc != NULL)            plist->current = rc;    }    return rc;}/****************************************************************************** * List_Find - 查找对应内容指针的结点,注意不是内容而是内容指针 * * Input: * @param plist the list in which the search is to be conducted * @param content pointer to the list item content itself * Output: * Returns: * @return the list item found, or NULL * modification history * -------------------- * 08-sep-2016, Simon written * -------------------- ******************************************************************************/List_Node_t* List_Find(List_t *plist, void *content){    return List_FindItem(plist, content, NULL);}/****************************************************************************** * List_AppendNoMalloc - 挂入一个已存在的结点 * * Input: * @param plist the list to which the item is to be added * @param content the list item content itself * @param new_node the List_Node_t to be used in adding the new item * Output: * Returns: * @return 0=fail, 1=succes * modification history * -------------------- * 08-sep-2016, Simon written * -------------------- ******************************************************************************/int List_AppendNoMalloc(List_t *plist, void *content, List_Node_t* new_node){    if(plist->count >= plist->max_cnt)    {        return 0;    }    /* for heap use */    new_node->content = content;    new_node->next = NULL;    new_node->prev = plist->tail;    if (plist->head == NULL)        plist->head = new_node;    else        plist->tail->next = new_node;    plist->tail = new_node;    ++(plist->count);    plist->size += sizeof(List_Node_t);    return 1;}/****************************************************************************** * List_Append - 挂入一个结点 * * Input: * @param plist the list to which the item is to be added * @param content the list item content itself * Output: * @return 0=fail, 1=succes * modification history * -------------------- * 08-sep-2016, Simon written * -------------------- ******************************************************************************/ //lint -e{429}int List_Append(List_t *plist, void *content){    List_Node_t* new_node = NULL;    if(plist->count >= plist->max_cnt)    {        return 0;    }    new_node = malloc(sizeof(List_Node_t));    if(new_node)    {        if(List_AppendNoMalloc(plist, content, new_node))        {            return 1;        }        else        {            free(new_node);        }    }    return 0;}/****************************************************************************** * List_Insert - 在指定位置插入结点 * * Input: * @param plist the list to which the item is to be added * @param content the list item content itself * @param index the position in the list. If NULL, this function is equivalent to ListAppend. * Output: * @return 0=fail, 1=succes * modification history * -------------------- * 08-sep-2016, Simon written * -------------------- ******************************************************************************/ //lint -e{593}int List_Insert(List_t *plist, void *content, List_Node_t* index){    List_Node_t* new_node = NULL;    if(plist->count >= plist->max_cnt)    {        return 0;    }    new_node = malloc(sizeof(List_Node_t));    if(new_node)    {        if ( index == NULL )            List_AppendNoMalloc(plist, content, new_node);        else        {            new_node->content = content;            new_node->next = index;            new_node->prev = index->prev;            index->prev = new_node;            if ( new_node->prev != NULL )                new_node->prev->next = new_node;            else                plist->head = new_node;            ++(plist->count);            plist->size += sizeof(List_Node_t);        }        return 1;    }    return 0;}/****************************************************************************** * List_Unlink - 删除并释放一个指定结点,通过比较内容来查找指定结点 *              使用一个回调函数来比较结点内容 * * Input: * @param plist the list in which the search is to be conducted * @param content pointer to the content to look for * @param cmp pointer to a function which compares each node * @param freeContent pointer to a function which the details of the steps in *      free content, NULL for only free the content memory itseft * Output: * Returns: * @return 1=item removed, 0=item not removed * modification history * -------------------- * 08-sep-2016, Simon written * -------------------- ******************************************************************************/int List_Unlink(List_t *plist, void *content, int(*cmp)(void*, void*), int (*freeContent)(void*)){    List_Node_t* next = NULL;    List_Node_t* saved = plist->current;    int saveddeleted = 0;    if (!List_FindItem(plist, content, cmp))        return 0; /* false, did not remove item */    if (plist->current->prev == NULL)        /* so this is the head node, and we have to update the "head" pointer */        plist->head = plist->current->next;    else        plist->current->prev->next = plist->current->next;    if (plist->current->next == NULL)        plist->tail = plist->current->prev;    else        plist->current->next->prev = plist->current->prev;    next = plist->current->next;    if (freeContent)    {        freeContent(plist->current->content);        free(plist->current->content);    }    if (saved == plist->current)        saveddeleted = 1;    free(plist->current);    plist->size -= sizeof(List_Node_t);    if (saveddeleted)        plist->current = next;    else        plist->current = saved;    --(plist->count);    return 1; /* successfully removed item */}/****************************************************************************** * List_Detach - 删除结点但不释放结点内容,通过比较结点指针来查找对应结点 * * Input: * @param plist the list in which the search is to be conducted * @param content pointer to the content to look for * Output: * Returns: * @return 1=item removed, 0=item not removed * modification history * -------------------- * 08-sep-2016, Simon written * -------------------- ******************************************************************************/int List_Detach(List_t *plist, void *content){    return List_Unlink(plist, content, NULL, NULL);}/****************************************************************************** * List_Remove - 删除结点并释放结点内容,对应的结点为指定的结点指针 * * Input: * @param plist the list from which the item is to be removed * @param content pointer to the content to look for * @param freeContent pointer to a function which the details of the steps in *      free content, NULL for only free the content memory itseft * Output: * Returns: * @return 1=item removed, 0=item not removed * modification history * -------------------- * 08-sep-2016, Simon written * -------------------- ******************************************************************************/int List_Remove(List_t *plist, void *content, int (*freeContent)(void*)){    if(freeContent)    {        return List_Unlink(plist, content, NULL, freeContent);    }    else    {        return List_Unlink(plist, content, NULL, __FreeContent);    }}/****************************************************************************** * List_DetachHead - 删除并释放链表头,不释放内容 * * Input: * @param plist the list from which the item is to be removed * Output: * Returns: * @return 1=item removed, 0=item not removed * modification history * -------------------- * 08-sep-2016, Simon written * -------------------- ******************************************************************************/void *List_DetachHead(List_t *plist){    void *content = NULL;    if (plist->count > 0)    {        List_Node_t* head = plist->head;        if (plist->current == head)            plist->current = head->next;        if (plist->tail == head) /* i.e. no of items in list == 1 */            plist->tail = NULL;        content = head->content;        plist->head = plist->head->next;        if (plist->head)            plist->head->prev = NULL;        free(head);        plist->size -= sizeof(List_Node_t);        --(plist->count);    }    return content;}/****************************************************************************** * List_RemoveHead - 删除并释放链表头及其内容 * * Input: * @param plist the list from which the item is to be removed * @param freeContent pointer to a function which the details of the steps in *      free content, NULL for only free the content memory itseft * Output: * Returns: * @return 1=item removed, 0=item not removed * modification history * -------------------- * 08-sep-2016, Simon written * -------------------- ******************************************************************************/int List_RemoveHead(List_t *plist, int (*freeContent)(void*)){    void *content = NULL;    content = List_DetachHead(plist);    if(content)    {        if(freeContent)        {            freeContent(content);        }        else        {            free(content);        }        return 1;    }    return 0;}/****************************************************************************** * List_PopTail - 删除链表尾但不释放结点内容 * * Input: * @param plist the list from which the item is to be removed * Output: * Returns: * @return the tail item removed (or NULL if none was) * modification history * -------------------- * 08-sep-2016, Simon written * -------------------- ******************************************************************************/void *List_PopTail(List_t *plist){    void *content = NULL;    if (plist->count > 0)    {        List_Node_t* tail = plist->tail;        if (plist->current == tail)            plist->current = tail->prev;        if (plist->head == tail) /* i.e. no of items in list == 1 */            plist->head = NULL;        content = tail->content;        plist->tail = plist->tail->prev;        if (plist->tail)            plist->tail->next = NULL;        free(tail);        plist->size -= sizeof(List_Node_t);        --(plist->count);    }    return content;}/****************************************************************************** * List_DetachItem - 删除指定结点但不释放结点内容 *              使用一个回调函数来比较结点内容 * * Input: * @param plist the list in which the search is to be conducted * @param content pointer to the content to look for * @param cmp pointer to a function which compares each node * Output: * Returns: * @return 1=item removed, 0=item not removed * modification history * -------------------- * 08-sep-2016, Simon written * -------------------- ******************************************************************************/int List_DetachItem(List_t *plist, void *content, int(*cmp)(void*, void*)){ /* do not free the content */    return List_Unlink(plist, content, cmp, NULL);}/****************************************************************************** * List_RemoveItem - 删除指定结点并释放内容 *              使用一个回调函数来比较结点内容 * * Input: * @param plist the list in which the search is to be conducted * @param content pointer to the content to look for * @param cmp pointer to a function which compares each node * @param freeContent pointer to a function which the details of the steps in *      free content, NULL for only free the content memory itseft * Output: * Returns: * @return 1=item removed, 0=item not removed * modification history * -------------------- * 08-sep-2016, Simon written * -------------------- ******************************************************************************/int List_RemoveItem(List_t *plist, void *content, int(*cmp)(void*, void*), int (*freeContent)(void*)){    if(freeContent)    {        return List_Unlink(plist, content, cmp, freeContent);    }    else    {        return List_Unlink(plist, content, cmp, __FreeContent);    }}/****************************************************************************** * List_Show - 扫描链表 * * Input: * @param plist the list in which the scan is to be conducted * Return: * modification history * -------------------- * 23-dec-2009, Simon written * -------------------- ******************************************************************************/void List_Show(List_t *plist){    int *content = NULL;    List_Node_t* current = NULL;    uint32_t index = 0;    printf("Total %u elements in LinkedList\r\n", plist->count);    while(List_NextNode(plist, ¤t) != NULL)    {        index++;        content = (int *)current->content;        //lint -e(626) -e(515) -e(705)        printf("The %d element is P-0x%x\r\n", index, content);    }}/****************************************************************************** * List_Count - 链表数据条数 * * Input: * @param plist the list in which the count to be know * Return: * @return the list count * modification history * -------------------- * 23-dec-2009, Simon written * -------------------- ******************************************************************************/uint32_t List_Count(List_t *plist){    return plist->count;}/****************************************************************************** * List_IsEmpty - 链表是否为空 * * Input: * @param plist the list in which the empty state to be know * Return: * @return 1=null, 0=not null * modification history * -------------------- * 23-dec-2009, Simon written * -------------------- ******************************************************************************/int List_IsEmpty(List_t *plist){    return plist->count == 0;}/****************************************************************************** * List_Spare - 链表剩余空间 * * Input: * @param plist the list in which the remaining count to be know * modification history * -------------------- * 23-dec-2009, Simon written * -------------------- ******************************************************************************/uint32_t List_Spare(List_t *plist){    return plist->max_cnt - plist->count;}/****************************************************************************** * List_Clear - 清空链表 * * Input: * @param plist the list in which the operation is to be applied * @param freeContent pointer to a function which the details of the steps in *      free content, NULL for only free the content memory itseft * Return: * modification history * -------------------- * 23-dec-2009, Simon written * -------------------- ******************************************************************************/void List_Clear(List_t *plist, int (*freeContent)(void*)){    while(List_RemoveHead(plist, freeContent));}/****************************************************************************** * List_Destroy - 删除链表 * * Input: * @param plist the list in which the operation is to be applied * modification history * -------------------- * 23-dec-2009, Simon written * -------------------- ******************************************************************************/void List_Destroy(List_t *plist){    List_Clear(plist, NULL);    free(plist);}
 |