2 aaa0878e 2019-01-08 stsp * Copyright (c) 2019 Stefan Sperling <stsp@openbsd.org>
4 aaa0878e 2019-01-08 stsp * Permission to use, copy, modify, and distribute this software for any
5 aaa0878e 2019-01-08 stsp * purpose with or without fee is hereby granted, provided that the above
6 aaa0878e 2019-01-08 stsp * copyright notice and this permission notice appear in all copies.
8 aaa0878e 2019-01-08 stsp * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 aaa0878e 2019-01-08 stsp * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 aaa0878e 2019-01-08 stsp * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 aaa0878e 2019-01-08 stsp * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 aaa0878e 2019-01-08 stsp * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 aaa0878e 2019-01-08 stsp * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 aaa0878e 2019-01-08 stsp * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 aaa0878e 2019-01-08 stsp #include <sys/tree.h>
19 aaa0878e 2019-01-08 stsp #include <stdlib.h>
20 aaa0878e 2019-01-08 stsp #include <string.h>
21 aaa0878e 2019-01-08 stsp #include <stdio.h>
22 aaa0878e 2019-01-08 stsp #include <limits.h>
24 aaa0878e 2019-01-08 stsp #include "got_error.h"
25 aaa0878e 2019-01-08 stsp #include "got_lib_pathset.h"
28 aaa0878e 2019-01-08 stsp #define MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
31 aaa0878e 2019-01-08 stsp struct got_pathset_element {
32 aaa0878e 2019-01-08 stsp RB_ENTRY(got_pathset_element) entry;
34 aaa0878e 2019-01-08 stsp void *data; /* API user data */
37 aaa0878e 2019-01-08 stsp RB_HEAD(got_pathset_tree, got_pathset_element);
40 aaa0878e 2019-01-08 stsp cmp_elements(const struct got_pathset_element *e1,
41 aaa0878e 2019-01-08 stsp const struct got_pathset_element *e2)
43 aaa0878e 2019-01-08 stsp size_t len1 = strlen(e1->path);
44 aaa0878e 2019-01-08 stsp size_t len2 = strlen(e2->path);
45 aaa0878e 2019-01-08 stsp size_t min_len = MIN(len1, len2);
46 aaa0878e 2019-01-08 stsp size_t i = 0;
48 aaa0878e 2019-01-08 stsp /* Skip over common prefix. */
49 aaa0878e 2019-01-08 stsp while (i < min_len && e1->path[i] == e2->path[i])
52 aaa0878e 2019-01-08 stsp /* Are the paths exactly equal? */
53 aaa0878e 2019-01-08 stsp if (len1 == len2 && i >= min_len)
56 aaa0878e 2019-01-08 stsp /* Order children in subdirectories directly after their parents. */
57 aaa0878e 2019-01-08 stsp if (e1->path[i] == '/' && e2->path[i] == '\0')
59 aaa0878e 2019-01-08 stsp if (e2->path[i] == '/' && e1->path[i] == '\0')
61 aaa0878e 2019-01-08 stsp if (e1->path[i] == '/')
63 aaa0878e 2019-01-08 stsp if (e2->path[i] == '/')
66 aaa0878e 2019-01-08 stsp /* Next character following the common prefix determines order. */
67 aaa0878e 2019-01-08 stsp return (unsigned char)e1->path[i] < (unsigned char)e2->path[i] ? -1 : 1;
70 aaa0878e 2019-01-08 stsp RB_PROTOTYPE(got_pathset_tree, got_pathset_element, entry, cmp_elements);
72 aaa0878e 2019-01-08 stsp struct got_pathset {
73 aaa0878e 2019-01-08 stsp struct got_pathset_tree entries;
74 aaa0878e 2019-01-08 stsp int totelem;
75 aaa0878e 2019-01-08 stsp #define GOT_OBJECT_IDSET_MAX_ELEM INT_MAX
78 aaa0878e 2019-01-08 stsp struct got_pathset *
79 aaa0878e 2019-01-08 stsp got_pathset_alloc(void)
81 aaa0878e 2019-01-08 stsp struct got_pathset *set;
83 aaa0878e 2019-01-08 stsp set = malloc(sizeof(*set));
84 aaa0878e 2019-01-08 stsp if (set == NULL)
85 aaa0878e 2019-01-08 stsp return NULL;
87 aaa0878e 2019-01-08 stsp RB_INIT(&set->entries);
88 aaa0878e 2019-01-08 stsp set->totelem = 0;
94 aaa0878e 2019-01-08 stsp free_element(struct got_pathset_element *entry)
96 aaa0878e 2019-01-08 stsp free(entry->path);
97 aaa0878e 2019-01-08 stsp free(entry);
101 aaa0878e 2019-01-08 stsp got_pathset_free(struct got_pathset *set)
103 aaa0878e 2019-01-08 stsp struct got_pathset_element *entry;
105 aaa0878e 2019-01-08 stsp while ((entry = RB_MIN(got_pathset_tree, &set->entries))) {
106 aaa0878e 2019-01-08 stsp RB_REMOVE(got_pathset_tree, &set->entries, entry);
107 aaa0878e 2019-01-08 stsp /* User data should be freed by caller. */
108 aaa0878e 2019-01-08 stsp free_element(entry);
114 aaa0878e 2019-01-08 stsp const struct got_error *
115 aaa0878e 2019-01-08 stsp got_pathset_add(struct got_pathset *set, const char *path, void *data)
117 aaa0878e 2019-01-08 stsp struct got_pathset_element *new;
119 aaa0878e 2019-01-08 stsp if (set->totelem >= GOT_OBJECT_IDSET_MAX_ELEM)
120 aaa0878e 2019-01-08 stsp return got_error(GOT_ERR_NO_SPACE);
122 aaa0878e 2019-01-08 stsp new = malloc(sizeof(*new));
123 aaa0878e 2019-01-08 stsp if (new == NULL)
124 aaa0878e 2019-01-08 stsp return got_error_from_errno();
126 aaa0878e 2019-01-08 stsp new->path = strdup(path);
127 aaa0878e 2019-01-08 stsp if (new->path == NULL)
128 aaa0878e 2019-01-08 stsp return got_error_from_errno();
130 aaa0878e 2019-01-08 stsp new->data = data;
132 aaa0878e 2019-01-08 stsp RB_INSERT(got_pathset_tree, &set->entries, new);
133 aaa0878e 2019-01-08 stsp set->totelem++;
134 aaa0878e 2019-01-08 stsp return NULL;
137 aaa0878e 2019-01-08 stsp static struct got_pathset_element *
138 aaa0878e 2019-01-08 stsp find_element(struct got_pathset *set, const char *path)
140 aaa0878e 2019-01-08 stsp struct got_pathset_element key, *entry;
141 aaa0878e 2019-01-08 stsp key.path = strdup(path);
142 aaa0878e 2019-01-08 stsp entry = RB_FIND(got_pathset_tree, &set->entries, &key);
143 aaa0878e 2019-01-08 stsp free(key.path);
144 aaa0878e 2019-01-08 stsp return entry;
148 aaa0878e 2019-01-08 stsp got_pathset_get(struct got_pathset *set, const char *path)
150 aaa0878e 2019-01-08 stsp struct got_pathset_element *entry = find_element(set, path);
151 aaa0878e 2019-01-08 stsp return entry ? entry->data : NULL;
154 aaa0878e 2019-01-08 stsp const struct got_error *
155 aaa0878e 2019-01-08 stsp got_pathset_remove(void **data, struct got_pathset *set, const char *path)
157 aaa0878e 2019-01-08 stsp struct got_pathset_element *entry;
160 aaa0878e 2019-01-08 stsp *data = NULL;
162 aaa0878e 2019-01-08 stsp if (set->totelem == 0)
163 aaa0878e 2019-01-08 stsp return got_error(GOT_ERR_NO_OBJ);
165 aaa0878e 2019-01-08 stsp if (path == NULL)
166 aaa0878e 2019-01-08 stsp entry = RB_ROOT(&set->entries);
168 aaa0878e 2019-01-08 stsp entry = find_element(set, path);
169 aaa0878e 2019-01-08 stsp if (entry == NULL)
170 aaa0878e 2019-01-08 stsp return got_error(GOT_ERR_NO_OBJ);
172 aaa0878e 2019-01-08 stsp RB_REMOVE(got_pathset_tree, &set->entries, entry);
174 aaa0878e 2019-01-08 stsp *data = entry->data;
175 aaa0878e 2019-01-08 stsp free_element(entry);
176 aaa0878e 2019-01-08 stsp set->totelem--;
177 aaa0878e 2019-01-08 stsp return NULL;
181 aaa0878e 2019-01-08 stsp got_pathset_contains(struct got_pathset *set, const char *path)
183 aaa0878e 2019-01-08 stsp struct got_pathset_element *entry = find_element(set, path);
184 aaa0878e 2019-01-08 stsp return entry ? 1 : 0;
187 aaa0878e 2019-01-08 stsp const struct got_error *
188 aaa0878e 2019-01-08 stsp got_pathset_for_each(struct got_pathset *set,
189 aaa0878e 2019-01-08 stsp const struct got_error *(*cb)(const char *, void *, void *), void *arg)
191 aaa0878e 2019-01-08 stsp const struct got_error *err;
192 aaa0878e 2019-01-08 stsp struct got_pathset_element *entry, *tmp;
194 aaa0878e 2019-01-08 stsp RB_FOREACH_SAFE(entry, got_pathset_tree, &set->entries, tmp) {
195 aaa0878e 2019-01-08 stsp err = (*cb)(entry->path, entry->data, arg);
197 aaa0878e 2019-01-08 stsp return err;
199 aaa0878e 2019-01-08 stsp return NULL;
202 efaf56b7 2019-01-08 stsp const struct got_error *
203 efaf56b7 2019-01-08 stsp got_pathset_for_each_reverse(struct got_pathset *set,
204 efaf56b7 2019-01-08 stsp const struct got_error *(*cb)(const char *, void *, void *), void *arg)
206 efaf56b7 2019-01-08 stsp const struct got_error *err;
207 efaf56b7 2019-01-08 stsp struct got_pathset_element *entry, *tmp;
209 efaf56b7 2019-01-08 stsp RB_FOREACH_REVERSE_SAFE(entry, got_pathset_tree, &set->entries, tmp) {
210 efaf56b7 2019-01-08 stsp err = (*cb)(entry->path, entry->data, arg);
212 efaf56b7 2019-01-08 stsp return err;
214 efaf56b7 2019-01-08 stsp return NULL;
218 aaa0878e 2019-01-08 stsp got_pathset_num_elements(struct got_pathset *set)
220 aaa0878e 2019-01-08 stsp return set->totelem;
223 aaa0878e 2019-01-08 stsp RB_GENERATE(got_pathset_tree, got_pathset_element, entry, cmp_elements);