strdup

char *new_string(char *str){
    char *new = (char *)malloc(strlen(str)+1);
    if (new == NULL) DIE_OUT_OF_MEMORY;
    strcpy(new, str); /* it's okay not to use strncpy */
    return new;
}

なんで strdup を使わないのだろう。メモリ確保エラーの処理を一元化したいとしてもこんな感じでいいのでは？

char *new_string(const char *str) {
    char *new = strdup(str);
    if (char) { perror(NULL); exit(-1); }
    return new;
}

あと、書いてから気づいたけどCで文字列を引数に取る関数は char * より、 const char * のほうがいいと思う。

追記

コメント書いたら返事をもらった。strdupはK&Rに載っていないからだそうだ。確かにちょっと調べてみた限りではANSI標準にも含まれていないみたい。

追記2

どうせstrlenで長さを調べるなら、memcpy のほうが早い可能性もあるような気がする。ブロック転送命令とか使えるし。こんな感じで。

char *new_string(const char *str) {
    size_t len = strlen(str);
    char *new_str = (char *) malloc(len + 1);
    if (!new_str) { perror(NULL); exit(-1); }
    memcpy(new_str, src, len + 1);
    return new_str;
}

実際にはあまり関係ないような気もするし、そこまで速度気にしてどうするよって話もあるけど。