← Back to branch summary

~ctwm/ctwm/trunk

« back to all changes in this revision

Viewing changes to ext/repl_str.c

  • Committer: Matthew Fuller
  • Date: 2016-01-25 01:46:38 UTC
  • mto: This revision was merged to the branch mainline in revision 427.
  • Revision ID: fullermd@over-yonder.net-20160125014638-u174wm6ct3p0qtwi
Add a dir to hold externally-sourced code, and bring in an
implementation of substring replacement.  The optimization in this
version is stupid overkill for what we'll need it for, but what the
heck.  No reason to go to the trouble of rolling our own.  Explicitly
in the public domain.

Show diffs side-by-side

added added

removed removed

Lines of Context:
ext/repl_str.c
 
1
/*
 
2
 * An implementation of replacing substrings in a string.
 
3
 *
 
4
 * Source: http://creativeandcritical.net/str-replace-c
 
5
 * Author: Laird Shaw
 
6
 * License: Public domain
 
7
 *
 
8
 * Brought on 2016-02-24
 
9
 */
 
10
 
 
11
#include <string.h>
 
12
#include <stdlib.h>
 
13
#include <stddef.h>
 
14
 
 
15
#include "repl_str.h"
 
16
 
 
17
 
 
18
/* An optimised string replacement function that caches string positions so that
 
19
 * strstr() doesn't need to be called twice for each position.
 
20
 * 
 
21
 * This code is entirely by me, and released into the public domain, so have no
 
22
 * doubts about your right to use it.
 
23
 */
 
24
char *replace_substr(const char *str, const char *old, const char *new) {
 
25
 
 
26
        /* Adjust each of the below values to suit your needs. */
 
27
 
 
28
        /* Increment positions cache size initially by this number. */
 
29
        size_t cache_sz_inc = 16;
 
30
        /* Thereafter, each time capacity needs to be increased,
 
31
         * multiply the increment by this factor. */
 
32
        const size_t cache_sz_inc_factor = 3;
 
33
        /* But never increment capacity by more than this number. */
 
34
        const size_t cache_sz_inc_max = 1048576;
 
35
 
 
36
        char *pret, *ret = NULL;
 
37
        const char *pstr2, *pstr = str;
 
38
        size_t i, count = 0;
 
39
        ptrdiff_t *pos_cache = NULL;
 
40
        size_t cache_sz = 0;
 
41
        size_t cpylen, orglen, retlen, newlen, oldlen = strlen(old);
 
42
 
 
43
        /* Find all matches and cache their positions. */
 
44
        while ((pstr2 = strstr(pstr, old)) != NULL) {
 
45
                count++;
 
46
 
 
47
                /* Increase the cache size when necessary. */
 
48
                if (cache_sz < count) {
 
49
                        cache_sz += cache_sz_inc;
 
50
                        pos_cache = realloc(pos_cache, sizeof(*pos_cache) * cache_sz);
 
51
                        if (pos_cache == NULL) {
 
52
                                goto end_repl_str;
 
53
                        }
 
54
                        cache_sz_inc *= cache_sz_inc_factor;
 
55
                        if (cache_sz_inc > cache_sz_inc_max) {
 
56
                                cache_sz_inc = cache_sz_inc_max;
 
57
                        }
 
58
                }
 
59
 
 
60
                pos_cache[count-1] = pstr2 - str;
 
61
                pstr = pstr2 + oldlen;
 
62
        }
 
63
 
 
64
        orglen = pstr - str + strlen(pstr);
 
65
 
 
66
        /* Allocate memory for the post-replacement string. */
 
67
        if (count > 0) {
 
68
                newlen = strlen(new);
 
69
                retlen = orglen + (newlen - oldlen) * count;
 
70
        } else  retlen = orglen;
 
71
        ret = malloc(retlen + 1);
 
72
        if (ret == NULL) {
 
73
                goto end_repl_str;
 
74
        }
 
75
 
 
76
        if (count == 0) {
 
77
                /* If no matches, then just duplicate the string. */
 
78
                strcpy(ret, str);
 
79
        } else {
 
80
                /* Otherwise, duplicate the string whilst performing
 
81
                 * the replacements using the position cache. */
 
82
                pret = ret;
 
83
                memcpy(pret, str, pos_cache[0]);
 
84
                pret += pos_cache[0];
 
85
                for (i = 0; i < count; i++) {
 
86
                        memcpy(pret, new, newlen);
 
87
                        pret += newlen;
 
88
                        pstr = str + pos_cache[i] + oldlen;
 
89
                        cpylen = (i == count-1 ? orglen : pos_cache[i+1]) - pos_cache[i] - oldlen;
 
90
                        memcpy(pret, pstr, cpylen);
 
91
                        pret += cpylen;
 
92
                }
 
93
                ret[retlen] = '\0';
 
94
        }
 
95
 
 
96
end_repl_str:
 
97
        /* Free the cache and return the post-replacement string,
 
98
         * which will be NULL in the event of an error. */
 
99
        free(pos_cache);
 
100
        return ret;
 
101
}