source: trunk/libtransmission/ptrarray.c @ 13683

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

(trunk, libT) first drop of the tr_quark patch.

  • Property svn:keywords set to Date Rev Author Id
File size: 4.6 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 13683 2012-12-22 20:35:19Z 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
163static void
164assertSortedAndUnique (const tr_ptrArray * t UNUSED,
165                       int compare (const void*, const void*) UNUSED)
166{
167#ifndef NDEBUG
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#endif
173}
174
175int
176tr_ptrArrayInsertSorted (tr_ptrArray * t,
177                         void        * ptr,
178                         int           compare (const void*, const void*))
179{
180  int pos;
181  int ret;
182
183  assertSortedAndUnique (t, compare);
184
185  pos = tr_ptrArrayLowerBound (t, ptr, compare, NULL);
186  ret = tr_ptrArrayInsert (t, ptr, pos);
187
188  assertSortedAndUnique (t, compare);
189  return ret;
190}
191
192void*
193tr_ptrArrayFindSorted (tr_ptrArray * t,
194                       const void  * ptr,
195                       int           compare (const void*, const void*))
196{
197  bool match = false;
198  const int pos = tr_ptrArrayLowerBound (t, ptr, compare, &match);
199  return match ? t->items[pos] : NULL;
200}
201
202void*
203tr_ptrArrayRemoveSorted (tr_ptrArray * t,
204                         const void  * ptr,
205                         int           compare (const void*, const void*))
206{
207  bool match;
208  void * ret = NULL;
209  const int pos = tr_ptrArrayLowerBound (t, ptr, compare, &match);
210
211  assertSortedAndUnique (t, compare);
212
213  if (match)
214    {
215      ret = t->items[pos];
216      assert (compare (ret, ptr) == 0);
217      tr_ptrArrayErase (t, pos, pos + 1);
218    }
219
220  assertSortedAndUnique (t, compare);
221  assert ((ret == NULL) || (compare (ret, ptr) == 0));
222  return ret;
223}
Note: See TracBrowser for help on using the repository browser.