fork(1) download

copy

char *volnitsky_strstr(const char *haystack, const char *needle)
{
    // Only for little-endian platforms and where access to misaligned W is
    // allowed.
 
    typedef         uint16_t        W_t;
    typedef         uint8_t         offset_t;
 
    const size_t W_size         = sizeof(W_t)
               , haystack_len   = strlen(haystack)
               , needle_len     = strlen(needle)
               , step           = needle_len - W_size + 1;
 
    int          i;
    size_t       h;
 
    if (needle_len < 2*W_size-1 || needle_len >= UINT8_MAX)
        return strstr(haystack, needle); // fall-back to stdlib search.
 
    // Make the hash table
    const size_t H_size         = 65536;
    offset_t     H[65536]       = {0};     // initializes ALL buckets with 0
 
    for (i = needle_len - W_size; i >= 0; i--) {
        h = *((W_t *) (needle + i)) % H_size;
 
        while (H[h])
            h = (h+1) % H_size; // find free cell
 
        H[h] = i+1;
    }
 
    // step through text
    const char *P       = haystack + needle_len   - W_size
             , *P_end   = haystack + haystack_len - needle_len;
    for (; P <= P_end; P += step) {
        for (h = *((W_t*) P) % H_size; H[h]; h = (h+1) % H_size) {
            const char* R = P - (H[h] - 1);
 
            for (i = 0; i < needle_len; i++) {
                if (R[i] != needle[i])
                    goto next_hash_cell;
            }
            return (char *) R; // found
 
            next_hash_cell:;
        }
    }
 
    // check tail
    return strstr(P - step + 1, needle);
}

prog.cpp: In function 'char* volnitsky_strstr(const char*, const char*)':
prog.cpp:6:21: error: 'uint16_t' does not name a type
     typedef         uint16_t        W_t;
                     ^
prog.cpp:7:21: error: 'uint8_t' does not name a type
     typedef         uint8_t         offset_t;
                     ^
prog.cpp:9:11: error: 'size_t' does not name a type
     const size_t W_size         = sizeof(W_t)
           ^
prog.cpp:15:5: error: 'size_t' was not declared in this scope
     size_t       h;
     ^
prog.cpp:17:9: error: 'needle_len' was not declared in this scope
     if (needle_len < 2*W_size-1 || needle_len >= UINT8_MAX)
         ^
prog.cpp:17:24: error: 'W_size' was not declared in this scope
     if (needle_len < 2*W_size-1 || needle_len >= UINT8_MAX)
                        ^
prog.cpp:17:50: error: 'UINT8_MAX' was not declared in this scope
     if (needle_len < 2*W_size-1 || needle_len >= UINT8_MAX)
                                                  ^
prog.cpp:18:39: error: 'strstr' was not declared in this scope
         return strstr(haystack, needle); // fall-back to stdlib search.
                                       ^
prog.cpp:21:11: error: 'size_t' does not name a type
     const size_t H_size         = 65536;
           ^
prog.cpp:22:5: error: 'offset_t' was not declared in this scope
     offset_t     H[65536]       = {0};     // initializes ALL buckets with 0
     ^
prog.cpp:24:14: error: 'needle_len' was not declared in this scope
     for (i = needle_len - W_size; i >= 0; i--) {
              ^
prog.cpp:24:27: error: 'W_size' was not declared in this scope
     for (i = needle_len - W_size; i >= 0; i--) {
                           ^
prog.cpp:25:9: error: 'h' was not declared in this scope
         h = *((W_t *) (needle + i)) % H_size;
         ^
prog.cpp:25:16: error: 'W_t' was not declared in this scope
         h = *((W_t *) (needle + i)) % H_size;
                ^
prog.cpp:25:21: error: expected primary-expression before ')' token
         h = *((W_t *) (needle + i)) % H_size;
                     ^
prog.cpp:25:39: error: 'H_size' was not declared in this scope
         h = *((W_t *) (needle + i)) % H_size;
                                       ^
prog.cpp:27:16: error: 'H' was not declared in this scope
         while (H[h])
                ^
prog.cpp:30:9: error: 'H' was not declared in this scope
         H[h] = i+1;
         ^
prog.cpp:34:38: error: 'needle_len' was not declared in this scope
     const char *P       = haystack + needle_len   - W_size
                                      ^
prog.cpp:34:53: error: 'W_size' was not declared in this scope
     const char *P       = haystack + needle_len   - W_size
                                                     ^
prog.cpp:36:17: error: 'P_end' was not declared in this scope
     for (; P <= P_end; P += step) {
                 ^
prog.cpp:36:29: error: 'step' was not declared in this scope
     for (; P <= P_end; P += step) {
                             ^
prog.cpp:37:14: error: 'h' was not declared in this scope
         for (h = *((W_t*) P) % H_size; H[h]; h = (h+1) % H_size) {
              ^
prog.cpp:37:21: error: 'W_t' was not declared in this scope
         for (h = *((W_t*) P) % H_size; H[h]; h = (h+1) % H_size) {
                     ^
prog.cpp:37:25: error: expected primary-expression before ')' token
         for (h = *((W_t*) P) % H_size; H[h]; h = (h+1) % H_size) {
                         ^
prog.cpp:37:27: error: expected ')' before 'P'
         for (h = *((W_t*) P) % H_size; H[h]; h = (h+1) % H_size) {
                           ^
prog.cpp:37:40: error: 'H' was not declared in this scope
         for (h = *((W_t*) P) % H_size; H[h]; h = (h+1) % H_size) {
                                        ^
prog.cpp:37:58: error: 'H_size' was not declared in this scope
         for (h = *((W_t*) P) % H_size; H[h]; h = (h+1) % H_size) {
                                                          ^
prog.cpp:51:23: error: 'step' was not declared in this scope
     return strstr(P - step + 1, needle);
                       ^
prog.cpp:51:39: error: 'strstr' was not declared in this scope
     return strstr(P - step + 1, needle);
                                       ^

Standard output is empty