modules/rosapps/applications/devutils/cdmake/dirhash.c

   1 /*
   2  * COPYRIGHT:       See COPYING in the top level directory
   3  * PROJECT:         ReactOS CD-ROM Maker
   4  * FILE:            tools/cdmake/dirhash.c
   5  * PURPOSE:         CD-ROM Premastering Utility - Directory names hashing
   6  * PROGRAMMERS:     Art Yerkes
   7  */
   8
   9 #include <string.h>
  10 #include <stdlib.h>
  11 #include <ctype.h>
  12 #include "config.h"
  13 #include "dirhash.h"
  14
  15 #ifndef max
  16 #define max(a, b) ((a) > (b) ? (a) : (b))
  17 #endif
  18
  19 /* This is the famous DJB hash */
  20 static unsigned int
  21 djb_hash(const char *name)
  22 {
  23     unsigned int val = 5381;
  24     int i = 0;
  25
  26     for (i = 0; name[i]; i++)
  27     {
  28         val = (33 * val) + name[i];
  29     }
  30
  31     return val;
  32 }
  33
  34 static void
  35 split_path(const char *path, char **dirname, char **filename /* OPTIONAL */)
  36 {
  37     const char *result;
  38
  39     /* Retrieve the file name */
  40     char *last_slash_1 = strrchr(path, '/');
  41     char *last_slash_2 = strrchr(path, '\\');
  42
  43     if (last_slash_1 || last_slash_2)
  44         result = max(last_slash_1, last_slash_2) + 1;
  45     else
  46         result = path;
  47
  48     /* Duplicate the file name for the user if needed */
  49     if (filename)
  50         *filename = strdup(result);
  51
  52     /* Remove any trailing directory separators */
  53     while (result > path && (*(result-1) == '/' || *(result-1) == '\\'))
  54         result--;
  55
  56     /* Retrieve and duplicate the directory */
  57     *dirname = malloc(result - path + 1);
  58     if (result > path)
  59         memcpy(*dirname, path, result - path);
  60     (*dirname)[result - path] = '\0'; // NULL-terminate
  61 }
  62
  63 void normalize_dirname(char *filename)
  64 {
  65     int i, tgt;
  66     int slash = 1;
  67
  68     for (i = 0, tgt = 0; filename[i]; i++)
  69     {
  70         if (slash)
  71         {
  72             if (filename[i] != '/' && filename[i] != '\\')
  73             {
  74                 filename[tgt++] = toupper(filename[i]);
  75                 slash = 0;
  76             }
  77         }
  78         else
  79         {
  80             if (filename[i] == '/' || filename[i] == '\\')
  81             {
  82                 slash = 1;
  83                 filename[tgt++] = DIR_SEPARATOR_CHAR;
  84             }
  85             else
  86             {
  87                 filename[tgt++] = toupper(filename[i]);
  88             }
  89         }
  90     }
  91     filename[tgt] = '\0'; // NULL-terminate
  92 }
  93
  94 static struct target_dir_entry *
  95 get_entry_by_normname(struct target_dir_hash *dh, const char *norm)
  96 {
  97     unsigned int hashcode;
  98     struct target_dir_entry *de;
  99     hashcode = djb_hash(norm);
 100     de = dh->buckets[hashcode % NUM_DIR_HASH_BUCKETS];
 101     while (de && strcmp(de->normalized_name, norm))
 102         de = de->next_dir_hash_entry;
 103     return de;
 104 }
 105
 106 static void
 107 delete_entry(struct target_dir_hash *dh, struct target_dir_entry *de)
 108 {
 109     struct target_dir_entry **ent;
 110     ent = &dh->buckets[de->hashcode % NUM_DIR_HASH_BUCKETS];
 111     while (*ent && ((*ent) != de))
 112         ent = &(*ent)->next_dir_hash_entry;
 113     if (*ent)
 114         *ent = (*ent)->next_dir_hash_entry;
 115 }
 116
 117 struct target_dir_entry *
 118 dir_hash_create_dir(struct target_dir_hash *dh, const char *casename, const char *targetnorm)
 119 {
 120     struct target_dir_entry *de, *parent_de;
 121     char *parentcase = NULL;
 122     char *case_name  = NULL;
 123     char *parentname = NULL;
 124     struct target_dir_entry **ent;
 125
 126     if (!dh->root.normalized_name)
 127     {
 128         dh->root.normalized_name = strdup("");
 129         dh->root.case_name = strdup("");
 130         dh->root.hashcode = djb_hash("");
 131         dh->buckets[dh->root.hashcode % NUM_DIR_HASH_BUCKETS] = &dh->root;
 132     }
 133
 134     /* Check whether the directory was already created and just return it if so */
 135     de = get_entry_by_normname(dh, targetnorm);
 136     if (de)
 137         return de;
 138
 139     /*
 140      * If *case_name == '\0' after the following call to split_path(...),
 141      * for example in the case where casename == "subdir/dir/", then just
 142      * create the directories "subdir" and "dir" by a recursive call to
 143      * dir_hash_create_dir(...) and return 'parent_de' instead (see after).
 144      * We do not (and we never) create a no-name directory inside it.
 145      */
 146     split_path(casename, &parentcase, &case_name);
 147     split_path(targetnorm, &parentname, NULL);
 148     parent_de = dir_hash_create_dir(dh, parentcase, parentname);
 149     free(parentname);
 150     free(parentcase);
 151
 152     /* See the remark above */
 153     if (!*case_name)
 154     {
 155         free(case_name);
 156         return parent_de;
 157     }
 158
 159     /* Now create the directory */
 160     de = calloc(1, sizeof(*de));
 161     de->parent = parent_de;
 162     de->normalized_name = strdup(targetnorm);
 163     de->case_name = case_name;
 164     de->hashcode = djb_hash(targetnorm);
 165
 166     de->next = parent_de->child;
 167     parent_de->child = de;
 168
 169     ent = &dh->buckets[de->hashcode % NUM_DIR_HASH_BUCKETS];
 170     while (*ent)
 171         ent = &(*ent)->next_dir_hash_entry;
 172     *ent = de;
 173
 174     return de;
 175 }
 176
 177 struct target_file *
 178 dir_hash_add_file(struct target_dir_hash *dh, const char *source, const char *target)
 179 {
 180     struct target_file *tf;
 181     struct target_dir_entry *de;
 182     char *targetdir  = NULL;
 183     char *targetfile = NULL;
 184     char *targetnorm;
 185
 186     /* First create the directory; check whether the file name is valid and bail out if not */
 187     split_path(target, &targetdir, &targetfile);
 188     if (!*targetfile)
 189     {
 190         free(targetdir);
 191         free(targetfile);
 192         return NULL;
 193     }
 194     targetnorm = strdup(targetdir);
 195     normalize_dirname(targetnorm);
 196     de = dir_hash_create_dir(dh, targetdir, targetnorm);
 197     free(targetnorm);
 198     free(targetdir);
 199
 200     /* Now add the file */
 201     tf = calloc(1, sizeof(*tf));
 202     tf->next = de->head;
 203     de->head = tf;
 204     tf->source_name = strdup(source);
 205     tf->target_name = targetfile;
 206
 207     return tf;
 208 }
 209
 210 static void
 211 dir_hash_destroy_dir(struct target_dir_hash *dh, struct target_dir_entry *de)
 212 {
 213     struct target_file *tf;
 214     struct target_dir_entry *te;
 215
 216     while ((te = de->child))
 217     {
 218         de->child = te->next;
 219         dir_hash_destroy_dir(dh, te);
 220         free(te);
 221     }
 222     while ((tf = de->head))
 223     {
 224         de->head = tf->next;
 225         free(tf->source_name);
 226         free(tf->target_name);
 227         free(tf);
 228     }
 229
 230     delete_entry(dh, de);
 231     free(de->normalized_name);
 232     free(de->case_name);
 233 }
 234
 235 void dir_hash_destroy(struct target_dir_hash *dh)
 236 {
 237     dir_hash_destroy_dir(dh, &dh->root);
 238 }