summaryrefslogtreecommitdiff
path: root/dviware/dvisvgm/libs/ff-woff/inc/dlist.h
blob: eb4fcb9621b27a87371810788c36a56cf6bf57f1 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
/* Copyright (C) 2012 by Ben Martin */
/*
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:

 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.

 * Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.

 * The name of the author may not be used to endorse or promote products
 * derived from this software without specific prior written permission.

 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
 * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
#ifndef _DLIST_H
#define _DLIST_H

/**
 * Doubly linked list abstraction. Putting a full member of this
 * struct first in another struct means you can treat it as a
 * dlinkedlist. You can have a struct in many lists simply by
 * embedding another dlistnode member and handing a pointer to that
 * member to the dlist() helper functions. Double linking has big
 * advantages in removal of single elements where you do not need to
 * rescan to find removeme->prev;
 */
struct dlistnode {
    struct dlistnode* next;
    struct dlistnode* prev;
};

/**
 * DEVELOPERS: make sure the start of this struct is compatible with
 * dlistnode. While I could use the dlistnode as a first member, using
 * a copy of the members in the same order as dlistnode has them
 * allows callers using this struct a bit simpler access.
 * 
 * While one can embed a dlistnode member into a struct to create
 * linked lists, sometimes you want to return a splice of one of those
 * lists. For example, if you have a double linked list of all your
 * hotkeys, you might like to return only the ones that have a
 * modifier of the Control key. You want to leave the hotkey structs
 * in their original list, but create a new kust that references just
 * a desired selection of objects.
 *
 * In other words, if you have some data you want to return in a
 * double linked list, then use this node type. You can build one up
 * using dlist_pushfront_external() and the caller can free that list
 * using dlist_free_external(). Any of the foreach() functions will
 * work to iterate a list of dlistnodeExternal as this list is
 * identical to a dlistnode with an extra ptr payload.
 */
struct dlistnodeExternal {
    struct dlistnode* next;
    struct dlistnode* prev;
    void* ptr;
};


/**
 * Push the node onto the head of the list
 */
extern void dlist_pushfront( struct dlistnode** list, struct dlistnode* node );

/**
 * Take the last node off the list and return it. If the list is empty, return 0.
 */
struct dlistnode* dlist_popback( struct dlistnode** list );

/**
 * the number of nodes in the list
 */
extern int  dlist_size( struct dlistnode** list );

/**
 * is the list empty
 */
extern int  dlist_isempty( struct dlistnode** list );

/**
 * Remove the node from the list. The node itself is not free()ed.
 * That is still up to the caller. All this function does is preserve
 * the list structure without the node being in it.
 */
extern void dlist_erase( struct dlistnode** list, struct dlistnode* node );
typedef void (*dlist_foreach_func_type)( struct dlistnode* );

/**
 * Call func for every node in the list. This is a defensive
 *  implementation, if you want to remove a node from the list inside
 *  func() that is perfectly fine.
 */
extern void dlist_foreach( struct dlistnode** list, dlist_foreach_func_type func );
typedef void (*dlist_foreach_udata_func_type)( struct dlistnode*, void* udata );

/**
 * Like dlist_foreach(), defensive coding still, but the udata pointer
 * is passed back to your visitor function.
 */
extern void dlist_foreach_udata( struct dlistnode** list, dlist_foreach_udata_func_type func, void* udata );

/**
 * Like dlist_foreach_udata() but nodes are visited in reverse order.
 */
extern void dlist_foreach_reverse_udata( struct dlistnode** list, dlist_foreach_udata_func_type func, void* udata );

/**
 * Assuming list is an externalNode list, push a newly allocated list node with
 * a dlistnodeExternal.ptr = ptr passed.
 */
extern void dlist_pushfront_external( struct dlistnode** list, void* ptr );

/**
 * Free a list of externalNode type. The externalNode memory is
 * free()ed, whatever externalNode.ptr is pointing to is not free()ed.
 */
extern void dlist_free_external( struct dlistnode** list );


typedef void (*dlist_visitor_func_type)( struct dlistnode* );

/**
 * To create a list of bounded length, use this function. Limit is the
 * maximum length the list can reach. If list nodes have to be removed
 * to be under this limit then "f" is used as a callback to free list
 * nodes. This allows application specific freeing of a list node, and
 * the ability to maintain a limit on the length of a list as a simple
 * one line call.
 *
 * The current implementation expects you to only be trimming one or
 * two entries at a time. It will still work for trimming 100 entries
 * at a single time, but might not be quite as optimized for that case
 * as it could be.
 */
extern void dlist_trim_to_limit( struct dlistnode** list, int limit, dlist_visitor_func_type f );


#endif // _DLIST_H