source: trunk/libtransmission/ptrarray.c @ 14224

Last change on this file since 14224 was 14224, checked in by jordan, 7 years ago

(trunk) restore copyright year as suggested in email by rms

  • Property svn:keywords set to Date Rev Author Id
File size: 5.5 KB
Line 
1/*
2 * This file Copyright (C) 2010-2014 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 14224 2014-01-18 20:56:57Z 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 = TR_PTR_ARRAY_INIT_STATIC;
23
24void
25tr_ptrArrayDestruct (tr_ptrArray * p, PtrArrayForeachFunc func)
26{
27  assert (p != NULL);
28  assert (p->items || !p->n_items);
29
30  if (func)
31    tr_ptrArrayForeach (p, func);
32
33  tr_free (p->items);
34}
35
36void
37tr_ptrArrayForeach (tr_ptrArray * t, PtrArrayForeachFunc func)
38{
39  int i;
40
41  assert (t);
42  assert (t->items || !t->n_items);
43  assert (func);
44
45  for (i=0; i<t->n_items; ++i)
46    func (t->items[i]);
47}
48
49void**
50tr_ptrArrayPeek (tr_ptrArray * t, int * size)
51{
52  *size = t->n_items;
53  return t->items;
54}
55
56int
57tr_ptrArrayInsert (tr_ptrArray * t, void * ptr, int pos)
58{
59  if (t->n_items >= t->n_alloc)
60    {
61      t->n_alloc = MAX (FLOOR, t->n_alloc * 2);
62      t->items = tr_renew (void*, t->items, t->n_alloc);
63    }
64
65  if (pos < 0 || pos > t->n_items)
66    pos = t->n_items;
67  else
68    memmove (t->items+pos+1, t->items+pos, sizeof(void*)*(t->n_items-pos));
69
70  t->items[pos] = ptr;
71  t->n_items++;
72  return pos;
73}
74
75void*
76tr_ptrArrayPop (tr_ptrArray* t)
77{
78  void * ret = NULL;
79
80  if (t->n_items)
81    ret = t->items[--t->n_items];
82
83  return ret;
84}
85
86void
87tr_ptrArrayErase (tr_ptrArray * t, int begin, int end)
88{
89  if (end < 0)
90    end = t->n_items;
91
92  assert (begin >= 0);
93  assert (begin < end);
94  assert (end <= t->n_items);
95
96  memmove (t->items+begin, t->items+end, sizeof(void*)*(t->n_items-end));
97
98  t->n_items -= (end - begin);
99}
100
101/**
102***
103**/
104
105int
106tr_ptrArrayLowerBound (const tr_ptrArray  * t,
107                       const void         * ptr,
108                       int                  compare (const void *, const void *),
109                       bool               * exact_match)
110{
111  int pos = -1;
112  bool match = false;
113
114  if (t->n_items == 0)
115    {
116      pos = 0;
117    }
118  else
119    {
120      int first = 0;
121      int last = t->n_items - 1;
122
123      for (;;)
124        {
125          const int half = (last - first) / 2;
126          const int c = compare (t->items[first + half], ptr);
127
128          if (c < 0)
129            {
130              const int new_first = first + half + 1;
131              if (new_first > last)
132                {
133                  pos = new_first;
134                  break;
135                }
136              first = new_first;
137            }
138          else if (c > 0)
139            {
140              const int new_last = first + half - 1;
141              if (new_last < first)
142                {
143                  pos = first;
144                  break;
145                }
146              last = new_last;
147            }
148          else
149            {
150              match = true;
151              pos = first + half;
152              break;
153            }
154        }
155    }
156
157  if (exact_match != NULL)
158    *exact_match = match;
159
160  return pos;
161}
162
163#ifdef NDEBUG
164#define assertArrayIsSortedAndUnique(array,compare) /* no-op */
165#define assertIndexIsSortedAndUnique(array,pos,compare) /* no-op */
166#else
167
168static void
169assertArrayIsSortedAndUnique (const tr_ptrArray * t,
170                              int compare (const void*, const void*))
171{
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}
177
178static void
179assertIndexIsSortedAndUnique (const tr_ptrArray * t,
180                              int pos,
181                              int compare (const void*, const void*))
182{
183  if (pos > 0)
184    assert (compare (t->items[pos-1], t->items[pos]) < 0);
185
186  if ((pos + 1) < t->n_items)
187    assert (compare (t->items[pos], t->items[pos+1]) < 0);
188}
189
190#endif
191
192int
193tr_ptrArrayInsertSorted (tr_ptrArray * t,
194                         void        * ptr,
195                         int           compare (const void*, const void*))
196{
197  int pos;
198  int ret;
199  assertArrayIsSortedAndUnique (t, compare);
200
201  pos = tr_ptrArrayLowerBound (t, ptr, compare, NULL);
202  ret = tr_ptrArrayInsert (t, ptr, pos);
203
204  assertIndexIsSortedAndUnique (t, ret, compare);
205  return ret;
206}
207
208void*
209tr_ptrArrayFindSorted (tr_ptrArray * t,
210                       const void  * ptr,
211                       int           compare (const void*, const void*))
212{
213  bool match = false;
214  const int pos = tr_ptrArrayLowerBound (t, ptr, compare, &match);
215  return match ? t->items[pos] : NULL;
216}
217
218static void*
219tr_ptrArrayRemoveSortedValue (tr_ptrArray * t,
220                              const void  * ptr,
221                              int           compare (const void*, const void*))
222{
223  int pos;
224  bool match;
225  void * ret = NULL;
226
227  assertArrayIsSortedAndUnique (t, compare);
228
229  pos = tr_ptrArrayLowerBound (t, ptr, compare, &match);
230
231  if (match)
232    {
233      ret = t->items[pos];
234      assert (compare (ret, ptr) == 0);
235      tr_ptrArrayErase (t, pos, pos + 1);
236    }
237
238  assert ((ret == NULL) || (compare (ret, ptr) == 0));
239  return ret;
240}
241
242void
243tr_ptrArrayRemoveSortedPointer (tr_ptrArray * t,
244                                const void  * ptr,
245                                int           compare (const void*, const void*))
246{
247#ifdef NDEBUG
248  tr_ptrArrayRemoveSortedValue (t, ptr, compare);
249#else
250  void * removed = tr_ptrArrayRemoveSortedValue (t, ptr, compare);
251  assert (removed != NULL);
252  assert (removed == ptr);
253  assert (tr_ptrArrayFindSorted (t, ptr, compare) == NULL);
254#endif
255}
Note: See TracBrowser for help on using the repository browser.