comparison: src/string.c
src/string.c
- changeset 580
- aac47db8da0b
- parent 579
- bbc46dcd5255
- child 581
- c067394737ca
equal
deleted
inserted
replaced
| 579:bbc46dcd5255 | 580:aac47db8da0b |
|---|---|
| 123 free(strings); | 123 free(strings); |
| 124 | 124 |
| 125 return result; | 125 return result; |
| 126 } | 126 } |
| 127 | 127 |
| 128 | 128 cxstring cx_strsubs( |
| 129 | 129 cxstring string, |
| 130 size_t start | |
| 131 ) { | |
| 132 return cx_strsubsl(string, start, string.length - start); | |
| 133 } | |
| 134 | |
| 135 cxmutstr cx_strsubs_m( | |
| 136 cxmutstr string, | |
| 137 size_t start | |
| 138 ) { | |
| 139 return cx_strsubsl_m(string, start, string.length - start); | |
| 140 } | |
| 141 | |
| 142 cxstring cx_strsubsl( | |
| 143 cxstring string, | |
| 144 size_t start, | |
| 145 size_t length | |
| 146 ) { | |
| 147 if (start > string.length) { | |
| 148 return (cxstring) {NULL, 0}; | |
| 149 } | |
| 150 | |
| 151 size_t rem_len = string.length - start; | |
| 152 if (length > rem_len) { | |
| 153 length = rem_len; | |
| 154 } | |
| 155 | |
| 156 return (cxstring) {string.ptr + start, length}; | |
| 157 } | |
| 158 | |
| 159 cxmutstr cx_strsubsl_m( | |
| 160 cxmutstr string, | |
| 161 size_t start, | |
| 162 size_t length | |
| 163 ) { | |
| 164 cxstring result = cx_strsubsl(cx_strcast(string), start, length); | |
| 165 return (cxmutstr) {(char *) result.ptr, result.length}; | |
| 166 } | |
| 167 | |
| 168 cxstring cx_strchr( | |
| 169 cxstring string, | |
| 170 int chr | |
| 171 ) { | |
| 172 chr = 0xFF & chr; | |
| 173 // TODO: improve by comparing multiple bytes at once | |
| 174 cx_for_n(i, string.length) { | |
| 175 if (string.ptr[i] == chr) { | |
| 176 return cx_strsubs(string, i); | |
| 177 } | |
| 178 } | |
| 179 return (cxstring) {NULL, 0}; | |
| 180 } | |
| 181 | |
| 182 cxmutstr cx_strchr_m( | |
| 183 cxmutstr string, | |
| 184 int chr | |
| 185 ) { | |
| 186 cxstring result = cx_strchr(cx_strcast(string), chr); | |
| 187 return (cxmutstr) {(char *) result.ptr, result.length}; | |
| 188 } | |
| 189 | |
| 190 cxstring cx_strrchr( | |
| 191 cxstring string, | |
| 192 int chr | |
| 193 ) { | |
| 194 chr = 0xFF & chr; | |
| 195 size_t i = string.length; | |
| 196 while (i > 0) { | |
| 197 i--; | |
| 198 // TODO: improve by comparing multiple bytes at once | |
| 199 if (string.ptr[i] == chr) { | |
| 200 return cx_strsubs(string, i); | |
| 201 } | |
| 202 } | |
| 203 return (cxstring) {NULL, 0}; | |
| 204 } | |
| 205 | |
| 206 cxmutstr cx_strrchr_m( | |
| 207 cxmutstr string, | |
| 208 int chr | |
| 209 ) { | |
| 210 cxstring result = cx_strrchr(cx_strcast(string), chr); | |
| 211 return (cxmutstr) {(char *) result.ptr, result.length}; | |
| 212 } | |
| 213 | |
| 214 #define ptable_r(dest, useheap, ptable, index) (dest = useheap ? \ | |
| 215 ((size_t*)ptable)[index] : (size_t) ((uint8_t*)ptable)[index]) | |
| 216 | |
| 217 #define ptable_w(useheap, ptable, index, src) do {\ | |
| 218 if (!useheap) ((uint8_t*)ptable)[index] = (uint8_t) src;\ | |
| 219 else ((size_t*)ptable)[index] = src;\ | |
| 220 } while (0) | |
| 221 | |
| 222 | |
| 223 cxstring cx_strstr( | |
| 224 cxstring haystack, | |
| 225 cxstring needle | |
| 226 ) { | |
| 227 if (needle.length == 0) { | |
| 228 return haystack; | |
| 229 } | |
| 230 | |
| 231 /* | |
| 232 * IMPORTANT: | |
| 233 * Our prefix table contains the prefix length PLUS ONE | |
| 234 * this is our decision, because we want to use the full range of size_t. | |
| 235 * The original algorithm needs a (-1) at one single place, | |
| 236 * and we want to avoid that. | |
| 237 */ | |
| 238 | |
| 239 /* static prefix table */ | |
| 240 static uint8_t s_prefix_table[512]; | |
| 241 | |
| 242 /* check pattern length and use appropriate prefix table */ | |
| 243 /* if the pattern exceeds static prefix table, allocate on the heap */ | |
| 244 register int useheap = needle.length >= 512; | |
| 245 register void *ptable = useheap ? calloc(needle.length + 1, | |
| 246 sizeof(size_t)) : s_prefix_table; | |
| 247 | |
| 248 /* keep counter in registers */ | |
| 249 register size_t i, j; | |
| 250 | |
| 251 /* fill prefix table */ | |
| 252 i = 0; | |
| 253 j = 0; | |
| 254 ptable_w(useheap, ptable, i, j); | |
| 255 while (i < needle.length) { | |
| 256 while (j >= 1 && needle.ptr[j - 1] != needle.ptr[i]) { | |
| 257 ptable_r(j, useheap, ptable, j - 1); | |
| 258 } | |
| 259 i++; | |
| 260 j++; | |
| 261 ptable_w(useheap, ptable, i, j); | |
| 262 } | |
| 263 | |
| 264 /* search */ | |
| 265 cxstring result = {NULL, 0}; | |
| 266 i = 0; | |
| 267 j = 1; | |
| 268 while (i < haystack.length) { | |
| 269 while (j >= 1 && haystack.ptr[i] != needle.ptr[j - 1]) { | |
| 270 ptable_r(j, useheap, ptable, j - 1); | |
| 271 } | |
| 272 i++; | |
| 273 j++; | |
| 274 if (j - 1 == needle.length) { | |
| 275 size_t start = i - needle.length; | |
| 276 result.ptr = haystack.ptr + start; | |
| 277 result.length = haystack.length - start; | |
| 278 break; | |
| 279 } | |
| 280 } | |
| 281 | |
| 282 /* if prefix table was allocated on the heap, free it */ | |
| 283 if (ptable != s_prefix_table) { | |
| 284 free(ptable); | |
| 285 } | |
| 286 | |
| 287 return result; | |
| 288 } | |
| 289 | |
| 290 cxmutstr cx_strstr_m( | |
| 291 cxmutstr haystack, | |
| 292 cxstring needle | |
| 293 ) { | |
| 294 cxstring result = cx_strstr(cx_strcast(haystack), needle); | |
| 295 return (cxmutstr) {(char *) result.ptr, result.length}; | |
| 296 } | |
| 297 | |
| 298 size_t cx_strsplit( | |
| 299 cxstring string, | |
| 300 cxstring delim, | |
| 301 size_t limit, | |
| 302 cxstring *output | |
| 303 ) { | |
| 304 // TODO: implement | |
| 305 return 0; | |
| 306 } | |
| 307 | |
| 308 size_t cx_strsplit_a( | |
| 309 CxAllocator *allocator, | |
| 310 cxstring string, | |
| 311 cxstring delim, | |
| 312 size_t limit, | |
| 313 cxstring **output | |
| 314 ) { | |
| 315 // TODO: implement | |
| 316 return 0; | |
| 317 } | |
| 318 | |
| 319 size_t cx_strsplit_m( | |
| 320 cxmutstr string, | |
| 321 cxstring delim, | |
| 322 size_t limit, | |
| 323 cxmutstr *output | |
| 324 ) { | |
| 325 return cx_strsplit(cx_strcast(string), | |
| 326 delim, limit, (cxstring *) output); | |
| 327 } | |
| 328 | |
| 329 size_t cx_strsplit_ma( | |
| 330 CxAllocator *allocator, | |
| 331 cxmutstr string, | |
| 332 cxstring delim, | |
| 333 size_t limit, | |
| 334 cxmutstr **output | |
| 335 ) { | |
| 336 return cx_strsplit_a(allocator, cx_strcast(string), | |
| 337 delim, limit, (cxstring **) output); | |
| 338 } |
