haskell-igraph-0.8.0: igraph/src/vector_ptr.c
/* -*- mode: C -*- */
/*
IGraph library.
Copyright (C) 2003-2012 Gabor Csardi <csardi.gabor@gmail.com>
334 Harvard street, Cambridge, MA 02139 USA
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., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA
*/
#include "igraph_types.h"
#include "igraph_vector_ptr.h"
#include "igraph_memory.h"
#include "igraph_random.h"
#include "igraph_error.h"
#include "config.h"
#include <assert.h>
#include <string.h> /* memcpy & co. */
#include <stdlib.h>
/**
* \section about_igraph_vector_ptr_objects Pointer vectors
* (<type>igraph_vector_ptr_t</type>)
*
* <para>The \type igraph_vector_ptr_t data type is very similar to
* the \type igraph_vector_t type, but it stores generic pointers instead of
* real numbers.</para>
*
* <para>This type has the same space complexity as \type
* igraph_vector_t, and most implemented operations work the same way
* as for \type igraph_vector_t. </para>
*
* <para>This type is mostly used to pass to or receive from a set of
* graphs to some \a igraph functions, such as \ref
* igraph_decompose(), which decomposes a graph to connected
* components.</para>
*
* <para>The same \ref VECTOR macro used for ordinary vectors can be
* used for pointer vectors as well, please note that a typeless
* generic pointer will be provided by this macro and you may need to
* cast it to a specific pointer before starting to work with it.</para>
*
* <para>Pointer vectors may have an associated item destructor function
* which takes a pointer and returns nothing. The item destructor will
* be called on each item in the pointer vector when it is destroyed by
* \ref igraph_vector_ptr_destroy() or \ref igraph_vector_ptr_destroy_all(),
* or when its elements are freed by \ref igraph_vector_ptr_free_all().
* Note that the semantics of an item destructor does not coincide with
* C++ destructors; for instance, when a pointer vector is resized to a
* smaller size, the extra items will \em not be destroyed automatically!
* Nevertheless, item destructors may become handy in many cases; for
* instance, a vector of graphs generated by \ref igraph_decompose() can
* be destroyed with a single call to \ref igraph_vector_ptr_destroy_all()
* if the item destructor is set to \ref igraph_destroy().</para>
*/
/**
* \ingroup vectorptr
* \function igraph_vector_ptr_init
* \brief Initialize a pointer vector (constructor).
*
* </para><para>
* This is the constructor of the pointer vector data type. All
* pointer vectors constructed this way should be destroyed via
* calling \ref igraph_vector_ptr_destroy().
* \param v Pointer to an uninitialized
* <type>igraph_vector_ptr_t</type> object, to be created.
* \param size Integer, the size of the pointer vector.
* \return Error code:
* \c IGRAPH_ENOMEM if out of memory
*
* Time complexity: operating system dependent, the amount of \quote
* time \endquote required to allocate \p size elements.
*/
int igraph_vector_ptr_init (igraph_vector_ptr_t* v, int long size) {
long int alloc_size = size > 0 ? size : 1;
assert(v != NULL);
if (size < 0) {
size = 0;
}
v->stor_begin = igraph_Calloc(alloc_size, void*);
if (v->stor_begin == 0) {
IGRAPH_ERROR("vector ptr init failed", IGRAPH_ENOMEM);
}
v->stor_end = v->stor_begin + alloc_size;
v->end = v->stor_begin + size;
v->item_destructor = 0;
return 0;
}
/**
*/
const igraph_vector_ptr_t *igraph_vector_ptr_view (const igraph_vector_ptr_t *v, void *const *data,
long int length) {
igraph_vector_ptr_t *v2 = (igraph_vector_ptr_t*) v;
v2->stor_begin = (void **)data;
v2->stor_end = (void**)data + length;
v2->end = v2->stor_end;
v2->item_destructor = 0;
return v;
}
/**
* \ingroup vectorptr
* \function igraph_vector_ptr_destroy
* \brief Destroys a pointer vector.
*
* </para><para>
* The destructor for pointer vectors.
* \param v Pointer to the pointer vector to destroy.
*
* Time complexity: operating system dependent, the \quote time
* \endquote required to deallocate O(n) bytes, n is the number of
* elements allocated for the pointer vector (not necessarily the
* number of elements in the vector).
*/
void igraph_vector_ptr_destroy (igraph_vector_ptr_t* v) {
assert(v != 0);
if (v->stor_begin != 0) {
igraph_Free(v->stor_begin);
v->stor_begin = NULL;
}
}
void igraph_i_vector_ptr_call_item_destructor_all(igraph_vector_ptr_t* v) {
void **ptr;
if (v->item_destructor != 0) {
for (ptr = v->stor_begin; ptr < v->end; ptr++) {
if (*ptr != 0) {
v->item_destructor(*ptr);
}
}
}
}
/**
* \ingroup vectorptr
* \function igraph_vector_ptr_free_all
* \brief Frees all the elements of a pointer vector.
*
* If an item destructor is set for this pointer vector, this function will
* first call the destructor on all elements of the vector and then
* free all the elements using free(). If an item destructor is not set,
* the elements will simply be freed.
*
* \param v Pointer to the pointer vector whose elements will be freed.
*
* Time complexity: operating system dependent, the \quote time
* \endquote required to call the destructor n times and then
* deallocate O(n) pointers, each pointing to a memory area of
* arbitrary size. n is the number of elements in the pointer vector.
*/
void igraph_vector_ptr_free_all (igraph_vector_ptr_t* v) {
void **ptr;
assert(v != 0);
assert(v->stor_begin != 0);
igraph_i_vector_ptr_call_item_destructor_all(v);
for (ptr = v->stor_begin; ptr < v->end; ptr++) {
igraph_Free(*ptr);
}
}
/**
* \ingroup vectorptr
* \function igraph_vector_ptr_destroy_all
* \brief Frees all the elements and destroys the pointer vector.
*
* This function is equivalent to \ref igraph_vector_ptr_free_all()
* followed by \ref igraph_vector_ptr_destroy().
*
* \param v Pointer to the pointer vector to destroy.
*
* Time complexity: operating system dependent, the \quote time
* \endquote required to deallocate O(n) pointers, each pointing to
* a memory area of arbitrary size, plus the \quote time \endquote
* required to deallocate O(n) bytes, n being the number of elements
* allocated for the pointer vector (not necessarily the number of
* elements in the vector).
*/
void igraph_vector_ptr_destroy_all (igraph_vector_ptr_t* v) {
assert(v != 0);
assert(v->stor_begin != 0);
igraph_vector_ptr_free_all(v);
igraph_vector_ptr_set_item_destructor(v, 0);
igraph_vector_ptr_destroy(v);
}
/**
* \ingroup vectorptr
* \brief Reserves memory for a pointer vector for later use.
*
* @return Error code:
* - <b>IGRAPH_ENOMEM</b>: out of memory
*/
int igraph_vector_ptr_reserve (igraph_vector_ptr_t* v, long int size) {
long int actual_size = igraph_vector_ptr_size(v);
void **tmp;
assert(v != NULL);
assert(v->stor_begin != NULL);
if (size <= igraph_vector_ptr_size(v)) {
return 0;
}
tmp = igraph_Realloc(v->stor_begin, (size_t) size, void*);
if (tmp == 0) {
IGRAPH_ERROR("vector ptr reserve failed", IGRAPH_ENOMEM);
}
v->stor_begin = tmp;
v->stor_end = v->stor_begin + size;
v->end = v->stor_begin + actual_size;
return 0;
}
/**
* \ingroup vectorptr
* \brief Decides whether the pointer vector is empty.
*/
igraph_bool_t igraph_vector_ptr_empty (const igraph_vector_ptr_t* v) {
assert(v != NULL);
assert(v->stor_begin != NULL);
return v->stor_begin == v->end;
}
/**
* \ingroup vectorptr
* \function igraph_vector_ptr_size
* \brief Gives the number of elements in the pointer vector.
*
* \param v The pointer vector object.
* \return The size of the object, ie. the number of pointers stored.
*
* Time complexity: O(1).
*/
long int igraph_vector_ptr_size (const igraph_vector_ptr_t* v) {
assert(v != NULL);
/* assert(v->stor_begin != NULL); */ /* TODO */
return v->end - v->stor_begin;
}
/**
* \ingroup vectorptr
* \function igraph_vector_ptr_clear
* \brief Removes all elements from a pointer vector.
*
* </para><para>
* This function resizes a pointer to vector to zero length. Note that
* the pointed objects are \em not deallocated, you should call
* free() on them, or make sure that their allocated memory is freed
* in some other way, you'll get memory leaks otherwise. If you have
* set up an item destructor earlier, the destructor will be called
* on every element.
*
* </para><para>
* Note that the current implementation of this function does
* \em not deallocate the memory required for storing the
* pointers, so making a pointer vector smaller this way does not give
* back any memory. This behavior might change in the future.
* \param v The pointer vector to clear.
*
* Time complexity: O(1).
*/
void igraph_vector_ptr_clear (igraph_vector_ptr_t* v) {
assert(v != NULL);
assert(v->stor_begin != NULL);
igraph_i_vector_ptr_call_item_destructor_all(v);
v->end = v->stor_begin;
}
/**
* \ingroup vectorptr
* \function igraph_vector_ptr_push_back
* \brief Appends an element to the back of a pointer vector.
*
* \param v The pointer vector.
* \param e The new element to include in the pointer vector.
* \return Error code.
* \sa igraph_vector_push_back() for the corresponding operation of
* the ordinary vector type.
*
* Time complexity: O(1) or O(n), n is the number of elements in the
* vector. The pointer vector implementation ensures that n subsequent
* push_back operations need O(n) time to complete.
*/
int igraph_vector_ptr_push_back (igraph_vector_ptr_t* v, void* e) {
assert(v != NULL);
assert(v->stor_begin != NULL);
/* full, allocate more storage */
if (v->stor_end == v->end) {
long int new_size = igraph_vector_ptr_size(v) * 2;
if (new_size == 0) {
new_size = 1;
}
IGRAPH_CHECK(igraph_vector_ptr_reserve(v, new_size));
}
*(v->end) = e;
v->end += 1;
return 0;
}
void *igraph_vector_ptr_pop_back (igraph_vector_ptr_t *v) {
assert(v != NULL);
assert(v->stor_begin != NULL);
assert(v->stor_begin != v->end);
v->end -= 1;
return *(v->end);
}
/**
* \ingroup vectorptr
* \function igraph_vector_ptr_insert
* \brief Inserts a single element into a pointer vector.
*
* Note that this function does not do range checking. Insertion will shift the
* elements from the position given to the end of the vector one position to the
* right, and the new element will be inserted in the empty space created at
* the given position. The size of the vector will increase by one.
*
* \param v The pointer vector object.
* \param pos The position where the new element is inserted.
* \param e The inserted element
*/
int igraph_vector_ptr_insert(igraph_vector_ptr_t* v, long int pos, void* e) {
long int size = igraph_vector_ptr_size(v);
IGRAPH_CHECK(igraph_vector_ptr_resize(v, size + 1));
if (pos < size) {
memmove(v->stor_begin + pos + 1, v->stor_begin + pos,
sizeof(void*) * (size_t) (size - pos));
}
v->stor_begin[pos] = e;
return 0;
}
/**
* \ingroup vectorptr
* \function igraph_vector_ptr_e
* \brief Access an element of a pointer vector.
*
* \param v Pointer to a pointer vector.
* \param pos The index of the pointer to return.
* \return The pointer at \p pos position.
*
* Time complexity: O(1).
*/
void* igraph_vector_ptr_e (const igraph_vector_ptr_t* v, long int pos) {
assert(v != NULL);
assert(v->stor_begin != NULL);
return * (v->stor_begin + pos);
}
/**
* \ingroup vectorptr
* \function igraph_vector_ptr_set
* \brief Assign to an element of a pointer vector.
*
* \param v Pointer to a pointer vector.
* \param pos The index of the pointer to update.
* \param value The new pointer to set in the vector.
*
* Time complexity: O(1).
*/
void igraph_vector_ptr_set (igraph_vector_ptr_t* v, long int pos, void* value) {
assert(v != NULL);
assert(v->stor_begin != NULL);
*(v->stor_begin + pos) = value;
}
/**
* \ingroup vectorptr
* \brief Set all elements of a pointer vector to the NULL pointer.
*/
void igraph_vector_ptr_null (igraph_vector_ptr_t* v) {
assert(v != NULL);
assert(v->stor_begin != NULL);
if (igraph_vector_ptr_size(v) > 0) {
memset(v->stor_begin, 0, sizeof(void*) *
(size_t) igraph_vector_ptr_size(v));
}
}
/**
* \ingroup vectorptr
* \function igraph_vector_ptr_resize
* \brief Resizes a pointer vector.
*
* </para><para>
* Note that if a vector is made smaller the pointed object are not
* deallocated by this function and the item destructor is not called
* on the extra elements.
*
* \param v A pointer vector.
* \param newsize The new size of the pointer vector.
* \return Error code.
*
* Time complexity: O(1) if the vector if made smaller. Operating
* system dependent otherwise, the amount of \quote time \endquote
* needed to allocate the memory for the vector elements.
*/
int igraph_vector_ptr_resize(igraph_vector_ptr_t* v, long int newsize) {
IGRAPH_CHECK(igraph_vector_ptr_reserve(v, newsize));
v->end = v->stor_begin + newsize;
return 0;
}
/**
* \ingroup vectorptr
* \brief Initializes a pointer vector from an array (constructor).
*
* \return Error code:
* \c IGRAPH_ENOMEM if out of memory
*/
int igraph_vector_ptr_init_copy(igraph_vector_ptr_t *v, void * *data, long int length) {
v->stor_begin = igraph_Calloc(length, void*);
if (v->stor_begin == 0) {
IGRAPH_ERROR("cannot init ptr vector from array", IGRAPH_ENOMEM);
}
v->stor_end = v->stor_begin + length;
v->end = v->stor_end;
v->item_destructor = 0;
memcpy(v->stor_begin, data, (size_t) length * sizeof(void*));
return 0;
}
/**
* \ingroup vectorptr
* \brief Copy the contents of a pointer vector to a regular C array.
*/
void igraph_vector_ptr_copy_to(const igraph_vector_ptr_t *v, void** to) {
assert(v != NULL);
assert(v->stor_begin != NULL);
if (v->end != v->stor_begin) {
memcpy(to, v->stor_begin, sizeof(void*) *
(size_t) (v->end - v->stor_begin));
}
}
/**
* \ingroup vectorptr
* \function igraph_vector_ptr_copy
* \brief Copy a pointer vector (constructor).
*
* </para><para>
* This function creates a pointer vector by copying another one. This
* is shallow copy, only the pointers in the vector will be copied.
*
* </para><para>
* It is potentially dangerous to copy a pointer vector with an associated
* item destructor. The copied vector will inherit the item destructor,
* which may cause problems when both vectors are destroyed as the items
* might get destroyed twice. Make sure you know what you are doing when
* copying a pointer vector with an item destructor, or unset the item
* destructor on one of the vectors later.
*
* \param to Pointer to an uninitialized pointer vector object.
* \param from A pointer vector object.
* \return Error code:
* \c IGRAPH_ENOMEM if out of memory
*
* Time complexity: O(n) if allocating memory for n elements can be
* done in O(n) time.
*/
int igraph_vector_ptr_copy(igraph_vector_ptr_t *to, const igraph_vector_ptr_t *from) {
assert(from != NULL);
/* assert(from->stor_begin != NULL); */ /* TODO */
to->stor_begin = igraph_Calloc(igraph_vector_ptr_size(from), void*);
if (to->stor_begin == 0) {
IGRAPH_ERROR("cannot copy ptr vector", IGRAPH_ENOMEM);
}
to->stor_end = to->stor_begin + igraph_vector_ptr_size(from);
to->end = to->stor_end;
to->item_destructor = from->item_destructor;
memcpy(to->stor_begin, from->stor_begin,
(size_t) igraph_vector_ptr_size(from)*sizeof(void*));
return 0;
}
/**
* \ingroup vectorptr
* \brief Remove an element from a pointer vector.
*/
void igraph_vector_ptr_remove(igraph_vector_ptr_t *v, long int pos) {
assert(v != NULL);
assert(v->stor_begin != NULL);
if (pos + 1 < igraph_vector_ptr_size(v)) { /* TOOD: why is this needed */
memmove(v->stor_begin + pos, v->stor_begin + pos + 1,
sizeof(void*) * (size_t) (igraph_vector_ptr_size(v) - pos - 1));
}
v->end--;
}
/**
* \ingroup vectorptr
* \brief Sort the pointer vector based on an external comparison function
*
* Sometimes it is necessary to sort the pointers in the vector based on
* the property of the element being referenced by the pointer. This
* function allows us to sort the vector based on an arbitrary external
* comparison function which accepts two \c void* pointers \c p1 and \c p2
* and returns an integer less than, equal to or greater than zero if the
* first argument is considered to be respectively less than, equal to, or
* greater than the second. \c p1 and \c p2 will point to the pointer in the
* vector, so they have to be double-dereferenced if one wants to get access
* to the underlying object the address of which is stored in \c v .
*/
void igraph_vector_ptr_sort(igraph_vector_ptr_t *v, int (*compar)(const void*, const void*)) {
qsort(v->stor_begin, (size_t) igraph_vector_ptr_size(v), sizeof(void*),
compar);
}
int igraph_vector_ptr_index_int(igraph_vector_ptr_t *v,
const igraph_vector_int_t *idx) {
void **tmp;
int i, n = igraph_vector_int_size(idx);
tmp = igraph_Calloc(n, void*);
if (!tmp) {
IGRAPH_ERROR("Cannot index pointer vector", IGRAPH_ENOMEM);
}
for (i = 0; i < n; i++) {
tmp[i] = VECTOR(*v)[ VECTOR(*idx)[i] ];
}
igraph_Free(v->stor_begin);
v->stor_begin = tmp;
v->stor_end = v->end = tmp + n;
return 0;
}
int igraph_vector_ptr_append (igraph_vector_ptr_t *to,
const igraph_vector_ptr_t *from) {
long int origsize = igraph_vector_ptr_size(to);
long int othersize = igraph_vector_ptr_size(from);
long int i;
IGRAPH_CHECK(igraph_vector_ptr_resize(to, origsize + othersize));
for (i = 0; i < othersize; i++, origsize++) {
to->stor_begin[origsize] = from->stor_begin[i];
}
return 0;
}
/**
* \ingroup vectorptr
* \function igraph_vector_ptr_set_item_destructor
* \brief Sets the item destructor for this pointer vector.
*
* The item destructor is a function which will be called on every non-null
* pointer stored in this vector when \ref igraph_vector_ptr_destroy(),
* igraph_vector_ptr_destroy_all() or \ref igraph_vector_ptr_free_all()
* is called.
*
* \return The old item destructor.
*
* Time complexity: O(1).
*/
igraph_finally_func_t* igraph_vector_ptr_set_item_destructor(
igraph_vector_ptr_t *v, igraph_finally_func_t *func) {
igraph_finally_func_t* result = v->item_destructor;
v->item_destructor = func;
return result;
}
/**
* \ingroup vectorptr
* \function igraph_vector_ptr_get_item_destructor
* \brief Gets the current item destructor for this pointer vector.
*
* The item destructor is a function which will be called on every non-null
* pointer stored in this vector when \ref igraph_vector_ptr_destroy(),
* igraph_vector_ptr_destroy_all() or \ref igraph_vector_ptr_free_all()
* is called.
*
* \return The current item destructor.
*
* Time complexity: O(1).
*/
igraph_finally_func_t* igraph_vector_ptr_get_item_destructor(const igraph_vector_ptr_t *v) {
assert(v != 0);
return v->item_destructor;
}