From: Ben Pfaff Date: Wed, 3 Feb 2010 06:10:11 +0000 (-0800) Subject: New "string_array" data structure for working with arrays of strings. X-Git-Tag: v0.7.4~22 X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?p=pspp-builds.git;a=commitdiff_plain;h=6f0ba24cc85db195ff3ba8bd4a16dd5440339b8d New "string_array" data structure for working with arrays of strings. Occasionally a dynamic array of strings is very useful, so this commit adds a set of helper functions for working with them. --- diff --git a/src/libpspp/automake.mk b/src/libpspp/automake.mk index 2795dc20..04c7e9f6 100644 --- a/src/libpspp/automake.mk +++ b/src/libpspp/automake.mk @@ -68,6 +68,8 @@ src_libpspp_libpspp_la_SOURCES = \ src/libpspp/sparse-xarray.h \ src/libpspp/start-date.c \ src/libpspp/start-date.h \ + src/libpspp/string-array.c \ + src/libpspp/string-array.h \ src/libpspp/string-map.c \ src/libpspp/string-map.h \ src/libpspp/string-set.c \ diff --git a/src/libpspp/string-array.c b/src/libpspp/string-array.c new file mode 100644 index 00000000..b9067ab6 --- /dev/null +++ b/src/libpspp/string-array.c @@ -0,0 +1,256 @@ +/* PSPP - a program for statistical analysis. + Copyright (C) 2010 Free Software Foundation, Inc. + + 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 3 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, see . */ + +#include + +#include "libpspp/string-array.h" + +#include +#include +#include + +#include "libpspp/array.h" +#include "libpspp/str.h" + +#include "gl/xalloc.h" + +/* Initializes SA as an initially empty array of strings. */ +void +string_array_init (struct string_array *sa) +{ + sa->strings = NULL; + sa->n = 0; + sa->allocated = 0; +} + +/* Initializes DST as an array of strings whose contents are initially copies + of the strings in SRC. */ +void +string_array_clone (struct string_array *dst, const struct string_array *src) +{ + size_t i; + + dst->strings = xmalloc (sizeof *dst->strings * src->n); + for (i = 0; i < src->n; i++) + dst->strings[i] = xstrdup (src->strings[i]); + dst->n = src->n; + dst->allocated = src->n; +} + +/* Exchanges the contents of A and B. */ +void +string_array_swap (struct string_array *a, struct string_array *b) +{ + struct string_array tmp = *a; + *a = *b; + *b = tmp; +} + +/* Frees the strings in SA. SA must be reinitialized (with + string_array_init()) before it is used again. */ +void +string_array_destroy (struct string_array *sa) +{ + if (sa != NULL) + { + string_array_clear (sa); + free (sa->strings); + } +} + +/* Returns true if SA contains at least one copy of STRING, otherwise false. + + This function runs in O(n) time in the number of strings in SA. */ +bool +string_array_contains (const struct string_array *sa, const char *string) +{ + return string_array_find (sa, string) != SIZE_MAX; +} + +/* If SA contains at least one copy of STRING, returns the smallest index of + any of those copies. If SA does not contain STRING, returns SIZE_MAX. + + This function runs in O(n) time in the number of strings in SA. */ +size_t +string_array_find (const struct string_array *sa, const char *string) +{ + size_t i; + + for (i = 0; i < sa->n; i++) + if (!strcmp (sa->strings[i], string)) + return i; + return SIZE_MAX; +} + +/* Appends a copy of STRING to SA. The caller retains ownership of STRING. */ +void +string_array_append (struct string_array *sa, const char *string) +{ + string_array_insert (sa, string, sa->n); +} + +/* Appends STRING to SA. Ownership of STRING transfers to SA. */ +void +string_array_append_nocopy (struct string_array *sa, char *string) +{ + string_array_insert_nocopy (sa, string, sa->n); +} + +/* Inserts a copy of STRING in SA just before the string with index BEFORE, + which must be less than or equal to the number of strings in SA. The caller + retains ownership of STRING. + + In general, this function runs in O(n) time in the number of strings that + must be shifted to higher indexes; if BEFORE is the number of strings in SA, + it runs in amortized constant time. */ +void +string_array_insert (struct string_array *sa, + const char *string, size_t before) +{ + string_array_insert_nocopy (sa, xstrdup (string), before); +} + +static void +string_array_expand__ (struct string_array *sa) +{ + if (sa->n >= sa->allocated) + sa->strings = x2nrealloc (sa->strings, &sa->allocated, + sizeof *sa->strings); +} + +/* Inserts STRING in SA just before the string with index BEFORE, which must be + less than or equal to the number of strings in SA. Ownership of STRING + transfers to SA. + + In general, this function runs in O(n) time in the number of strings that + must be shifted to higher indexes; if BEFORE is the number of strings in SA, + it runs in amortized constant time. */ +void +string_array_insert_nocopy (struct string_array *sa, char *string, + size_t before) +{ + string_array_expand__ (sa); + if (before < sa->n) + insert_element (sa->strings, sa->n, sizeof *sa->strings, before); + + sa->strings[before] = string; + sa->n++; +} + +/* Deletes from SA the string with index IDX, which must be less than the + number of strings in SA, and shifts down the strings with higher indexes. + Frees the string. + + In general, this function runs in O(n) time in the number of strings that + must be shifted to lower indexes. If IDX is the last string in SA, it runs + in amortized constant time. */ +void +string_array_delete (struct string_array *sa, size_t idx) +{ + free (string_array_delete_nofree (sa, idx)); +} + +/* Deletes from SA the string with index IDX, which must be less than the + number of strings in SA. Returns the string, which the caller is + responsible for freeing with free(). + + In general, this function runs in O(n) time in the number of strings that + must be shifted to lower indexes. If IDX is the last string in SA, it runs + in amortized constant time. */ +char * +string_array_delete_nofree (struct string_array *sa, size_t idx) +{ + char *s = sa->strings[idx]; + if (idx != sa->n - 1) + remove_element (sa->strings, sa->n, sizeof *sa->strings, idx); + sa->n--; + return s; +} + +/* Deletes all of the strings from SA and frees them. */ +void +string_array_clear (struct string_array *sa) +{ + size_t i; + + for (i = 0; i < sa->n; i++) + free (sa->strings[i]); + sa->n = 0; +} + +/* Ensures that 'sa->strings[sa->n]' is a null pointer (until SA is modified + further). */ +void +string_array_terminate_null (struct string_array *sa) +{ + string_array_expand__ (sa); + sa->strings[sa->n] = NULL; +} + +/* Reduces the amount of memory allocated for SA's strings to the minimum + necessary. */ +void +string_array_shrink (struct string_array *sa) +{ + if (sa->allocated > sa->n) + { + if (sa->n > 0) + sa->strings = xrealloc (sa->strings, sa->n * sizeof *sa->strings); + else + { + free (sa->strings); + sa->strings = NULL; + } + sa->allocated = sa->n; + } +} + +static int +compare_strings (const void *a_, const void *b_) +{ + const void *const *a = a_; + const void *const *b = b_; + + return strcmp (*a, *b); +} + +/* Sorts the strings in SA into order according to strcmp(). */ +void +string_array_sort (struct string_array *sa) +{ + qsort (sa->strings, sa->n, sizeof *sa->strings, compare_strings); +} + +/* Returns a single string that consists of each of the strings in SA + concatenated, separated from each other with SEPARATOR. + + The caller is responsible for freeing the returned string with free(). */ +char * +string_array_join (const struct string_array *sa, const char *separator) +{ + struct string dst; + const char *s; + size_t i; + + ds_init_empty (&dst); + STRING_ARRAY_FOR_EACH (s, i, sa) + { + if (i > 0) + ds_put_cstr (&dst, separator); + ds_put_cstr (&dst, s); + } + return ds_steal_cstr (&dst); +} diff --git a/src/libpspp/string-array.h b/src/libpspp/string-array.h new file mode 100644 index 00000000..f3ec0423 --- /dev/null +++ b/src/libpspp/string-array.h @@ -0,0 +1,96 @@ +/* PSPP - a program for statistical analysis. + Copyright (C) 2010 Free Software Foundation, Inc. + + 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 3 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, see . */ + +#ifndef LIBPSPP_STRING_ARRAY_H +#define LIBPSPP_STRING_ARRAY_H + +#include +#include + +/* An unordered array of strings. + + Not opaque by any means. */ +struct string_array + { + char **strings; + size_t n; + size_t allocated; + }; + +/* Suitable for use as the initializer for a string_array named ARRAY. Typical + usage: + struct string_array array = STRING_ARRAY_INITIALIZER (array); + STRING_ARRAY_INITIALIZER is an alternative to calling string_array_init. */ +#define STRING_ARRAY_INITIALIZER(ARRAY) { NULL, 0, 0 } + +void string_array_init (struct string_array *); +void string_array_clone (struct string_array *, const struct string_array *); +void string_array_swap (struct string_array *, struct string_array *); +void string_array_destroy (struct string_array *); + +static inline size_t string_array_count (const struct string_array *); +static inline bool string_array_is_empty (const struct string_array *); + +bool string_array_contains (const struct string_array *, const char *); +size_t string_array_find (const struct string_array *, const char *); + +void string_array_append (struct string_array *, const char *); +void string_array_append_nocopy (struct string_array *, char *); +void string_array_insert (struct string_array *, const char *, size_t before); +void string_array_insert_nocopy (struct string_array *, char *, size_t before); +void string_array_delete (struct string_array *, size_t idx); +char *string_array_delete_nofree (struct string_array *, size_t idx); + +void string_array_clear (struct string_array *); + +void string_array_terminate_null (struct string_array *); +void string_array_shrink (struct string_array *); + +void string_array_sort (struct string_array *); + +char *string_array_join (const struct string_array *, const char *separator); + +/* Macros for conveniently iterating through a string_array, e.g. to print all + of the strings in "my_array": + + const char *string; + size_t idx; + + STRING_ARRAY_FOR_EACH (string, idx, &my_array) + puts (string); +*/ +#define STRING_ARRAY_FOR_EACH(STRING, IDX, ARRAY) \ + for ((IDX) = 0; \ + ((IDX) < (ARRAY)->n \ + ? ((STRING) = (ARRAY)->strings[IDX], true) \ + : false); \ + (IDX)++) + +/* Returns the number of strings currently in ARRAY. */ +static inline size_t +string_array_count (const struct string_array *array) +{ + return array->n; +} + +/* Returns true if ARRAY currently contains no strings, false otherwise. */ +static inline bool +string_array_is_empty (const struct string_array *array) +{ + return array->n == 0; +} + +#endif /* libpspp/string-array.h */