LinkedList

LinkedList is a standard ASSS data type. It is the simplest way of representing a sequential list of data.

Properties

• Allows inserting new data anywhere in the list (linear time), but is fastest for inserting to the beginning or end (constant time.)
• Searching for data in the list takes linear time.
• Most effective data structure to use when you will be using all of the items in the structure at once regularly.

Declaration Examples

/* LinkedLists can be declared in one of two ways depending on preference and need, either as a pointer that gets
   dynamically allocated with the function LLAlloc() or as a struct that is initialized with LL_INITIALIZER or LLInit(). */

LinkedList *listA = LLAlloc();
LinkedList listB = LL_INITIALIZER;
LinkedList listC;

LLInit(&listC);

Usage Examples

/* partial module for controlling an opt-in list for an arena */

local int arenaDataKey;
typedef struct arenaDataStruct
{
	LinkedList *memberList;
} arenaDataStruct;

/* ?optin command players can use to get on the list */
local void Coptin(const char *tc, const char *params, Player *p, const Target *target)
{
	arenaDataStruct *ad = P_ARENA_DATA(p->arena, arenaDataKey);

	/* use the astrdup function to copy the player's name into the membersList. */
	LLAdd(ad->membersList, astrdup(p->name));
	chat->SendMessage(p, "You have been added to the members list.");

	/* note that this function does not check to see if the person's name is already on the list. */
}

/* ?listmembers command players can use to see who is on the list */
local void Clistmembers(const char *tc, const char *params, Player *p, const Target *target)
{
	Link *link;
	char *memberName;
	arenaDataStruct *ad = P_ARENA_DATA(p->arena, arenaDataKey);

	chat->SendMessage(p, "Members:");
	FOR_EACH(ad->membersList, memberName, link)
	{
		chat->SendMessage(p, "- %s", memberName);
	}
}

/* a function to be called when initializing arena data, before we can use our list */
local void initializeArenaData(Arena *a)
{
	arenaDataStruct *ad = P_ARENA_DATA(a, arenaDataKey);

	/* dynamically allocate the member list */
	ad->memberList = LLAlloc();
}

/* a function to be called when the list is no longer needed */
local void cleanupArenaData(Arena *a)
{
	arenaDataStruct *ad = P_ARENA_DATA(a, arenaDataKey);

	/* astrdup dynamically allocates memory that has to be passed to afree when finished.
	   the LLEnum function will call afree for each item in the list to take care of this for us. */
	LLEnum(ad->memberList, afree);

	/* now we have freed all of the data in the list, we can free the list itself. */
	LLFree(ad->memberList);
}

LinkedList sorting function

Sorting functions passed to LLSort must be of the form:

int function(const void *a, const void *b);

Standard Functions

Initialization/Cleanup

• LinkedList * LLAlloc(void): Allocates and initalizes a new LinkedList.
• void LLInit(LinkedList *): Initializes the linked list, should only be called before first use. Does not need to be called after LLAlloc, it's useful for statically allocated LinkedLists (LinkedList, not LinkedList *)
• void LLEmpty(LinkedList *): Removes all items from the list (doesn't deallocate them, you have to take care of this on your own.)
• void LLFree(LinkedList *): Calls LLEmpty on the list and then frees it.

Data Manipulation

• void LLAdd(LinkedList *, const void *data): Adds data to the end of the list.
• void LLAddFirst(LinkedList *, const void *data): Adds data to the beginning of the list.
• void LLInsertAfter(LinkedList *, Link *link, const void *data): Adds data to a list after the specified Link *.
• void LLRemove(LinkedList *, const void *data): Removes the first occurrence of the data from the list.
• void LLRemoveAll(LinkedList *, const void *data): Removes all occurrences of the data from the list.
• void * LLRemoveFirst(LinkedList *): Removes the first item in the list and returns it.
• int LLIsEmpty(LinkedList *): Returns true if there is nothing in the list.
• int LLCount(LinkedList *): Returns the number of items on the list.
• int Member(LinkedList *, const void *data): Returns true if the specified data is on the list at least once
• void LLEnum(LinkedList *, void(*fn)(const void *)): Calls the specified function (fn) once for each item in the list. The function LLEnumNC also exists, where the specified function takes a non-const parameter instead.
• Link * LLGetHead(LinkedList *): Returns the first Link in the list.
• void LLSort(LinkedList *, int (*lt)(const void *, const void *)): Sorts the list using the specified less-than function. Given two parameters, the function will decide which is the lesser one. If NULL is specified as the function, LLSort will sort based on which pointer value is lower. The standard ASSS function LLSort_StringCompare exists and can be passed into LLSort for sorting char * values.

Standard Macros

• LL_INITIALIZER: Can be used to initialize a LinkedList declared on the stack. (LinkedList a = LL_INITIALIZER)
• FOR_EACH(list, var, link): Iterates through the LinkedList, calling the ensuing block once for each item in the list (storing the item in var.) Link *link and var must be declared ahead of time.