/*
* Copyright (c) 2012 Martin Sucha
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* - The name of the author may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
/** @addtogroup edit
* @{
*/
/**
* @file
* @brief Simple searching facility.
*/
#include <errno.h>
#include <stdlib.h>
#include <stddef.h>
#include <types/common.h>
#include "search.h"
#include "search_impl.h"
search_t *search_init(const char *pattern, void *client_data, search_ops_t ops,
bool reverse)
{
search_t *search = calloc(1, sizeof(search_t));
if (search == NULL)
return NULL;
char32_t *p = str_to_awstr(pattern);
if (p == NULL) {
free(search);
return NULL;
}
search->pattern_length = wstr_length(p);
if (reverse) {
/* Reverse the pattern */
size_t pos, half;
half = search->pattern_length / 2;
for (pos = 0; pos < half; pos++) {
char32_t tmp = p[pos];
p[pos] = p[search->pattern_length - pos - 1];
p[search->pattern_length - pos - 1] = tmp;
}
}
search->pattern = p;
search->client_data = client_data;
search->ops = ops;
search->back_table = calloc(search->pattern_length, sizeof(ssize_t));
if (search->back_table == NULL) {
free(search->pattern);
free(search);
return NULL;
}
search->pattern_pos = 0;
search->back_table[0] = -1;
search->back_table[1] = 0;
size_t table_idx = 2;
size_t pattern_idx = 0;
while (table_idx < search->pattern_length) {
if (ops.equals(search->pattern[table_idx - 1],
search->pattern[pattern_idx])) {
pattern_idx++;
search->back_table[table_idx] = pattern_idx;
table_idx++;
} else if (pattern_idx > 0) {
pattern_idx = search->back_table[pattern_idx];
} else {
pattern_idx = 0;
table_idx++;
}
}
return search;
}
errno_t search_next_match(search_t *s, match_t *match)
{
search_equals_fn eq = s->ops.equals;
char32_t cur_char;
errno_t rc = EOK;
while ((rc = s->ops.producer(s->client_data, &cur_char)) == EOK && cur_char > 0) {
/* Deal with mismatches */
while (s->pattern_pos > 0 && !eq(cur_char, s->pattern[s->pattern_pos])) {
s->pattern_pos = s->back_table[s->pattern_pos];
}
/* Check if the character matched */
if (eq(cur_char, s->pattern[s->pattern_pos])) {
s->pattern_pos++;
if (s->pattern_pos == s->pattern_length) {
s->pattern_pos = s->back_table[s->pattern_pos];
rc = s->ops.mark(s->client_data, &match->end);
if (rc != EOK)
return rc;
match->length = s->pattern_length;
return EOK;
}
}
}
match->end = NULL;
match->length = 0;
return rc;
}
void search_fini(search_t *search)
{
free(search->pattern);
free(search->back_table);
}
bool char_exact_equals(const char32_t a, const char32_t b)
{
return a == b;
}
/** @}
*/