[geany/geany] bf0702: Use uctags implementation of keyword.c/h
Jiří Techet
git-noreply at xxxxx
Sat Sep 10 07:25:57 UTC 2016
Branch: refs/heads/master
Author: Jiří Techet <techet at gmail.com>
Committer: Jiří Techet <techet at gmail.com>
Date: Fri, 29 Jul 2016 14:55:07 UTC
Commit: bf0702e2ec63009c731a6a65d40c89f5ac6695d2
https://github.com/geany/geany/commit/bf0702e2ec63009c731a6a65d40c89f5ac6695d2
Log Message:
-----------
Use uctags implementation of keyword.c/h
Basically just the stuff I added to uctags to improve hashing of keywords.
This patch drops some extra stuff from uctags we don't need at the moment
and which would require changes in other files.
Modified Paths:
--------------
ctags/main/keyword.c
ctags/main/keyword.h
Modified: ctags/main/keyword.c
284 lines changed, 131 insertions(+), 153 deletions(-)
===================================================================
@@ -1,43 +1,39 @@
/*
-*
-* Copyright (c) 1998-2001, Darren Hiebert
+* Copyright (c) 1998-2002, Darren Hiebert
*
* This source code is released for free distribution under the terms of the
-* GNU General Public License.
+* GNU General Public License version 2 or (at your option) any later version.
*
* Manages a keyword hash.
*/
/*
* INCLUDE FILES
*/
-#include "general.h" /* must always come first */
+#include "general.h" /* must always come first */
#include <string.h>
+#include "debug.h"
#include "keyword.h"
-#include "main.h"
#include "options.h"
-
-/*
-* MACROS
-*/
-#define HASH_EXPONENT 7 /* must be less than 17 */
+#include "routines.h"
+#include "main.h"
/*
* DATA DECLARATIONS
*/
typedef struct sHashEntry {
- struct sHashEntry *next;
- const char *string;
- langType language;
- int value;
+ struct sHashEntry *next;
+ const char *string;
+ langType language;
+ int value;
} hashEntry;
/*
* DATA DEFINITIONS
*/
-static const unsigned int TableSize = 1 << HASH_EXPONENT;
+static const unsigned int TableSize = 2039; /* prime */
static hashEntry **HashTable = NULL;
/*
@@ -46,71 +42,61 @@ static hashEntry **HashTable = NULL;
static hashEntry **getHashTable (void)
{
- static boolean allocated = FALSE;
+ static boolean allocated = FALSE;
- if (! allocated)
- {
- unsigned int i;
+ if (! allocated)
+ {
+ unsigned int i;
- HashTable = xMalloc (TableSize, hashEntry*);
+ HashTable = xMalloc (TableSize, hashEntry*);
- for (i = 0 ; i < TableSize ; ++i)
- HashTable [i] = NULL;
+ for (i = 0 ; i < TableSize ; ++i)
+ HashTable [i] = NULL;
- allocated = TRUE;
- }
- return HashTable;
+ allocated = TRUE;
+ }
+ return HashTable;
}
static hashEntry *getHashTableEntry (unsigned long hashedValue)
{
- hashEntry **const table = getHashTable ();
- hashEntry *entry;
+ hashEntry **const table = getHashTable ();
+ hashEntry *entry;
- Assert (hashedValue < TableSize);
- entry = table [hashedValue];
+ Assert (hashedValue < TableSize);
+ entry = table [hashedValue];
- return entry;
+ return entry;
}
-static unsigned long hashValue (const char *const string)
+static unsigned int hashValue (const char *const string, langType language)
{
- unsigned long value = 0;
- const unsigned char *p;
-
- Assert (string != NULL);
-
- /* We combine the various words of the multiword key using the method
- * described on page 512 of Vol. 3 of "The Art of Computer Programming".
- */
- for (p = (const unsigned char *) string ; *p != '\0' ; ++p)
- {
- value <<= 1;
- if (value & 0x00000100L)
- value = (value & 0x000000ffL) + 1L;
- value ^= *p;
- }
- /* Algorithm from page 509 of Vol. 3 of "The Art of Computer Programming"
- * Treats "value" as a 16-bit integer plus 16-bit fraction.
- */
- value *= 40503L; /* = 2^16 * 0.6180339887 ("golden ratio") */
- value &= 0x0000ffffL; /* keep fractional part */
- value >>= 16 - HASH_EXPONENT; /* scale up by hash size and move down */
-
- return value;
+ const signed char *p;
+ unsigned int h = 5381;
+
+ Assert (string != NULL);
+
+ /* "djb" hash as used in g_str_hash() in glib */
+ for (p = (const signed char *)string; *p != '\0'; p++)
+ h = (h << 5) + h + *p;
+
+ /* consider language as an extra "character" and add it to the hash */
+ h = (h << 5) + h + language;
+
+ return h;
}
-static hashEntry *newEntry (const char *const string,
- langType language, int value)
+static hashEntry *newEntry (
+ const char *const string, langType language, int value)
{
- hashEntry *const entry = xMalloc (1, hashEntry);
+ hashEntry *const entry = xMalloc (1, hashEntry);
- entry->next = NULL;
- entry->string = string;
- entry->language = language;
- entry->value = value;
+ entry->next = NULL;
+ entry->string = string;
+ entry->language = language;
+ entry->value = value;
- return entry;
+ return entry;
}
/* Note that it is assumed that a "value" of zero means an undefined keyword
@@ -120,135 +106,127 @@ static hashEntry *newEntry (const char *const string,
*/
extern void addKeyword (const char *const string, langType language, int value)
{
- const unsigned long hashedValue = hashValue (string);
- hashEntry *tableEntry = getHashTableEntry (hashedValue);
- hashEntry *entry = tableEntry;
-
-#ifdef TM_DEBUG
- fprintf(stderr, "Adding keyword %s to language %d\n", string, language);
-#endif
- if (entry == NULL)
- {
- hashEntry **const table = getHashTable ();
- hashEntry *new = newEntry (string, language, value);
+ const unsigned int index = hashValue (string, language) % TableSize;
+ hashEntry *entry = getHashTableEntry (index);
- table [hashedValue] = new;
- }
- else
- {
- hashEntry *prev = NULL;
-
- while (entry != NULL)
+ if (entry == NULL)
{
- if (language == entry->language &&
- strcmp (string, entry->string) == 0)
- {
- Assert (("Already in table" == NULL));
- }
- prev = entry;
- entry = entry->next;
+ hashEntry **const table = getHashTable ();
+ table [index] = newEntry (string, language, value);
}
- if (entry == NULL)
+ else
{
- hashEntry *new = newEntry (string, language, value);
-
- Assert (prev != NULL);
- prev->next = new;
+ hashEntry *prev = NULL;
+
+ while (entry != NULL)
+ {
+ if (language == entry->language &&
+ strcmp (string, entry->string) == 0)
+ {
+ Assert (("Already in table" == NULL));
+ }
+ prev = entry;
+ entry = entry->next;
+ }
+ if (entry == NULL)
+ {
+ Assert (prev != NULL);
+ prev->next = newEntry (string, language, value);
+ }
}
- }
}
extern int lookupKeyword (const char *const string, langType language)
{
- const unsigned long hashedValue = hashValue (string);
- hashEntry *entry = getHashTableEntry (hashedValue);
- int value = -1;
+ const unsigned int index = hashValue (string, language) % TableSize;
+ hashEntry *entry = getHashTableEntry (index);
+ int result = -1;
- while (entry != NULL)
- {
- if (language == entry->language && strcmp (string, entry->string) == 0)
+ while (entry != NULL)
{
- value = entry->value;
- break;
+ if (language == entry->language && strcmp (string, entry->string) == 0)
+ {
+ result = entry->value;
+ break;
+ }
+ entry = entry->next;
}
- entry = entry->next;
- }
- return value;
+ return result;
}
extern void freeKeywordTable (void)
{
- if (HashTable != NULL)
- {
- unsigned int i;
-
- for (i = 0 ; i < TableSize ; ++i)
+ if (HashTable != NULL)
{
- hashEntry *entry = HashTable [i];
-
- while (entry != NULL)
- {
- hashEntry *next = entry->next;
- eFree (entry);
- entry = next;
- }
+ unsigned int i;
+
+ for (i = 0 ; i < TableSize ; ++i)
+ {
+ hashEntry *entry = HashTable [i];
+
+ while (entry != NULL)
+ {
+ hashEntry *next = entry->next;
+ eFree (entry);
+ entry = next;
+ }
+ }
+ eFree (HashTable);
}
- eFree (HashTable);
- }
}
#ifdef TM_DEBUG
static void printEntry (const hashEntry *const entry)
{
- printf (" %-15s %-7s\n", entry->string, getLanguageName (entry->language));
+ printf (" %-15s %-7s\n", entry->string, getLanguageName (entry->language));
}
static unsigned int printBucket (const unsigned int i)
{
- hashEntry **const table = getHashTable ();
- hashEntry *entry = table [i];
- unsigned int measure = 1;
- boolean first = TRUE;
-
- printf ("%2d:", i);
- if (entry == NULL)
- printf ("\n");
- else while (entry != NULL)
- {
- if (! first)
- printf (" ");
- else
+ hashEntry **const table = getHashTable ();
+ hashEntry *entry = table [i];
+ unsigned int measure = 1;
+ boolean first = TRUE;
+
+ printf ("%2d:", i);
+ if (entry == NULL)
+ printf ("\n");
+ else while (entry != NULL)
{
- printf (" ");
- first = FALSE;
+ if (! first)
+ printf (" ");
+ else
+ {
+ printf (" ");
+ first = FALSE;
+ }
+ printEntry (entry);
+ entry = entry->next;
+ measure = 2 * measure;
}
- printEntry (entry);
- entry = entry->next;
- measure = 2 * measure;
- }
- return measure - 1;
+ return measure - 1;
}
extern void printKeywordTable (void)
{
- unsigned long emptyBucketCount = 0;
- unsigned long measure = 0;
- unsigned int i;
+ unsigned long emptyBucketCount = 0;
+ unsigned long measure = 0;
+ unsigned int i;
- for (i = 0 ; i < TableSize ; ++i)
- {
- const unsigned int pass = printBucket (i);
+ for (i = 0 ; i < TableSize ; ++i)
+ {
+ const unsigned int pass = printBucket (i);
- measure += pass;
- if (pass == 0)
- ++emptyBucketCount;
- }
+ measure += pass;
+ if (pass == 0)
+ ++emptyBucketCount;
+ }
- printf ("spread measure = %ld\n", measure);
- printf ("%ld empty buckets\n", emptyBucketCount);
+ printf ("spread measure = %ld\n", measure);
+ printf ("%ld empty buckets\n", emptyBucketCount);
}
#endif
-/* vi:set tabstop=8 shiftwidth=4: */
+/* vi:set tabstop=4 shiftwidth=4: */
Modified: ctags/main/keyword.h
15 lines changed, 7 insertions(+), 8 deletions(-)
===================================================================
@@ -1,19 +1,18 @@
/*
-*
-* Copyright (c) 1998-2001, Darren Hiebert
+* Copyright (c) 1998-2002, Darren Hiebert
*
* This source code is released for free distribution under the terms of the
-* GNU General Public License.
+* GNU General Public License version 2 or (at your option) any later version.
*
* External interface to keyword.c
*/
-#ifndef _KEYWORD_H
-#define _KEYWORD_H
+#ifndef CTAGS_MAIN_KEYWORD_H
+#define CTAGS_MAIN_KEYWORD_H
/*
* INCLUDE FILES
*/
-#include "general.h" /* must always come first */
+#include "general.h" /* must always come first */
#include "parse.h"
@@ -27,6 +26,6 @@ extern void freeKeywordTable (void);
extern void printKeywordTable (void);
#endif
-#endif /* _KEYWORD_H */
+#endif /* CTAGS_MAIN_KEYWORD_H */
-/* vi:set tabstop=8 shiftwidth=4: */
+/* vi:set tabstop=4 shiftwidth=4: */
--------------
This E-Mail was brought to you by github_commit_mail.py (Source: https://github.com/geany/infrastructure).
More information about the Commits
mailing list