blob: a1cd87d4a369bb1140ef4783139589e629b1702d [file] [log] [blame]
Alexander Afanasyev6b997c52011-08-08 12:55:25 -07001/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
Ilya Moiseenkoc115fba2011-08-01 10:53:18 -07002/*
Alexander Afanasyev6b997c52011-08-08 12:55:25 -07003 * Copyright (c) 2011 University of California, Los Angeles
Ilya Moiseenkoc115fba2011-08-01 10:53:18 -07004 *
Alexander Afanasyev6b997c52011-08-08 12:55:25 -07005 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License version 2 as
7 * published by the Free Software Foundation;
Ilya Moiseenkoc115fba2011-08-01 10:53:18 -07008 *
Alexander Afanasyev6b997c52011-08-08 12:55:25 -07009 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 *
18 * Author: Ilya Moiseenko <iliamo@cs.ucla.edu>
Ilya Moiseenkoc115fba2011-08-01 10:53:18 -070019 */
20
21#include "ccn_indexbuf.h"
22
23/**
24 * @file ccn_indexbuf.c
25 * @brief Support for expandable buffer of non-negative values.
26 *
27 * Part of the CCNx C Library.
28 *
29 * Copyright (C) 2008, 2009 Palo Alto Research Center, Inc.
30 *
31 * This library is free software; you can redistribute it and/or modify it
32 * under the terms of the GNU Lesser General Public License version 2.1
33 * as published by the Free Software Foundation.
34 * This library is distributed in the hope that it will be useful,
35 * but WITHOUT ANY WARRANTY; without even the implied warranty of
36 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
37 * Lesser General Public License for more details. You should have received
38 * a copy of the GNU Lesser General Public License along with this library;
39 * if not, write to the Free Software Foundation, Inc., 51 Franklin Street,
40 * Fifth Floor, Boston, MA 02110-1301 USA.
41 */
42#include <stddef.h>
43#include <stdlib.h>
44#include <string.h>
45
46#define ELEMENT size_t
47
48/**
49 * Create a new indexbuf.
50 */
51struct ccn_indexbuf *
52ccn_indexbuf_create(void)
53{
54 struct ccn_indexbuf *c;
55 c = (ccn_indexbuf*)calloc(1, sizeof(*c));
56 return(c);
57}
58
59/**
60 * Deallocate indexbuf.
61 */
62void
63ccn_indexbuf_destroy(struct ccn_indexbuf **cbp)
64{
65 struct ccn_indexbuf *c = *cbp;
66 if (c != NULL) {
67 if (c->buf != NULL) {
68 free(c->buf);
69 }
70 free(c);
71 *cbp = NULL;
72 }
73}
74
75/**
76 * Expand buffer as necessary to hold at least n more values.
77 * @returns pointer to reserved space
78 */
79ELEMENT *
80ccn_indexbuf_reserve(struct ccn_indexbuf *c, size_t n)
81{
82 size_t newlim = n + c->n;
83 size_t oldlim = c->limit;
84 ELEMENT *buf = c->buf;
85 if (newlim < n)
86 return(NULL);
87 if (newlim > oldlim) {
88 if (2 * oldlim > newlim)
89 newlim = 2 * oldlim;
90 buf = (size_t*)realloc(c->buf, newlim * sizeof(ELEMENT));
91 if (buf == NULL)
92 return(NULL);
93 memset(buf + oldlim, 0, (newlim - oldlim) * sizeof(ELEMENT));
94 c->buf = buf;
95 c->limit = newlim;
96 }
97 buf += c->n;
98 return(buf);
99}
100
101/**
102 * Append multiple elements to the indexbuf.
103 * @returns 0 for success, -1 for failure.
104 */
105int
106ccn_indexbuf_append(struct ccn_indexbuf *c, const ELEMENT *p, size_t n)
107{
108 ELEMENT *dst = ccn_indexbuf_reserve(c, n);
109 if (dst == NULL)
110 return(-1);
111 memcpy(dst, p, n * sizeof(ELEMENT));
112 c->n += n;
113 return(0);
114}
115
116/**
117 * Append v to the indexbuf
118 * @returns 0 for success, -1 for failure.
119 */
120int
121ccn_indexbuf_append_element(struct ccn_indexbuf *c, ELEMENT v)
122{
123 ELEMENT *dst = ccn_indexbuf_reserve(c, 1);
124 if (dst == NULL)
125 return(-1);
126 *dst = v;
127 c->n += 1;
128 return(0);
129}
130
131/**
132 * @returns index at which the element was found or appended, or -1 if not found.
133 */
134int
135ccn_indexbuf_member(struct ccn_indexbuf *x, ELEMENT val)
136{
137 int i;
138 if (x == NULL)
139 return (-1);
140 for (i = x->n - 1; i >= 0; i--)
141 if (x->buf[i] == val)
142 return(i);
143 return(-1);
144}
145
146/**
147 * Removes up to one instance of val from the indexbuf.
148 * Order of elements not preserved.
149 */
150void
151ccn_indexbuf_remove_element(struct ccn_indexbuf *x, ELEMENT val)
152{
153 int i;
154 if (x == NULL) return;
155 for (i = x->n - 1; i >= 0; i--)
156 if (x->buf[i] == val) {
157 x->buf[i] = x->buf[--x->n]; /* move last element into vacant spot */
158 return;
159 }
160}
161
162/**
163 * @returns index at which the element was found or appended,
164 * or -1 in case of error.
165 */
166int
167ccn_indexbuf_set_insert(struct ccn_indexbuf *x, ELEMENT val)
168{
169 int i;
170 if (x == NULL)
171 return (-1);
172 for (i = 0; i < (int)x->n; i++)
173 if (x->buf[i] == val)
174 return(i);
175 if (ccn_indexbuf_append_element(x, val) < 0)
176 return(-1);
177 return(i);
178}
179
180/**
181 * Removes first occurrence of val, preserving order
182 * @returns index at which the element was found,
183 * or -1 if the element was not found.
184 */
185int
186ccn_indexbuf_remove_first_match(struct ccn_indexbuf *x, ELEMENT val)
187{
188 int i;
189 int n;
190 if (x == NULL)
191 return (-1);
192 for (i = 0, n = x->n; i < n; i++) {
193 if (x->buf[i] == val) {
194 if (i + 1 < n)
195 memmove(&(x->buf[i]),
196 &(x->buf[i + 1]),
197 sizeof(x->buf[i]) * (n - i - 1));
198 x->n--;
199 return(i);
200 }
201 }
202 return(-1);
203}
204
205/**
206 * If val is present in the indexbuf, move it to the final place.
207 */
208void
209ccn_indexbuf_move_to_end(struct ccn_indexbuf *x, ELEMENT val)
210{
211 int i;
212 int n;
213 if (x == NULL)
214 return;
215 for (i = 0, n = x->n; i + 1 < n; i++) {
216 if (x->buf[i] == val) {
217 memmove(&(x->buf[i]),
218 &(x->buf[i + 1]),
219 sizeof(x->buf[i]) * (n - i - 1));
220 x->buf[n - 1] = val;
221 return;
222 }
223 }
224}
225
226/**
227 * If val is present in the indexbuf, move it to the first place.
228 */
229void
230ccn_indexbuf_move_to_front(struct ccn_indexbuf *x, ELEMENT val)
231{
232 int i;
233 int n;
234 if (x == NULL)
235 return;
236 for (i = 0, n = x->n; i < n; i++) {
237 if (x->buf[i] == val) {
238 memmove(&(x->buf[1]),
239 &(x->buf[0]),
240 sizeof(x->buf[i]) * i);
241 x->buf[0] = val;
242 return;
243 }
244 }
245
246}
247