source: trunk/libtransmission/ptrarray.c @ 13625

Last change on this file since 13625 was 13625, checked in by jordan, 8 years ago

Follow more common whitespace style conventions in the C code (libtransmission, daemon, utils, cli, gtk).

  • Property svn:keywords set to Date Rev Author Id
File size: 5.0 KB
Line 
1/*
2 * This file Copyright (C) Mnemosyne LLC
3 *
4 * This file is licensed by the GPL version 2. Works owned by the
5 * Transmission project are granted a special exemption to clause 2 (b)
6 * so that the bulk of its code can remain under the MIT license.
7 * This exemption does not extend to derived works not owned by
8 * the Transmission project.
9 *
10 * $Id: ptrarray.c 13625 2012-12-05 17:29:46Z jordan $
11 */
12
13#include <assert.h>
14#include <stdlib.h> /* tr_renew () -> realloc () */
15#include <string.h> /* memmove */
16
17#include "ptrarray.h"
18#include "utils.h"
19
20#define FLOOR 32
21
22const tr_ptrArray TR_PTR_ARRAY_INIT = { NULL, 0, 0 };
23
24void
25tr_ptrArrayDestruct (tr_ptrArray * p, PtrArrayForeachFunc func)
26{
27    assert (p);
28    assert (p->items || !p->n_items);
29
30    if (func)
31        tr_ptrArrayForeach (p, func);
32
33    tr_free (p->items);
34
35    memset (p, ~0, sizeof (tr_ptrArray));
36}
37
38void
39tr_ptrArrayForeach (tr_ptrArray *       t,
40                    PtrArrayForeachFunc func)
41{
42    int i;
43
44    assert (t);
45    assert (t->items || !t->n_items);
46    assert (func);
47
48    for (i = 0; i < t->n_items; ++i)
49        func (t->items[i]);
50}
51
52void**
53tr_ptrArrayPeek (tr_ptrArray * t,
54                 int *         size)
55{
56    *size = t->n_items;
57    return t->items;
58}
59
60int
61tr_ptrArrayInsert (tr_ptrArray * t,
62                   void        * ptr,
63                   int           pos)
64{
65    if (t->n_items >= t->n_alloc)
66    {
67        t->n_alloc = MAX (FLOOR, t->n_alloc * 2);
68        t->items = tr_renew (void*, t->items, t->n_alloc);
69    }
70
71    if (pos < 0 || pos > t->n_items)
72        pos = t->n_items;
73    else
74        memmove (t->items + pos + 1,
75                 t->items + pos,
76                 sizeof (void*) * (t->n_items - pos));
77
78    t->items[pos] = ptr;
79    t->n_items++;
80    return pos;
81}
82
83void*
84tr_ptrArrayPop (tr_ptrArray* t)
85{
86    void * ret = NULL;
87
88    if (t->n_items)
89        ret = t->items[--t->n_items];
90
91    return ret;
92}
93
94void
95tr_ptrArrayErase (tr_ptrArray * t,
96                  int           begin,
97                  int           end)
98{
99    assert (begin >= 0);
100    if (end < 0) end = t->n_items;
101    assert (begin < end);
102    assert (end <= t->n_items);
103
104    memmove (t->items + begin,
105             t->items + end,
106             sizeof (void*) * (t->n_items - end));
107
108    t->n_items -= (end - begin);
109}
110
111/**
112***
113**/
114
115int
116tr_ptrArrayLowerBound (const tr_ptrArray  * t,
117                       const void         * ptr,
118                       int                  compare (const void *, const void *),
119                       bool               * exact_match)
120{
121    int pos = -1;
122    bool match = false;
123
124    if (t->n_items == 0)
125    {
126        pos = 0;
127    }
128    else
129    {
130        int first = 0;
131        int last = t->n_items - 1;
132
133        for (;;)
134        {
135            const int half = (last - first) / 2;
136            const int c = compare (t->items[first + half], ptr);
137
138            if (c < 0) {
139                const int new_first = first + half + 1;
140                if (new_first > last) {
141                    pos = new_first;
142                    break;
143                }
144                first = new_first;
145            }
146            else if (c > 0) {
147                const int new_last = first + half - 1;
148                if (new_last < first) {
149                    pos = first;
150                    break;
151                }
152                last = new_last;
153            }
154            else {
155                match = true;
156                pos = first + half;
157                break;
158            }
159        }
160    }
161
162    if (exact_match)
163        *exact_match = match;
164    return pos;
165}
166
167static void
168assertSortedAndUnique (const tr_ptrArray * t UNUSED,
169                       int compare (const void*, const void*) UNUSED)
170{
171#ifndef NDEBUG
172    int i;
173
174    for (i = 0; i < t->n_items - 2; ++i)
175        assert (compare (t->items[i], t->items[i + 1]) < 0);
176#endif
177}
178
179int
180tr_ptrArrayInsertSorted (tr_ptrArray * t,
181                         void *        ptr,
182                         int           compare (const void*, const void*))
183{
184    int pos;
185    int ret;
186
187    assertSortedAndUnique (t, compare);
188
189    pos = tr_ptrArrayLowerBound (t, ptr, compare, NULL);
190    ret = tr_ptrArrayInsert (t, ptr, pos);
191
192    assertSortedAndUnique (t, compare);
193    return ret;
194}
195
196void*
197tr_ptrArrayFindSorted (tr_ptrArray * t,
198                       const void *  ptr,
199                       int           compare (const void*, const void*))
200{
201    bool match = false;
202    const int pos = tr_ptrArrayLowerBound (t, ptr, compare, &match);
203    return match ? t->items[pos] : NULL;
204}
205
206void*
207tr_ptrArrayRemoveSorted (tr_ptrArray * t,
208                         const void  * ptr,
209                         int           compare (const void*, const void*))
210{
211    bool match;
212    void * ret = NULL;
213    const int pos = tr_ptrArrayLowerBound (t, ptr, compare, &match);
214    assertSortedAndUnique (t, compare);
215
216    if (match)
217    {
218        ret = t->items[pos];
219        assert (compare (ret, ptr) == 0);
220        tr_ptrArrayErase (t, pos, pos + 1);
221    }
222    assertSortedAndUnique (t, compare);
223    assert ((ret == NULL) || (compare (ret, ptr) == 0));
224    return ret;
225}
Note: See TracBrowser for help on using the repository browser.