1/*****************************************************************************
2
3Copyright (c) 2006, 2016, Oracle and/or its affiliates. All Rights Reserved.
4
5This program is free software; you can redistribute it and/or modify it under
6the terms of the GNU General Public License as published by the Free Software
7Foundation; version 2 of the License.
8
9This program is distributed in the hope that it will be useful, but WITHOUT
10ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12
13You should have received a copy of the GNU General Public License along with
14this program; if not, write to the Free Software Foundation, Inc.,
1551 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
16
17*****************************************************************************/
18
19/*******************************************************************//**
20@file ut/ut0list.cc
21A double-linked list
22
23Created 4/26/2006 Osku Salerma
24************************************************************************/
25
26#include "ut0list.h"
27
28/****************************************************************//**
29Create a new list.
30@return list */
31ib_list_t*
32ib_list_create(void)
33/*=================*/
34{
35 return(static_cast<ib_list_t*>(ut_zalloc_nokey(sizeof(ib_list_t))));
36}
37
38/****************************************************************//**
39Free a list. */
40void
41ib_list_free(
42/*=========*/
43 ib_list_t* list) /*!< in: list */
44{
45 /* We don't check that the list is empty because it's entirely valid
46 to e.g. have all the nodes allocated from a single heap that is then
47 freed after the list itself is freed. */
48
49 ut_free(list);
50}
51
52/****************************************************************//**
53Add the data after the indicated node.
54@return new list node */
55static
56ib_list_node_t*
57ib_list_add_after(
58/*==============*/
59 ib_list_t* list, /*!< in: list */
60 ib_list_node_t* prev_node, /*!< in: node preceding new node (can
61 be NULL) */
62 void* data, /*!< in: data */
63 mem_heap_t* heap) /*!< in: memory heap to use */
64{
65 ib_list_node_t* node;
66
67 node = static_cast<ib_list_node_t*>(
68 mem_heap_alloc(heap, sizeof(*node)));
69
70 node->data = data;
71
72 if (!list->first) {
73 /* Empty list. */
74
75 ut_a(!prev_node);
76
77 node->prev = NULL;
78 node->next = NULL;
79
80 list->first = node;
81 list->last = node;
82 } else if (!prev_node) {
83 /* Start of list. */
84
85 node->prev = NULL;
86 node->next = list->first;
87
88 list->first->prev = node;
89
90 list->first = node;
91 } else {
92 /* Middle or end of list. */
93
94 node->prev = prev_node;
95 node->next = prev_node->next;
96
97 prev_node->next = node;
98
99 if (node->next) {
100 node->next->prev = node;
101 } else {
102 list->last = node;
103 }
104 }
105
106 return(node);
107}
108
109/****************************************************************//**
110Add the data to the end of the list.
111@return new list node */
112ib_list_node_t*
113ib_list_add_last(
114/*=============*/
115 ib_list_t* list, /*!< in: list */
116 void* data, /*!< in: data */
117 mem_heap_t* heap) /*!< in: memory heap to use */
118{
119 return(ib_list_add_after(list, ib_list_get_last(list), data, heap));
120}
121
122/****************************************************************//**
123Remove the node from the list. */
124void
125ib_list_remove(
126/*===========*/
127 ib_list_t* list, /*!< in: list */
128 ib_list_node_t* node) /*!< in: node to remove */
129{
130 if (node->prev) {
131 node->prev->next = node->next;
132 } else {
133 /* First item in list. */
134
135 ut_ad(list->first == node);
136
137 list->first = node->next;
138 }
139
140 if (node->next) {
141 node->next->prev = node->prev;
142 } else {
143 /* Last item in list. */
144
145 ut_ad(list->last == node);
146
147 list->last = node->prev;
148 }
149
150 node->prev = node->next = NULL;
151}
152