blob 9e32b7d9 (10228B) - Raw
1 const std = @import("index.zig"); 2 const debug = std.debug; 3 const assert = debug.assert; 4 const mem = std.mem; 5 const Allocator = mem.Allocator; 6 7 /// Generic non-intrusive doubly linked list. 8 pub fn LinkedList(comptime T: type) type { 9 return BaseLinkedList(T, void, ""); 10 } 11 12 /// Generic intrusive doubly linked list. 13 pub fn IntrusiveLinkedList(comptime ParentType: type, comptime field_name: []const u8) type { 14 return BaseLinkedList(void, ParentType, field_name); 15 } 16 17 /// Generic doubly linked list. 18 fn BaseLinkedList(comptime T: type, comptime ParentType: type, comptime field_name: []const u8) type { 19 return struct { 20 const Self = this; 21 22 /// Node inside the linked list wrapping the actual data. 23 pub const Node = struct { 24 prev: ?*Node, 25 next: ?*Node, 26 data: T, 27 28 pub fn init(value: *const T) Node { 29 return Node{ 30 .prev = null, 31 .next = null, 32 .data = value.*, 33 }; 34 } 35 36 pub fn initIntrusive() Node { 37 // TODO: when #678 is solved this can become `init`. 38 return Node.init({}); 39 } 40 41 pub fn toData(node: *Node) *ParentType { 42 comptime assert(isIntrusive()); 43 return @fieldParentPtr(ParentType, field_name, node); 44 } 45 }; 46 47 first: ?*Node, 48 last: ?*Node, 49 len: usize, 50 51 /// Initialize a linked list. 52 /// 53 /// Returns: 54 /// An empty linked list. 55 pub fn init() Self { 56 return Self{ 57 .first = null, 58 .last = null, 59 .len = 0, 60 }; 61 } 62 63 fn isIntrusive() bool { 64 return ParentType != void or field_name.len != 0; 65 } 66 67 /// Insert a new node after an existing one. 68 /// 69 /// Arguments: 70 /// node: Pointer to a node in the list. 71 /// new_node: Pointer to the new node to insert. 72 pub fn insertAfter(list: *Self, node: *Node, new_node: *Node) void { 73 new_node.prev = node; 74 if (node.next) |next_node| { 75 // Intermediate node. 76 new_node.next = next_node; 77 next_node.prev = new_node; 78 } else { 79 // Last element of the list. 80 new_node.next = null; 81 list.last = new_node; 82 } 83 node.next = new_node; 84 85 list.len += 1; 86 } 87 88 /// Insert a new node before an existing one. 89 /// 90 /// Arguments: 91 /// node: Pointer to a node in the list. 92 /// new_node: Pointer to the new node to insert. 93 pub fn insertBefore(list: *Self, node: *Node, new_node: *Node) void { 94 new_node.next = node; 95 if (node.prev) |prev_node| { 96 // Intermediate node. 97 new_node.prev = prev_node; 98 prev_node.next = new_node; 99 } else { 100 // First element of the list. 101 new_node.prev = null; 102 list.first = new_node; 103 } 104 node.prev = new_node; 105 106 list.len += 1; 107 } 108 109 /// Insert a new node at the end of the list. 110 /// 111 /// Arguments: 112 /// new_node: Pointer to the new node to insert. 113 pub fn append(list: *Self, new_node: *Node) void { 114 if (list.last) |last| { 115 // Insert after last. 116 list.insertAfter(last, new_node); 117 } else { 118 // Empty list. 119 list.prepend(new_node); 120 } 121 } 122 123 /// Insert a new node at the beginning of the list. 124 /// 125 /// Arguments: 126 /// new_node: Pointer to the new node to insert. 127 pub fn prepend(list: *Self, new_node: *Node) void { 128 if (list.first) |first| { 129 // Insert before first. 130 list.insertBefore(first, new_node); 131 } else { 132 // Empty list. 133 list.first = new_node; 134 list.last = new_node; 135 new_node.prev = null; 136 new_node.next = null; 137 138 list.len = 1; 139 } 140 } 141 142 /// Remove a node from the list. 143 /// 144 /// Arguments: 145 /// node: Pointer to the node to be removed. 146 pub fn remove(list: *Self, node: *Node) void { 147 if (node.prev) |prev_node| { 148 // Intermediate node. 149 prev_node.next = node.next; 150 } else { 151 // First element of the list. 152 list.first = node.next; 153 } 154 155 if (node.next) |next_node| { 156 // Intermediate node. 157 next_node.prev = node.prev; 158 } else { 159 // Last element of the list. 160 list.last = node.prev; 161 } 162 163 list.len -= 1; 164 assert(list.len == 0 or (list.first != null and list.last != null)); 165 } 166 167 /// Remove and return the last node in the list. 168 /// 169 /// Returns: 170 /// A pointer to the last node in the list. 171 pub fn pop(list: *Self) ?*Node { 172 const last = list.last orelse return null; 173 list.remove(last); 174 return last; 175 } 176 177 /// Remove and return the first node in the list. 178 /// 179 /// Returns: 180 /// A pointer to the first node in the list. 181 pub fn popFirst(list: *Self) ?*Node { 182 const first = list.first orelse return null; 183 list.remove(first); 184 return first; 185 } 186 187 /// Allocate a new node. 188 /// 189 /// Arguments: 190 /// allocator: Dynamic memory allocator. 191 /// 192 /// Returns: 193 /// A pointer to the new node. 194 pub fn allocateNode(list: *Self, allocator: *Allocator) !*Node { 195 comptime assert(!isIntrusive()); 196 return allocator.create(Node); 197 } 198 199 /// Deallocate a node. 200 /// 201 /// Arguments: 202 /// node: Pointer to the node to deallocate. 203 /// allocator: Dynamic memory allocator. 204 pub fn destroyNode(list: *Self, node: *Node, allocator: *Allocator) void { 205 comptime assert(!isIntrusive()); 206 allocator.destroy(node); 207 } 208 209 /// Allocate and initialize a node and its data. 210 /// 211 /// Arguments: 212 /// data: The data to put inside the node. 213 /// allocator: Dynamic memory allocator. 214 /// 215 /// Returns: 216 /// A pointer to the new node. 217 pub fn createNode(list: *Self, data: *const T, allocator: *Allocator) !*Node { 218 comptime assert(!isIntrusive()); 219 var node = try list.allocateNode(allocator); 220 node.* = Node.init(data); 221 return node; 222 } 223 }; 224 } 225 226 test "basic linked list test" { 227 const allocator = debug.global_allocator; 228 var list = LinkedList(u32).init(); 229 230 var one = try list.createNode(1, allocator); 231 var two = try list.createNode(2, allocator); 232 var three = try list.createNode(3, allocator); 233 var four = try list.createNode(4, allocator); 234 var five = try list.createNode(5, allocator); 235 defer { 236 list.destroyNode(one, allocator); 237 list.destroyNode(two, allocator); 238 list.destroyNode(three, allocator); 239 list.destroyNode(four, allocator); 240 list.destroyNode(five, allocator); 241 } 242 243 list.append(two); // {2} 244 list.append(five); // {2, 5} 245 list.prepend(one); // {1, 2, 5} 246 list.insertBefore(five, four); // {1, 2, 4, 5} 247 list.insertAfter(two, three); // {1, 2, 3, 4, 5} 248 249 // Traverse forwards. 250 { 251 var it = list.first; 252 var index: u32 = 1; 253 while (it) |node| : (it = node.next) { 254 assert(node.data == index); 255 index += 1; 256 } 257 } 258 259 // Traverse backwards. 260 { 261 var it = list.last; 262 var index: u32 = 1; 263 while (it) |node| : (it = node.prev) { 264 assert(node.data == (6 - index)); 265 index += 1; 266 } 267 } 268 269 var first = list.popFirst(); // {2, 3, 4, 5} 270 var last = list.pop(); // {2, 3, 4} 271 list.remove(three); // {2, 4} 272 273 assert(list.first.?.data == 2); 274 assert(list.last.?.data == 4); 275 assert(list.len == 2); 276 } 277 278 const ElementList = IntrusiveLinkedList(Element, "link"); 279 const Element = struct { 280 value: u32, 281 link: IntrusiveLinkedList(Element, "link").Node, 282 }; 283 284 test "basic intrusive linked list test" { 285 const allocator = debug.global_allocator; 286 var list = ElementList.init(); 287 288 var one = Element{ 289 .value = 1, 290 .link = ElementList.Node.initIntrusive(), 291 }; 292 var two = Element{ 293 .value = 2, 294 .link = ElementList.Node.initIntrusive(), 295 }; 296 var three = Element{ 297 .value = 3, 298 .link = ElementList.Node.initIntrusive(), 299 }; 300 var four = Element{ 301 .value = 4, 302 .link = ElementList.Node.initIntrusive(), 303 }; 304 var five = Element{ 305 .value = 5, 306 .link = ElementList.Node.initIntrusive(), 307 }; 308 309 list.append(&two.link); // {2} 310 list.append(&five.link); // {2, 5} 311 list.prepend(&one.link); // {1, 2, 5} 312 list.insertBefore(&five.link, &four.link); // {1, 2, 4, 5} 313 list.insertAfter(&two.link, &three.link); // {1, 2, 3, 4, 5} 314 315 // Traverse forwards. 316 { 317 var it = list.first; 318 var index: u32 = 1; 319 while (it) |node| : (it = node.next) { 320 assert(node.toData().value == index); 321 index += 1; 322 } 323 } 324 325 // Traverse backwards. 326 { 327 var it = list.last; 328 var index: u32 = 1; 329 while (it) |node| : (it = node.prev) { 330 assert(node.toData().value == (6 - index)); 331 index += 1; 332 } 333 } 334 335 var first = list.popFirst(); // {2, 3, 4, 5} 336 var last = list.pop(); // {2, 3, 4} 337 list.remove(&three.link); // {2, 4} 338 339 assert(list.first.?.toData().value == 2); 340 assert(list.last.?.toData().value == 4); 341 assert(list.len == 2); 342 }