1 /*
2  * list.h
3  * Copyright 2014 John Lindgren
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  *
8  * 1. Redistributions of source code must retain the above copyright notice,
9  *    this list of conditions, and the following disclaimer.
10  *
11  * 2. Redistributions in binary form must reproduce the above copyright notice,
12  *    this list of conditions, and the following disclaimer in the documentation
13  *    provided with the distribution.
14  *
15  * This software is provided "as is" and without any warranty, express or
16  * implied. In no event shall the authors be liable for any damages arising from
17  * the use of this software.
18  */
19 
20 #ifndef LIBAUDCORE_LIST_H
21 #define LIBAUDCORE_LIST_H
22 
23 struct ListNode
24 {
25     friend class ListBase;
26 
27 private:
28     ListNode * prev = nullptr;
29     ListNode * next = nullptr;
30 };
31 
32 class ListBase
33 {
34 protected:
35     typedef void (*DestroyFunc)(ListNode *);
36 
37     ListNode * head = nullptr;
38     ListNode * tail = nullptr;
39 
40     void insert_after(ListNode * prev, ListNode * node);
41     void remove(ListNode * node);
42     void clear(DestroyFunc destroy);
43 
prev(ListNode * node)44     static ListNode * prev(ListNode * node) { return node->prev; }
next(ListNode * node)45     static ListNode * next(ListNode * node) { return node->next; }
46 };
47 
48 template<class C>
49 class List : private ListBase
50 {
51 public:
head()52     C * head() const { return (C *)ListBase::head; }
tail()53     C * tail() const { return (C *)ListBase::tail; }
54 
prev(C * node)55     static C * prev(C * node) { return (C *)ListBase::prev(node); }
next(C * node)56     static C * next(C * node) { return (C *)ListBase::next(node); }
57 
insert_after(C * prev,C * node)58     void insert_after(C * prev, C * node)
59     {
60         ListBase::insert_after(prev, node);
61     }
remove(C * node)62     void remove(C * node) { ListBase::remove(node); }
63 
prepend(C * node)64     void prepend(C * node) { insert_after(nullptr, node); }
append(C * node)65     void append(C * node) { insert_after(tail(), node); }
66 
clear()67     void clear() { ListBase::clear(destroy); }
68 
pop_head()69     C * pop_head()
70     {
71         C * node = head();
72         if (node)
73             remove(node);
74         return node;
75     }
76 
77     template<class MatchFunc>
find(MatchFunc match)78     C * find(MatchFunc match)
79     {
80         for (C * node = head(); node; node = next(node))
81         {
82             if (match(*node))
83                 return node;
84         }
85 
86         return nullptr;
87     }
88 
89 private:
destroy(ListNode * node)90     static void destroy(ListNode * node) { delete (C *)node; }
91 };
92 
93 #endif // LIBAUDCORE_LIST_H
94