summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJason Woodward2019-07-05 16:42:35 +0000
committerJason Woodward2019-07-12 02:39:13 +0000
commite4c7e3d20d80a77aa91e00f8c070cb6ca5aa324d (patch)
treea54a2b7450c278c24f63507e2bb535722d074bfa
parentc84b8a95306ab225da2dd08d05d3ea63240ad400 (diff)
downloadslapt-get-e4c7e3d20d80a77aa91e00f8c070cb6ca5aa324d.tar.gz
add slapt_vector_t
-rw-r--r--src/common.c136
-rw-r--r--src/common.h20
-rw-r--r--t/test_common.c33
3 files changed, 188 insertions, 1 deletions
diff --git a/src/common.c b/src/common.c
index eefe427..b2b3d6b 100644
--- a/src/common.c
+++ b/src/common.c
@@ -82,7 +82,7 @@ char *slapt_regex_extract_match(const slapt_regex_t *r, const char *src, const i
if (m.rm_so != -1) {
uint32_t len = m.rm_eo - m.rm_so + 1;
- str = malloc(sizeof *str * len);
+ str = slapt_malloc(sizeof *str * len);
str = strncpy(str, src + m.rm_so, len);
if (len > 0)
@@ -515,3 +515,137 @@ char *slapt_strip_whitespace(const char *s)
++s, --len;
return strndup(s, len);
}
+
+
+slapt_vector_t *slapt_vector_t_init(slapt_vector_t_free_function f) {
+ slapt_vector_t *v = NULL;
+ v = slapt_malloc(sizeof *v);
+ v->size = 0;
+ v->capacity = 0;
+ v->items = slapt_malloc(sizeof *v->items);
+ v->free_function = f;
+ v->sorted = false;
+ return v;
+}
+
+void slapt_vector_t_free(slapt_vector_t *v) {
+ if (v->free_function) {
+ for (uint32_t i = 0; i < v->size; i++ ) {
+ v->free_function(v->items[i]);
+ }
+ }
+ free(v->items);
+ free(v);
+}
+
+void slapt_vector_t_add(slapt_vector_t *v, void *a) {
+ if (v->capacity == v->size) {
+ uint32_t new_capacity = (v->capacity+1) * 2;
+ v->items = realloc(v->items, sizeof *v->items * new_capacity);
+ if (v->items == NULL) {
+ exit(EXIT_FAILURE);
+ }
+ v->capacity = new_capacity;
+ }
+ v->items[v->size++] = a;
+ v->sorted = false;
+}
+
+void slapt_vector_t_remove(slapt_vector_t *v, void *j) {
+ bool found = false;
+ for (uint32_t i = 0; i < v->size; i++) {
+ if (j == v->items[i]) {
+ if (v->free_function) {
+ v->free_function(v->items[i]);
+ }
+ found = true;
+ }
+ if (found && ((i+1) < v->size)) {
+ v->items[i] = v->items[i + 1];
+ }
+ }
+ if (found) {
+ v->size--;
+ }
+}
+
+void slapt_vector_t_sort(slapt_vector_t *v, slapt_vector_t_qsort_cmp cmp) {
+ if (v->size > 0) {
+ qsort(v->items, v->size, sizeof(v->items[0]), cmp);
+ v->sorted = true;
+ }
+}
+
+int slapt_vector_t_index_of(slapt_vector_t *v, slapt_vector_t_cmp cmp, void *opt) {
+ if (v->sorted) {
+ int min = 0, max = v->size - 1;
+
+ while (max >= min) {
+ int pivot = (min + max) / 2;
+ int cmpv = cmp(v->items[pivot], opt);
+ if (cmpv == 0) {
+ return pivot;
+ } else {
+ if (cmpv < 0)
+ min = pivot + 1;
+ else
+ max = pivot - 1;
+ }
+ }
+ } else {
+ for (uint32_t i = 0; i < v->size; i++) {
+ if (cmp(v->items[i], opt) == 0) {
+ return i;
+ }
+ }
+ }
+ return -1;
+}
+
+slapt_vector_t *slapt_vector_t_search(slapt_vector_t *v, slapt_vector_t_cmp cmp, void *opt) {
+ slapt_vector_t *matches = slapt_vector_t_init(NULL);
+
+ if (v->sorted) {
+ uint32_t min = 0, max = v->size - 1;
+ int idx = slapt_vector_t_index_of(v, cmp, opt);
+ if (idx < 0) {
+ slapt_vector_t_free(matches);
+ return NULL;
+ }
+
+ uint32_t start = idx, end = idx;
+
+ while (start > min) {
+ if (cmp(v->items[start - 1], opt) == 0) {
+ start -= 1;
+ } else {
+ break;
+ }
+ }
+
+ while (end < max) {
+ if (cmp(v->items[end + 1], opt) == 0) {
+ end += 1;
+ } else {
+ break;
+ }
+ }
+
+ for (uint32_t i = start; i <= end; i++) {
+ slapt_vector_t_add(matches, v->items[i]);
+ }
+
+ } else {
+ for (uint32_t i = 0; i < v->size; i++) {
+ if (cmp(v->items[i], opt) == 0) {
+ slapt_vector_t_add(matches, v->items[i]);
+ }
+ }
+ }
+
+ if (!matches->size) {
+ slapt_vector_t_free(matches);
+ return NULL;
+ }
+ return matches;
+}
diff --git a/src/common.h b/src/common.h
index c0f6f71..eb3eb75 100644
--- a/src/common.h
+++ b/src/common.h
@@ -74,6 +74,26 @@ typedef struct {
#define slapt_list_t_foreach(item, list) char *item; for (uint32_t item##_counter = 0; (item##_counter < list->count) && (item = list->items[item##_counter]); item##_counter++)
+typedef int (*slapt_vector_t_cmp)(const void *, const void *);
+typedef int (*slapt_vector_t_qsort_cmp)(const void *, const void *);
+typedef void (*slapt_vector_t_free_function)(void*);
+typedef struct slapt_vector_t {
+ uint32_t size;
+ uint32_t capacity;
+ slapt_vector_t_free_function free_function;
+ bool sorted;
+ void **items;
+} slapt_vector_t;
+slapt_vector_t *slapt_vector_t_init(slapt_vector_t_free_function);
+void slapt_vector_t_free(slapt_vector_t *);
+void slapt_vector_t_add(slapt_vector_t *, void *);
+void slapt_vector_t_remove(slapt_vector_t *v, void *);
+void slapt_vector_t_sort(slapt_vector_t *, slapt_vector_t_qsort_cmp);
+int slapt_vector_t_index_of(slapt_vector_t *, slapt_vector_t_cmp, void *);
+slapt_vector_t *slapt_vector_t_search(slapt_vector_t *, slapt_vector_t_cmp, void *);
+#define slapt_vector_t_foreach(type, item, list) type item; for (uint32_t item##_counter = 0; (item##_counter < list->size) && (item = list->items[item##_counter]); item##_counter++)
+
+
FILE *slapt_open_file(const char *file_name, const char *mode);
slapt_regex_t *slapt_init_regex(const char *regex_string);
void slapt_execute_regex(slapt_regex_t *regex_t, const char *string);
diff --git a/t/test_common.c b/t/test_common.c
index 8254e19..d90aa05 100644
--- a/t/test_common.c
+++ b/t/test_common.c
@@ -72,6 +72,38 @@ START_TEST(test_slapt_str_replace_chr)
}
END_TEST
+int test_cmp_via_strcmp(const void *a, const void *b) {
+ char *sa = *(char **)a;
+ char *sb = *(char **)b;
+ return strcmp(sa, sb);
+}
+START_TEST(test_slapt_vector_t)
+{
+ slapt_vector_t *v = slapt_vector_t_init(NULL);
+ slapt_vector_t_add(v, "one");
+ slapt_vector_t_add(v, "two");
+ slapt_vector_t_add(v, "three");
+ slapt_vector_t_add(v, "four");
+
+ fail_unless(v->size == 4);
+ fail_unless(v->capacity >= v->size);
+
+ int idx = slapt_vector_t_index_of(v, (slapt_vector_t_cmp)strcmp, "three");
+ fail_unless(idx == 2);
+
+ slapt_vector_t_remove(v, v->items[idx]);
+ fail_unless(v->size == 3);
+ fail_unless(-1 == slapt_vector_t_index_of(v, (slapt_vector_t_cmp)strcmp, "three"));
+
+ slapt_vector_t_sort(v, test_cmp_via_strcmp);
+ fail_unless(0 == slapt_vector_t_index_of(v, (slapt_vector_t_cmp)strcmp, "four"));
+ fail_unless(1 == slapt_vector_t_index_of(v, (slapt_vector_t_cmp)strcmp, "one"));
+ fail_unless(2 == slapt_vector_t_index_of(v, (slapt_vector_t_cmp)strcmp, "two"));
+
+ slapt_vector_t_free(v);
+}
+END_TEST
+
Suite *common_test_suite()
{
Suite *s = suite_create("Common");
@@ -82,6 +114,7 @@ Suite *common_test_suite()
tcase_add_test(tc, test_slapt_create_dir_structure);
tcase_add_test(tc, test_slapt_gen_md5_sum_of_file);
tcase_add_test(tc, test_slapt_str_replace_chr);
+ tcase_add_test(tc, test_slapt_vector_t);
suite_add_tcase(s, tc);
return s;