diff options
Diffstat (limited to 'contrib/libvcd/salloc.c')
| -rw-r--r-- | contrib/libvcd/salloc.c | 212 |
1 files changed, 212 insertions, 0 deletions
diff --git a/contrib/libvcd/salloc.c b/contrib/libvcd/salloc.c new file mode 100644 index 000000000..d6fc41c68 --- /dev/null +++ b/contrib/libvcd/salloc.c @@ -0,0 +1,212 @@ +/* + $Id: salloc.c,v 1.2 2004/04/11 12:20:32 miguelfreitas Exp $ + + Copyright (C) 2000 Herbert Valerio Riedel <hvr@gnu.org> + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +*/ + +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif + +#include <string.h> +#include <stdlib.h> + +#include <cdio/cdio.h> + +/* Public headers */ +#include <libvcd/types.h> +#include <libvcd/logging.h> + +/* Private headers */ +#include "vcd_assert.h" +#include "salloc.h" +#include "util.h" + +static const char _rcsid[] = "$Id: salloc.c,v 1.2 2004/04/11 12:20:32 miguelfreitas Exp $"; + +#define VCD_SALLOC_CHUNK_SIZE 16 + +struct _VcdSalloc +{ + uint8_t *data; + uint32_t len; + uint32_t alloced_chunks; +}; + +static void +_vcd_salloc_set_size (VcdSalloc *bitmap, uint32_t newlen) +{ + uint32_t new_alloced_chunks; + + vcd_assert (bitmap != NULL); + vcd_assert (newlen >= bitmap->len); + + new_alloced_chunks = newlen / VCD_SALLOC_CHUNK_SIZE; + if (newlen % VCD_SALLOC_CHUNK_SIZE) + new_alloced_chunks++; + + if (bitmap->alloced_chunks < new_alloced_chunks) + { + bitmap->data = + realloc (bitmap->data, new_alloced_chunks * VCD_SALLOC_CHUNK_SIZE); + memset (bitmap->data + (VCD_SALLOC_CHUNK_SIZE * bitmap->alloced_chunks), + 0, + VCD_SALLOC_CHUNK_SIZE * (new_alloced_chunks - + bitmap->alloced_chunks)); + bitmap->alloced_chunks = new_alloced_chunks; + } + + bitmap->len = newlen; +} + +static bool +_vcd_salloc_is_set (const VcdSalloc *bitmap, uint32_t sector) +{ + unsigned _byte = sector / 8; + unsigned _bit = sector % 8; + + if (_byte < bitmap->len) + return (bitmap->data[_byte] & (1 << _bit)) != 0; + else + return false; +} + +static void +_vcd_salloc_set (VcdSalloc *bitmap, uint32_t sector) +{ + unsigned _byte = sector / 8; + unsigned _bit = sector % 8; + + if (_byte >= bitmap->len) + { + unsigned oldlen = bitmap->len; + _vcd_salloc_set_size (bitmap, _byte + 1); + memset (bitmap->data + oldlen, 0x00, _byte + 1 - oldlen); + } + + bitmap->data[_byte] |= (1 << _bit); +} + +static void +_vcd_salloc_unset (VcdSalloc *bitmap, uint32_t sector) +{ + unsigned _byte = sector / 8; + unsigned _bit = sector % 8; + + if (_byte >= bitmap->len) + vcd_assert_not_reached (); + + bitmap->data[_byte] &= ~(1 << _bit); +} + +/* exported */ + +uint32_t _vcd_salloc (VcdSalloc *bitmap, uint32_t hint, uint32_t size) +{ + if (!size) + { + size++; + vcd_warn + ("request of 0 sectors allocment fixed up to 1 sector (this is harmless)"); + } + + vcd_assert (size > 0); + + if (hint != SECTOR_NIL) + { + uint32_t i; + for (i = 0; i < size; i++) + if (_vcd_salloc_is_set (bitmap, hint + i)) + return SECTOR_NIL; + + /* everything's ok for allocing */ + + i = size; + while (i) + _vcd_salloc_set (bitmap, hint + (--i)); + /* we begin with highest byte, in order to minimizing + realloc's in sector_set */ + + return hint; + } + + /* find the lowest possible ... */ + + hint = 0; + + while (_vcd_salloc (bitmap, hint, size) == SECTOR_NIL) + hint++; + + return hint; +} + +void +_vcd_salloc_free (VcdSalloc *bitmap, uint32_t sec, uint32_t size) +{ + uint32_t i; + + for (i = 0; i < size; i++) + { + vcd_assert (_vcd_salloc_is_set (bitmap, sec + i)); + + _vcd_salloc_unset (bitmap, sec + i); + } +} + +VcdSalloc * +_vcd_salloc_new (void) +{ + VcdSalloc *newobj = _vcd_malloc (sizeof (VcdSalloc)); + return newobj; +} + +void +_vcd_salloc_destroy (VcdSalloc *bitmap) +{ + vcd_assert (bitmap != NULL); + + free (bitmap->data); + free (bitmap); +} + +uint32_t _vcd_salloc_get_highest (const VcdSalloc *bitmap) +{ + uint8_t last; + unsigned n; + + vcd_assert (bitmap != NULL); + + last = bitmap->data[bitmap->len - 1]; + + vcd_assert (last != 0); + + n = 8; + while (n) + if ((1 << --n) & last) + break; + + return (bitmap->len - 1) * 8 + n; +} + + +/* + * Local variables: + * c-file-style: "gnu" + * tab-width: 8 + * indent-tabs-mode: nil + * End: + */ |