GSLinkedList documentation

Authors

Richard Frith-Macdonald (rfm@gnu.org)

Date: Generated at 2025-02-28 22:10:47 +0000

Copyright: (C) 2010 Free Software Foundation, Inc.


Contents -

  1. Software documentation for the GSLinkStore class
  2. Software documentation for the GSLinkedList class
  3. Software documentation for the GSListLink class
  4. GSLinkedList types
  5. GSLinkedList functions

Software documentation for the GSLinkStore class

GSLinkStore : GSLinkedList

Declared in:
GSLinkedList.h
This class extends GSLinkedList by providing storage for unused links and re-using those links when a new link is needed.
This avoids the overhead of allocating/deallocating links and provides an API more like a mutable array.

Instance Variables

Method summary


addObject: 

- (void) addObject: (id)anObject;
Adds an object at the end of the list (calls -insertObject:after:).

firstObject 

- (id) firstObject;
Returns the first (head) object in the list or nil if the list is empty.

insertObject: after: 

- (void) insertObject: (id)anObject after: (GSListLink*)at;
Inserts anObject immediately after the specified link. If at is nil the object is inserted at the end of the list (as tail).

insertObject: before: 

- (void) insertObject: (id)anObject before: (GSListLink*)at;
Inserts anObject immediately before the specified link. If at is nil the object is inserted at the start of the list (as head).

lastObject 

- (id) lastObject;
Returns the last (tail) object in the list or nil if the list is empty.

purge 

- (void) purge;
Removes any unused links from the list (to release the memory they occupied).

removeFirstObject 

- (void) removeFirstObject;
Removes the first object from the list (or does nothing if the list is empty).

removeLastObject 

- (void) removeLastObject;
Removes the last object from the list (or does nothing if the list is empty).

removeObjectAt: 

- (void) removeObjectAt: (GSListLink*)at;
Removes the object in the specified link.

removeObjectAtIndex: 

- (void) removeObjectAtIndex: (NSUInteger)index;
Removes the object at the specified position.



Instance Variables for GSLinkStore Class

free

@public GSListLink* free;
The unused links




Software documentation for the GSLinkedList class

GSLinkedList : NSObject

Declared in:
GSLinkedList.h
GSLinkedList manages a list of GSListLink objects.
The notional direction of the list is from head to tail. So the head is considered to be the first link in the list and tail is considered to be the last (head is before tail, tail is after head).

Instance Variables

Method summary


append: 

- (void) append: (GSListLink*)link;
Appends link at the end of the linked list managed by the receiver.
Retains the link.

count 

- (NSUInteger) count;
Returns the number of links in the list.

empty 

- (void) empty;
Remove all links from the list and release them all.

findEqual: from: back: 

- (GSListLink*) findEqual: (NSObject*)object from: (GSListLink*)start back: (BOOL)aFlag;
Searches the linked list returning the link containing object or nil if it is not found.
The comparison is performed using the [NSObject -isEqual:] method of object.
If start is nil then the whole list is searched.
This method will not find links containing nil items.

findIdentical: from: back: 

- (GSListLink*) findIdentical: (NSObject*)object from: (GSListLink*)start back: (BOOL)aFlag;
Searches the linked list returning the link containing object or nil if it is not found.
If start is nil then the whole list is searched.
A direct pointer comparison is used to determine equality.

head 

- (GSListLink*) head;
Returns the first link in the list.

insert: after: 

- (void) insert: (GSListLink*)link after: (GSListLink*)at;
Inserts other immediately after the receiver.
Retains the link.

insert: before: 

- (void) insert: (GSListLink*)link before: (GSListLink*)at;
Inserts other immediately before the receiver.
Retains the link.

removeLink: 

- (void) removeLink: (GSListLink*)link;
Removes the link from the receiver.
releases the link.

tail 

- (GSListLink*) tail;
Returns the last link in the list.



Instance Variables for GSLinkedList Class

count

@public NSUInteger count;
Description forthcoming.

head

@public GSListLink* head;
Description forthcoming.

tail

@public GSListLink* tail;
Description forthcoming.




Software documentation for the GSListLink class

GSListLink : NSObject

Declared in:
GSLinkedList.h
GSListLink provides simple doubly linked list functionality to avoid the need to constantly re-invent it (as the OpenStep/Cocoa APIs do not provide this). The emphasis is on speed of operation so instance variables are directly accessible and inline functions are provided to manipulate them (without error cehcking), but you can/should avoid these direct access features unless speed is really critical.
A list may either be 'normal'... (where the head/tail ends of the list have a nil pointer to the previous/next link) or 'circular' in which case the list is not terminated.
The GSListLink item carries a minimal payload of a single item which is retained by the link.
The GSListLink owner is an optional pointer to an object which 'owns' the link... a GSLinkedList instance may use this to check link ownership when manipulating links.

Instance Variables

Method summary


initCircular 

- (id) initCircular;
Initialise the receiver as a link for a circular linked list.

item 

- (NSObject*) item;
Return the item in the link.

next 

- (GSListLink*) next;
Return the next item in the list containing the receiver, or nil if there are no more items.

owner 

- (GSLinkedList*) owner;
Return the list which owns the receiver or nil if the receiver is not in a list.

previous 

- (GSListLink*) previous;
Return the previous item in the list containing the receiver, or nil if there are no more items.

setItem: 

- (void) setItem: (NSObject*)anItem;
Set an item value by retaining it and releasing any previous value.



Instance Variables for GSListLink Class

item

@public NSObject* item;
Description forthcoming.

next

@public GSListLink* next;
Description forthcoming.

owner

@public GSLinkedList* owner;
Description forthcoming.

previous

@public GSListLink* previous;
Description forthcoming.




GSLinkedList types

NSUInteger

typedef unsigned int NSUInteger;
Description forthcoming.

GSLinkedList functions

GSLinkCircularInsertAfter

void GSLinkCircularInsertAfter(GSListLink* link, GSListLink* at);
Inserts link after at in a circular list.
Arguments must not be nil and link must not be in a list (ie its next and previous pointers must point to itsself).

GSLinkCircularInsertBefore

void GSLinkCircularInsertBefore(GSListLink* link, GSListLink* at);
Inserts link before at in a circular list.
Arguments must not be nil and link must not be in a list (ie its next and previous pointers must point to itsself).

GSLinkCircularRemove

void GSLinkCircularRemove(GSListLink* link);
Removes link from any list it is in.
The link argument must not be nil.

GSLinkInsertAfter

void GSLinkInsertAfter(GSListLink* link, GSListLink* at);
Inserts link after at in a normal list.
Arguments must not be nil and link must not be in a list (ie its next and previous pointers must both be nil).

GSLinkInsertBefore

void GSLinkInsertBefore(GSListLink* link, GSListLink* at);
Inserts link before at in a normal list.
Arguments must not be nil and link must not be in a list (ie its next and previous pointers must both be nil).

GSLinkRemove

void GSLinkRemove(GSListLink* link);
Removes link from the list it is in.
The link argument must not be nil.

GSLinkStoreInsertObjectAfter

void GSLinkStoreInsertObjectAfter(NSObject* anObject, GSLinkStore* list, GSListLink* at);
Adds the object to the list after the specified link.
Calls GSLinkedListInsertAfter() .

GSLinkStoreInsertObjectBefore

void GSLinkStoreInsertObjectBefore(NSObject* anObject, GSLinkStore* list, GSListLink* at);
Adds the object to the list before the specified link.
Calls GSLinkedListInsertBefore() .

GSLinkStoreRemoveObjectAt

void GSLinkStoreRemoveObjectAt(GSLinkStore* list, GSListLink* at);
Removes the object held in the specified link.
If at is nil or is not owned by the list, this does nothing.

GSLinkedListFindEqual

GSListLink* GSLinkedListFindEqual(NSObject* object, GSLinkedList* list, GSListLink* from, BOOL back);
Searches from list to the end looking for the first link containing object (as determined by using object's [NSObject -isEqual:] method).
If back is YES, the search is in the direction from tail to head rather than the normal search from head to tail.
If from is nil the list is search from head or tail as appropriate to the direction in which it is searched.

GSLinkedListFindIdentical

GSListLink* GSLinkedListFindIdentical(NSObject* object, GSLinkedList* list, GSListLink* from, BOOL back);
Searches from list to the end looking for the first link containing object (as determined by direct pointer comparison).
If back is YES, the search is in the direction from tail to head rather than the normal search from head to tail.
If from is nil the list is search from head or tail as appropriate to the direction in which it is searched.

GSLinkedListFirstObject

id GSLinkedListFirstObject(GSLinkedList* list);
Returns the first object in the list.

GSLinkedListInsertAfter

void GSLinkedListInsertAfter(GSListLink* link, GSLinkedList* list, GSListLink* at);
Inserts link immediately after at.
If at is nil, inserts at the end of the list (link becomes tail).
Updates the head, tail and count variables of list.
Does not retain link .

GSLinkedListInsertBefore

void GSLinkedListInsertBefore(GSListLink* link, GSLinkedList* list, GSListLink* at);
Inserts link immediately before at.
If at is nil, inserts at the start of the list (link becomes head).
Updates the head, tail and count variables of list.
Does not retain link .

GSLinkedListLastObject

id GSLinkedListLastObject(GSLinkedList* list);
Returns the last object in the list.

GSLinkedListMoveToHead

void GSLinkedListMoveToHead(GSListLink* link, GSLinkedList* list);
Moves the link to the head of the list if it is not already there.

GSLinkedListMoveToTail

void GSLinkedListMoveToTail(GSListLink* link, GSLinkedList* list);
Moves the link to the tail of the list if it is not already there.

GSLinkedListRemove

void GSLinkedListRemove(GSListLink* link, GSLinkedList* list);
Removes link from the list.
Updates the head, tail and count variables of list.
Does not release link.