haskell-igraph-0.8.0: igraph/src/igraph_strvector.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_strvector.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 igraph_strvector_t
* <para>The <type>igraph_strvector_t</type> type is a vector of strings.
* The current implementation is very simple and not too efficient. It
* works fine for not too many strings, e.g. the list of attribute
* names is returned in a string vector by \ref
* igraph_cattribute_list(). Do not expect great performance from this
* type.</para>
*
* <para>
* \example examples/simple/igraph_strvector.c
* </para>
*/
/**
* \ingroup strvector
* \function igraph_strvector_init
* \brief Initialize
*
* Reserves memory for the string vector, a string vector must be
* first initialized before calling other functions on it.
* All elements of the string vector are set to the empty string.
* \param sv Pointer to an initialized string vector.
* \param len The (initial) length of the string vector.
* \return Error code.
*
* Time complexity: O(\p len).
*/
int igraph_strvector_init(igraph_strvector_t *sv, long int len) {
long int i;
sv->data = igraph_Calloc(len, char*);
if (sv->data == 0) {
IGRAPH_ERROR("strvector init failed", IGRAPH_ENOMEM);
}
for (i = 0; i < len; i++) {
sv->data[i] = igraph_Calloc(1, char);
if (sv->data[i] == 0) {
igraph_strvector_destroy(sv);
IGRAPH_ERROR("strvector init failed", IGRAPH_ENOMEM);
}
sv->data[i][0] = '\0';
}
sv->len = len;
return 0;
}
/**
* \ingroup strvector
* \function igraph_strvector_destroy
* \brief Free allocated memory
*
* Destroy a string vector. It may be reinitialized with \ref
* igraph_strvector_init() later.
* \param sv The string vector.
*
* Time complexity: O(l), the total length of the strings, maybe less
* depending on the memory manager.
*/
void igraph_strvector_destroy(igraph_strvector_t *sv) {
long int i;
assert(sv != 0);
if (sv->data != 0) {
for (i = 0; i < sv->len; i++) {
if (sv->data[i] != 0) {
igraph_Free(sv->data[i]);
}
}
igraph_Free(sv->data);
}
}
/**
* \ingroup strvector
* \function igraph_strvector_get
* \brief Indexing
*
* Query an element of a string vector. See also the \ref STR macro
* for an easier way.
* \param sv The input string vector.
* \param idx The index of the element to query.
* \param Pointer to a <type>char*</type>, the address of the string
* is stored here.
*
* Time complexity: O(1).
*/
void igraph_strvector_get(const igraph_strvector_t *sv, long int idx,
char **value) {
assert(sv != 0);
assert(sv->data != 0);
assert(sv->data[idx] != 0);
*value = sv->data[idx];
}
/**
* \ingroup strvector
* \function igraph_strvector_set
* \brief Set an element
*
* The provided \p value is copied into the \p idx position in the
* string vector.
* \param sv The string vector.
* \param idx The position to set.
* \param value The new value.
* \return Error code.
*
* Time complexity: O(l), the length of the new string. Maybe more,
* depending on the memory management, if reallocation is needed.
*/
int igraph_strvector_set(igraph_strvector_t *sv, long int idx,
const char *value) {
assert(sv != 0);
assert(sv->data != 0);
if (sv->data[idx] == 0) {
sv->data[idx] = igraph_Calloc(strlen(value) + 1, char);
if (sv->data[idx] == 0) {
IGRAPH_ERROR("strvector set failed", IGRAPH_ENOMEM);
}
} else {
char *tmp = igraph_Realloc(sv->data[idx], strlen(value) + 1, char);
if (tmp == 0) {
IGRAPH_ERROR("strvector set failed", IGRAPH_ENOMEM);
}
sv->data[idx] = tmp;
}
strcpy(sv->data[idx], value);
return 0;
}
/**
* \ingroup strvector
* \function igraph_strvector_set2
* \brief Sets an element
*
* This is almost the same as \ref igraph_strvector_set, but the new
* value is not a zero terminated string, but its length is given.
* \param sv The string vector.
* \param idx The position to set.
* \param value The new value.
* \param len The length of the new value.
* \return Error code.
*
* Time complexity: O(l), the length of the new string. Maybe more,
* depending on the memory management, if reallocation is needed.
*/
int igraph_strvector_set2(igraph_strvector_t *sv, long int idx,
const char *value, int len) {
assert(sv != 0);
assert(sv->data != 0);
if (sv->data[idx] == 0) {
sv->data[idx] = igraph_Calloc(len + 1, char);
if (sv->data[idx] == 0) {
IGRAPH_ERROR("strvector set failed", IGRAPH_ENOMEM);
}
} else {
char *tmp = igraph_Realloc(sv->data[idx], (size_t) len + 1, char);
if (tmp == 0) {
IGRAPH_ERROR("strvector set failed", IGRAPH_ENOMEM);
}
sv->data[idx] = tmp;
}
memcpy(sv->data[idx], value, (size_t) len * sizeof(char));
sv->data[idx][len] = '\0';
return 0;
}
/**
* \ingroup strvector
* \function igraph_strvector_remove_section
* \brief Removes a section from a string vector.
* \todo repair realloc
*/
void igraph_strvector_remove_section(igraph_strvector_t *v, long int from,
long int to) {
long int i;
/* char **tmp; */
assert(v != 0);
assert(v->data != 0);
for (i = from; i < to; i++) {
if (v->data[i] != 0) {
igraph_Free(v->data[i]);
}
}
for (i = 0; i < v->len - to; i++) {
v->data[from + i] = v->data[to + i];
}
v->len -= (to - from);
/* try to make it smaller */
/* tmp=igraph_Realloc(v->data, v->len, char*); */
/* if (tmp!=0) { */
/* v->data=tmp; */
/* } */
}
/**
* \ingroup strvector
* \function igraph_strvector_remove
* \brief Removes a single element from a string vector.
*
* The string will be one shorter.
* \param The string vector.
* \param elem The index of the element to remove.
*
* Time complexity: O(n), the length of the string.
*/
void igraph_strvector_remove(igraph_strvector_t *v, long int elem) {
assert(v != 0);
assert(v->data != 0);
igraph_strvector_remove_section(v, elem, elem + 1);
}
/**
* \ingroup strvector
* \function igraph_strvector_move_interval
* \brief Copies an interval of a string vector.
*/
void igraph_strvector_move_interval(igraph_strvector_t *v, long int begin,
long int end, long int to) {
long int i;
assert(v != 0);
assert(v->data != 0);
for (i = to; i < to + end - begin; i++) {
if (v->data[i] != 0) {
igraph_Free(v->data[i]);
}
}
for (i = 0; i < end - begin; i++) {
if (v->data[begin + i] != 0) {
size_t len = strlen(v->data[begin + i]) + 1;
v->data[to + i] = igraph_Calloc(len, char);
memcpy(v->data[to + i], v->data[begin + i], sizeof(char)*len);
}
}
}
/**
* \ingroup strvector
* \function igraph_strvector_copy
* \brief Initialization by copying.
*
* Initializes a string vector by copying another string vector.
* \param to Pointer to an uninitialized string vector.
* \param from The other string vector, to be copied.
* \return Error code.
*
* Time complexity: O(l), the total length of the strings in \p from.
*/
int igraph_strvector_copy(igraph_strvector_t *to,
const igraph_strvector_t *from) {
long int i;
char *str;
assert(from != 0);
/* assert(from->data != 0); */
to->data = igraph_Calloc(from->len, char*);
if (to->data == 0) {
IGRAPH_ERROR("Cannot copy string vector", IGRAPH_ENOMEM);
}
to->len = from->len;
for (i = 0; i < from->len; i++) {
int ret;
igraph_strvector_get(from, i, &str);
ret = igraph_strvector_set(to, i, str);
if (ret != 0) {
igraph_strvector_destroy(to);
IGRAPH_ERROR("cannot copy string vector", ret);
}
}
return 0;
}
/**
* \function igraph_strvector_append
* Concatenate two string vectors.
*
* \param to The first string vector, the result is stored here.
* \param from The second string vector, it is kept unchanged.
* \return Error code.
*
* Time complexity: O(n+l2), n is the number of strings in the new
* string vector, l2 is the total length of strings in the \p from
* string vector.
*/
int igraph_strvector_append(igraph_strvector_t *to,
const igraph_strvector_t *from) {
long int len1 = igraph_strvector_size(to), len2 = igraph_strvector_size(from);
long int i;
igraph_bool_t error = 0;
IGRAPH_CHECK(igraph_strvector_resize(to, len1 + len2));
for (i = 0; i < len2; i++) {
if (from->data[i][0] != '\0') {
igraph_Free(to->data[len1 + i]);
to->data[len1 + i] = strdup(from->data[i]);
if (!to->data[len1 + i]) {
error = 1;
break;
}
}
}
if (error) {
igraph_strvector_resize(to, len1);
IGRAPH_ERROR("Cannot append string vector", IGRAPH_ENOMEM);
}
return 0;
}
/**
* \function igraph_strvector_clear
* Remove all elements
*
* After this operation the string vector will be empty.
* \param sv The string vector.
*
* Time complexity: O(l), the total length of strings, maybe less,
* depending on the memory manager.
*/
void igraph_strvector_clear(igraph_strvector_t *sv) {
long int i, n = igraph_strvector_size(sv);
char **tmp;
for (i = 0; i < n; i++) {
igraph_Free(sv->data[i]);
}
sv->len = 0;
/* try to give back some memory */
tmp = igraph_Realloc(sv->data, 1, char*);
if (tmp != 0) {
sv->data = tmp;
}
}
/**
* \ingroup strvector
* \function igraph_strvector_resize
* \brief Resize
*
* If the new size is bigger then empty strings are added, if it is
* smaller then the unneeded elements are removed.
* \param v The string vector.
* \param newsize The new size.
* \return Error code.
*
* Time complexity: O(n), the number of strings if the vector is made
* bigger, O(l), the total length of the deleted strings if it is made
* smaller, maybe less, depending on memory management.
*/
int igraph_strvector_resize(igraph_strvector_t* v, long int newsize) {
long int toadd = newsize - v->len, i, j;
char **tmp;
long int reallocsize = newsize;
if (reallocsize == 0) {
reallocsize = 1;
}
assert(v != 0);
assert(v->data != 0);
/* printf("resize %li to %li\n", v->len, newsize); */
if (newsize < v->len) {
for (i = newsize; i < v->len; i++) {
igraph_Free(v->data[i]);
}
/* try to give back some space */
tmp = igraph_Realloc(v->data, (size_t) reallocsize, char*);
/* printf("resize %li to %li, %p\n", v->len, newsize, tmp); */
if (tmp != 0) {
v->data = tmp;
}
} else if (newsize > v->len) {
igraph_bool_t error = 0;
tmp = igraph_Realloc(v->data, (size_t) reallocsize, char*);
if (tmp == 0) {
IGRAPH_ERROR("cannot resize string vector", IGRAPH_ENOMEM);
}
v->data = tmp;
for (i = 0; i < toadd; i++) {
v->data[v->len + i] = igraph_Calloc(1, char);
if (v->data[v->len + i] == 0) {
error = 1;
break;
}
v->data[v->len + i][0] = '\0';
}
if (error) {
/* There was an error, free everything we've allocated so far */
for (j = 0; j < i; j++) {
if (v->data[v->len + i] != 0) {
igraph_Free(v->data[v->len + i]);
}
}
/* Try to give back space */
tmp = igraph_Realloc(v->data, (size_t) (v->len), char*);
if (tmp != 0) {
v->data = tmp;
}
IGRAPH_ERROR("Cannot resize string vector", IGRAPH_ENOMEM);
}
}
v->len = newsize;
return 0;
}
/**
* \ingroup strvector
* \function igraph_strvector_size
* \brief Gives the size of a string vector.
*
* \param sv The string vector.
* \return The length of the string vector.
*
* Time complexity: O(1).
*/
long int igraph_strvector_size(const igraph_strvector_t *sv) {
assert(sv != 0);
assert(sv->data != 0);
return sv->len;
}
/**
* \ingroup strvector
* \function igraph_strvector_add
* \brief Adds an element to the back of a string vector.
*
* \param v The string vector.
* \param value The string to add, it will be copied.
* \return Error code.
*
* Time complexity: O(n+l), n is the total number of strings, l is the
* length of the new string.
*/
int igraph_strvector_add(igraph_strvector_t *v, const char *value) {
long int s = igraph_strvector_size(v);
char **tmp;
assert(v != 0);
assert(v->data != 0);
tmp = igraph_Realloc(v->data, (size_t) s + 1, char*);
if (tmp == 0) {
IGRAPH_ERROR("cannot add string to string vector", IGRAPH_ENOMEM);
}
v->data = tmp;
v->data[s] = igraph_Calloc(strlen(value) + 1, char);
if (v->data[s] == 0) {
IGRAPH_ERROR("cannot add string to string vector", IGRAPH_ENOMEM);
}
strcpy(v->data[s], value);
v->len += 1;
return 0;
}
/**
* \ingroup strvector
* \function igraph_strvector_permdelete
* \brief Removes elements from a string vector (for internal use)
*/
void igraph_strvector_permdelete(igraph_strvector_t *v, const igraph_vector_t *index,
long int nremove) {
long int i;
char **tmp;
assert(v != 0);
assert(v->data != 0);
for (i = 0; i < igraph_strvector_size(v); i++) {
if (VECTOR(*index)[i] != 0) {
v->data[ (long int) VECTOR(*index)[i] - 1 ] = v->data[i];
} else {
igraph_Free(v->data[i]);
}
}
/* Try to make it shorter */
tmp = igraph_Realloc(v->data, v->len - nremove ?
(size_t) (v->len - nremove) : 1, char*);
if (tmp != 0) {
v->data = tmp;
}
v->len -= nremove;
}
/**
* \ingroup strvector
* \function igraph_strvector_remove_negidx
* \brief Removes elements from a string vector (for internal use)
*/
void igraph_strvector_remove_negidx(igraph_strvector_t *v, const igraph_vector_t *neg,
long int nremove) {
long int i, idx = 0;
char **tmp;
assert(v != 0);
assert(v->data != 0);
for (i = 0; i < igraph_strvector_size(v); i++) {
if (VECTOR(*neg)[i] >= 0) {
v->data[idx++] = v->data[i];
} else {
igraph_Free(v->data[i]);
}
}
/* Try to give back some memory */
tmp = igraph_Realloc(v->data, v->len - nremove ?
(size_t) (v->len - nremove) : 1, char*);
if (tmp != 0) {
v->data = tmp;
}
v->len -= nremove;
}
int igraph_strvector_print(const igraph_strvector_t *v, FILE *file,
const char *sep) {
long int i, n = igraph_strvector_size(v);
if (n != 0) {
fprintf(file, "%s", STR(*v, 0));
}
for (i = 1; i < n; i++) {
fprintf(file, "%s%s", sep, STR(*v, i));
}
return 0;
}
int igraph_strvector_index(const igraph_strvector_t *v,
igraph_strvector_t *newv,
const igraph_vector_t *idx) {
long int i, newlen = igraph_vector_size(idx);
IGRAPH_CHECK(igraph_strvector_resize(newv, newlen));
for (i = 0; i < newlen; i++) {
long int j = (long int) VECTOR(*idx)[i];
char *str;
igraph_strvector_get(v, j, &str);
igraph_strvector_set(newv, i, str);
}
return 0;
}