list.cpp File Reference

LINKED LIST implementation. More...

#include "list.h"
#include "common.h"
#include "mem.h"
#include <assert.h>
#include <string.h>

Include dependency graph for list.cpp:

Go to the source code of this file.

Functions
static linkedList_t *	LIST_AllocateEntry (void *const data, linkedList_t *const next=0)
static void	LIST_AppendEntry (linkedList_t **list, linkedList_t *const entry)
linkedList_t *	LIST_Add (linkedList_t **listDest, void const *data, size_t length)
	Adds an entry to a new or to an already existing linked list.
const linkedList_t *	LIST_ContainsString (const linkedList_t *list, const char *string)
	Searches for the first occurrence of a given string.
linkedList_t *	LIST_GetPointer (linkedList_t *list, const void *data)
	Searches for the first occurrence of a given pointer.
static linkedList_t *	LIST_AllocateString (char const *data, linkedList_t *const next=0)
void	LIST_AddStringSorted (linkedList_t **listDest, const char *data)
void	LIST_PrependString (linkedList_t **listDest, const char *data)
	Adds a string as first entry to a linked list.
void	LIST_AddString (linkedList_t **listDest, const char *data)
	Adds an string to a new or to an already existing linked list. The string is copied here.
void	LIST_AddPointer (linkedList_t **listDest, void *data)
	Adds just a pointer to a new or to an already existing linked list.
bool	LIST_RemoveEntry (linkedList_t **list, linkedList_t *entry)
	Removes one entry from the linked list.
void	LIST_Delete (linkedList_t **list)
bool	LIST_Remove (linkedList_t **list, const void *data)
static linkedList_t *	_LIST_Sort (linkedList_t *list, linkedListSort_t sorter, const void *userData)
	This is the actual sort function. Notice that it returns the new head of the list. (It has to, because the head will not generally be the same element after the sort.).
void	LIST_Sort (linkedList_t **list, linkedListSort_t sorter, const void *userData)
linkedList_t *	LIST_CopyStructure (linkedList_t *src)
	Copies the list structure data - but not the content from the original list. We are only using pointers here.
bool	LIST_IsEmpty (const linkedList_t *list)
	Checks whether the given list is empty.
int	LIST_Count (const linkedList_t *list)
void *	LIST_GetByIdx (linkedList_t *list, int index)
	Get an entry of a linked list by its index in the list.
void *	LIST_GetRandom (linkedList_t *list)

Detailed Description

LINKED LIST implementation.

Definition in file list.cpp.

Function Documentation

_LIST_Sort()

linkedList_t * _LIST_Sort ( linkedList_t * list, linkedListSort_t sorter, const void * userData )

static

This is the actual sort function. Notice that it returns the new head of the list. (It has to, because the head will not generally be the same element after the sort.).

Note

see http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

Definition at line 227 of file list.cpp.

References i, and linkedList_t::next.

Referenced by LIST_Sort().

LIST_Add()

linkedList_t * LIST_Add	(	linkedList_t **	listDest,
		void const *	data,
		size_t	length )

Adds an entry to a new or to an already existing linked list.

See also

LIST_AddString

LIST_RemoveEntry

Returns

Returns a pointer to the data that has been added, wrapped in a linkedList_t

Todo

Optimize this to not allocate memory for every entry - but use a hunk

Definition at line 54 of file list.cpp.

References com_genericPool, data, length, LIST_AllocateEntry(), LIST_AppendEntry(), and Mem_PoolAllocTypeN.

Referenced by LIST_Add().

LIST_AddPointer()

void LIST_AddPointer	(	linkedList_t **	listDest,
		void *	data )

Adds just a pointer to a new or to an already existing linked list.

See also

LIST_Add

LIST_RemoveEntry

Todo

Optimize this to not allocate memory for every entry - but use a hunk

Definition at line 153 of file list.cpp.

References data, LIST_AllocateEntry(), LIST_AppendEntry(), and linkedList_t::ptr.

Referenced by GAME_AppendTeamMember(), GAME_GetImportData(), GAME_LoadTeamInfo(), GAME_Spawn(), HUD_PopupFiremodeReservation(), LIST_CopyStructure(), and UI_CvarListenerNodeBind().

LIST_AddString()

void LIST_AddString	(	linkedList_t **	listDest,
		const char *	data )

Adds an string to a new or to an already existing linked list. The string is copied here.

See also

LIST_Add

LIST_RemoveEntry

LIST_PrependString

Todo

Optimize this to not allocate memory for every entry - but use a hunk

Definition at line 139 of file list.cpp.

References data, LIST_AllocateString(), and LIST_AppendEntry().

Referenced by Com_LuaTableToStringList(), Com_ParseActorNames(), Com_ParseActorSounds(), Com_ParseList(), FS_GetModList(), GAME_GetImportData(), GAME_InitMissionBriefing(), HUD_PopupFiremodeReservation(), Irc_Client_Names_f(), Sys_ListFilteredFiles(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), UI_AddCvarListener_f(), UI_CvarListenerNodeCallback(), UI_ExecuteCallAction(), UI_MaterialEditorUpdate(), UI_PushWindow_f(), UI_TextNodeGenerateLineSplit(), and cgame_import_t::void().

LIST_AddStringSorted()

void LIST_AddStringSorted	(	linkedList_t **	listDest,
		const char *	data )

Definition at line 107 of file list.cpp.

References data, LIST_AllocateString(), linkedList_t::next, and Q_StringSort().

Referenced by _AddToListBlock(), GAME_GetImportData(), TEST_F(), and cgame_import_t::void().

LIST_AllocateEntry()

linkedList_t * LIST_AllocateEntry ( void *const data, linkedList_t *const next = 0 )

static

Definition at line 32 of file list.cpp.

References com_genericPool, data, linkedList_t::data, Mem_PoolAllocType, and linkedList_t::next.

Referenced by LIST_Add(), LIST_AddPointer(), and LIST_AllocateString().

LIST_AllocateString()

linkedList_t * LIST_AllocateString ( char const * data, linkedList_t *const next = 0 )

static

Definition at line 102 of file list.cpp.

References data, LIST_AllocateEntry(), and Mem_StrDup.

Referenced by LIST_AddString(), LIST_AddStringSorted(), and LIST_PrependString().

LIST_AppendEntry()

void LIST_AppendEntry ( linkedList_t ** list, linkedList_t *const entry )

static

Append entry to end of list.

Definition at line 41 of file list.cpp.

References linkedList_t::next.

Referenced by LIST_Add(), LIST_AddPointer(), and LIST_AddString().

LIST_ContainsString()

const linkedList_t * LIST_ContainsString	(	const linkedList_t *	list,
		const char *	string )

Searches for the first occurrence of a given string.

Returns

the linkedList_t pointer if the string is found, otherwise nullptr

Note

if string is nullptr, the function returns nullptr

See also

LIST_AddString

Definition at line 73 of file list.cpp.

References linkedList_t::data, linkedList_t::next, and Q_streq.

Referenced by _AddToListBlock(), GAME_ChangeEquip(), GAME_GetImportData(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), UI_AddCvarListener_f(), UI_RemoveCvarListener_f(), and UI_UpdateInvisOptions().

LIST_CopyStructure()

linkedList_t * LIST_CopyStructure

(

linkedList_t *

src

)

Copies the list structure data - but not the content from the original list. We are only using pointers here.

Definition at line 321 of file list.cpp.

References data, dest, LIST_AddPointer(), and LIST_Foreach.

LIST_Count()

int LIST_Count

(

const linkedList_t *

list

)

See also

LIST_Add

LIST_RemoveEntry

Definition at line 344 of file list.cpp.

References count, and linkedList_t::next.

Referenced by Com_ParseActorModels(), Com_ParseBodyPart(), Com_ParseEquipment(), FS_BuildFileList(), GAME_GetImportData(), GAME_InitializeBattlescape(), GAME_SaveTeam(), GAME_SendCurrentTeamSpawningInfo(), GAME_UpdateActiveTeamList(), HUD_PopupFiremodeReservation(), HUD_ShotReserve_f(), cgame_import_t::int(), LIST_GetRandom(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TR_List_f(), and UI_ExecuteEventActionsEx().

LIST_Delete()

void LIST_Delete

(

linkedList_t **

list

)

See also

LIST_Add

LIST_RemoveEntry

Definition at line 195 of file list.cpp.

References linkedList_t::data, Mem_Free, linkedList_t::next, and linkedList_t::ptr.

Referenced by _wrap_push_window(), CL_ParseLanguages(), CL_ParseSequence(), Com_AddObjectLinks(), Com_ParseActorModels(), Com_ParseActorNames(), Com_ParseBodyPart(), Com_ParseEquipment(), Com_ParseList(), Com_ParseTeam(), uiLineChartNode::deleteNode(), FS_BuildFileList(), GAME_GetImportData(), GAME_ResetCharacters(), GAME_SetMode(), HUD_PopupFiremodeReservation(), M_ParseMusic(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), UI_ClearLineChart(), UI_ExecuteCallAction(), UI_PushWindow_f(), UI_ResetData(), UI_TextNodeGenerateLineSplit(), and cgame_import_t::void().

LIST_GetByIdx()

void * LIST_GetByIdx	(	linkedList_t *	list,
		int	index )

Get an entry of a linked list by its index in the list.

Parameters

[in]	list	Linked list to get the entry from.
[in]	index	The index of the entry in the linked list.

Returns

A void pointer of the content in the list-entry.

Definition at line 362 of file list.cpp.

References linkedList_t::data, i, index, LIST_IsEmpty(), and linkedList_t::next.

Referenced by CL_ChangeSkin_f(), GAME_GetImportData(), HUD_ShotReserve_f(), LIST_GetRandom(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), UI_ExecuteLuaMethod(), and UI_GetTextFromList().

LIST_GetPointer()

linkedList_t * LIST_GetPointer	(	linkedList_t *	list,
		const void *	data )

Searches for the first occurrence of a given pointer.

Returns

the linkedList_t pointer if the string is found, otherwise nullptr

Note

if data is nullptr, the function returns nullptr

O(n)

Only use this for small linked lists

Definition at line 91 of file list.cpp.

References data, linkedList_t::data, and linkedList_t::next.

Referenced by GAME_GetImportData(), LIST_Remove(), and UI_CvarListenerNodeBind().

LIST_GetRandom()

void * LIST_GetRandom

(

linkedList_t *

list

)

Definition at line 381 of file list.cpp.

References LIST_Count(), and LIST_GetByIdx().

Referenced by GAME_GetImportData(), TEST_F(), and UI_MapInfo().

LIST_IsEmpty()

bool LIST_IsEmpty

(

const linkedList_t *

list

)

Checks whether the given list is empty.

Parameters

[in]

list

The linked list to check

Returns

true if empty, false otherwise

Definition at line 335 of file list.cpp.

Referenced by cgame_import_t::bool(), GAME_ChangeEquip(), GAME_GetCGameAPI(), GAME_GetImportData(), GAME_InitMissionBriefing(), GAME_IsTeamEmpty(), GAME_SaveTeam_f(), GAME_Spawn(), GAME_SpawnSoldiers(), GAME_StartMatch(), GAME_UpdateInventory(), LIST_GetByIdx(), LIST_Sort(), uiCvarNode::onWindowClosed(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), GameTest::testCountSpawnpointsForMap(), GameTest::testCountSpawnpointsForMapInMultiplayerMode(), GameTest::testCountSpawnpointsForMapWithAssembly(), GameTest::testCountSpawnpointsForMapWithAssemblyAndAircraft(), and UI_RemoveCvarListener_f().

LIST_PrependString()

void LIST_PrependString	(	linkedList_t **	listDest,
		const char *	data )

Adds a string as first entry to a linked list.

Parameters

listDest	The linked list to add the string, too. If this is nullptr, a new list is created
data	The string to add to the list

See also

LIST_AddString

Todo

Optimize this to not allocate memory for every entry - but use a hunk

Definition at line 127 of file list.cpp.

References data, and LIST_AllocateString().

Referenced by GAME_GetImportData(), and TEST_F().

LIST_Remove()

bool LIST_Remove	(	linkedList_t **	list,
		const void *	data )

See also

LIST_Add

LIST_RemoveEntry

Definition at line 213 of file list.cpp.

References data, LIST_GetPointer(), and LIST_RemoveEntry().

Referenced by cgame_import_t::bool(), GAME_GetImportData(), GAME_SaveTeamState_f(), uiCvarNode::onWindowClosed(), and TEST_F().

LIST_RemoveEntry()

bool LIST_RemoveEntry	(	linkedList_t **	list,
		linkedList_t *	entry )

Removes one entry from the linked list.

See also

LIST_AddString

LIST_Add

LIST_AddPointer

LIST_Delete

Returns

true if the removal was successful, false otherwise.

Definition at line 172 of file list.cpp.

References linkedList_t::data, Mem_Free, linkedList_t::next, and linkedList_t::ptr.

Referenced by cgame_import_t::bool(), GAME_GetImportData(), LIST_Remove(), TEST_F(), and UI_RemoveCvarListener_f().

LIST_Sort()

void LIST_Sort	(	linkedList_t **	list,
		linkedListSort_t	sorter,
		const void *	userData )

Definition at line 310 of file list.cpp.

References _LIST_Sort(), and LIST_IsEmpty().