reactos/tools/cdmake/dirhash.c

   1 #include <string.h>
   2 #include <stdlib.h>
   3 #include <ctype.h>
   4 #include "dirsep.h"
   5 #include "dirhash.h"
   6
   7 /* This is the famous DJB hash */
   8 static unsigned int
   9 djb_hash(const char *name)
  10 {
  11     unsigned int val = 5381;
  12     int i = 0;
  13
  14     for (i = 0; name[i]; i++)
  15     {
  16         val = (33 * val) + name[i];
  17     }
  18
  19     return val;
  20 }
  21
  22 static const char *
  23 chop_filename(const char *target)
  24 {
  25     char *last_slash = strrchr(target, '/');
  26     if (!last_slash)
  27         last_slash = strrchr(target, '\\');
  28     if (last_slash)
  29         return last_slash + 1;
  30     else
  31         return target;
  32 }
  33
  34 static void
  35 chop_dirname(const char *name, char **dirname)
  36 {
  37     char *last_slash = strrchr(name, '/');
  38     if (!last_slash)
  39         last_slash = strrchr(name, '\\');
  40     if (!last_slash)
  41     {
  42         *dirname = malloc(1);
  43         **dirname = 0;
  44     }
  45     else
  46     {
  47         char *newdata = malloc(last_slash - name + 1);
  48         memcpy(newdata, name, last_slash - name);
  49         newdata[last_slash - name] = 0;
  50         *dirname = newdata;
  51     }
  52 }
  53
  54 static struct target_dir_entry *
  55 get_entry_by_normname(struct target_dir_hash *dh, const char *norm)
  56 {
  57     unsigned int hashcode;
  58     struct target_dir_entry *de;
  59     hashcode = djb_hash(norm);
  60     de = dh->buckets[hashcode % NUM_DIR_HASH_BUCKETS];
  61     while (de && strcmp(de->normalized_name, norm))
  62         de = de->next_dir_hash_entry;
  63     return de;
  64 }
  65
  66 static void
  67 delete_entry(struct target_dir_hash *dh, struct target_dir_entry *de)
  68 {
  69     struct target_dir_entry **ent;
  70     ent = &dh->buckets[de->hashcode % NUM_DIR_HASH_BUCKETS];
  71     while (*ent && ((*ent) != de))
  72         ent = &(*ent)->next_dir_hash_entry;
  73     if (*ent)
  74         *ent = (*ent)->next_dir_hash_entry;
  75 }
  76
  77 void normalize_dirname(char *filename)
  78 {
  79     int i, tgt;
  80     int slash = 1;
  81
  82     for (i = 0, tgt = 0; filename[i]; i++)
  83     {
  84         if (slash)
  85         {
  86             if (filename[i] != '/' && filename[i] != '\\')
  87             {
  88                 filename[tgt++] = toupper(filename[i]);
  89                 slash = 0;
  90             }
  91         }
  92         else
  93         {
  94             if (filename[i] == '/' || filename[i] == '\\')
  95             {
  96                 slash = 1;
  97                 filename[tgt++] = DIR_SEPARATOR_CHAR;
  98             }
  99             else
 100             {
 101                 filename[tgt++] = toupper(filename[i]);
 102             }
 103         }
 104     }
 105     filename[tgt] = 0;
 106
 107     while (tgt && (filename[--tgt] == DIR_SEPARATOR_CHAR))
 108     {
 109         filename[tgt] = 0;
 110     }
 111 }
 112
 113 struct target_dir_entry *
 114 dir_hash_create_dir(struct target_dir_hash *dh, const char *casename, const char *targetnorm)
 115 {
 116     struct target_dir_entry *de, *parent_de;
 117     char *parentname = NULL;
 118     char *parentcase = NULL;
 119     struct target_dir_entry **ent;
 120
 121     if (!dh->root.normalized_name)
 122     {
 123         dh->root.normalized_name = strdup("");
 124         dh->root.case_name = strdup("");
 125         dh->root.hashcode = djb_hash("");
 126         dh->buckets[dh->root.hashcode % NUM_DIR_HASH_BUCKETS] = &dh->root;
 127     }
 128
 129     de = get_entry_by_normname(dh, targetnorm);
 130     if (de)
 131         return de;
 132
 133     chop_dirname(targetnorm, &parentname);
 134     chop_dirname(casename, &parentcase);
 135     parent_de = dir_hash_create_dir(dh, parentcase, parentname);
 136     free(parentname);
 137     free(parentcase);
 138
 139     de = calloc(1, sizeof(*de));
 140     de->head = NULL;
 141     de->child = NULL;
 142     de->parent = parent_de;
 143     de->normalized_name = strdup(targetnorm);
 144     de->case_name = strdup(chop_filename(casename));
 145     de->hashcode = djb_hash(targetnorm);
 146
 147     de->next = parent_de->child;
 148     parent_de->child = de;
 149
 150     ent = &dh->buckets[de->hashcode % NUM_DIR_HASH_BUCKETS];
 151     while (*ent)
 152     {
 153         ent = &(*ent)->next_dir_hash_entry;
 154     }
 155     *ent = de;
 156
 157     return de;
 158 }
 159
 160 void dir_hash_add_file(struct target_dir_hash *dh, const char *source, const char *target)
 161 {
 162     struct target_file *tf;
 163     struct target_dir_entry *de;
 164     char *targetdir = NULL;
 165     char *targetnorm;
 166
 167     chop_dirname(target, &targetdir);
 168     targetnorm = strdup(targetdir);
 169     normalize_dirname(targetnorm);
 170     de = dir_hash_create_dir(dh, targetdir, targetnorm);
 171     free(targetnorm);
 172     free(targetdir);
 173
 174     tf = calloc(1, sizeof(*tf));
 175     tf->next = de->head;
 176     de->head = tf;
 177     tf->source_name = strdup(source);
 178     tf->target_name = strdup(chop_filename(target));
 179 }
 180
 181 static void
 182 dir_hash_destroy_dir(struct target_dir_hash *dh, struct target_dir_entry *de)
 183 {
 184     struct target_file *tf;
 185     struct target_dir_entry *te;
 186
 187     while ((te = de->child))
 188     {
 189         de->child = te->next;
 190         dir_hash_destroy_dir(dh, te);
 191         free(te);
 192     }
 193     while ((tf = de->head))
 194     {
 195         de->head = tf->next;
 196         free(tf->source_name);
 197         free(tf->target_name);
 198         free(tf);
 199     }
 200
 201     delete_entry(dh, de);
 202     free(de->normalized_name);
 203     free(de->case_name);
 204 }
 205
 206 void dir_hash_destroy(struct target_dir_hash *dh)
 207 {
 208     dir_hash_destroy_dir(dh, &dh->root);
 209 }