348 changes: 0 additions & 348 deletions src/root/async.c

This file was deleted.

559 changes: 0 additions & 559 deletions src/root/checkedint.c

This file was deleted.

267 changes: 0 additions & 267 deletions src/root/file.c

This file was deleted.

241 changes: 241 additions & 0 deletions src/root/file.d
Original file line number Diff line number Diff line change
@@ -0,0 +1,241 @@
// Compiler implementation of the D programming language
// Copyright (c) 1999-2015 by Digital Mars
// All Rights Reserved
// written by Walter Bright
// http://www.digitalmars.com
// Distributed under the Boost Software License, Version 1.0.
// http://www.boost.org/LICENSE_1_0.txt

module ddmd.root.file;

import core.stdc.errno, core.stdc.stdio, core.stdc.stdlib, core.stdc.string, core.sys.posix.fcntl, core.sys.posix.sys.types, core.sys.posix.unistd, core.sys.posix.utime, core.sys.windows.windows;
import ddmd.root.array, ddmd.root.filename, ddmd.root.rmem;

version (Windows) alias WIN32_FIND_DATAA = WIN32_FIND_DATA;

struct File
{
int _ref; // != 0 if this is a reference to someone else's buffer
ubyte* buffer; // data for our file
size_t len; // amount of data in buffer[]
FileName* name; // name of our file

extern (D) this(const(char)* n)
{
_ref = 0;
buffer = null;
len = 0;
name = new FileName(n);
}

extern (C++) static File* create(const(char)* n)
{
return new File(n);
}

/****************************** File ********************************/
extern (D) this(const(FileName)* n)
{
_ref = 0;
buffer = null;
len = 0;
name = cast(FileName*)n;
}

extern (C++) ~this()
{
if (buffer)
{
if (_ref == 0)
mem.xfree(buffer);
version (Windows)
{
if (_ref == 2)
UnmapViewOfFile(buffer);
}
}
}

extern (C++) char* toChars()
{
return name.toChars();
}

/*************************************
*/
extern (C++) bool read()
{
if (len)
return false; // already read the file
version (Posix)
{
size_t size;
stat_t buf;
ssize_t numread;
char* name = this.name.toChars();
//printf("File::read('%s')\n",name);
int fd = open(name, O_RDONLY);
if (fd == -1)
{
//printf("\topen error, errno = %d\n",errno);
goto err1;
}
if (!_ref)
.free(buffer);
_ref = 0; // we own the buffer now
//printf("\tfile opened\n");
if (fstat(fd, &buf))
{
printf("\tfstat error, errno = %d\n", errno);
goto err2;
}
size = cast(size_t)buf.st_size;
buffer = cast(ubyte*).malloc(size + 2);
if (!buffer)
{
printf("\tmalloc error, errno = %d\n", errno);
goto err2;
}
numread = .read(fd, buffer, size);
if (numread != size)
{
printf("\tread error, errno = %d\n", errno);
goto err2;
}
if (close(fd) == -1)
{
printf("\tclose error, errno = %d\n", errno);
goto err;
}
len = size;
// Always store a wchar ^Z past end of buffer so scanner has a sentinel
buffer[size] = 0; // ^Z is obsolete, use 0
buffer[size + 1] = 0;
return false;
err2:
close(fd);
err:
.free(buffer);
buffer = null;
len = 0;
err1:
return true;
}
else version (Windows)
{
DWORD size;
DWORD numread;
char* name = this.name.toChars();
HANDLE h = CreateFileA(name, GENERIC_READ, FILE_SHARE_READ, null, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL | FILE_FLAG_SEQUENTIAL_SCAN, null);
if (h == INVALID_HANDLE_VALUE)
goto err1;
if (!_ref)
.free(buffer);
_ref = 0;
size = GetFileSize(h, null);
buffer = cast(ubyte*).malloc(size + 2);
if (!buffer)
goto err2;
if (ReadFile(h, buffer, size, &numread, null) != TRUE)
goto err2;
if (numread != size)
goto err2;
if (!CloseHandle(h))
goto err;
len = size;
// Always store a wchar ^Z past end of buffer so scanner has a sentinel
buffer[size] = 0; // ^Z is obsolete, use 0
buffer[size + 1] = 0;
return 0;
err2:
CloseHandle(h);
err:
.free(buffer);
buffer = null;
len = 0;
err1:
return true;
}
else
{
assert(0);
}
}

/*********************************************
* Write a file.
* Returns:
* false success
*/
extern (C++) bool write()
{
version (Posix)
{
ssize_t numwritten;
char* name = this.name.toChars();
int fd = open(name, O_CREAT | O_WRONLY | O_TRUNC, (6 << 6) | (4 << 3) | 4);
if (fd == -1)
goto err;
numwritten = .write(fd, buffer, len);
if (len != numwritten)
goto err2;
if (close(fd) == -1)
goto err;
return false;
err2:
close(fd);
.remove(name);
err:
return true;
}
else version (Windows)
{
DWORD numwritten;
char* name = this.name.toChars();
HANDLE h = CreateFileA(name, GENERIC_WRITE, 0, null, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL | FILE_FLAG_SEQUENTIAL_SCAN, null);
if (h == INVALID_HANDLE_VALUE)
goto err;
if (WriteFile(h, buffer, len, &numwritten, null) != TRUE)
goto err2;
if (len != numwritten)
goto err2;
if (!CloseHandle(h))
goto err;
return false;
err2:
CloseHandle(h);
DeleteFileA(name);
err:
return true;
}
else
{
assert(0);
}
}

/* Set buffer
*/
extern (C++) void setbuffer(void* buffer, size_t len)
{
this.buffer = cast(ubyte*)buffer;
this.len = len;
}

// delete file
extern (C++) void remove()
{
version (Posix)
{
int dummy = .remove(this.name.toChars());
}
else version (Windows)
{
DeleteFileA(this.name.toChars());
}
else
{
assert(0);
}
}
}
672 changes: 0 additions & 672 deletions src/root/filename.c

This file was deleted.

682 changes: 682 additions & 0 deletions src/root/filename.d

Large diffs are not rendered by default.

654 changes: 0 additions & 654 deletions src/root/longdouble.c

This file was deleted.

96 changes: 0 additions & 96 deletions src/root/man.c

This file was deleted.

74 changes: 74 additions & 0 deletions src/root/man.d
Original file line number Diff line number Diff line change
@@ -0,0 +1,74 @@
// Compiler implementation of the D programming language
// Copyright (c) 1999-2015 by Digital Mars
// All Rights Reserved
// written by Walter Bright
// http://www.digitalmars.com
// Distributed under the Boost Software License, Version 1.0.
// http://www.boost.org/LICENSE_1_0.txt

module ddmd.root.man;

import core.stdc.stdio, core.stdc.stdlib, core.stdc.string, core.sys.posix.sys.types, core.sys.posix.sys.wait, core.sys.posix.unistd, core.sys.windows.windows;

version (Windows)
{
extern (C++) void browse(const(char)* url)
{
ShellExecuteA(null, "open", url, null, null, SW_SHOWNORMAL);
}
}
else version (OSX)
{
extern (C++) void browse(const(char)* url)
{
pid_t childpid;
const(char)*[5] args;
char* browser = getenv("BROWSER");
if (browser)
{
browser = strdup(browser);
args[0] = browser;
args[1] = url;
args[2] = null;
}
else
{
//browser = "/Applications/Safari.app/Contents/MacOS/Safari";
args[0] = "open";
args[1] = "-a";
args[2] = "/Applications/Safari.app";
args[3] = url;
args[4] = null;
}
childpid = fork();
if (childpid == 0)
{
execvp(args[0], cast(char**)args);
perror(args[0]); // failed to execute
return;
}
}
}
else version (Posix)
{
extern (C++) void browse(const(char)* url)
{
pid_t childpid;
const(char)*[3] args;
const(char)* browser = getenv("BROWSER");
if (browser)
browser = strdup(browser);
else
browser = "x-www-browser";
args[0] = browser;
args[1] = url;
args[2] = null;
childpid = fork();
if (childpid == 0)
{
execvp(args[0], cast(char**)args);
perror(args[0]); // failed to execute
return;
}
}
}
50 changes: 0 additions & 50 deletions src/root/object.c

This file was deleted.

399 changes: 0 additions & 399 deletions src/root/outbuffer.c

This file was deleted.

419 changes: 419 additions & 0 deletions src/root/outbuffer.d

Large diffs are not rendered by default.

1,145 changes: 0 additions & 1,145 deletions src/root/port.c

This file was deleted.

242 changes: 0 additions & 242 deletions src/root/response.c

This file was deleted.

201 changes: 201 additions & 0 deletions src/root/response.d
Original file line number Diff line number Diff line change
@@ -0,0 +1,201 @@
// Compiler implementation of the D programming language
// Copyright (c) 1999-2015 by Digital Mars
// All Rights Reserved
// written by Walter Bright
// http://www.digitalmars.com
// Distributed under the Boost Software License, Version 1.0.
// http://www.boost.org/LICENSE_1_0.txt

module ddmd.root.response;

import core.stdc.stdio, core.stdc.stdlib, core.stdc.string;
import ddmd.root.file, ddmd.root.filename;

/*********************************
* #include <stdlib.h>
* int response_expand(int *pargc,char ***pargv);
*
* Expand any response files in command line.
* Response files are arguments that look like:
* @NAME
* The name is first searched for in the environment. If it is not
* there, it is searched for as a file name.
* Arguments are separated by spaces, tabs, or newlines. These can be
* imbedded within arguments by enclosing the argument in '' or "".
* Recursively expands nested response files.
*
* To use, put the line:
* response_expand(&argc,&argv);
* as the first executable statement in main(int argc, char **argv).
* argc and argv are adjusted to be the new command line arguments
* after response file expansion.
*
* Digital Mars's MAKE program can be notified that a program can accept
* long command lines via environment variables by preceding the rule
* line for the program with a *.
*
* Returns:
* 0 success
* !=0 failure (argc, argv unchanged)
*/
extern (C++) bool response_expand(Strings* args)
{
const(char)* cp;
int recurse = 0;
for (size_t i = 0; i < args.dim;)
{
cp = (*args)[i];
if (*cp != '@')
{
++i;
continue;
}
args.remove(i);
char* buffer;
char* bufend;
cp++;
char* p = getenv(cp);
if (p)
{
buffer = strdup(p);
if (!buffer)
goto noexpand;
bufend = buffer + strlen(buffer);
}
else
{
auto f = File(cp);
if (f.read())
goto noexpand;
f._ref = 1;
buffer = cast(char*)f.buffer;
bufend = buffer + f.len;
}
// The logic of this should match that in setargv()
int comment = 0;
for (p = buffer; p < bufend; p++)
{
char* d;
char c, lastc;
ubyte instring;
int num_slashes, non_slashes;
switch (*p)
{
case 26:
/* ^Z marks end of file */
goto L2;
case 0xD:
case '\n':
if (comment)
{
comment = 0;
}
case 0:
case ' ':
case '\t':
continue;
// scan to start of argument
case '#':
comment = 1;
continue;
case '@':
if (comment)
{
continue;
}
recurse = 1;
default:
/* start of new argument */
if (comment)
{
continue;
}
args.insert(i, p);
++i;
instring = 0;
c = 0;
num_slashes = 0;
for (d = p; 1; p++)
{
lastc = c;
if (p >= bufend)
{
*d = 0;
goto L2;
}
c = *p;
switch (c)
{
case '"':
/*
Yes this looks strange,but this is so that we are
MS Compatible, tests have shown that:
\\\\"foo bar" gets passed as \\foo bar
\\\\foo gets passed as \\\\foo
\\\"foo gets passed as \"foo
and \"foo gets passed as "foo in VC!
*/
non_slashes = num_slashes % 2;
num_slashes = num_slashes / 2;
for (; num_slashes > 0; num_slashes--)
{
d--;
*d = '\0';
}
if (non_slashes)
{
*(d - 1) = c;
}
else
{
instring ^= 1;
}
break;
case 26:
*d = 0; // terminate argument
goto L2;
case 0xD:
// CR
c = lastc;
continue;
// ignore
case '@':
recurse = 1;
goto Ladd;
case ' ':
case '\t':
if (!instring)
{
case '\n':
case 0:
*d = 0; // terminate argument
goto Lnextarg;
}
default:
Ladd:
if (c == '\\')
num_slashes++;
else
num_slashes = 0;
*d++ = c;
break;
}
}
break;
}
Lnextarg:
}
L2:
}
if (recurse)
{
/* Recursively expand @filename */
if (response_expand(args))
goto noexpand;
}
return false; /* success */
noexpand:
/* error */
/* BUG: any file buffers are not free'd */
return true;
}
163 changes: 0 additions & 163 deletions src/root/rmem.c

This file was deleted.

209 changes: 87 additions & 122 deletions src/root/speller.c → src/root/speller.d
Original file line number Diff line number Diff line change
@@ -1,25 +1,18 @@
// Compiler implementation of the D programming language
// Copyright (c) 1999-2015 by Digital Mars
// All Rights Reserved
// written by Walter Bright
// http://www.digitalmars.com
// Distributed under the Boost Software License, Version 1.0.
// http://www.boost.org/LICENSE_1_0.txt

/* Copyright (c) 2010-2014 by Digital Mars
* All Rights Reserved, written by Walter Bright
* http://www.digitalmars.com
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt)
* https://github.com/D-Programming-Language/dmd/blob/master/src/root/speller.c
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
module ddmd.root.speller;

#if __sun || _MSC_VER
#include <alloca.h>
#endif
import core.stdc.limits, core.stdc.stdlib, core.stdc.string;

#include "speller.h"
extern (C++) alias fp_speller_t = void* function(void*, const(char)*, int*);

const char idchars[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_";
extern (C++) __gshared const(char)* idchars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_";

/**************************************************
* combine a new result from the spell checker to
Expand All @@ -35,7 +28,7 @@ const char idchars[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123
* true if the cost is less or equal 0
* false otherwise
*/
bool combineSpellerResult(void*& p, int& cost, void* np, int ncost)
extern (C++) bool combineSpellerResult(ref void* p, ref int cost, void* np, int ncost)
{
if (np && ncost < cost)
{
Expand All @@ -47,29 +40,25 @@ bool combineSpellerResult(void*& p, int& cost, void* np, int ncost)
return false;
}

void *spellerY(const char *seed, size_t seedlen, fp_speller_t fp, void *fparg,
const char *charset, size_t index, int* cost)
extern (C++) void* spellerY(const(char)* seed, size_t seedlen, fp_speller_t fp, void* fparg, const(char)* charset, size_t index, int* cost)
{
if (!seedlen)
return NULL;
return null;
assert(seed[seedlen] == 0);

char tmp[30];
char *buf;
if (seedlen <= sizeof(tmp) - 2)
buf = tmp;
char[30] tmp;
char* buf;
if (seedlen <= tmp.sizeof - 2)
buf = tmp.ptr;
else
{
buf = (char *)alloca(seedlen + 2); // leave space for extra char
buf = cast(char*)alloca(seedlen + 2); // leave space for extra char
if (!buf)
return NULL; // no matches
return null; // no matches
}

memcpy(buf, seed, index);
*cost = INT_MAX;
void* p = NULL;
void* p = null;
int ncost;

/* Delete at seed[index] */
if (index < seedlen)
{
Expand All @@ -79,62 +68,53 @@ void *spellerY(const char *seed, size_t seedlen, fp_speller_t fp, void *fparg,
if (combineSpellerResult(p, *cost, np, ncost))
return p;
}

if (charset && *charset)
{
/* Substitutions */
if (index < seedlen)
{
memcpy(buf, seed, seedlen + 1);
for (const char *s = charset; *s; s++)
for (const(char)* s = charset; *s; s++)
{
buf[index] = *s;

//printf("sub buf = '%s'\n", buf);
void* np = (*fp)(fparg, buf, &ncost);
if (combineSpellerResult(p, *cost, np, ncost))
return p;
}
assert(buf[seedlen] == 0);
}

/* Insertions */
memcpy (buf + index + 1, seed + index, seedlen + 1 - index);

for (const char *s = charset; *s; s++)
memcpy(buf + index + 1, seed + index, seedlen + 1 - index);
for (const(char)* s = charset; *s; s++)
{
buf[index] = *s;

//printf("ins buf = '%s'\n", buf);
void* np = (*fp)(fparg, buf, &ncost);
if (combineSpellerResult(p, *cost, np, ncost))
return p;
}
assert(buf[seedlen + 1] == 0);
}

return p; // return "best" result
return p; // return "best" result
}

void *spellerX(const char *seed, size_t seedlen, fp_speller_t fp, void *fparg,
const char *charset, int flag)
extern (C++) void* spellerX(const(char)* seed, size_t seedlen, fp_speller_t fp, void* fparg, const(char)* charset, int flag)
{
if (!seedlen)
return NULL;

char tmp[30];
char *buf;
if (seedlen <= sizeof(tmp) - 2)
buf = tmp;
return null;
char[30] tmp;
char* buf;
if (seedlen <= tmp.sizeof - 2)
buf = tmp.ptr;
else
{
buf = (char *)alloca(seedlen + 2); // leave space for extra char
buf = cast(char*)alloca(seedlen + 2); // leave space for extra char
if (!buf)
return NULL; // no matches
return null; // no matches
}
int cost = INT_MAX, ncost;
void *p = NULL, *np;

void* p = null, np;
/* Deletions */
memcpy(buf, seed + 1, seedlen);
for (size_t i = 0; i < seedlen; i++)
Expand All @@ -146,10 +126,8 @@ void *spellerX(const char *seed, size_t seedlen, fp_speller_t fp, void *fparg,
np = (*fp)(fparg, buf, &ncost);
if (combineSpellerResult(p, cost, np, ncost))
return p;

buf[i] = seed[i];
}

/* Transpositions */
if (!flag)
{
Expand All @@ -159,25 +137,21 @@ void *spellerX(const char *seed, size_t seedlen, fp_speller_t fp, void *fparg,
// swap [i] and [i + 1]
buf[i] = seed[i + 1];
buf[i + 1] = seed[i];

//printf("tra buf = '%s'\n", buf);
if (combineSpellerResult(p, cost, (*fp)(fparg, buf, &ncost), ncost))
return p;

buf[i] = seed[i];
}
}

if (charset && *charset)
{
/* Substitutions */
memcpy(buf, seed, seedlen + 1);
for (size_t i = 0; i < seedlen; i++)
{
for (const char *s = charset; *s; s++)
for (const(char)* s = charset; *s; s++)
{
buf[i] = *s;

//printf("sub buf = '%s'\n", buf);
if (flag)
np = spellerY(buf, seedlen, fp, fparg, charset, i + 1, &ncost);
Expand All @@ -188,15 +162,13 @@ void *spellerX(const char *seed, size_t seedlen, fp_speller_t fp, void *fparg,
}
buf[i] = seed[i];
}

/* Insertions */
memcpy(buf + 1, seed, seedlen + 1);
for (size_t i = 0; i <= seedlen; i++) // yes, do seedlen+1 iterations
for (size_t i = 0; i <= seedlen; i++) // yes, do seedlen+1 iterations
{
for (const char *s = charset; *s; s++)
for (const(char)* s = charset; *s; s++)
{
buf[i] = *s;

//printf("ins buf = '%s'\n", buf);
if (flag)
np = spellerY(buf, seedlen + 1, fp, fparg, charset, i + 1, &ncost);
Expand All @@ -205,11 +177,10 @@ void *spellerX(const char *seed, size_t seedlen, fp_speller_t fp, void *fparg,
if (combineSpellerResult(p, cost, np, ncost))
return p;
}
buf[i] = seed[i]; // going past end of seed[] is ok, as we hit the 0
buf[i] = seed[i]; // going past end of seed[] is ok, as we hit the 0
}
}

return p; // return "best" result
return p; // return "best" result
}

/**************************************************
Expand All @@ -225,71 +196,65 @@ void *spellerX(const char *seed, size_t seedlen, fp_speller_t fp, void *fparg,
* NULL no correct spellings found
* void* value returned by fp() for first possible correct spelling
*/

void *speller(const char *seed, fp_speller_t fp, void *fparg, const char *charset)
extern (C++) void* speller(const(char)* seed, fp_speller_t fp, void* fparg, const(char)* charset)
{
size_t seedlen = strlen(seed);
size_t maxdist = seedlen < 4 ? seedlen / 2 : 2;
for (int distance = 0; distance < maxdist; distance++)
{ void *p = spellerX(seed, seedlen, fp, fparg, charset, distance);
{
void* p = spellerX(seed, seedlen, fp, fparg, charset, distance);
if (p)
return p;
// if (seedlen > 10)
// break;
// if (seedlen > 10)
// break;
}
return NULL; // didn't find it
}


#if UNITTEST

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

void *speller_test(void *fparg, const char *s, int* cost)
{
//printf("speller_test(%s, %s)\n", fparg, s);
*cost = 0;
if (strcmp((char *)fparg, s) == 0)
return fparg;
return NULL;
return null; // didn't find it
}

void unittest_speller()
version (unittest)
{
static const char *cases[][3] =
extern (C++) void* speller_test(void* fparg, const(char)* s, int* cost)
{
{ "hello", "hell", "y" },
{ "hello", "hel", "y" },
{ "hello", "ello", "y" },
{ "hello", "llo", "y" },
{ "hello", "hellox", "y" },
{ "hello", "helloxy", "y" },
{ "hello", "xhello", "y" },
{ "hello", "xyhello", "y" },
{ "hello", "ehllo", "y" },
{ "hello", "helol", "y" },
{ "hello", "abcd", "n" },
{ "hello", "helxxlo", "y" },
{ "hello", "ehlxxlo", "n" },
{ "hello", "heaao", "y" },
{ "_123456789_123456789_123456789_123456789", "_123456789_123456789_123456789_12345678", "y" },
{ NULL, NULL, NULL }
};
//printf("unittest_speller()\n");
const void *p = speller("hello", &speller_test, (void *)"hell", idchars);
assert(p != NULL);
for (int i = 0; cases[i][0]; i++)
//printf("speller_test(%s, %s)\n", fparg, s);
*cost = 0;
if (strcmp(cast(char*)fparg, s) == 0)
return fparg;
return null;
}

extern (C++) void unittest_speller()
{
//printf("case [%d]\n", i);
void *p = speller(cases[i][0], &speller_test, (void *)cases[i][1], idchars);
if (p)
assert(cases[i][2][0] == 'y');
else
assert(cases[i][2][0] == 'n');
static __gshared const(char)*** cases =
[
["hello", "hell", "y"],
["hello", "hel", "y"],
["hello", "ello", "y"],
["hello", "llo", "y"],
["hello", "hellox", "y"],
["hello", "helloxy", "y"],
["hello", "xhello", "y"],
["hello", "xyhello", "y"],
["hello", "ehllo", "y"],
["hello", "helol", "y"],
["hello", "abcd", "n"],
["hello", "helxxlo", "y"],
["hello", "ehlxxlo", "n"],
["hello", "heaao", "y"],
["_123456789_123456789_123456789_123456789", "_123456789_123456789_123456789_12345678", "y"],
[null, null, null]
];
//printf("unittest_speller()\n");
const(void)* p = speller("hello", &speller_test, cast(void*)"hell", idchars);
assert(p !is null);
for (int i = 0; cases[i][0]; i++)
{
//printf("case [%d]\n", i);
void* p = speller(cases[i][0], &speller_test, cast(void*)cases[i][1], idchars);
if (p)
assert(cases[i][2][0] == 'y');
else
assert(cases[i][2][0] == 'n');
}
//printf("unittest_speller() success\n");
}
//printf("unittest_speller() success\n");
}

#endif
255 changes: 0 additions & 255 deletions src/root/stringtable.c

This file was deleted.

270 changes: 270 additions & 0 deletions src/root/stringtable.d
Original file line number Diff line number Diff line change
@@ -0,0 +1,270 @@
// Compiler implementation of the D programming language
// Copyright (c) 1999-2015 by Digital Mars
// All Rights Reserved
// written by Walter Bright
// http://www.digitalmars.com
// Distributed under the Boost Software License, Version 1.0.
// http://www.boost.org/LICENSE_1_0.txt

module ddmd.root.stringtable;

import core.stdc.stdint, core.stdc.string;
import ddmd.root.rmem;

enum POOL_BITS = 12;
enum POOL_SIZE = (1U << POOL_BITS);

// TODO: Merge with root.String
// MurmurHash2 was written by Austin Appleby, and is placed in the public
// domain. The author hereby disclaims copyright to this source code.
// https://sites.google.com/site/murmurhash/
extern (C++) static uint32_t calcHash(const(char)* key, size_t len)
{
// 'm' and 'r' are mixing constants generated offline.
// They're not really 'magic', they just happen to work well.
const(uint32_t) m = 0x5bd1e995;
const(int) r = 24;
// Initialize the hash to a 'random' value
uint32_t h = cast(uint32_t)len;
// Mix 4 bytes at a time into the hash
const(uint8_t)* data = cast(const(uint8_t)*)key;
while (len >= 4)
{
uint32_t k = data[3] << 24 | data[2] << 16 | data[1] << 8 | data[0];
k *= m;
k ^= k >> r;
k *= m;
h *= m;
h ^= k;
data += 4;
len -= 4;
}
// Handle the last few bytes of the input array
switch (len & 3)
{
case 3:
h ^= data[2] << 16;
case 2:
h ^= data[1] << 8;
case 1:
h ^= data[0];
h *= m;
default:
break;
}
// Do a few final mixes of the hash to ensure the last few
// bytes are well-incorporated.
h ^= h >> 13;
h *= m;
h ^= h >> 15;
return h;
}

extern (C++) static size_t nextpow2(size_t val)
{
size_t res = 1;
while (res < val)
res <<= 1;
return res;
}

extern (C++) __gshared const(double) loadFactor = 0.8;

struct StringEntry
{
uint32_t hash;
uint32_t vptr;
}

// StringValue is a variable-length structure. It has neither proper c'tors nor a
// factory method because the only thing which should be creating these is StringTable.
struct StringValue
{
void* ptrvalue;
size_t length;

extern (C++) char* lstring()
{
return cast(char*)(&this + 1);
}

extern (C++) const(size_t) len()
{
return length;
}

extern (C++) const(const(char)*) toDchars()
{
return cast(const(char)*)(&this + 1);
}
}

struct StringTable
{
private:
StringEntry* table;
size_t tabledim;
uint8_t** pools;
size_t npools;
size_t nfill;
size_t count;

public:
extern (C++) void _init(size_t size = 0)
{
size = nextpow2(cast(size_t)(size / loadFactor));
if (size < 32)
size = 32;
table = cast(StringEntry*)mem.xcalloc(size, (table[0]).sizeof);
tabledim = size;
pools = null;
npools = nfill = 0;
count = 0;
}

extern (C++) void reset(size_t size = 0)
{
for (size_t i = 0; i < npools; ++i)
mem.xfree(pools[i]);
mem.xfree(table);
mem.xfree(pools);
table = null;
pools = null;
_init(size);
}

extern (C++) ~this()
{
for (size_t i = 0; i < npools; ++i)
mem.xfree(pools[i]);
mem.xfree(table);
mem.xfree(pools);
table = null;
pools = null;
}

extern (C++) StringValue* lookup(const(char)* s, size_t length)
{
const(hash_t) hash = calcHash(s, length);
const(size_t) i = findSlot(hash, s, length);
// printf("lookup %.*s %p\n", (int)length, s, table[i].value ?: NULL);
return getValue(table[i].vptr);
}

extern (C++) StringValue* insert(const(char)* s, size_t length)
{
const(hash_t) hash = calcHash(s, length);
size_t i = findSlot(hash, s, length);
if (table[i].vptr)
return null; // already in table
if (++count > tabledim * loadFactor)
{
grow();
i = findSlot(hash, s, length);
}
table[i].hash = hash;
table[i].vptr = allocValue(s, length);
// printf("insert %.*s %p\n", (int)length, s, table[i].value ?: NULL);
return getValue(table[i].vptr);
}

extern (C++) StringValue* update(const(char)* s, size_t length)
{
const(hash_t) hash = calcHash(s, length);
size_t i = findSlot(hash, s, length);
if (!table[i].vptr)
{
if (++count > tabledim * loadFactor)
{
grow();
i = findSlot(hash, s, length);
}
table[i].hash = hash;
table[i].vptr = allocValue(s, length);
}
// printf("update %.*s %p\n", (int)length, s, table[i].value ?: NULL);
return getValue(table[i].vptr);
}

/********************************
* Walk the contents of the string table,
* calling fp for each entry.
* Params:
* fp = function to call. Returns !=0 to stop
* Returns:
* last return value of fp call
*/
extern (C++) int apply(int function(StringValue*) fp)
{
for (size_t i = 0; i < tabledim; ++i)
{
StringEntry* se = &table[i];
if (!se.vptr)
continue;
StringValue* sv = getValue(se.vptr);
int result = (*fp)(sv);
if (result)
return result;
}
return 0;
}

private:
extern (C++) uint32_t allocValue(const(char)* s, size_t length)
{
const(size_t) nbytes = StringValue.sizeof + length + 1;
if (!npools || nfill + nbytes > POOL_SIZE)
{
pools = cast(uint8_t**)mem.xrealloc(pools, ++npools * (pools[0]).sizeof);
pools[npools - 1] = cast(uint8_t*)mem.xmalloc(nbytes > POOL_SIZE ? nbytes : POOL_SIZE);
nfill = 0;
}
StringValue* sv = cast(StringValue*)&pools[npools - 1][nfill];
sv.ptrvalue = null;
sv.length = length;
.memcpy(sv.lstring(), s, length);
sv.lstring()[length] = 0;
const(uint32_t) vptr = cast(uint32_t)(npools << POOL_BITS | nfill);
nfill += nbytes + (-nbytes & 7); // align to 8 bytes
return vptr;
}

extern (C++) StringValue* getValue(uint32_t vptr)
{
if (!vptr)
return null;
const(size_t) idx = (vptr >> POOL_BITS) - 1;
const(size_t) off = vptr & POOL_SIZE - 1;
return cast(StringValue*)&pools[idx][off];
}

extern (C++) size_t findSlot(hash_t hash, const(char)* s, size_t length)
{
// quadratic probing using triangular numbers
// http://stackoverflow.com/questions/2348187/moving-from-linear-probing-to-quadratic-probing-hash-collisons/2349774#2349774
for (size_t i = hash & (tabledim - 1), j = 1;; ++j)
{
StringValue* sv;
if (!table[i].vptr || table[i].hash == hash && (sv = getValue(table[i].vptr)).length == length && .memcmp(s, sv.lstring(), length) == 0)
return i;
i = (i + j) & (tabledim - 1);
}
}

extern (C++) void grow()
{
const(size_t) odim = tabledim;
StringEntry* otab = table;
tabledim *= 2;
table = cast(StringEntry*)mem.xcalloc(tabledim, (table[0]).sizeof);
for (size_t i = 0; i < odim; ++i)
{
StringEntry* se = &otab[i];
if (!se.vptr)
continue;
StringValue* sv = getValue(se.vptr);
table[findSlot(se.hash, sv.lstring(), sv.length)] = *se;
}
mem.xfree(otab);
}
}
Loading