comparison: ucx/string.c
ucx/string.c
- changeset 236
- ffc6d0910342
- parent 235
- 7cf1e41833a2
- child 237
- 5ba9de6361ff
equal
deleted
inserted
replaced
| 235:7cf1e41833a2 | 236:ffc6d0910342 |
|---|---|
| 27 */ | 27 */ |
| 28 | 28 |
| 29 #include <stdlib.h> | 29 #include <stdlib.h> |
| 30 #include <string.h> | 30 #include <string.h> |
| 31 #include <stdarg.h> | 31 #include <stdarg.h> |
| 32 #include <stdint.h> | |
| 32 #include <ctype.h> | 33 #include <ctype.h> |
| 33 | 34 |
| 34 #include "string.h" | 35 #include "string.h" |
| 35 #include "allocator.h" | 36 #include "allocator.h" |
| 36 | 37 |
| 173 n.ptr = NULL; | 174 n.ptr = NULL; |
| 174 n.length = 0; | 175 n.length = 0; |
| 175 return n; | 176 return n; |
| 176 } | 177 } |
| 177 | 178 |
| 179 typedef size_t(*prefix_table_rfun)(void*,size_t); | |
| 180 typedef void(*prefix_table_wfun)(void*,size_t,size_t); | |
| 181 | |
| 182 static size_t s_prefix_table_r(void* table, size_t index) { | |
| 183 return (size_t) ((uint8_t*)table)[index]; | |
| 184 } | |
| 185 static void s_prefix_table_w(void* table, size_t index, size_t value) { | |
| 186 ((uint8_t*)table)[index] = (uint8_t) value; | |
| 187 } | |
| 188 static size_t h_prefix_table_r(void* table, size_t index) { | |
| 189 return ((size_t*)table)[index]; | |
| 190 } | |
| 191 static void h_prefix_table_w(void* table, size_t index, size_t value) { | |
| 192 ((size_t*)table)[index] = value; | |
| 193 } | |
| 194 | |
| 178 sstr_t sstrstr(sstr_t string, sstr_t match) { | 195 sstr_t sstrstr(sstr_t string, sstr_t match) { |
| 179 if (match.length == 0) { | 196 if (match.length == 0) { |
| 180 return string; | 197 return string; |
| 181 } | 198 } |
| 182 | 199 |
| 183 for (size_t i = 0 ; i < string.length ; i++) { | 200 /* prepare default return value in case of no match */ |
| 184 sstr_t substr = sstrsubs(string, i); | 201 sstr_t result = sstrn(NULL, 0); |
| 185 if (sstrprefix(substr, match)) { | 202 |
| 186 return substr; | 203 /* |
| 187 } | 204 * IMPORTANT: |
| 188 } | 205 * our prefix table contains the prefix length PLUS ONE |
| 189 | 206 * this is our decision, because we want to use the full range of size_t |
| 190 sstr_t emptystr; | 207 * the original algorithm needs a (-1) at one single place |
| 191 emptystr.length = 0; | 208 * and we want to avoid that |
| 192 emptystr.ptr = NULL; | 209 */ |
| 193 return emptystr; | 210 |
| 211 /* static prefix table */ | |
| 212 static uint8_t s_prefix_table[256]; | |
| 213 | |
| 214 /* check pattern length and use appropriate prefix table */ | |
| 215 register void* ptable; | |
| 216 prefix_table_rfun ptable_r; | |
| 217 prefix_table_wfun ptable_w; | |
| 218 if (match.length > 255) { | |
| 219 /* pattern exceeds static prefix table, allocate on the heap */ | |
| 220 ptable = calloc(match.length+1, sizeof(size_t)); | |
| 221 ptable_r = h_prefix_table_r; | |
| 222 ptable_w = h_prefix_table_w; | |
| 223 } else { | |
| 224 ptable = s_prefix_table; | |
| 225 ptable_r = s_prefix_table_r; | |
| 226 ptable_w = s_prefix_table_w; | |
| 227 } | |
| 228 | |
| 229 /* keep counter in registers */ | |
| 230 register size_t i, j; | |
| 231 | |
| 232 /* fill prefix table */ | |
| 233 i = 0; j = 0; | |
| 234 ptable_w(ptable, i, j); | |
| 235 while (i < match.length) { | |
| 236 while (j >= 1 && match.ptr[j-1] != match.ptr[i]) { | |
| 237 j = ptable_r(ptable, j-i); | |
| 238 } | |
| 239 i++; j++; | |
| 240 ptable_w(ptable, i, j); | |
| 241 } | |
| 242 | |
| 243 /* search */ | |
| 244 i = 0; j = 1; | |
| 245 while (i < string.length) { | |
| 246 while (j >= 1 && string.ptr[i] != match.ptr[j-1]) { | |
| 247 j = ptable_r(ptable, j-1); | |
| 248 } | |
| 249 i++; j++; | |
| 250 if (j-1 == match.length) { | |
| 251 size_t start = i - match.length; | |
| 252 result.ptr = string.ptr + start; | |
| 253 result.length = string.length - start; | |
| 254 break; | |
| 255 } | |
| 256 } | |
| 257 | |
| 258 /* if prefix table was allocated on the heap, free it */ | |
| 259 if (ptable != s_prefix_table) { | |
| 260 free(ptable); | |
| 261 } | |
| 262 | |
| 263 return result; | |
| 194 } | 264 } |
| 195 | 265 |
| 196 sstr_t* sstrsplit(sstr_t s, sstr_t d, ssize_t *n) { | 266 sstr_t* sstrsplit(sstr_t s, sstr_t d, ssize_t *n) { |
| 197 return sstrsplit_a(ucx_default_allocator(), s, d, n); | 267 return sstrsplit_a(ucx_default_allocator(), s, d, n); |
| 198 } | 268 } |
