Chapter 5
Collections

Items

The following definitions are useful. An item is simply a block of memory.

typedef kBlock kItem;

typedef kInteger (*kItemCompare)(kItem aItem1, kItem aItem2);
typedef kVoid (*kItemApply)(kItem aItem);

Lists

The following are public. You should be used to them by now.

typedef kBlock kList;

typedef enum
{
  kListErrorOk,
  kListErrorHeapFull,
  kListErrorEmpty,
  kListErrorUnknown,
  kListErrorNilIterator
} kListErrorKind;

The following are private. They encapsulate the list node and list structures.

typedef struct SListNodeStruct
{
  kItem sItem;
  struct SListNodeStruct *sNext;
} kListNodeStruct;

typedef struct SListStruct
{
  kListNodeStruct *sHead, *sTail, *sIter;
  kSize sSize;
  kItemCompare sItemCompare;
} kListStruct;

We must initialize and deinitialize a list.

kList kListInit(kItemCompare aCompare)
{
  kListStruct *vList = (kListStruct*)kPointerInit(sizeof(kListStruct));

  if(!vList)
  {
    kError = kListErrorHeapFull;

    return 0;
  }

  vList->sHead = vList->sTail = vList->sIter = kNil;
  vList->sSize = 0;
  vList->sItemCompare = aCompare;

  kError = kListErrorOk;

  return kBlockUnlock((kPointer)vList);
}

kVoid kListDone(kList aList)
{
  kListRemoveAll(aList);
  kBlockDone(aList);

  kError = kListErrorOk;
}

There are functions to test if a list is empty and to obtain the number of elements of a list.

kBool kListIsEmpty(kList aList)
{
  kListStruct *vList = (kListStruct*)kBlockLock(aList);

  if(!vList)
  {
    kError = kListErrorUnknown;

    return kTrue;
  }

  kSize vSize = vList->sSize;

  kBlockUnlock((kPointer)vList);

  kError = kListErrorOk;

  return vSize == 0;
}

kSize kListGetSize(kList aList)
{
  kListStruct *vList = (kListStruct*)kBlockLock(aList);

  if(!vList)
  {
    kError = kListErrorUnknown;

    return 0;
  }

  kSize vSize = vList->sSize;

  kBlockUnlock((kPointer)vList);

  kError = kListErrorOk;

  return vSize;
}

Next come a function to add an item at the end the list, another at the beginning, and a function to remove all the items in a list.

kVoid kListAppend(kList aList, kItem aItem)
{
  kListStruct *vList = (kListStruct*)kBlockLock(aList);

  if(!vList)
  {
    kError = kListErrorUnknown;

    return;
  }

  kListNodeStruct *vListNode = (kListNodeStruct*)kPointerInit(sizeof(kListNodeStruct));

  if(vListNode)
  {
    vListNode->sItem = aItem;
    vListNode->sNext = kNil;

    kBlockIncRefs(aItem);
  }
  else
  {
    kBlockUnlock((kPointer)vList);

    kError = kListErrorHeapFull;

    return;
  }

  if(vList->sHead)
    vList->sTail = vList->sTail->sNext = vListNode;
  else
    vList->sTail = vList->sHead = vListNode;

  vList->sSize++;

  kBlockUnlock((kPointer)vListNode);
  kBlockUnlock((kPointer)vList);

  kError = kListErrorOk;
}

kVoid kListPreppend(kList aList, kItem aItem)
{
  kListStruct *vList = (kListStruct*)kBlockLock(aList);

  if(!vList)
  {
    kError = kListErrorUnknown;

    return;
  }

  kListNodeStruct *vListNode = (kListNodeStruct*)kPointerInit(sizeof(kListNodeStruct));

  if(vListNode)
  {
    vListNode->sItem = aItem;

    kBlockIncRefs(aItem);
  }
  else
  {
    kBlockUnlock((kPointer)vList);

    kError = kListErrorHeapFull;

    return;
  }

  if(vList->sHead)
  {
    vListNode->sNext = vList->sHead;
    vList->sHead = vListNode;
  }
  else
  {
    vListNode->sNext = kNil;
    vList->sTail = vList->sHead = vListNode;
  }

  vList->sSize++;

  kBlockUnlock((kPointer)vListNode);
  kBlockUnlock((kPointer)vList);

  kError = kListErrorOk;
}

kVoid kListRemoveAll(kList aList)
{
  kListIterFirst(aList);
  while(!kListIsEmpty(aList))
    kListIterRemove(aList);
}

Next, come the functions that deal with iterators. First, a function to place an iterator at the start of the list. Next, a function to move the iterator to the next item of the list. The other two functions test whether the iterator is at the start or at the end of the list.

kVoid kListIterFirst(kList aList)
{
  kListStruct *vList = (kListStruct*)kBlockLock(aList);

  if(!vList)
  {
    kError = kListErrorUnknown;

    return;
  }

  vList->sIter = vList->sHead;

  kBlockUnlock((kPointer)vList);

  kError = kListErrorOk;
}

kBool kListIterNext(kList aList)
{
  kListStruct *vList = (kListStruct*)kBlockLock(aList);

  if(!vList)
  {
    kError = kListErrorUnknown;

    return kFalse;
  }

  kListNodeStruct *vListNode = vList->sIter ? vList->sIter = vList->sIter->sNext : kNil;

  kBlockUnlock((kPointer)vList);

  kError = kListErrorOk;

  if(vListNode)
    return kTrue;
  else
    return kFalse;
}

kBool kListIterIsFirst(kList aList)
{
  kListStruct *vList = (kListStruct*)kBlockLock(aList);

  if(!vList)
  {
    kError = kListErrorUnknown;

    return kFalse;
  }

  kBool vBool = vList->sIter == vList->sHead; // In empty list, iterator also is first!

  kBlockUnlock((kPointer)vList);

  kError = kListErrorOk;

  return vBool;
}

kBool kListIterIsLast(kList aList)
{
  kListStruct *vList = (kListStruct*)kBlockLock(aList);

  if(!vList)
  {
    kError = kListErrorUnknown;

    return kFalse;
  }

  kBool vBool = vList->sIter ? vList->sIter->sNext == kNil : kTrue; // In empty list, iterator also is last!

  kBlockUnlock((kPointer)vList);

  kError = kListErrorOk;

  return vBool;
}

We may obtain the element at the current iterator position with the following function.

kItem kListIterGetItem(kList aList)
{
  kListStruct *vList = (kListStruct*)kBlockLock(aList);

  if(!vList)
  {
    kError = kListErrorUnknown;

    return 0;
  }

  kItem vItem = vList->sIter ? vList->sIter->sItem : 0;

  kBlockUnlock((kPointer)vList);

  kError = kListErrorOk;

  return vItem;
}

We have functions that insert an item at the current iterator position, that replace the item at the iterator, and that remove the item at the iterator.

kVoid kListIterInsert(kList aList, kItem aItem)
{
  kListStruct *vList = (kListStruct*)kBlockLock(aList);

  if(!vList)
  {
    kError = kListErrorUnknown;

    return;
  }

  if(vList->sIter)
  {
    kListNodeStruct *vListNode = (kListNodeStruct*)kPointerInit(sizeof(kListNodeStruct));

    if(vListNode)
    {
      kBlockIncRefs(aItem);

      vListNode->sItem = aItem;
      vListNode->sNext = vList->sIter->sNext;

      vList->sIter->sNext = vListNode;
      vList->sSize++;
    }
    else
    {
      kBlockUnlock((kPointer)vList);

      kError = kListErrorHeapFull;

      return;
    }

    kBlockUnlock((kPointer)vList);

    kError = kListErrorOk;
  }
  else
  {
    kBlockUnlock((kPointer)vList);

    kError = kListErrorNilIterator;
  }
}

kVoid kListIterReplace(kList aList, kItem aItem)
{
  kListStruct *vList = (kListStruct*)kBlockLock(aList);

  if(!vList)
  {
    kError = kListErrorUnknown;

    return;
  }

  if(vList->sIter)
  {
    kBlockDecRefs(vList->sIter->sItem);
    vList->sIter->sItem = aItem;
    kBlockIncRefs(vList->sIter->sItem);

    kBlockUnlock((kPointer)vList);

    kError = kListErrorOk;
  }
  else
  {
    kBlockUnlock((kPointer)vList);

    kError = kListErrorNilIterator;
  }
}

kVoid kListIterRemove(kList aList)
{
  kListStruct *vList = (kListStruct*)kBlockLock(aList);

  if(!vList)
  {
    kError = kListErrorUnknown;

    return;
  }

  kListNodeStruct *vListNodeToRemove = vList->sIter;

  if(vListNodeToRemove)
  {
    kListNodeStruct *vListIter = vList->sHead;

    if(vListIter == vListNodeToRemove)
      vList->sIter = vList->sHead = vList->sHead->sNext;
    else
    {
      while(vListIter->sNext != vListNodeToRemove)
        vListIter = vListIter->sNext;
      vListIter->sNext = vListNodeToRemove->sNext;
      vList->sIter = vListIter;
    }

    if(!vList->sHead)
      vList->sTail = kNil;
    if(!vListIter->sNext)
      vList->sTail = vListIter;

    vList->sSize--;

    kBlockDecRefs(vListNodeToRemove->sItem);
    kPointerDone((kPointer)vListNodeToRemove);

    kBlockUnlock((kPointer)vList);

    kError = kListErrorOk;
  }
  else
  {
    kBlockUnlock((kPointer)vList);

    kError = kListErrorNilIterator;
  }
}

Copyright © 2025 Rui Cuco. All rights reserved.