ReactOS  0.4.13-dev-52-g0efcfec
dirhash.c
Go to the documentation of this file.
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)
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)
60  (*dirname)[result - path] = '\0'; // NULL-terminate
61 }
62 
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;
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;
101  while (de && strcmp(de->normalized_name, norm))
102  de = de->next_dir_hash_entry;
103  return de;
104 }
105 
106 static void
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
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 
236 {
237  dir_hash_destroy_dir(dh, &dh->root);
238 }
struct target_file * head
Definition: dirhash.h:29
unsigned int hashcode
Definition: dirhash.h:23
_Tp _STLP_CALL norm(const complex< _Tp > &__z)
Definition: _complex.h:741
GLsizei const GLchar ** path
Definition: glext.h:7234
#define free
Definition: debug_ros.c:5
#define max(a, b)
Definition: dirhash.c:16
__cdecl __MINGW_NOTHROW char * dirname(char *)
HFONT tf
Definition: icontest.c:17
void dir_hash_destroy(struct target_dir_hash *dh)
Definition: dirhash.c:235
_Check_return_ _CRTIMP _CONST_RETURN char *__cdecl strrchr(_In_z_ const char *_Str, _In_ int _Ch)
const char * filename
Definition: ioapi.h:135
struct target_dir_entry * child
Definition: dirhash.h:28
Definition: dirhash.h:21
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
#define DIR_SEPARATOR_CHAR
Definition: config.h:5
char * case_name
Definition: dirhash.h:31
_Check_return_ _CRTIMP char *__cdecl strdup(_In_opt_z_ const char *_Src)
static struct target_dir_entry * get_entry_by_normname(struct target_dir_hash *dh, const char *norm)
Definition: dirhash.c:95
static void split_path(const char *path, char **dirname, char **filename)
Definition: dirhash.c:35
smooth NULL
Definition: ftsmooth.c:416
struct target_dir_entry root
Definition: dirhash.h:37
struct target_dir_entry * parent
Definition: dirhash.h:27
GLuint GLfloat * val
Definition: glext.h:7180
int toupper(int c)
Definition: utclib.c:881
struct target_dir_entry * next
Definition: dirhash.h:26
struct target_dir_entry * next_dir_hash_entry
Definition: dirhash.h:24
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
#define NUM_DIR_HASH_BUCKETS
Definition: dirhash.h:12
struct target_dir_entry * dir_hash_create_dir(struct target_dir_hash *dh, const char *casename, const char *targetnorm)
Definition: dirhash.c:118
static void delete_entry(struct target_dir_hash *dh, struct target_dir_entry *de)
Definition: dirhash.c:107
Definition: services.c:325
struct target_file * dir_hash_add_file(struct target_dir_hash *dh, const char *source, const char *target)
Definition: dirhash.c:178
void normalize_dirname(char *filename)
Definition: dirhash.c:63
Definition: name.c:36
#define calloc
Definition: rosglue.h:14
GLenum target
Definition: glext.h:7315
int strcmp(const char *String1, const char *String2)
Definition: utclib.c:469
static void dir_hash_destroy_dir(struct target_dir_hash *dh, struct target_dir_entry *de)
Definition: dirhash.c:211
#define malloc
Definition: debug_ros.c:4
char * normalized_name
Definition: dirhash.h:30
static unsigned int djb_hash(const char *name)
Definition: dirhash.c:21
GLuint64EXT * result
Definition: glext.h:11304
struct target_dir_entry * buckets[NUM_DIR_HASH_BUCKETS]
Definition: dirhash.h:36