Hyperthèse

Apache Portable Runtime (APR)

June 26, 2011

Dans mon école, les 1ère année doivent coder un projet de C qui consiste à chercher des anagrammes dans un texte. Outre le fait que j’ai depuis longtemps passé la 1ère année et rendu mon projet, je m’amuse régulièrement à le re-coder pour aider les petits nouveaux ou encore pouvoir si je ferais mieux que la dernière fois.

Entre temps, j’ai découvert une librairie assez géniale, la APR (Apache Portable Runtime de son petit nom). Elle est à la base du serveur web bien connu, et propose des fonctions très intéressantes. Pour résumer grossièrement, il s’agit d’une libc améliorée, disponible sur plusieures plateformes (Linux, *BSD, Windows par exemple). Elle a comme avantage de proposer des fonctionalités plus poussées que la libc de base, comme des mmap, des threads, ou des hashtables. Mais surtout, elle a un mécanisme de gestion de la mémoire par pools très efficace, en ce sens qu’elle permet de n’oublier aucun free, ou encore d’avoir un équivalement de sprintf qui alloue tout seul la chaîne de destination.

Donc l’idée c’était de re-coder mon bidule de B23 (le projet des 1ère années) en utilisant cette librairie pour voir ce que ça donnerait. Et au passage j’ai cassé quelques consignes pour gagner un chouilla en perfs quand même. Assez bavardé, le code :

/***
 * B23 Anagrams
 *
 * Author: Rémy Sanchez <remy.sanchez@hyperthese.net>
 * Licence: WTFPL
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <ctype.h>

#include <apr-1.0/apr_general.h>
#include <apr-1.0/apr_pools.h>
#include <apr-1.0/apr_file_info.h>
#include <apr-1.0/apr_mmap.h>

#define apr_assert(expr) if((expr) != APR_SUCCESS) abort();

struct word {
        char *orig;
        char *sort;
        size_t len;
};
typedef struct word word_t;

struct anagram {
        char *word;
        size_t len;
        apr_array_header_t *l;
};
typedef struct anagram anagram_t;

struct dictionary {
        struct anagram a;
        struct dictionary *left;
        struct dictionary *right;
};
typedef struct dictionary dictionary_t;

/*
 * Returns the minimum between a and b
 */
size_t min(size_t a, size_t b) {
        return (a < b) ? a : b;
}

/*
 * mmap the specific file
 */
void map_to_mem(const char *file, apr_mmap_t **mem, apr_pool_t *mp) {
        apr_finfo_t finfo;
        apr_file_t *fd;

        // Get file infos
        apr_assert(apr_stat(&finfo, file, APR_FINFO_SIZE, mp));

        // Open the file
        apr_assert(apr_file_open(&fd, file, APR_READ | APR_BINARY, APR_OS_DEFAULT, mp));

        // Map the thing
        apr_assert(apr_mmap_create(mem, fd, 0, finfo.size, APR_MMAP_READ, mp));
}

/*
 * Copy a string while sorting its letters
 */
void sortcpy(unsigned char *orig, unsigned char *sort, size_t len) {
        unsigned char min = 0xff, last_min = 0;
        size_t idx = -1, last_idx = -1, re_idx = -1, left = 0, right = len;

        // For each letter in the destination string
        for(size_t i = 0; i < len; i++) {
                min = 0xff;
                re_idx = -1;

                // For each letter in the source string
                for(size_t j = left; j < right; j++) {
                        // "Normalize" the character
                        char c = tolower(orig[j]);

                        // If you found a new smallest charcter
                        if(c > last_min && c <= min) {
                                min = c;
                                idx = j;
                        }

                        // If you detect a repetition of the previous
                        // smallest character
                        if(c == last_min && j < last_idx) {
                                re_idx = j;
                        }
                }

                // Was there a repetition ?
                if(re_idx == -1) {
                        // If the character was in the extremities,
                        // reduce the boundary of search for next time.
                        if(idx == left) {
                                left++;
                        } else if(idx == right) {
                                right--;
                        }

                        // Copy the caracter to the destination string
                        sort[i] = min;

                        // Reset values
                        last_min = min;
                        last_idx = idx;
                } else {
                        // Same thing as before, but in the case of a
                        // repetition

                        if(re_idx == left) {
                                left++;
                        } else if(re_idx == right) {
                                right--;
                        }

                        sort[i] = tolower(last_min);
                        last_idx = re_idx;
                }
        }

        // It's a C standard string, so finish it with a null character
        sort[len] = '\0';
}

/*
 * Insert a word into a dictionary.
 */
dictionary_t *tree_insert(dictionary_t *dict, word_t word, apr_pool_t *mp) {
        // Don't have to create a node
        if(dict != NULL) {
                // Compare the given word to this node's word
                int cmp = strcmp(dict->a.word, word.sort);

                if(cmp > 0) {
                        // If smaller put left
                        dict->left = tree_insert(dict->left, word, mp);
                } else if(cmp < 0) {
                        // If greater put right
                        dict->right = tree_insert(dict->right, word, mp);
                } else {
                        // If identical, then maybe we have found a new
                        // anagram
                        int found = 0;
                        char **arr = (char**)dict->a.l->elts;

                        // For each element already in the array
                        for(size_t i = 0; i < dict->a.l->nelts; i++) {
                                if(!strncmp(arr[i], word.orig, min(word.len, dict->a.len))) {
                                        // We found a matching string,
                                        // so you only have a double
                                        found = 1;
                                        break;
                                }
                        }

                        // No matching word was found
                        if(!found) {
                                // Push the word at the end of the
                                // anagram's list
                                *(char**)apr_array_push(dict->a.l) = word.orig;
                        }
                }

                // Return the dictionary
                return dict;
        } else {
                // A null dictionary was given, so you have to create
                // this node
                dictionary_t *new = apr_palloc(mp, sizeof(dictionary_t));

                // Initialize leaves
                new->left = NULL;
                new->right = NULL;

                // Input basic data
                new->a.word = word.sort;
                new->a.len = word.len;

                // And push current word
                new->a.l = apr_array_make(mp, 10, sizeof(char*));
                *(char**)apr_array_push(new->a.l) = word.orig;

                // Return the new dictionary
                return new;
        }
}

/*
 * Print a tree in a hierarchical manner.
 */
void tree_print(dictionary_t *dict, int n) {
        // Print identation
        for(int i = 0; i < n; i++) {
                printf(" ");
        }

        // Print current node
        printf("- %s\n", dict->a.word);

        // Print child nodes
        if(dict->left != NULL) tree_print(dict->left, n+1);
        if(dict->right != NULL) tree_print(dict->right, n+1);
}

/*
 * Print a tree in a flat manner.
 */
void tree_print_flat(dictionary_t *dict) {
        // If the dictionnary is null, give up here
        if(dict == NULL) return;

        // You print data in alphabetical order, so you begin by
        // printing what's in the left node.
        tree_print_flat(dict->left);

        // Only print this node if there is more than 1 word matching
        // the anagram
        if(dict->a.l->nelts > 1) {
                char **words;
                words = (char**)dict->a.l->elts;

                // Print the sorted word
                printf("* %s\n", dict->a.word);

                // Print each matching word
                for(int i = 0; i < dict->a.l->nelts; i++) {
                        printf("\t- ");
                        fwrite(words[i], sizeof(char), dict->a.len, stdout);
                        printf("\n");
                }
        }

        // And finish by printing what's in the right node
        tree_print_flat(dict->right);
}

// Builds the tree from a string
void make_tree(dictionary_t **dict, char *text, apr_pool_t *mp) {
        char *start = NULL, was_letter = 0;
        size_t len = 0;

        do {
                if(isalpha(*text)) {
                        // You are in a word

                        if(!was_letter) {
                                // If you were not in a word at the
                                // previous character, reset values and
                                // start a new word
                                was_letter = 1;
                                len = 0;
                                start = text;
                        }

                        // Increment the string's length
                        len++;
                } else {
                        // You are not in a letter

                        if(was_letter) {
                                // It's the end of a word

                                // If the word is long enough to be
                                // intersting
                                if(len > 2) {
                                        // Allocate the new word structure
                                        word_t *word = apr_palloc(mp, sizeof(word_t));

                                        // Copy what we can
                                        word->orig = start;
                                        word->len = len;

                                        // Allocate the memory for
                                        // sorted string
                                        word->sort = apr_palloc(mp,
                                        sizeof(char) * (len + 1));

                                        // Copy/sort the string
                                        sortcpy(start, word->sort, len);

                                        // And insert the node
                                        *dict = tree_insert(*dict, *word, mp);
                                }

                                // You're not in a word anymore
                                was_letter = 0;
                        }
                }
        } while(*(++text)); // Loop for each character
}

/*
 * Main function, does the thing
 */
int main(int argc, const char *argv[]) {
        apr_status_t rv;
        apr_pool_t *mp = NULL;
        apr_mmap_t *mem = NULL;
        dictionary_t *dict;
        char *str = NULL;

        // Check input
        if(argc != 2) {
                printf("%s: analyze a text to find anagrams\n", argv[0]);
                printf("Usage: %s FILE\n", argv[0]);

                exit(1);
        }

        // Initialize APR
        apr_assert(apr_initialize());

        // Create the pool
        apr_assert(apr_pool_create(&mp, NULL));

        // Map the thing
        map_to_mem(argv[1], &mem, mp);
        str = mem->mm;

        // Do the work
        make_tree(&dict, str, mp);
        tree_print_flat(dict);

        // Cleanup
        apr_pool_destroy(mp);
        apr_terminate();

        // Everything went fine
        return 0;
}

Donc ici je n’utilise que la gestion de la mémoire, et les tableaux dynamiques proposés par APR, mais il y a bien sûr une multitude de choses proposées. Comme source d’information, on notera avant tout le site officiel, avec une doc pas trop mal, et on peut aussi s’aider d’un des seuls tutos APR qui existent sur le net.

En bref, APR est magique et très agréable à utiliser, car elle permet d’éliminer les problèmes majeurs du C. De plus, un petit coup d’œil au code d’Apache permettra de remarquer à quel point elle permet d’écrire un code propre et maintenable. Par contre étrangement cette librairie est utilisée par très peu de projets, probablement à cause de la non-communication autour… En tout cas, c’est une librairie que je recommande vivement !

Filed under: Divers