my_str_str.c

gistfile1.txt

#ifndef MY_STR_STR
#define MY_STR_STR

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>

#define NO_KEEP_TRACK_OF_TIME 1

#ifdef KEEP_TRACK_OF_TIME
double proc_alloc;
double proc_sort;
double proc_fill;
double proc_seeker_cicle;
#endif

struct header;
struct element;
struct good;

char* my_strstr(const char *str_par, const char *pat_par,
                          size_t str_len, size_t pat_len);
char * seeker_cicle_strstr(unsigned char *str,
                           unsigned char *pat,
                           struct good *g,
                           size_t str_len,
                           size_t plen);
size_t GetBufferSizeForGood(size_t elements_length);
struct good* CreateGood(void* buf, size_t elements_len);
void AddElementToGood(struct good *g, unsigned char ch, size_t index);
void GoodSort(struct good* g,const char *str, size_t len);


struct header{
    size_t count;
    size_t end_el;
    size_t first_el;
};
struct element{
    size_t index;
    size_t next_el;
};
struct good{
    struct header headers[256];
    //нулевой элемент всегда не используется
    //чтоб проще было
    struct element* elements;
    size_t last_not_used_el;
    size_t elements_len;
};


char* my_strstr(const char *str_par, const char *pat_par,
                          size_t str_len, size_t pat_len)
{
#ifdef KEEP_TRACK_OF_TIME
    clock_t time_begin = clock();
#endif
    const unsigned char *str = str_par;
    const unsigned char * pat = pat_par;

    if(sizeof(char)!=1){
        //Не предусмотренно
        perror("sizeof(char)!=1");
    }

    size_t plen = pat_len;

    if(str == NULL || pat == NULL){
        return (NULL);
    }

    if(str_len < pat_len || str_len == 0 || pat_len == 0){
        return (NULL);
    }

    //Выделяем память
    size_t sum_len = GetBufferSizeForGood(pat_len);

    void *m = NULL;
    struct good* g = NULL;

    m = malloc(sum_len);
    memset(m, 0, sum_len);
    if(m == NULL){
        perror("memory allocation failure in my_str_str");
        return (NULL);
    }
#ifdef KEEP_TRACK_OF_TIME
    clock_t time_after_allock = clock();
#endif

    //
    g = CreateGood(m, pat_len);
    GoodSort(g, pat, pat_len);

#ifdef KEEP_TRACK_OF_TIME
    clock_t time_after_fill = clock();
#endif

#ifdef KEEP_TRACK_OF_TIME
    clock_t time_after_sort = clock();
#endif

    char *found = seeker_cicle_strstr(str, pat, g, str_len, plen);
    free(m);

#ifdef KEEP_TRACK_OF_TIME
    clock_t seeker_cicle_time = clock();
    clock_t full_time = seeker_cicle_time - time_begin;
    proc_alloc = (double) (time_after_allock-time_begin)/(double)full_time;
    proc_fill = (double) (time_after_fill-time_after_allock) / (double)full_time;
    proc_sort = (double)(time_after_sort - time_after_fill)/ (double)full_time;
    proc_seeker_cicle = (double) (seeker_cicle_time-time_after_sort)/ (double) full_time;
#endif

    return found;
}

//цикл поиска
inline char * seeker_cicle_strstr(unsigned char *str,
                                  unsigned char *pat,
                                  struct good *g,
                                  size_t str_len,
                                  size_t plen)
{
    struct element *elements = g->elements;
    char *str_adr;
    char *str_end = str+str_len;
    unsigned char* pat_end = pat + plen;
    for (str_adr = str; str_adr < str_end; str_adr+=plen)
    {
        //
        unsigned char chan_char = (*str_adr);
        struct header *h = &(g->headers[chan_char]);
        if (h->count > 0) {
            //
            int ind = h->first_el;
            //
            do {
                int el_ind = elements[ind].index;

                if(el_ind <= str_adr)
                {
                    unsigned char* begin_this_pos = str_adr - el_ind;
                    if (begin_this_pos >= str)
                    {
                        unsigned char* str_pos = begin_this_pos;
                        unsigned char* pat_pos = pat;

                        for (; pat_pos < pat_end && (*str_pos) == (*pat_pos); pat_pos++, str_pos++);
                        if (pat_pos == pat_end){
                            return begin_this_pos;
                        }
                    }
                }
                ind = elements[ind].next_el;
            } while (ind != 0);
        }
    }
    return (NULL);
}

inline size_t GetBufferSizeForGood(size_t elements_length){
    //на один элемент больше, так как нулевой не используется
    return sizeof(struct good) + sizeof(struct element)*(elements_length+1);
}

inline struct good* CreateGood(void* buf, size_t elements_len){
    struct good* n_good = (struct good*)buf;
    n_good->elements = buf+sizeof(struct good);
    n_good->last_not_used_el = 1;
    n_good->elements_len = elements_len;

    return n_good;
}

inline void AddElementToGood(struct good *g, unsigned char ch, size_t index){

    struct header *h = &(g->headers[ch]);
    h->count++;

    size_t cur_el_index = g->last_not_used_el;
    struct element *el = &(g->elements[cur_el_index]);
    el->index = index;

    if(h->first_el == 0){
        h->first_el = cur_el_index;
        h->end_el = cur_el_index;
    }
    else{
        struct element *last_el = &(g->elements[h->end_el]);
        last_el->next_el = cur_el_index;
        h->end_el = cur_el_index;
    }
    //
    g->last_not_used_el++;
}

//Хорошая сортировка
inline void GoodSort(struct good* g,const char *str, size_t len)
{
    //
    size_t i;
    for(i=0; i<len; i++)
        AddElementToGood(g,str[i],i);
}
int flag;


#endif // MY_STR_STR