196904Sgrog/*- 296904Sgrog * Copyright (c) 2009 The NetBSD Foundation, Inc. 396904Sgrog * All rights reserved. 496904Sgrog * 596904Sgrog * This code is derived from software contributed to The NetBSD Foundation 696904Sgrog * by David A. Holland. 796904Sgrog * 896904Sgrog * Redistribution and use in source and binary forms, with or without 996904Sgrog * modification, are permitted provided that the following conditions 1096904Sgrog * are met: 1196904Sgrog * 1. Redistributions of source code must retain the above copyright 1296904Sgrog * notice, this list of conditions and the following disclaimer. 1396904Sgrog * 2. Redistributions in binary form must reproduce the above copyright 1496904Sgrog * notice, this list of conditions and the following disclaimer in the 1596904Sgrog * documentation and/or other materials provided with the distribution. 1696904Sgrog * 1796904Sgrog * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 1896904Sgrog * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 1996904Sgrog * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 2096904Sgrog * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 2196904Sgrog * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 2296904Sgrog * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 2396904Sgrog * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 2496904Sgrog * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 2596904Sgrog * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 2696904Sgrog * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 2796904Sgrog * POSSIBILITY OF SUCH DAMAGE. 2896904Sgrog */ 2996904Sgrog 3096904Sgrog#include <stdlib.h> 3196904Sgrog#include <string.h> 3296904Sgrog 3396904Sgrog#define ARRAYINLINE 3496904Sgrog#include "array.h" 3596904Sgrog 3696904Sgrogstruct array * 3796895Sgrogarray_create(void) 3896895Sgrog{ 3996895Sgrog struct array *a; 4096895Sgrog 4196895Sgrog a = domalloc(sizeof(*a)); 4296895Sgrog array_init(a); 4396895Sgrog return a; 4496895Sgrog} 4596895Sgrog 4696895Sgrogvoid 4796895Sgrogarray_destroy(struct array *a) 4896895Sgrog{ 4996895Sgrog array_cleanup(a); 5096895Sgrog dofree(a, sizeof(*a)); 5196895Sgrog} 5296895Sgrog 5396895Sgrogvoid 5496895Sgrogarray_init(struct array *a) 5596895Sgrog{ 5696895Sgrog a->num = a->max = 0; 5796895Sgrog a->v = NULL; 5896895Sgrog} 5996895Sgrog 6096895Sgrogvoid 6196895Sgrogarray_cleanup(struct array *a) 6296895Sgrog{ 6396895Sgrog arrayassert(a->num == 0); 6496895Sgrog dofree(a->v, a->max * sizeof(a->v[0])); 6596895Sgrog#ifdef ARRAYS_CHECKED 6696895Sgrog a->v = NULL; 6796895Sgrog#endif 6896895Sgrog} 6996895Sgrog 7096895Sgrogvoid 7196895Sgrogarray_setsize(struct array *a, unsigned num) 7296895Sgrog{ 7396895Sgrog unsigned newmax; 7496895Sgrog void **newptr; 7596895Sgrog 7696895Sgrog if (num > a->max) { 7796895Sgrog newmax = a->max; 7896895Sgrog while (num > newmax) { 7996895Sgrog newmax = newmax ? newmax*2 : 4; 8096895Sgrog } 8196895Sgrog newptr = dorealloc(a->v, a->max * sizeof(a->v[0]), 8296895Sgrog newmax * sizeof(a->v[0])); 8396895Sgrog a->v = newptr; 8496895Sgrog a->max = newmax; 8596895Sgrog } 8696895Sgrog a->num = num; 8796895Sgrog} 8896895Sgrog 8996895Sgrogvoid 9096895Sgrogarray_insert(struct array *a, unsigned index_) 9196895Sgrog{ 9296895Sgrog unsigned movers; 9396895Sgrog 9496895Sgrog arrayassert(a->num <= a->max); 9596895Sgrog arrayassert(index_ < a->num); 9696895Sgrog 9796895Sgrog movers = a->num - index_; 9896895Sgrog 9996895Sgrog array_setsize(a, a->num + 1); 10096895Sgrog 10196895Sgrog memmove(a->v + index_+1, a->v + index_, movers*sizeof(*a->v)); 10296895Sgrog} 10396895Sgrog 10496895Sgrogvoid 10596895Sgrogarray_remove(struct array *a, unsigned index_) 10696895Sgrog{ 10796895Sgrog unsigned movers; 10896895Sgrog 10996895Sgrog arrayassert(a->num <= a->max); 11096895Sgrog arrayassert(index_ < a->num); 11196895Sgrog 11296895Sgrog movers = a->num - (index_ + 1); 11396895Sgrog memmove(a->v + index_, a->v + index_+1, movers*sizeof(*a->v)); 11496895Sgrog a->num--; 11596895Sgrog} 11696895Sgrog