Skip to content

Commit

Permalink
Add generic pointer array and implement strList using it
Browse files Browse the repository at this point in the history 
A resizable array that can be also used as a stack is a useful
data structure that is currently missing in ctags and it's
re-implemented at various places unnecessarily (searching for
'realloc' in ctags sources reveals several places where
pointer array could be used).

The implementation just moves all the non-string-specific
functions from strList into the new ptrArray and uses ptrArray
internally. The only functional changes are:

- instead of creating 0-sized array at the beginning, the
  new implementation creates an array of size 8
- the new implementation always doubles the size of the array
  on reallocation; previously the array was increased by 10
  elements only
- the simplest functions were rewritten as macros to avoid
  function call overhead
  • Loading branch information
@techee
techee committed Sep 27, 2016
1 parent aef7003 commit d6067f1
Show file tree
Hide file tree
Showing 7 changed files with 228 additions and 92 deletions.
152 changes: 152 additions & 0 deletions main/ptrarray.c
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,152 @@
/*
* Copyright (c) 1999-2002, Darren Hiebert
*
* This source code is released for free distribution under the terms of the
* GNU General Public License version 2 or (at your option) any later version.
*
* This module contains functions managing resizable pointer arrays.
*/

/*
* INCLUDE FILES
*/
#include "general.h" /* must always come first */

#include <string.h>

#include "debug.h"
#include "ptrarray.h"

/*
* DATA DECLARATIONS
*/

struct sPtrArray {
unsigned int max;
unsigned int count;
void **array;
ptrArrayDeleteFunc deleteFunc;
};

/*
* FUNCTION DEFINITIONS
*/

extern ptrArray *ptrArrayNew (ptrArrayDeleteFunc deleteFunc)
{
ptrArray* const result = xMalloc (1, ptrArray);
result->max = 8;
result->count = 0;
result->array = xMalloc (result->max, void*);
result->deleteFunc = deleteFunc;
return result;
}

extern void ptrArrayAdd (ptrArray *const current, void *ptr)
{
Assert (current != NULL);
if (current->count == current->max)
{
current->max *= 2;
current->array = xRealloc (current->array, current->max, void*);
}
current->array [current->count++] = ptr;
}

extern void ptrArrayRemoveLast (ptrArray *const current)
{
Assert (current != NULL);
Assert (current->count > 0);
--current->count;
}

/* Combine array `from' into `current', deleting `from' */
extern void ptrArrayCombine (ptrArray *const current, ptrArray *const from)
{
unsigned int i;
Assert (current != NULL);
Assert (from != NULL);
for (i = 0 ; i < from->count ; ++i)
ptrArrayAdd (current, from->array [i]);
from->count = 0;
ptrArrayDelete (from);
}

extern unsigned int ptrArrayCount (const ptrArray *const current)
{
Assert (current != NULL);
return current->count;
}

extern void* ptrArrayItem (const ptrArray *const current, const unsigned int indx)
{
Assert (current != NULL);
return current->array [indx];
}

extern void* ptrArrayLast (const ptrArray *const current)
{
Assert (current != NULL);
Assert (current->count > 0);
return current->array [current->count - 1];
}

extern void ptrArrayClear (ptrArray *const current)
{
Assert (current != NULL);
if (current->deleteFunc)
{
unsigned int i;
for (i = 0 ; i < current->count ; ++i)
current->deleteFunc (current->array [i]);
}
current->count = 0;
}

extern void ptrArrayDelete (ptrArray *const current)
{
if (current != NULL)
{
ptrArrayClear (current);
eFree (current->array);
eFree (current);
}
}

extern bool ptrArrayHasTest (const ptrArray *const current,
bool (*test)(const void *ptr, void *userData),
void *userData)
{
bool result = false;
unsigned int i;
Assert (current != NULL);
for (i = 0 ; ! result && i < current->count ; ++i)
result = (*test)(current->array [i], userData);
return result;
}

extern void ptrArrayReverse (const ptrArray *const current)
{
unsigned int i, j;
void *tmp;

Assert (current != NULL);
for (i = 0, j = current->count - 1 ; i < (current->count / 2); ++i, --j)
{
tmp = current->array[i];
current->array[i] = current->array[j];
current->array[j] = tmp;
}
}

extern void ptrArrayDeleteItem (ptrArray* const current, unsigned int indx)
{
void *ptr = current->array[indx];

if (current->deleteFunc)
current->deleteFunc (ptr);

memmove (current->array + indx, current->array + indx + 1,
(current->count - indx) * sizeof (*current->array));
--current->count;
}
46 changes: 46 additions & 0 deletions main/ptrarray.h
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,46 @@
/*
* Copyright (c) 1999-2002, Darren Hiebert
*
* This source code is released for free distribution under the terms of the
* GNU General Public License version 2 or (at your option) any later version.
*
* Defines external interface to resizable pointer arrays.
*/
#ifndef CTAGS_MAIN_PTRARRAY_H
#define CTAGS_MAIN_PTRARRAY_H

/*
* INCLUDE FILES
*/
#include "general.h" /* must always come first */

/*
* DATA DECLARATIONS
*/

typedef void (*ptrArrayDeleteFunc) (void *data);

struct sPtrArray;
typedef struct sPtrArray ptrArray;

/*
* FUNCTION PROTOTYPES
*/

extern ptrArray *ptrArrayNew (ptrArrayDeleteFunc deleteFunc);
extern void ptrArrayAdd (ptrArray *const current, void *ptr);
extern void ptrArrayRemoveLast (ptrArray *const current);
extern void ptrArrayCombine (ptrArray *const current, ptrArray *const from);
extern void ptrArrayClear (ptrArray *const current);
extern unsigned int ptrArrayCount (const ptrArray *const current);
extern void* ptrArrayItem (const ptrArray *const current, const unsigned int indx);
extern void* ptrArrayLast (const ptrArray *const current);
extern void ptrArrayDelete (ptrArray *const current);
extern bool ptrArrayHasInsensitive (const ptrArray *const current, const void *const ptr);
extern bool ptrArrayHasTest (const ptrArray *const current,
bool (*test)(const void *ptr, void *userData),
void *userData);
extern void ptrArrayReverse (const ptrArray *const current);
extern void ptrArrayDeleteItem (ptrArray* const current, unsigned int indx);

#endif /* CTAGS_MAIN_PTRARRAY_H */
105 changes: 18 additions & 87 deletions main/strlist.c
View file
Original file line number Diff line number Diff line change
Expand Up @@ -26,53 +26,24 @@

extern stringList *stringListNew (void)
{
stringList* const result = xMalloc (1, stringList);
result->max = 0;
result->count = 0;
result->list = NULL;
return result;
return ptrArrayNew ((ptrArrayDeleteFunc)vStringDelete);
}

extern void stringListAdd (stringList *const current, vString *string)
{
enum { incrementalIncrease = 10 };
Assert (current != NULL);
if (current->list == NULL)
{
Assert (current->max == 0);
current->count = 0;
current->max = incrementalIncrease;
current->list = xMalloc (current->max, vString*);
}
else if (current->count == current->max)
{
current->max += incrementalIncrease;
current->list = xRealloc (current->list, current->max, vString*);
}
current->list [current->count++] = string;
ptrArrayAdd (current, string);
}

extern void stringListRemoveLast (stringList *const current)
{
Assert (current != NULL);
Assert (current->count > 0);
--current->count;
current->list [current->count] = NULL;
ptrArrayRemoveLast (current);
}

/* Combine list `from' into `current', deleting `from' */
extern void stringListCombine (
stringList *const current, stringList *const from)
{
unsigned int i;
Assert (current != NULL);
Assert (from != NULL);
for (i = 0 ; i < from->count ; ++i)
{
stringListAdd (current, from->list [i]);
from->list [i] = NULL;
}
stringListDelete (from);
ptrArrayCombine (current, from);
}

extern stringList* stringListNewFromArgv (const char* const* const argv)
Expand Down Expand Up @@ -108,50 +79,28 @@ extern stringList* stringListNewFromFile (const char* const fileName)

extern unsigned int stringListCount (const stringList *const current)
{
Assert (current != NULL);
return current->count;
return ptrArrayCount (current);
}

extern vString* stringListItem (
const stringList *const current, const unsigned int indx)
{
Assert (current != NULL);
return current->list [indx];
return ptrArrayItem (current, indx);
}

extern vString* stringListLast (const stringList *const current)
{
Assert (current != NULL);
Assert (current->count > 0);
return current->list [current->count - 1];
return ptrArrayLast (current);
}

extern void stringListClear (stringList *const current)
{
unsigned int i;
Assert (current != NULL);
for (i = 0 ; i < current->count ; ++i)
{
vStringDelete (current->list [i]);
current->list [i] = NULL;
}
current->count = 0;
ptrArrayClear (current);
}

extern void stringListDelete (stringList *const current)
{
if (current != NULL)
{
if (current->list != NULL)
{
stringListClear (current);
eFree (current->list);
current->list = NULL;
}
current->max = 0;
current->count = 0;
eFree (current);
}
ptrArrayDelete (current);
}

static bool compareString (
Expand All @@ -176,8 +125,8 @@ static int stringListIndex (
Assert (current != NULL);
Assert (string != NULL);
Assert (test != NULL);
for (i = 0 ; result == -1 && i < current->count ; ++i)
if ((*test)(string, current->list [i]))
for (i = 0 ; result == -1 && i < ptrArrayCount (current) ; ++i)
if ((*test)(string, ptrArrayItem (current, i)))
result = i;
return result;
}
Expand Down Expand Up @@ -224,31 +173,22 @@ extern bool stringListHasTest (const stringList *const current,
bool result = false;
unsigned int i;
Assert (current != NULL);
for (i = 0 ; ! result && i < current->count ; ++i)
result = (*test)(vStringValue (current->list [i]), userData);
for (i = 0 ; ! result && i < ptrArrayCount (current) ; ++i)
result = (*test)(vStringValue ((vString *)ptrArrayItem (current, i)), userData);
return result;
}

extern bool stringListDeleteItemExtension (stringList* const current, const char* const extension)

{
bool result = false;
int where;
#ifdef CASE_INSENSITIVE_FILENAMES
where = stringListIndex (current, extension, compareStringInsensitive);
#else
where = stringListIndex (current, extension, compareString);
#endif
if (where != -1)
{
vStringDelete (current->list [where]);
memmove (current->list + where, current->list + where + 1,
(current->count - where) * sizeof (*current->list));
current->list [current->count - 1] = NULL;
--current->count;
result = true;
}
return result;
ptrArrayDeleteItem (current, where);
return where != -1;
}

extern bool stringListExtensionMatched (
Expand Down Expand Up @@ -302,20 +242,11 @@ extern void stringListPrint (const stringList *const current, FILE *fp)
{
unsigned int i;
Assert (current != NULL);
for (i = 0 ; i < current->count ; ++i)
fprintf (fp, "%s%s", (i > 0) ? ", " : "", vStringValue (current->list [i]));
for (i = 0 ; i < ptrArrayCount (current) ; ++i)
fprintf (fp, "%s%s", (i > 0) ? ", " : "", vStringValue ((vString *)ptrArrayItem (current, i)));
}

extern void stringListReverse (const stringList *const current)
{
unsigned int i, j;
vString *tmp;

Assert (current != NULL);
for (i = 0, j = current->count - 1 ; i < (current->count / 2); ++i, --j)
{
tmp = current->list[i];
current->list[i] = current->list[j];
current->list[j] = tmp;
}
ptrArrayReverse (current);
}
Loading

0 comments on commit d6067f1

Please sign in to comment.