source: trunk/libtransmission/ptrarray.c

Last change on this file was 14592, checked in by mikedld, 5 years ago

Use tr_realloc (BSD reallocf-alike) instead of plain realloc

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