It is recommended to use the kernel list only after you know the one-way and two-way circular lists. Do not use the kernel list first

Kernel linked list. H file

#ifndef __DLIST_H
#define __DLIST_H

```mermaid
graph TD
Start --> Stop
Copy the code

/* This file is from Linux Kernel (include/linux/list.h)

and modified by simply removing hardware prefetching of list items.
Here by copyright, credits attributed to wherever they belong.
Kulesh Shanmugasundaram (kulesh [squiggly] isis.poly.edu)

* /

/ *

Simple doubly linked list implementation.
Some of the internal functions (” __xxx “) are useful when
manipulating whole lists rather than single entries, as
sometimes we already know the next/prev entries and we can
generate better code by using them directly rather than
using the generic single-entry routines.

/ / *

container_of – cast a member of a structure out to the containing structure
@ptr: the pointer to the member.
@type: the type of the container struct this is embedded in.
@member: the name of the member within the struct.

*/ #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

#define container_of(ptr, type, member) ({ const typeof( ((type *)0)->member ) *__mptr = (ptr); (type *)( (char )__mptr – offsetof(type,member) ); } /

These are non-NULL pointers that will result in page faults
under normal circumstances, used to verify that nobody uses
non-initialized list entries.

*/ #define LIST_POISON1 ((void *) 0x00100100) #define LIST_POISON2 ((void *) 0x00200)

Struct list_head {struct list_head *next, *prev; };

#define LIST_HEAD_INIT(name) {&(name), &(name)}

#define LIST_HEAD(name)

struct list_head name = LIST_HEAD_INIT(name)

#define INIT_LIST_HEAD(PTR) do {(PTR)->next = (PTR); (ptr)->prev = (ptr); } while (0)

/ *

Insert a new entry between two known consecutive entries.
This is only for internal list manipulation where we know
the prev/next entries already!

* /

Static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next) { next->prev = new; new->next = next; new->prev = prev; prev->next = new;

}

/ * *

List_add – Add a new entry
@new: new entry to be added
@head: list head to add it after
Insert a new entry after the specified head.
This is good for implementing stacks.

Static list_add(struct list_head *new, struct list_head *head) {__list_add(new, struct list_head *head) head, head->next); }

/ * *

List_add_tail – Add a new entry
@new: new entry to be added
@head: list head to add it before
Insert a new entry before the specified head.
This is useful for implementing queues.

Static list_add_tail(struct list_head *new, struct list_head *head) {__list_add(new, struct list_head *head) head->prev, head); }

/ *

Delete a list entry by making the prev/next entries
point to each other.
This is only for internal list manipulation where we know
the prev/next entries already!

Static inline void __list_del(struct list_head *prev, struct list_head *prev, struct list_head *next) { next->prev = prev; prev->next = next; }

/ * *

List_del — Deletes entry from list.
@entry: the element to delete from the list.
Note: list_empty on entry does not return true after this, the entry is in an undefined state.

*/ / get the entry node: Static inline void list_del(struct list_head *entry) {__list_del(entry->prev, entry->next); entry->next = (void *) 0; entry->prev = (void *) 0; }

/ * *

List_del_init – Deletes entry from list and reinitialize it.
@entry: the element to delete from the list.

*/ / get the entry node: Static inline void list_del_init(struct list_head *entry) {__list_del(entry->prev, entry->next); INIT_LIST_HEAD(entry); }

/ * *

List_move — delete from one list and add as another’s head
@list: the entry to move
@head: the head that will precede our entry

Static list_head (struct list_head *list, struct list_head *list) struct list_head *head) { __list_del(list->prev, list->next); list_add(list, head); }

/ * *

List_move_tail — delete from one list and add as another’s tail
@list: the entry to move
@head: the head that will follow our entry

Static list_head (struct list_head *list) static list_head (struct list_head *list) struct list_head *head) { __list_del(list->prev, list->next); list_add_tail(list, head); }

/ * *

List_empty – tests whether a list is empty
@head: the list to test.

Static list_empty(struct list_head *head) {return list_head ->next == head; }

// List: 1 2 3 4 5 6 7 // head: 11 22 33 44 // result :head: 1 2 3 4 5 6 7 11 22 33 44 static inline void __list_splice(struct list_head *list, struct list_head *head) { struct list_head *first = list->next; struct list_head *last = list->prev; struct list_head *at = head->next;

first->prev = head;
head->next = first;

last->next = at;
at->prev = last;
Copy the code

}

/ * *

List_splice — join two lists
@list: the new list to add.
@head: the place to add it in the first list.

*/ static inline void list_splice(struct list_head *list, struct list_head *head) { if (! list_empty(list)) __list_splice(list, head); }

/ * *

List_splice_init — join two lists and reinitialise the emptied list.
@list: the new list to add.
@head: the place to add it in the first list.
The list at @list is reinitialised

*/ static inline void list_splice_init(struct list_head *list, struct list_head *head) { if (!list_empty(list)) { __list_splice(list, head); INIT_LIST_HEAD(list); } }

/ * *

List_entry – Get the struct for this entry
@ptr: the &struct list_head pointer.
@type: the type of the struct this is embedded in.
@member: the name of the list_struct within the struct.

*/ / small pointer PTR, large structure type type, small structure inside the large structure member name list // small pointer address, #define list_entry(PTR, type, member) ((type *)((char *)(PTR)-(unsigned long)(&(type *)0)->member))) #define list_entry(PTR, type, member) ((char *)(PTR)->member))

/ * *

list_for_each – iterate over a list
@pos: the &struct list_head to use as a loop counter.
@head: the head for your list.

* /

#define list_for_each(pos, head) for (pos = (head)->next; #define list_for_each(pos, head)->next; pos ! = (head); pos = pos->next)

/ * *

list_for_each_prev – iterate over a list backwards
@pos: the &struct list_head to use as a loop counter.
@head: the head for your list.

#define list_for_each_prev(pos, head) for (pos = (head)->prev; pos ! = (head); pos = pos->prev)

/ * *

list_for_each_safe – iterate over a list safe against removal of list entry
@pos: the &struct list_head to use as a loop counter.
@n: another &struct list_head to use as temporary storage
@head: the head for your list.

*/ // a safe traversal to prevent node deletion in the loop body, #define list_for_each_safe(pos, n, head) for (pos = (head)->next, n = pos->next; pos ! = (head); pos = n, n = pos->next)

/ * *

list_for_each_entry – iterate over list of given type
@pos: the type * to use as a loop counter.
@head: the head for your list.
@member: the name of the list_struct within the struct.

*/ / get a pointer to a large structure: //pos is a large structure pointer variable in traversal, #define list_for_each_entry(pos, head, member) for (pos = list_entry((head)->next, typeof(*pos), member); &pos->member ! = (head); pos = list_entry(pos->member.next, typeof(*pos), member))

/ * *

List_for_each_entry_safe – Iterate over list of given type safe against removal of list entry
@pos: the type * to use as a loop counter.
@n: another type * to use as temporary storage
@head: the head for your list.
@member: the name of the list_struct within the struct.

*/ #define list_for_each_entry_safe(pos, n, head, member) for (pos = list_entry((head)->next, typeof(*pos), member), n = list_entry(pos->member.next, typeof(*pos), member); &pos->member ! = (head); pos = n, n = list_entry(n->member.next, typeof(*n), member))

#endif

Railway management system based on Linux

Please see the link below for the project code (the blogger also made efforts @@)

Simple application of a few small procedures

While learning, you can refer to the comments to understand the code, and the code blogger has run it himself

#include "list.h"
#include <stdio.h>
#include <stdlib.h>

typedef int Datatype;

// Data node structure declaration
typedef struct node// Large structure: store data {
	Datatype data;
	struct list_head list;		// small structure: store precursor pointer and successor pointer
}Node, *Link;

Link init_list(a);
Link create_node(Datatype data);
void display(Link head);
void delete_node(Link head, Datatype data);
Link find_node(Link head, Datatype data);

// Initialize the linked list
Link init_list(a)
{
	// Create a node
	Link head = malloc(sizeof(Node));
	// Create pure linked lists
	if(head ! =NULL)
	{
		INIT_LIST_HEAD(&(head->list));
	}
	return head;
}

// Create a node
Link create_node(Datatype data)
{
	Link new = malloc(sizeof(Node));
	if (new! =NULL)
	{
		new->data = data;
		new->list.prev = NULL;
		new->list.next = NULL;
	}
	return new;
}

/ / traverse
void display(Link head)
{
	Link Node_p = NULL;
	Link N = NULL;
	list_for_each_entry_safe(Node_p, N, &(head->list), list)
	{
		printf("%d ", Node_p->data);
	}
	printf("\n");
}

// Delete a node
void delete_node(Link head, Datatype data)
{
	Link Node_p = NULL;
	Link N = NULL;
	list_for_each_entry_safe(Node_p, N, &(head->list), list)
	{
		if (Node_p->data == data)
		{
			list_del(&(Node_p->list));// Delete a node
			free(Node_p); }}printf("No such object \n");

	// Link Node_p = find_node(head, data);
	// if (Node_p == NULL)
	/ / {
	// printf(" no such object \n");
	// }
	// else
	/ / {
	// list_del(&(Node_p->list)); // Delete a node
	// free(Node_p);
	// }
}

// Find the node
Link find_node(Link head, Datatype data)
{
	Link Node_p = NULL;
	Link N = NULL;
	list_for_each_entry_safe(Node_p, N, &(head->list), list)
	{
		if (Node_p->data == data)
		{
			returnNode_p; }}return NULL;
}

int main(int argc, char const *argv[])
{
	// Initialize an empty linked list
	Link head = init_list();

	// Create node in insert
	int i;
	for (i = 0; i < 5; ++i)
	{	
		Link new = create_node(i+1);	
		list_add_tail(&(new->list), &(head->list));
	}

	/ / traverse
	display(head);

	return 0;
}
Copy the code


```c
#include "list.h"
#include <stdio.h>
#include <stdlib.h>

// Data node structure declaration
struct node// Large structure: store data {
	int data;
	struct list_head list;		// small structure: store precursor pointer and successor pointer
};

int main(int argc, char const *argv[])
{
	// Create a node
	struct node *head = malloc(sizeof(struct node));
	struct node *head1 = malloc(sizeof(struct node));
	// Create pure linked lists
	if(head ! =NULL)
	{
		INIT_LIST_HEAD(&(head->list));
	}
	if(head1 ! =NULL)
	{
		INIT_LIST_HEAD(&(head1->list));
	}
	int i;
	for (i = 0; i < 5; ++i)
	{
		struct node *new = malloc(sizeof(struct node));
		if (new! =NULL)
		{
			new->data = i+1;
			new->list.prev = NULL;
			new->list.next = NULL;
		}
		else
		{
			i--;
			continue;
		}

		// Insert a node into the list
		/ / head
		// list_add(&(new->list), &(head->list));
		/ / end plug
		list_add_tail(&(new->list), &(head->list));
	}

	for (i = 0; i < 5; ++i)
	{
		struct node *new = malloc(sizeof(struct node));
		if (new! =NULL)
		{
			new->data = i+11;
			new->list.prev = NULL;
			new->list.next = NULL;
		}
		else
		{
			i--;
			continue;
		}

		// Insert a node into the list
		/ / head
		// list_add(&(new->list), &(head->list));
		/ / end plug
		list_add_tail(&(new->list), &(head1->list));
	}
	create_node(head,11);

	/ / traverse

	struct list_head *pos = NULL;
	struct list_head *n = NULL;

	struct node *Node_p = NULL;
	struct node *N = NULL;

	/ / the first
	// list_for_each(pos, &(head->list))
	/ / {
	// struct node *p = list_entry(pos, struct node, list);
	// printf("%d ", p->data);
	// }
	// printf("\n");

	/ / the second
	// list_for_each_prev(pos, &(head->list))
	/ / {
	// struct node *p = list_entry(pos, struct node, list);
	// printf("%d ", p->data);
		
	// }
	// printf("\n");

	/ / the third kind
	// list_for_each_safe(pos, n, &(head->list))
	/ / {
	// struct node *p = list_entry(pos, struct node, list);
	// if (p->data == 3)
	// 	{
	// list_del(&(p->list));
	/ /}
	// else
	// printf("%d ", p->data);
	// }
	// printf("\n");

	/ / the fourth
	// list_for_each_entry(Node_p, &(head->list), list)
	/ / {
	// printf("%d ", Node_p->data);
	// }
	// printf("\n");

	/ / 5 kinds
	// list_for_each_entry_safe(Node_p, N, &(head->list), list)
	/ / {
	// if (Node_p->data == 3)
	// 	{
	// // list_del(&(Node_p->list)); // Delete a node
	// // free(Node_p);

	// list_del_init(&(Node_p->list));
	/ /}
	// else
	// printf("%d ", Node_p->data);
	// }
	// printf("\n");

	// Move the node
	struct node *N1 = NULL;
	struct node *N2 = NULL;
	list_for_each_entry_safe(Node_p, N, &(head->list), list)
	{
		if (Node_p->data == 2)
		{
			N1 = Node_p;
		}
		if (Node_p->data == 4)
		{
			N2 = Node_p;
		}
	}

	list_move(&(N1->list), &(N2->list));
	list_move_tail(&(N1->list), &(N2->list));

	list_for_each_entry_safe(Node_p, N, &(head->list), list)
	{
		printf("%d ", Node_p->data);	
	}
	printf("\n");


	// merge linked lists
	list_splice(&(head->list), &(head1->list));

	list_for_each_entry_safe(Node_p, N, &(head1->list), list)
	{
		printf("%d ", Node_p->data);	
	}
	printf("\n");


	return 0;
}
Copy the code

#include "list.h" #include <stdio.h> #include <stdlib.h> typedef int Datatype; Typedef struct node {Datatype data; struct list_head list; }Node, *Link; // initialize the linked list Link init_list() {// Create a Node Link head = malloc(sizeof(Node)); // create a pure linked list if (head! = NULL ) { INIT_LIST_HEAD( &( head->list ) ) ; } return head ; } // create a node Link head = malloc(sizeof(struct node)); // Add data int a to the data field in the large structure; Link new = malloc( sizeof( struct node ) ); if ( new ! = NULL ) { new->data = a ; new->list.prev = NULL ; new->list.next = NULL ; } / / head list_add (& (new - > list), & (head - > list)); // list_add_tail(&(new -> list), &(head -> list)); Link create_node(Datatype data) {Link new = malloc(sizeof(Node)); if ( new ! = NULL ) { new->data = data ; new->list.prev = NULL ; new->list.next = NULL ; } return new ; } void display(Link head) {Link Node_p = NULL; Link N = NULL; list_for_each_entry_safe(Node_p, N, &(head->list), list) { printf("%d ", Node_p->data); } printf("\n"); } void delete_node(Link head, Datatype data) {Link Node_p = NULL; Link N = NULL ; list_for_each_entry_safe(Node_p, N, &(head->list), list) { if ( Node_p->data == data ) { list_del(&(Node_p->list)); // Delete node free(Node_p); }} printf(" no such object \n"); // Link Node_p = find_node(head, data); / / if / / (Node_p = = NULL) {/ / printf (" no the \ n "); // } // else // { // list_del(&(Node_p->list)); // Delete node // free(Node_p); Link find_node(Link head, Datatype data) {Link Node_p = NULL; Link N = NULL; list_for_each_entry_safe( Node_p , N , &( head -> list ) , list ) { if ( Node_p -> data == data ) { return Node_p ; } } return NULL ; } // Link N1 = NULL; Link N2 = NULL ; list_for_each_entry_safe( Node_p , N , &( head -> list ), list ) { if ( Node_p -> data == 2 ) { N1 = Node_p ; } if ( Node_p -> data == 4 ) { N2 = Node_p ; } // list_move(&(N1 -> list), &(N2 -> list)); List_move_tail (&(N1 -> list), &(N2 -> list)); List_splice (&(head -> list), &(head1 -> list)); list_for_each_entry_safe( Node_p , N , &( head1 -> list ) , list ) { printf( "%d", Node_p -> data ) ; } printf("\n"); / / 123456789Copy the code

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Kernel linked lists of data structures

Kernel linked list. H file

Railway management system based on Linux

Simple application of a few small procedures

Kernel linked lists of data structures

Kernel linked list. H file

Railway management system based on Linux

Simple application of a few small procedures

Related Posts

LeetCode high frequency 题 目 : Linked list (2)

Visitor Pattern

With native JS and Node data interface to achieve the avatar upload function

LeetCode high frequency 题目 : Linked list (2)