diff options
| -rw-r--r-- | src/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/afb-export.c | 130 | ||||
| -rw-r--r-- | src/globset.c | 449 | ||||
| -rw-r--r-- | src/globset.h | 56 | ||||
| -rw-r--r-- | src/tests/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/tests/globset/CMakeLists.txt | 23 | ||||
| -rw-r--r-- | src/tests/globset/globset.in | 30 | ||||
| -rw-r--r-- | src/tests/globset/globset.out | 30 | ||||
| -rw-r--r-- | src/tests/globset/test-globset.c | 60 |
9 files changed, 693 insertions, 87 deletions
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index 7038205c..e1a1073a 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -67,6 +67,7 @@ SET(AFB_LIB_SOURCES fdev.c fdev-epoll.c fdev-systemd.c + globset.c jobs.c locale-root.c pearson.c diff --git a/src/afb-export.c b/src/afb-export.c index cabb4858..bfd76539 100644 --- a/src/afb-export.c +++ b/src/afb-export.c @@ -50,6 +50,7 @@ #include "afb-calls.h" #include "jobs.h" #include "verbose.h" +#include "globset.h" #include "sig-monitor.h" #include "wrap-json.h" @@ -58,24 +59,6 @@ ************************************************************************/ /* - * structure for handling events - */ -struct event_handler -{ - /* link to the next event handler of the list */ - struct event_handler *next; - - /* function to call on the case of the event */ - void (*callback)(void *, const char*, struct json_object*, struct afb_api_x3*); - - /* closure for the callback */ - void *closure; - - /* the handled pattern */ - char pattern[1]; -}; - -/* * Actually supported versions */ enum afb_api_version @@ -138,7 +121,7 @@ struct afb_export struct afb_evt_listener *listener; /* event handler list */ - struct event_handler *event_handlers; + struct globset *event_handlers; /* creator if any */ struct afb_export *creator; @@ -1161,7 +1144,8 @@ static const struct afb_api_x3_itf hooked_api_x3_itf = { */ static void listener_of_events(void *closure, const char *event, int eventid, struct json_object *object) { - struct event_handler *handler; + const struct globset_handler *handler; + void (*callback)(void *, const char*, struct json_object*, struct afb_api_x3*); struct afb_export *export = from_api_x3(closure); /* hook the event before */ @@ -1170,26 +1154,24 @@ static void listener_of_events(void *closure, const char *event, int eventid, st /* transmit to specific handlers */ /* search the handler */ - handler = export->event_handlers; - while (handler) { - if (!fnmatch(handler->pattern, event, 0)) { - if (!(export->hooksvc & afb_hook_flag_api_on_event_handler)) - handler->callback(handler->closure, event, object, to_api_x3(export)); - else { - afb_hook_api_on_event_handler_before(export, event, eventid, object, handler->pattern); - handler->callback(handler->closure, event, object, to_api_x3(export)); - afb_hook_api_on_event_handler_after(export, event, eventid, object, handler->pattern); - } + handler = export->event_handlers ? globset_match(export->event_handlers, event) : NULL; + if (handler) { + callback = handler->callback; + if (!(export->hooksvc & afb_hook_flag_api_on_event_handler)) + callback(handler->closure, event, object, to_api_x3(export)); + else { + afb_hook_api_on_event_handler_before(export, event, eventid, object, handler->pattern); + callback(handler->closure, event, object, to_api_x3(export)); + afb_hook_api_on_event_handler_after(export, event, eventid, object, handler->pattern); } - handler = handler->next; + } else { + /* transmit to default handler */ + if (export->on_any_event_v3) + export->on_any_event_v3(to_api_x3(export), event, object); + else if (export->on_any_event_v12) + export->on_any_event_v12(event, object); } - /* transmit to default handler */ - if (export->on_any_event_v3) - export->on_any_event_v3(to_api_x3(export), event, object); - else if (export->on_any_event_v12) - export->on_any_event_v12(event, object); - /* hook the event after */ if (export->hooksvc & afb_hook_flag_api_on_event) afb_hook_api_on_event_after(export, event, eventid, object); @@ -1220,40 +1202,32 @@ int afb_export_event_handler_add( void *closure) { int rc; - struct event_handler *handler, **previous; + /* ensure the listener */ rc = ensure_listener(export); if (rc < 0) return rc; - /* search the handler */ - previous = &export->event_handlers; - while ((handler = *previous) && strcasecmp(handler->pattern, pattern)) - previous = &handler->next; - - /* error if found */ - if (handler) { - ERROR("[API %s] event handler %s already exists", export->api.apiname, pattern); - errno = EEXIST; - return -1; + /* ensure the globset for event handling */ + if (!export->event_handlers) { + export->event_handlers = globset_create(); + if (!export->event_handlers) + goto oom_error; } - /* create the event */ - handler = malloc(strlen(pattern) + sizeof * handler); - if (!handler) { - ERROR("[API %s] can't allocate event handler %s", export->api.apiname, pattern); - errno = ENOMEM; + /* add the handler */ + rc = globset_add(export->event_handlers, pattern, callback, closure); + if (rc == 0) + return 0; + + if (errno == EEXIST) { + ERROR("[API %s] event handler %s already exists", export->api.apiname, pattern); return -1; } - /* init and record */ - handler->next = NULL; - handler->callback = callback; - handler->closure = closure; - strcpy(handler->pattern, pattern); - *previous = handler; - - return 0; +oom_error: + ERROR("[API %s] can't allocate event handler %s", export->api.apiname, pattern); + return -1; } int afb_export_event_handler_del( @@ -1261,27 +1235,13 @@ int afb_export_event_handler_del( const char *pattern, void **closure) { - struct event_handler *handler, **previous; - - /* search the handler */ - previous = &export->event_handlers; - while ((handler = *previous) && strcasecmp(handler->pattern, pattern)) - previous = &handler->next; - - /* error if found */ - if (!handler) { - ERROR("[API %s] event handler %s already exists", export->api.apiname, pattern); - errno = ENOENT; - return -1; - } - - /* remove the found event */ - if (closure) - *closure = handler->closure; + if (export->event_handlers + && !globset_del(export->event_handlers, pattern, closure)) + return 0; - *previous = handler->next; - free(handler); - return 0; + ERROR("[API %s] event handler %s not found", export->api.apiname, pattern); + errno = ENOENT; + return -1; } /****************************************************************************** @@ -1346,13 +1306,9 @@ void afb_export_unref(struct afb_export *export) void afb_export_destroy(struct afb_export *export) { - struct event_handler *handler; - if (export) { - while ((handler = export->event_handlers)) { - export->event_handlers = handler->next; - free(handler); - } + if (export->event_handlers) + globset_destroy(export->event_handlers); if (export->listener != NULL) afb_evt_listener_unref(export->listener); afb_session_unref(export->session); diff --git a/src/globset.c b/src/globset.c new file mode 100644 index 00000000..228d8523 --- /dev/null +++ b/src/globset.c @@ -0,0 +1,449 @@ +/* + * Copyright (C) 2018 "IoT.bzh" + * Author: José Bollo <jose.bollo@iot.bzh> + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#define _GNU_SOURCE + +#include <stdlib.h> +#include <string.h> +#include <errno.h> + +#include "globset.h" + +#define GLOB '*' + +/************************************************************************* + * internal types + ************************************************************************/ + +/** + * internal structure for handling patterns + */ +struct pathndl +{ + /* link to the next handler of the list */ + struct pathndl *next; + + /* the hash value for the pattern */ + size_t hash; + + /* the handler */ + struct globset_handler handler; +}; + +/** + * Structure that handles a set of global pattern handlers + */ +struct globset +{ + /** linked list of global patterns */ + struct pathndl *globs; + + /** hash dictionary of exact matches */ + struct pathndl **exacts; + + /** mask used for accessing dictionary of exact matches */ + unsigned gmask; + + /** count of handlers stored in the dictionary of exact matches */ + unsigned count; +}; + +/** + * Matches whether the string 'str' matches the pattern 'pat' + * and returns its matching score. + * + * @param pat the glob pattern + * @param str the string to match + * @return 0 if no match or number representing the matching score + */ +static unsigned match(const char *pat, const char *str) +{ + unsigned r, rs, rr; + char c; + + /* scan the prefix without glob */ + r = 1; + while ((c = *pat++) != GLOB) { + if (c != *str++) + return 0; /* no match */ + if (!c) + return r; /* match up to end */ + r++; + } + + /* glob found */ + c = *pat++; + if (!c) + return r; /* not followed by pattern */ + + /* evaluate the best score for following pattern */ + rs = 0; + while (*str) { + if (*str++ == c) { + /* first char matches, check remaining string */ + rr = match(pat, str); + if (rr > rs) + rs = rr; + } + } + + /* best score or not match if rs == 0 */ + return rs ? rs + r : 0; +} + +/** + * Normalize the string 'from' to the string 'to' and computes the hash code. + * The normalization translates upper characters to lower characters. + * The returned hash code is greater than zero for exact patterns or zero + * for global patterns. + * + * @param from string to normalize + * @param to where to store the normalization + * @return 0 if 'from' is a glob pattern or the hash code for exacts patterns + */ +static unsigned normhash(const char *from, char *to) +{ + unsigned i, hash; + int isglob; + char c; + + isglob = 0; /* is glob? */ + i = hash = 0; /* index and hash code */ + + /* copy the normalized string and compute isglob and hash */ + while ((c = from[i])) { + if (c == GLOB) { + /* it is a glob pattern */ + isglob = 1; + hash = 0; + } else { + /* normalize to lower */ + if (c >= 'A' && c <= 'Z') + c = (char)(c + 'a' - 'A'); + /* compute hash if not glob */ + if (!isglob) { + hash += (unsigned)(unsigned char)c; + hash += hash << 10; + hash ^= hash >> 6; + } + } + to[i++] = c; + } + to[i] = c; + if (!isglob) { + /* finalize hash if not glob */ + hash += i; + hash += hash << 3; + hash ^= hash >> 11; + hash += hash << 15; + if (hash == 0) + hash = 1 + i; + } + return hash; +} + +/** + * Ensure that there is enough place to store one more exact pattern + * in the dictionary. + * + * @param set the set that has to grow if needed + * @return 0 in case of success or -1 on case of error + */ +static int grow(struct globset *set) +{ + unsigned old_gmask, new_gmask, i; + struct pathndl **new_exacts, **old_exacts, *ph, *next_ph; + + /* test if grow is needed */ + old_gmask = set->gmask; + if (old_gmask - (old_gmask >> 2) > set->count + 1) + return 0; + + /* compute the new mask */ + new_gmask = (old_gmask << 1) | 15; + if (new_gmask + 1 <= new_gmask) { + errno = EOVERFLOW; + return -1; + } + + /* allocates the new array */ + new_exacts = calloc(1 + (size_t)new_gmask, sizeof *new_exacts); + if (!new_exacts) + return -1; + + /* copy values */ + old_exacts = set->exacts; + set->exacts = new_exacts; + set->gmask = new_gmask; + if (old_gmask) { + for(i = 0 ; i <= old_gmask ; i++) { + ph = old_exacts[i]; + while (ph) { + next_ph = ph->next; + ph->next = new_exacts[ph->hash & new_gmask]; + new_exacts[ph->hash & new_gmask] = ph; + ph = next_ph; + } + } + free(old_exacts); + } + + /* release the previous values */ + return 0; +} + +/** + * Search in set the handler for the normalized pattern 'normal' of 'has' code. + * + * @param set the set to search + * @param normal the normalized pattern + * @param hash hash code of the normalized pattern + * @param pprev pointer where to store the pointer pointing to the returned result + * @return the handler found, can be NULL + */ +static struct pathndl *search( + struct globset *set, + const char *normal, + unsigned hash, + struct pathndl ***pprev) +{ + struct pathndl *ph, **pph; + + if (!hash) + pph = &set->globs; + else if (set->exacts) + pph = &set->exacts[hash & set->gmask]; + else + return NULL; + while ((ph = *pph) && strcmp(normal, ph->handler.pattern)) + pph = &ph->next; + *pprev = pph; + return ph; +} + + + + + + + + +/** + * Allocates a new set of handlers + * + * @return the new allocated global pattern set of handlers or NULL on failure + */ +struct globset *globset_create() +{ + return calloc(1, sizeof(struct globset)); +} + +/** + * Destroy the set + * @param set the set to destroy + */ +void globset_destroy(struct globset *set) +{ + unsigned i; + struct pathndl *ph, *next_ph; + + /* free exact pattern handlers */ + if (set->gmask) { + for(i = 0 ; i <= set->gmask ; i++) { + ph = set->exacts[i]; + while (ph) { + next_ph = ph->next; + free(ph); + ph = next_ph; + } + } + free(set->exacts); + } + + /* free global pattern handlers */ + ph = set->globs; + while (ph) { + next_ph = ph->next; + free(ph); + ph = next_ph; + } + + /* free the set */ + free(set); +} + +/** + * Add a handler for the given pattern + * @param set the set + * @param pattern the pattern of the handler + * @param callback the handler's callback + * @param closure the handler's closure + * @return 0 in case of success or -1 in case of error (ENOMEM, EEXIST) + */ +int globset_add( + struct globset *set, + const char *pattern, + void *callback, + void *closure) +{ + struct pathndl *ph, **pph; + unsigned hash; + size_t len; + char *pat; + + /* normalize */ + len = strlen(pattern); + pat = alloca(1 + len); + hash = normhash(pattern, pat); + + /* grows if needed */ + if (hash && grow(set)) + return -1; + + /* search */ + ph = search(set, pat, hash, &pph); + if (ph) { + /* found */ + errno = EEXIST; + return -1; + } + + /* not found, create it */ + ph = malloc(len + sizeof *ph); + if (!ph) + return -1; + + /* initialize it */ + ph->next = NULL; + ph->hash = hash; + ph->handler.callback = callback; + ph->handler.closure = closure; + strcpy(ph->handler.pattern, pat); + *pph = ph; + if (hash) + set->count++; + return 0; +} + +/** + * Delete the handler for the pattern + * @param set the set + * @param pattern the pattern to delete + * @param closure where to put the closure if not NULL + * @return 0 in case of success or -1 in case of error (ENOENT) + */ +int globset_del( + struct globset *set, + const char *pattern, + void **closure) +{ + struct pathndl *ph, **pph; + unsigned hash; + char *pat; + + /* normalize */ + pat = alloca(1 + strlen(pattern)); + hash = normhash(pattern, pat); + + /* search */ + ph = search(set, pat, hash, &pph); + if (!ph) { + /* not found */ + errno = ENOENT; + return -1; + } + + /* found, remove it */ + if (hash) + set->count--; + *pph = ph->next; + + /* store the closure back */ + if (closure) + *closure = ph->handler.closure; + + /* free the memory */ + free(ph); + return 0; +} + +/** + * Search the handler of 'pattern' + * @param set the set + * @param pattern the pattern to search + * @return the handler found or NULL + */ +struct globset_handler *globset_search( + struct globset *set, + const char *pattern) +{ + struct pathndl *ph, **pph; + unsigned hash; + char *pat; + + /* local normalization */ + pat = alloca(1 + strlen(pattern)); + hash = normhash(pattern, pat); + + /* search */ + ph = search(set, pat, hash, &pph); + return ph ? &ph->handler : NULL; +} + +/** + * Search a handler for the string 'text' + * @param set the set + * @param text the text to match + * @return the handler found or NULL + */ +const struct globset_handler *globset_match( + struct globset *set, + const char *text) +{ + struct pathndl *ph, *iph; + unsigned hash, g, s; + char *txt; + + /* local normalization */ + txt = alloca(1 + strlen(text)); + hash = normhash(text, txt); + + /* first, look in dictionary of exact matches */ + ph = NULL; + if (hash && set->exacts) { + ph = set->exacts[hash & set->gmask]; + while(ph && (ph->hash != hash || strcmp(txt, ph->handler.pattern))) + ph = ph->next; + } + + /* then if not found */ + if (ph == NULL) { + /* look in glob patterns for the best match */ + s = 0; + iph = set->globs; + while(iph) { + g = match(iph->handler.pattern, txt); + if (g > s) { + s = g; + ph = iph; + } + iph = iph->next; + } + } + return ph ? &ph->handler : NULL; +} + diff --git a/src/globset.h b/src/globset.h new file mode 100644 index 00000000..40ed2fad --- /dev/null +++ b/src/globset.h @@ -0,0 +1,56 @@ +/* + * Copyright (C) 2018 "IoT.bzh" + * Author: José Bollo <jose.bollo@iot.bzh> + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#pragma once + +struct globset_handler +{ + /* callback of the handler */ + void *callback; + + /* closure of the handler */ + void *closure; + + /* the pattern */ + char pattern[1]; +}; + +struct globset; + +extern struct globset *globset_create(); + +extern void globset_destroy(struct globset *set); + +extern int globset_add( + struct globset *set, + const char *pattern, + void *callback, + void *closure); + +extern int globset_del( + struct globset *set, + const char *pattern, + void **closure); + +extern struct globset_handler *globset_search( + struct globset *set, + const char *pattern); + +extern const struct globset_handler *globset_match( + struct globset *set, + const char *text); + diff --git a/src/tests/CMakeLists.txt b/src/tests/CMakeLists.txt index b516a9db..b0ddbdbf 100644 --- a/src/tests/CMakeLists.txt +++ b/src/tests/CMakeLists.txt @@ -25,6 +25,7 @@ if(check_FOUND) add_subdirectory(apiset) add_subdirectory(apiv3) add_subdirectory(wrap-json) + add_subdirectory(globset) else(check_FOUND) MESSAGE(WARNING "check not found! no test!") endif(check_FOUND) diff --git a/src/tests/globset/CMakeLists.txt b/src/tests/globset/CMakeLists.txt new file mode 100644 index 00000000..6bc9e600 --- /dev/null +++ b/src/tests/globset/CMakeLists.txt @@ -0,0 +1,23 @@ +########################################################################### +# Copyright (C) 2017, 2018 "IoT.bzh" +# +# author: José Bollo <jose.bollo@iot.bzh> +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. +########################################################################### + +add_executable(test-globset test-globset.c) +target_include_directories(test-globset PRIVATE ../..) +target_link_libraries(test-globset afb-lib ${link_libraries}) +add_test(NAME globset COMMAND test-globset) + diff --git a/src/tests/globset/globset.in b/src/tests/globset/globset.in new file mode 100644 index 00000000..3aa5bd52 --- /dev/null +++ b/src/tests/globset/globset.in @@ -0,0 +1,30 @@ +kilil +?kilil ++kilil +kilil +?kilil +kil +-error ++kilil +-kilil ++kilil ++kilil ++kil* +kilil +kililo ++*/* +ryjt +rthetrfh +trhzrt/rztyrt ++zer*o* +zero +zerksdjfhkjdsffbhqkdbfdozz +zer/o ++a* ++az* ++aze* +alij +azdfbgfhnb +az +azefgnjfghn,dfnh +qsd diff --git a/src/tests/globset/globset.out b/src/tests/globset/globset.out new file mode 100644 index 00000000..e0f4c074 --- /dev/null +++ b/src/tests/globset/globset.out @@ -0,0 +1,30 @@ +match [kilil]: NOT FOUND +search [kilil]: NOT FOUND +add [kilil]: 0, Success +match [kilil]: found by kilil +search [kilil]: found +match [kil]: NOT FOUND +del [error]: -1, No such file or directory +add [kilil]: -1, File exists +del [kilil]: 0, Success +add [kilil]: 0, Success +add [kilil]: -1, File exists +add [kil*]: 0, Success +match [kilil]: found by kilil +match [kililo]: found by kil* +add [*/*]: 0, Success +match [ryjt]: NOT FOUND +match [rthetrfh]: NOT FOUND +match [trhzrt/rztyrt]: found by */* +add [zer*o*]: 0, Success +match [zero]: found by zer*o* +match [zerksdjfhkjdsffbhqkdbfdozz]: found by zer*o* +match [zer/o]: found by zer*o* +add [a*]: 0, Success +add [az*]: 0, Success +add [aze*]: 0, Success +match [alij]: found by a* +match [azdfbgfhnb]: found by az* +match [az]: found by az* +match [azefgnjfghn,dfnh]: found by aze* +match [qsd]: NOT FOUND diff --git a/src/tests/globset/test-globset.c b/src/tests/globset/test-globset.c new file mode 100644 index 00000000..6369332a --- /dev/null +++ b/src/tests/globset/test-globset.c @@ -0,0 +1,60 @@ +/* + * Copyright (C) 2018 "IoT.bzh" + * Author: José Bollo <jose.bollo@iot.bzh> + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#define _GNU_SOURCE + +#include <stdio.h> +#include <string.h> +#include <errno.h> + +#include "globset.h" + +int main() +{ + int rc; + char buffer[1024], *str; + const struct globset_handler *gh; + struct globset *set; + + setvbuf(stdout, NULL, _IOLBF, 0); + set = globset_create(); + while (fgets(buffer, sizeof buffer, stdin)) { + str = strchr(buffer,'\n'); + if (str) *str = 0; + errno = 0; + switch (buffer[0]) { + case '+': + rc = globset_add(set, &buffer[1], NULL, NULL); + printf("add [%s]: %d, %m\n", &buffer[1], rc); + break; + case '-': + rc = globset_del(set, &buffer[1], NULL); + printf("del [%s]: %d, %m\n", &buffer[1], rc); + break; + case '?': + gh = globset_search(set, &buffer[1]); + printf("search [%s]: %s%s\n", &buffer[1], gh ? "found " : "NOT FOUND", gh ? gh->pattern : ""); + break; + default: + gh = globset_match(set, buffer); + printf("match [%s]: %s%s\n", buffer, gh ? "found by " : "NOT FOUND", gh ? gh->pattern : ""); + break; + } + } + globset_destroy(set); + return 0; +} |