src/tadsearch.c

   1 /*
   2  * tadsearch.c
   3  *
   4  * Copyright (c) 2011 project bchan
   5  *
   6  * This software is provided 'as-is', without any express or implied
   7  * warranty. In no event will the authors be held liable for any damages
   8  * arising from the use of this software.
   9  *
  10  * Permission is granted to anyone to use this software for any purpose,
  11  * including commercial applications, and to alter it and redistribute it
  12  * freely, subject to the following restrictions:
  13  *
  14  * 1. The origin of this software must not be misrepresented; you must not
  15  *    claim that you wrote the original software. If you use this software
  16  *    in a product, an acknowledgment in the product documentation would be
  17  *    appreciated but is not required.
  18  *
  19  * 2. Altered source versions must be plainly marked as such, and must not be
  20  *    misrepresented as being the original software.
  21  *
  22  * 3. This notice may not be removed or altered from any source
  23  *    distribution.
  24  *
  25  */
  26
  27 #include    "tadsearch.h"
  28 #include    "tadlib.h"
  29
  30 #include        <bstdio.h>
  31 #include        <bstdlib.h>
  32 #include        <tstring.h>
  33
  34 /* http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%93%E3%83%B3-%E3%82%AB%E3%83%BC%E3%83%97%E6%96%87%E5%AD%97%E5%88%97%E6%A4%9C%E7%B4%A2%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0 */
  35
  36 /* Rabin-Karp String Search Algorithm */
  37
  38 struct tcloopbuf_t_ {
  39         W len;
  40         W pos;
  41         TC buf[1];
  42 };
  43 typedef struct tcloopbuf_t_ tcloopbuf_t;
  44
  45 LOCAL TC tcloopbuf_getbackchar(tcloopbuf_t *loopbuf, W n)
  46 {
  47         return loopbuf->buf[(loopbuf->pos - 1 - n) % loopbuf->len];
  48 }
  49
  50 LOCAL Bool tcloopbuf_compairtail(tcloopbuf_t *loopbuf, tcstrbuffer_t *str)
  51 {
  52         W i;
  53         TC ch_buf, ch_str;
  54
  55         for (i = 0; i < str->strlen; i++) {
  56                 ch_buf = loopbuf->buf[(loopbuf->pos - 1 - i) % loopbuf->len];
  57                 ch_str = str->buffer[(str->strlen - 1 - i)];
  58                 if (ch_buf != ch_str) {
  59                         return False;
  60                 }
  61         }
  62         return True;
  63 }
  64
  65 LOCAL VOID tcloopbuf_putchar(tcloopbuf_t *loopbuf, TC ch)
  66 {
  67         loopbuf->buf[loopbuf->pos++ % loopbuf->len] = ch;
  68 }
  69
  70 LOCAL tcloopbuf_t *tcloopbuf_new(W len)
  71 {
  72         tcloopbuf_t *loopbuf;
  73
  74         loopbuf = malloc(sizeof(tcloopbuf_t) + sizeof(W)*len);
  75         if (loopbuf == NULL) {
  76                 return NULL;
  77         }
  78
  79         loopbuf->len = len + 1;
  80         loopbuf->pos = 0;
  81
  82         return loopbuf;
  83 }
  84
  85 LOCAL VOID tcloopbuf_delete(tcloopbuf_t *loopbuf)
  86 {
  87         free(loopbuf);
  88 }
  89
  90 struct tadlib_rk_hash_t_ {
  91         tcstrbuffer_t *orig;
  92         W expectedhash;
  93         W currenthash;
  94 };
  95 typedef struct tadlib_rk_hash_t_ tadlib_rk_hash_t;
  96
  97 struct tadlib_rk_hashset_t_ {
  98         W setlen;
  99         tadlib_rk_hash_t array[1];
 100 };
 101 typedef struct tadlib_rk_hashset_t_ tadlib_rk_hashset_t;
 102
 103 LOCAL W make_expectedhash(tcstrbuffer_t *buffer)
 104 {
 105         W i, sum = 0;
 106
 107         for (i = 0; i < buffer->strlen; i++) {
 108                 sum += buffer->buffer[i];
 109         }
 110
 111         return sum;
 112 }
 113
 114 LOCAL Bool rk_hash_count(tadlib_rk_hash_t *hash, TC ch, W pos, tcloopbuf_t *loopbuf)
 115 {
 116         TC prev_ch;
 117         Bool ok;
 118
 119         if (pos < hash->orig->strlen) {
 120                 hash->currenthash += ch;
 121                 return False;
 122         }
 123
 124         if (pos == hash->orig->strlen) {
 125                 hash->currenthash += ch;
 126         } else {
 127                 prev_ch = tcloopbuf_getbackchar(loopbuf, hash->orig->strlen);
 128                 hash->currenthash += ch - prev_ch;
 129         }
 130
 131         if (hash->currenthash == hash->expectedhash) {
 132                 ok = tcloopbuf_compairtail(loopbuf, hash->orig);
 133                 if (ok == True) {
 134                         return True;
 135                 }
 136         }
 137
 138         return False;
 139 }
 140
 141 LOCAL W rk_hashset_count(tadlib_rk_hashset_t *hashset, TC ch, W pos, tcloopbuf_t *loopbuf)
 142 {
 143         W i;
 144         Bool hit;
 145
 146         for (i = 0; i < hashset->setlen; i++) {
 147                 hit = rk_hash_count(hashset->array + i, ch, pos, loopbuf);
 148                 if (hit == True) {
 149                         return i;
 150                 }
 151         }
 152
 153         return -1;
 154 }
 155
 156 LOCAL tadlib_rk_hashset_t* rk_hashset_new(tcstrbuffer_t *strset, W setlen)
 157 {
 158         tadlib_rk_hashset_t *hashset;
 159         W i;
 160
 161         hashset = malloc(sizeof(W) + (sizeof(tadlib_rk_hash_t) * setlen));
 162         if (hashset == NULL) {
 163                 return NULL;
 164         }
 165         hashset->setlen = setlen;
 166         for (i = 0; i < setlen; i++) {
 167                 hashset->array[i].orig = strset + i;
 168                 hashset->array[i].expectedhash = make_expectedhash(strset + i);
 169                 hashset->array[i].currenthash = 0;
 170         }
 171
 172         return hashset;
 173 }
 174
 175 LOCAL VOID rk_hashset_delete(tadlib_rk_hashset_t *hashset)
 176 {
 177         free(hashset);
 178 }
 179
 180 LOCAL W tadlib_rk_getmaxlenfromstrset(tcstrbuffer_t *strset, W setlen)
 181 {
 182         W i, max;
 183
 184         max = -1;
 185         for (i = 0; i < setlen; i++) {
 186                 if (strset[i].strlen > max) {
 187                         max = strset[i].strlen;
 188                 }
 189         }
 190
 191         return max;
 192 }
 193
 194 EXPORT W tadlib_rabinkarpsearch(TC *str, W len, tcstrbuffer_t *strset, W setlen, tadlib_rk_result_t *result)
 195 {
 196         taditerator_t iter;
 197         TADITERATOR_RESULT_T iter_result;
 198         TC ch, *pos;
 199         LTADSEG *seg;
 200         W size;
 201         UB *data0;
 202         W found, max, ret = 0, n;
 203         tcloopbuf_t *loopbuf;
 204         tadlib_rk_hashset_t *hashset;
 205
 206         max = tadlib_rk_getmaxlenfromstrset(strset, setlen);
 207
 208         loopbuf = tcloopbuf_new(max);
 209         if (loopbuf == NULL) {
 210                 return -1;
 211         }
 212         hashset = rk_hashset_new(strset, setlen);
 213         if (hashset == NULL) {
 214                 tcloopbuf_delete(loopbuf);
 215                 return -1;
 216         }
 217
 218         taditerator_initialize(&iter, str, len);
 219         n = 0;
 220         for (;;) {
 221                 iter_result = taditerator_next(&iter, &pos, &ch, &seg, &size, &data0);
 222                 if (iter_result == TADITERATOR_RESULT_END) {
 223                         break;
 224                 }
 225                 if (iter_result != TADITERATOR_RESULT_CHARCTOR) {
 226                         continue;
 227                 }
 228                 n++;
 229                 tcloopbuf_putchar(loopbuf, ch);
 230                 found = rk_hashset_count(hashset, ch, n, loopbuf);
 231                 if (found >= 0) {
 232                         result->i = found;
 233                         ret = 1;
 234                         break;
 235                 }
 236         }
 237         taditerator_finalize(&iter);
 238
 239         rk_hashset_delete(hashset);
 240         tcloopbuf_delete(loopbuf);
 241
 242         return ret;
 243 }