关于整理工作中用到的链表和哈希表的简单操作

2019-11-06 06:17:08

字体：大中小

来源：转载

供稿：网友

linux c 关于链表和哈希表的简单操作

单向链表单向循环链表双向链表双向循环链表哈希表

单向链表

定义

typedef struct tagSL_NODE{ struct tagSL_NODE *next;} sl_node_s;#define SL_ENTRY(ptr, type, member) (container_of(ptr, type, member))typedef struct tagSL_HEAD{ sl_node_s *pfirst;} sl_head_s;static inline void api_sl_init(IN sl_head_s *plist);static inline void api_sl_node_init(IN sl_node_s *pnode);static inline BOOL_T api_sl_is_empty(IN const sl_head_s *plist);static inline sl_node_s *api_sl_first(IN const sl_head_s *plist);static inline sl_node_s *api_sl_next(IN const sl_node_s *pnode);static inline void api_sl_add_head(IN sl_head_s *plist, IN sl_node_s *pnode);static inline sl_node_s *api_sl_del_head(IN sl_head_s *plist);static inline void api_sl_add_after(IN sl_head_s *plist, IN sl_node_s *PRev, IN sl_node_s *pinst);static inline sl_node_s *api_sl_del_after(IN sl_head_s *plist, IN sl_node_s *prev);static inline void api_sl_del(IN sl_head_s *plist, IN const sl_node_s *pnode);static inline void api_sl_append(IN sl_head_s *pdstlist, IN sl_head_s *psrclist);static inline void api_sl_free_all(IN sl_head_s *plist, IN void (*pfFree)(void *));/************************************宏定义**********************************/#define SL_FOREACH(plist, pnode) / for((pnode) = api_sl_first(plist); / NULL != (pnode); / (pnode) = api_sl_next(pnode))#define SL_FOREACH_SAFE(plist, pnode, next) / for((pnode) = api_sl_first(plist); / (NULL != (pnode)) && ({(next) = api_sl_next(pnode); BOOL_TRUE;}); / (pnode) = (next))#define SL_FOREACH_PREVPTR(plist, pnode, prev) / for((pnode) = api_sl_first(plist), (prev) = (sl_node_s *)NULL; / NULL != (pnode); / (void)({(prev) = (pnode); (pnode) = api_sl_next(pnode);}))#define SL_ENTRY_FIRST(plist, type, member) / (api_sl_is_empty(plist) ? NULL : SL_ENTRY(api_sl_first(plist), type, member))#define SL_ENTRY_NEXT(pstEntry, member) / (NULL == (pstEntry) ? NULL: / (NULL == api_sl_next(&((pstEntry)->member))) ? NULL : / SL_ENTRY(api_sl_next(&((pstEntry)->member)), typeof(*(pstEntry)), member))#define SL_FOREACH_ENTRY(plist, pstEntry, member) / for((pstEntry) = SL_ENTRY_FIRST(plist, typeof(*(pstEntry)), member); / NULL != (pstEntry); / (pstEntry) = SL_ENTRY_NEXT(pstEntry, member))#define SL_FOREACH_ENTRY_SAFE(plist, pstEntry, nextEntry, member) / for((pstEntry) = SL_ENTRY_FIRST(plist, typeof(*(pstEntry)), member); / (NULL != (pstEntry)) && / ({(nextEntry) = SL_ENTRY_NEXT(pstEntry, member); BOOL_TRUE;}); / (pstEntry) = (nextEntry))#define SL_FOREACH_ENTRY_PREVPTR(plist, pstEntry, prevEntry, member) / for((pstEntry) = SL_ENTRY_FIRST(plist, typeof(*(pstEntry)), member), / (prevEntry) = NULL ; / NULL != (pstEntry); / (void)({(prevEntry) = (pstEntry); (pstEntry) = SL_ENTRY_NEXT(prevEntry);}))

简单使用

#include <stdio.h>#include <stdlib.h>#include "list.h"typedef struct { sl_node_s node; int data;}sl_data_s;sl_head_s g_sl_list;sl_data_s *get_node (int data){ sl_data_s *pnode = NULL; pnode = (sl_data_s *)malloc (sizeof(sl_data_s)); if (pnode == NULL) { return NULL; } api_sl_node_init(&pnode->node); pnode->data = data; return pnode;}void show_node(){ sl_node_s *curr = NULL, *next = NULL; sl_data_s *node = NULL; SL_FOREACH_SAFE(&g_sl_list, curr, next) { if (curr != NULL) { node = (sl_data_s *)curr; printf("%d -> ", node->data); } } printf("/n"); return;}int main (){ sl_data_s *pnode = NULL; api_sl_init(&g_sl_list); pnode = get_node(2); if (pnode != NULL) { api_sl_add_head(&g_sl_list, &pnode->node); } show_node(); pnode = get_node(3); if (pnode != NULL) { api_sl_add_head(&g_sl_list, &pnode->node); } show_node(); api_sl_del_after(&g_sl_list, &pnode->node); show_node(); pnode = get_node(5); if (pnode != NULL) { api_sl_add_head(&g_sl_list, &pnode->node); } show_node(); api_sl_add_after(&g_sl_list, &pnode->node, &(get_node(8))->node); show_node(); api_sl_del_head(&g_sl_list); show_node(); return 0;}

单向循环链表

typedef struct tagSTQ_NODE{ struct tagSTQ_NODE *next;} stq_node_s;#define STQ_ENTRY(ptr, type, member) (container_of(ptr, type, member))typedef struct tagSTQ_HEAD{ stq_node_s *pfirst; stq_node_s *plast;} stq_head_s;static inline void api_stq_init(IN stq_head_s *plist);static inline void api_stq_node_init(IN stq_node_s *pnode);static inline BOOL_T api_stq_is_empty(IN const stq_head_s *plist);static inline stq_node_s *api_stq_first(IN const stq_head_s *plist);static inline stq_node_s *api_stq_last(IN const stq_head_s *plist);static inline stq_node_s *api_stq_next(IN const stq_node_s *pnode);static inline void api_stq_add_head(IN stq_head_s *plist, IN stq_node_s *pnode);static inline stq_node_s *api_stq_del_head(IN stq_head_s *plist);static inline void api_stq_add_tail(IN stq_head_s *plist, IN stq_node_s *pnode);static inline void api_stq_add_after(IN stq_head_s *plist, IN stq_node_s *prev, IN stq_node_s *pinst);static inline stq_node_s *api_stq_del_after(IN stq_head_s *plist, IN stq_node_s *prev);static inline void api_stq_del(IN stq_head_s *plist, IN const stq_node_s *pnode);static inline void api_stq_append(IN stq_head_s *pdstlist, IN stq_head_s *psrclist);static inline void api_stq_free_all(IN stq_head_s *plist, IN void (*pfFree)(void *));/************************************宏定义**********************************/#define STQ_FOREACH(plist, pnode) / for((pnode) = api_stq_first(plist); / NULL != (pnode); / (pnode) = api_stq_next(pnode))#define STQ_FOREACH_SAFE(plist, pnode, next) / for((pnode) = api_stq_first(plist); / (NULL != (pnode)) && ({(next) = api_stq_next(pnode); BOOL_TRUE;}); / (pnode) = (next))#define STQ_FOREACH_PREVPTR(plist, pnode, prev) / for((pnode) = api_stq_first(plist), (prev) = (stq_node_s *)NULL; / NULL != (pnode); / (void)({(prev) = (pnode); (pnode) = api_stq_next(pnode);}))#define STQ_ENTRY_FIRST(plist, type, member) / (api_stq_is_empty(plist) ? NULL : STQ_ENTRY(api_stq_first(plist), type, member))#define STQ_ENTRY_LAST(plist, type, member) / (api_stq_is_empty(plist) ? NULL : STQ_ENTRY(api_stq_last(plist), type, member))#define STQ_ENTRY_NEXT(pstEntry, member) / (NULL == (pstEntry) ? NULL: / (NULL == api_stq_next(&((pstEntry)->member))) ? NULL : / STQ_ENTRY(api_stq_next(&((pstEntry)->member)), typeof(*(pstEntry)), member))#define STQ_FOREACH_ENTRY(plist, pstEntry, member) / for((pstEntry) = STQ_ENTRY_FIRST(plist, typeof(*(pstEntry)), member); / NULL != (pstEntry); / (pstEntry) = STQ_ENTRY_NEXT(pstEntry, member))#define STQ_FOREACH_ENTRY_SAFE(plist, pstEntry, nextEntry, member) / for((pstEntry) = STQ_ENTRY_FIRST(plist, typeof(*(pstEntry)), member); / (NULL != (pstEntry)) && / ({(nextEntry) = STQ_ENTRY_NEXT(pstEntry, member); BOOL_TRUE;}); / (pstEntry) = (nextEntry))#define STQ_FOREACH_ENTRY_PREVPTR(plist, pstEntry, prevEntry, member) / for((pstEntry) = STQ_ENTRY_FIRST(plist, typeof(*(pstEntry)), member), / (prevEntry) = NULL ; / NULL != (pstEntry); / (void)({(prevEntry) = (pstEntry); (pstEntry) = STQ_ENTRY_NEXT(prevEntry);}))

双向链表

typedef struct tagDL_NODE{ struct tagDL_NODE *next; struct tagDL_NODE **ppstpre; /* the address of previous element's next */} dl_node_s;#define DL_ENTRY(ptr,type, member) (container_of(ptr, type, member))#define DL_NODE_FROM_PPRE(ppstpre) (container_of(ppstpre, dl_node_s, next))#define DL_ENTRY_FROM_PPRE(ppstpre, type, member) / DL_ENTRY(DL_NODE_FROM_PPRE(ppstpre), type, member)typedef struct tagDL_HEAD{ dl_node_s *pfirst;} dl_head_s;static inline void api_dl_init(IN dl_head_s *plist);static inline void api_dl_node_init(IN dl_node_s *pnode);static inline BOOL_T api_dl_is_empty(IN const dl_head_s *plist);static inline dl_node_s *api_dl_first(IN const dl_head_s *plist);static inline dl_node_s *api_dl_next(IN const dl_node_s *pnode);static inline dl_node_s *api_dl_prev(IN const dl_node_s *pnode);static inline void api_dl_del(IN const dl_node_s *pnode);static inline void api_dl_add_head(IN dl_head_s *plist, IN dl_node_s *pnode);static inline dl_node_s *api_dl_del_head(IN dl_head_s *plist);static inline void api_dl_add_after(IN dl_node_s *prev, IN dl_node_s *pinst);static inline void api_dl_add_after_ptr(IN dl_node_s **ppstpre, IN dl_node_s *pinst);static inline void api_dl_add_before(IN dl_node_s *prev, IN dl_node_s *pinst);static inline void api_dl_append(IN dl_head_s *pdstlist, IN dl_head_s *psrclist);static inline void api_dl_free_all(IN dl_head_s *plist, IN void (*pfFree)(void *));/************************************宏定义**********************************/#define DL_FOREACH(plist, pnode) / for((pnode) = api_dl_first(plist); / NULL != (pnode); / (pnode) = api_dl_next(pnode))#define DL_FOREACH_SAFE(plist, pnode, next) / for((pnode) = api_dl_first(plist); / (NULL != (pnode)) && ({(next) = api_dl_next(pnode); BOOL_TRUE;}); / (pnode) = (next))#define DL_FOREACH_PREVPTR(plist, pnode, ppstpre) / for((pnode) = api_dl_first(plist), (ppstpre) = &((plist)->pfirst); / NULL != (pnode); / (void)({(ppstpre) = &((pnode)->next); (pnode) = api_dl_next(pnode);}))#define DL_ENTRY_FIRST(plist, type, member) / (api_dl_is_empty(plist) ? NULL : DL_ENTRY(api_dl_first(plist), type, member))#define DL_ENTRY_NEXT(pstEntry, member) / (NULL == (pstEntry) ? NULL: / (NULL == api_dl_next(&((pstEntry)->member))) ? NULL : / DL_ENTRY(api_dl_next(&((pstEntry)->member)), typeof(*(pstEntry)), member))#define DL_ENTRY_PREV(pstEntry, member) / (NULL == (pstEntry) ? NULL: / (NULL == api_dl_prev(&((pstEntry)->member))) ? NULL : / DL_ENTRY(api_dl_prev(&((pstEntry)->member)), typeof(*(pstEntry)), member))#define DL_FOREACH_ENTRY(plist, pstEntry, member) / for((pstEntry) = DL_ENTRY_FIRST(plist, typeof(*(pstEntry)), member); / NULL != (pstEntry); / (pstEntry) = DL_ENTRY_NEXT(pstEntry, member))#define DL_FOREACH_ENTRY_SAFE(plist, pstEntry, nextEntry, member) / for((pstEntry) = DL_ENTRY_FIRST(plist, typeof(*(pstEntry)), member); / (NULL != (pstEntry)) && / ({(nextEntry) = DL_ENTRY_NEXT(pstEntry, member); BOOL_TRUE;}); / (pstEntry) = (nextEntry))#define DL_FOREACH_ENTRY_PREVPTR(plist, pstEntry, ppstpre, member) / for((pstEntry) = DL_ENTRY_FIRST(plist, typeof(*(pstEntry)), member), / (ppstpre) = &((plist)->pfirst); / NULL != (pstEntry); / (void)({(ppstpre) = &((pstEntry)->member.next); (pstEntry) = DL_ENTRY_NEXT(pstEntry, member);}))

双向循环链表

typedef struct tagDTQ_NODE{ struct tagDTQ_NODE *prev; struct tagDTQ_NODE *next;} dtq_node_s;#define DTQ_ENTRY(ptr, type, member) (container_of(ptr, type, member))typedef struct tagDTQ_HEAD{ dtq_node_s stHead;} dtq_head_s;static inline void api_dtq_init(IN dtq_head_s *plist);static inline void api_dtq_node_init(IN dtq_node_s *pnode);static inline BOOL_T api_dtq_is_empty(IN const dtq_head_s *plist);static inline dtq_node_s *api_dtq_first(IN const dtq_head_s *plist);static inline dtq_node_s *api_dtq_last(IN const dtq_head_s *plist);static inline BOOL_T api_dtq_is_end_ofq(IN const dtq_head_s *plist, IN const dtq_node_s *pnode);static inline dtq_node_s *api_dtq_prev(IN const dtq_node_s *pnode);static inline dtq_node_s *api_dtq_next(IN const dtq_node_s *pnode);static inline void api_dtq_add_after(IN dtq_node_s *prev, IN dtq_node_s *pinst);static inline void api_dtq_add_before(IN dtq_node_s *next, IN dtq_node_s *pinst);static inline void api_dtq_del(IN dtq_node_s *pnode);static inline void api_dtq_add_head(IN dtq_head_s *plist, IN dtq_node_s *pnode);static inline dtq_node_s *api_dtq_del_head(IN dtq_head_s *plist);static inline void api_dtq_add_tail(IN dtq_head_s *plist, IN dtq_node_s *pnode);static inline dtq_node_s *api_dtq_del_tail(IN dtq_head_s *plist);static inline void api_dtq_append(IN dtq_head_s *pdstlist, IN dtq_head_s *psrclist);static inline void api_dtq_free_all(IN dtq_head_s *plist, IN void (*pfFree)(void *));/************************************宏定义**********************************/#define DTQ_FOREACH(plist, pnode) / for((pnode) = api_dtq_first(plist); / (pnode) != &((plist)->stHead); / (pnode) = api_dtq_next(pnode))#define DTQ_FOREACH_SAFE(plist, pnode, nextnode) / for((pnode) = (plist)->stHead.next; / (pnode) != &((plist)->stHead) && / ({(nextnode) = api_dtq_next(pnode); BOOL_TRUE;}); / (pnode) = (nextnode))#define DTQ_FOREACH_REVERSE(plist, pnode) / for((pnode) = api_dtq_last(plist); / (BOOL_TRUE) != api_dtq_is_end_ofq(plist, pnode); / (pnode) = api_dtq_prev(pnode)#define DTQ_FOREACH_REVERSE_SAFE(plist, pnode, prev) / for((pnode) = api_dtq_last(plist); / (BOOL_TRUE != api_dtq_is_end_ofq(plist, pnode)) && / ({(prev) = api_dtq_prev(pnode); BOOL_TRUE;}); / (pnode) = (prev))#define DTQ_ENTRY_FIRST(plist, type, member) / ({dtq_node_s *pnode__Tmp__Mx = api_dtq_first(plist); / (NULL == pnode__Tmp__Mx) ? NULL : DTQ_ENTRY(pnode__Tmp__Mx, type, member);})#define DTQ_ENTRY_LAST(plist, type, member) / ({dtq_node_s *pnode__Tmp__Mx = api_dtq_last(plist); / (NULL == pnode__Tmp__Mx) ? NULL : DTQ_ENTRY(pnode__Tmp__Mx, type, member);})#define DTQ_ENTRY_NEXT(plist, pstEntry, member) / (api_dtq_is_end_ofq(plist, (NULL == (pstEntry) ? NULL : api_dtq_next(&((pstEntry)->member)))) ? / NULL : / DTQ_ENTRY(api_dtq_next(&((pstEntry)->member)), typeof(*(pstEntry)), member))#define DTQ_ENTRY_PREV(plist, pstEntry, member) / (api_dtq_is_end_ofq(plist, (NULL == (pstEntry) ? NULL : api_dtq_prev(&((pstEntry)->member)))) ? / NULL : / DTQ_ENTRY(api_dtq_prev(&((pstEntry)->member)), typeof(*(pstEntry)), member))#define DTQ_FOREACH_ENTRY(plist, pstEntry, member) / for((pstEntry) = DTQ_ENTRY((plist)->stHead.next, typeof(*(pstEntry)), member); / ((&(pstEntry)->member != &(plist)->stHead) || ({pstEntry = NULL; BOOL_FALSE;})); / (pstEntry) = DTQ_ENTRY((pstEntry)->member.next, typeof(*(pstEntry)), member))#define DTQ_FOREACH_ENTRY_SAFE(plist, pstEntry, nextEntry, member) / for((pstEntry) = DTQ_ENTRY((plist)->stHead.next, typeof(*(pstEntry)), member); / (((&(pstEntry)->member != &(plist)->stHead) && / ({(nextEntry) = DTQ_ENTRY((pstEntry)->member.next, typeof(*(pstEntry)), member); BOOL_TRUE;})) || / ({(pstEntry) = NULL; BOOL_FALSE;})); / (pstEntry) = (nextEntry))#define DTQ_FOREACH_ENTRY_REVERSE(plist, pstEntry, member) / for ((pstEntry) = DTQ_ENTRY_LAST(plist, typeof(*(pstEntry)), member); / NULL != (pstEntry); / (pstEntry) = DTQ_ENTRY_PREV(plist, pstEntry, member))#define DTQ_FOREACH_ENTRY_REVERSE_SAFE(plist, pstEntry, prevEntry, member) / for((pstEntry) = DTQ_ENTRY_LAST(plist, typeof(*(pstEntry)), member); / (NULL !=(pstEntry)) && / ({(prevEntry) = DTQ_ENTRY_PREV(plist, pstEntry, member); BOOL_TRUE;}); / (pstEntry) = (prevEntry))