aboutsummaryrefslogtreecommitdiffstats
path: root/src/list.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/list.c426
1 files changed, 234 insertions, 192 deletions
diff --git a/src/list.c b/src/list.c
index e681054fa..1bec3deab 100644
--- a/src/list.c
+++ b/src/list.c
@@ -16,7 +16,6 @@
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
-
#include "list.h"
#include <stdlib.h>
@@ -25,31 +24,36 @@
#include <time.h>
#include <stdio.h>
-static void makeListNodesArray(List * list) {
- ListNode * node = list->firstNode;
+static void makeListNodesArray(List * list)
+{
+ ListNode *node = list->firstNode;
long i;
- if(!list->numberOfNodes) return;
+ if (!list->numberOfNodes)
+ return;
list->nodesArray = realloc(list->nodesArray,
- sizeof(ListNode *)*list->numberOfNodes);
+ sizeof(ListNode *) * list->numberOfNodes);
- for(i=0;i<list->numberOfNodes;i++) {
+ for (i = 0; i < list->numberOfNodes; i++) {
list->nodesArray[i] = node;
node = node->nextNode;
}
}
-static void freeListNodesArray(List * list) {
- if(!list->nodesArray) return;
+static void freeListNodesArray(List * list)
+{
+ if (!list->nodesArray)
+ return;
free(list->nodesArray);
list->nodesArray = NULL;
}
-List * makeList(ListFreeDataFunc * freeDataFunc, int strdupKeys) {
- List * list = malloc(sizeof(List));
+List *makeList(ListFreeDataFunc * freeDataFunc, int strdupKeys)
+{
+ List *list = malloc(sizeof(List));
- assert(list!=NULL);
+ assert(list != NULL);
list->sorted = 0;
list->firstNode = NULL;
@@ -62,61 +66,63 @@ List * makeList(ListFreeDataFunc * freeDataFunc, int strdupKeys) {
return list;
}
-ListNode * insertInListBeforeNode(List * list, ListNode * beforeNode, int pos, char * key, void * data)
+ListNode *insertInListBeforeNode(List * list, ListNode * beforeNode, int pos,
+ char *key, void *data)
{
- ListNode * node;
+ ListNode *node;
- assert(list!=NULL);
- assert(key!=NULL);
- /*assert(data!=NULL);*/
+ assert(list != NULL);
+ assert(key != NULL);
+ /*assert(data!=NULL); */
node = malloc(sizeof(ListNode));
- assert(node!=NULL);
+ assert(node != NULL);
node->nextNode = beforeNode;
- if(beforeNode==list->firstNode) {
- if(list->firstNode==NULL) {
- assert(list->lastNode==NULL);
+ if (beforeNode == list->firstNode) {
+ if (list->firstNode == NULL) {
+ assert(list->lastNode == NULL);
list->lastNode = node;
- }
- else {
- assert(list->lastNode!=NULL);
- assert(list->lastNode->nextNode==NULL);
+ } else {
+ assert(list->lastNode != NULL);
+ assert(list->lastNode->nextNode == NULL);
list->firstNode->prevNode = node;
}
node->prevNode = NULL;
list->firstNode = node;
- }
- else {
- if(beforeNode) {
+ } else {
+ if (beforeNode) {
node->prevNode = beforeNode->prevNode;
beforeNode->prevNode = node;
- }
- else {
+ } else {
node->prevNode = list->lastNode;
list->lastNode = node;
}
node->prevNode->nextNode = node;
}
- if(list->strdupKeys) node->key = strdup(key);
- else node->key = key;
+ if (list->strdupKeys)
+ node->key = strdup(key);
+ else
+ node->key = key;
node->data = data;
list->numberOfNodes++;
-
- if(list->sorted) {
+
+ if (list->sorted) {
list->nodesArray = realloc(list->nodesArray,
- list->numberOfNodes*sizeof(ListNode *));
- if(node == list->lastNode) {
- list->nodesArray[list->numberOfNodes-1] = node;
- }
- else if(pos < 0) makeListNodesArray(list);
+ list->numberOfNodes *
+ sizeof(ListNode *));
+ if (node == list->lastNode) {
+ list->nodesArray[list->numberOfNodes - 1] = node;
+ } else if (pos < 0)
+ makeListNodesArray(list);
else {
- memmove(list->nodesArray+pos+1, list->nodesArray+pos,
- sizeof(ListNode *)*
- (list->numberOfNodes-pos-1));
+ memmove(list->nodesArray + pos + 1,
+ list->nodesArray + pos,
+ sizeof(ListNode *) * (list->numberOfNodes -
+ pos - 1));
list->nodesArray[pos] = node;
}
}
@@ -124,30 +130,33 @@ ListNode * insertInListBeforeNode(List * list, ListNode * beforeNode, int po
return node;
}
-ListNode * insertInList(List * list, char * key, void * data) {
- ListNode * node;
+ListNode *insertInList(List * list, char *key, void *data)
+{
+ ListNode *node;
- assert(list!=NULL);
- assert(key!=NULL);
- /*assert(data!=NULL);*/
+ assert(list != NULL);
+ assert(key != NULL);
+ /*assert(data!=NULL); */
node = malloc(sizeof(ListNode));
- assert(node!=NULL);
+ assert(node != NULL);
- if(list->nodesArray) freeListNodesArray(list);
+ if (list->nodesArray)
+ freeListNodesArray(list);
- if(list->firstNode==NULL) {
- assert(list->lastNode==NULL);
+ if (list->firstNode == NULL) {
+ assert(list->lastNode == NULL);
list->firstNode = node;
- }
- else {
- assert(list->lastNode!=NULL);
- assert(list->lastNode->nextNode==NULL);
+ } else {
+ assert(list->lastNode != NULL);
+ assert(list->lastNode->nextNode == NULL);
list->lastNode->nextNode = node;
}
- if(list->strdupKeys) node->key = strdup(key);
- else node->key = key;
+ if (list->strdupKeys)
+ node->key = strdup(key);
+ else
+ node->key = key;
node->data = data;
node->nextNode = NULL;
@@ -156,28 +165,29 @@ ListNode * insertInList(List * list, char * key, void * data) {
list->lastNode = node;
list->numberOfNodes++;
-
+
return node;
}
-int insertInListWithoutKey(List * list, void * data) {
- ListNode * node;
+int insertInListWithoutKey(List * list, void *data)
+{
+ ListNode *node;
- assert(list!=NULL);
- assert(data!=NULL);
+ assert(list != NULL);
+ assert(data != NULL);
node = malloc(sizeof(ListNode));
- assert(node!=NULL);
-
- if(list->nodesArray) freeListNodesArray(list);
+ assert(node != NULL);
+
+ if (list->nodesArray)
+ freeListNodesArray(list);
- if(list->firstNode==NULL) {
- assert(list->lastNode==NULL);
+ if (list->firstNode == NULL) {
+ assert(list->lastNode == NULL);
list->firstNode = node;
- }
- else {
- assert(list->lastNode!=NULL);
- assert(list->lastNode->nextNode==NULL);
+ } else {
+ assert(list->lastNode != NULL);
+ assert(list->lastNode->nextNode == NULL);
list->lastNode->nextNode = node;
}
@@ -189,153 +199,163 @@ int insertInListWithoutKey(List * list, void * data) {
list->lastNode = node;
list->numberOfNodes++;
-
+
return 1;
}
/* if _key_ is not found, *_node_ is assigned to the node before which
the info would be found */
-int findNodeInList(List * list, char * key, ListNode ** node, int * pos) {
+int findNodeInList(List * list, char *key, ListNode ** node, int *pos)
+{
long high;
long low;
long cur;
- ListNode * tmpNode;
+ ListNode *tmpNode;
int cmp;
- assert(list!=NULL);
+ assert(list != NULL);
- if(list->sorted && list->nodesArray) {
- high = list->numberOfNodes-1;
+ if (list->sorted && list->nodesArray) {
+ high = list->numberOfNodes - 1;
low = 0;
cur = high;
- while(high>low) {
- cur = (high+low)/2;
+ while (high > low) {
+ cur = (high + low) / 2;
tmpNode = list->nodesArray[cur];
- cmp = strcmp(tmpNode->key,key);
- if(cmp==0) {
+ cmp = strcmp(tmpNode->key, key);
+ if (cmp == 0) {
*node = tmpNode;
*pos = cur;
return 1;
- }
- else if(cmp>0) high = cur;
+ } else if (cmp > 0)
+ high = cur;
else {
- if(low==cur) break;
+ if (low == cur)
+ break;
low = cur;
}
}
cur = high;
- if(cur>=0) {
+ if (cur >= 0) {
tmpNode = list->nodesArray[cur];
*node = tmpNode;
*pos = high;
- cmp = tmpNode ? strcmp(tmpNode->key,key) : -1;
- if( 0 == cmp ) return 1;
- else if( cmp > 0) return 0;
+ cmp = tmpNode ? strcmp(tmpNode->key, key) : -1;
+ if (0 == cmp)
+ return 1;
+ else if (cmp > 0)
+ return 0;
else {
*pos = -1;
*node = NULL;
return 0;
}
- }
- else {
+ } else {
*pos = 0;
*node = list->firstNode;
return 0;
}
- }
- else {
+ } else {
tmpNode = list->firstNode;
-
- while(tmpNode!=NULL && strcmp(tmpNode->key,key)!=0) {
+
+ while (tmpNode != NULL && strcmp(tmpNode->key, key) != 0) {
tmpNode = tmpNode->nextNode;
}
-
- *node = tmpNode;
- if(tmpNode) return 1;
+
+ *node = tmpNode;
+ if (tmpNode)
+ return 1;
}
return 0;
}
-int findInList(List * list, char * key, void ** data) {
- ListNode * node;
+int findInList(List * list, char *key, void **data)
+{
+ ListNode *node;
int pos;
-
- if(findNodeInList(list, key, &node, &pos)) {
- if(data) *data = node->data;
+
+ if (findNodeInList(list, key, &node, &pos)) {
+ if (data)
+ *data = node->data;
return 1;
}
return 0;
}
-int deleteFromList(List * list,char * key) {
- ListNode * tmpNode;
+int deleteFromList(List * list, char *key)
+{
+ ListNode *tmpNode;
- assert(list!=NULL);
+ assert(list != NULL);
tmpNode = list->firstNode;
- while(tmpNode!=NULL && strcmp(tmpNode->key,key)!=0) {
+ while (tmpNode != NULL && strcmp(tmpNode->key, key) != 0) {
tmpNode = tmpNode->nextNode;
}
- if(tmpNode!=NULL)
- deleteNodeFromList(list,tmpNode);
+ if (tmpNode != NULL)
+ deleteNodeFromList(list, tmpNode);
else
return 0;
return 1;
}
-void deleteNodeFromList(List * list,ListNode * node) {
- assert(list!=NULL);
- assert(node!=NULL);
-
- if(node->prevNode==NULL) {
+void deleteNodeFromList(List * list, ListNode * node)
+{
+ assert(list != NULL);
+ assert(node != NULL);
+
+ if (node->prevNode == NULL) {
list->firstNode = node->nextNode;
- }
- else {
+ } else {
node->prevNode->nextNode = node->nextNode;
}
- if(node->nextNode==NULL) {
+ if (node->nextNode == NULL) {
list->lastNode = node->prevNode;
- }
- else {
+ } else {
node->nextNode->prevNode = node->prevNode;
}
- if(list->freeDataFunc) {
+ if (list->freeDataFunc) {
list->freeDataFunc(node->data);
}
- if(list->strdupKeys) free(node->key);
+ if (list->strdupKeys)
+ free(node->key);
free(node);
list->numberOfNodes--;
- if(list->nodesArray) {
+ if (list->nodesArray) {
freeListNodesArray(list);
- if(list->sorted) makeListNodesArray(list);
+ if (list->sorted)
+ makeListNodesArray(list);
}
}
-
-void freeList(void * list) {
- ListNode * tmpNode;
- ListNode * tmpNode2;
- assert(list!=NULL);
+void freeList(void *list)
+{
+ ListNode *tmpNode;
+ ListNode *tmpNode2;
+
+ assert(list != NULL);
- tmpNode = ((List *)list)->firstNode;
+ tmpNode = ((List *) list)->firstNode;
- if(((List *)list)->nodesArray) free(((List *)list)->nodesArray);
+ if (((List *) list)->nodesArray)
+ free(((List *) list)->nodesArray);
- while(tmpNode!=NULL) {
+ while (tmpNode != NULL) {
tmpNode2 = tmpNode->nextNode;
- if(((List *)list)->strdupKeys) free(tmpNode->key);
- if(((List *)list)->freeDataFunc) {
- ((List *)list)->freeDataFunc(tmpNode->data);
+ if (((List *) list)->strdupKeys)
+ free(tmpNode->key);
+ if (((List *) list)->freeDataFunc) {
+ ((List *) list)->freeDataFunc(tmpNode->data);
}
free(tmpNode);
tmpNode = tmpNode2;
@@ -344,16 +364,17 @@ void freeList(void * list) {
free(list);
}
-static void swapNodes(ListNode * nodeA, ListNode * nodeB) {
- char * key;
- void * data;
-
- assert(nodeA!=NULL);
- assert(nodeB!=NULL);
+static void swapNodes(ListNode * nodeA, ListNode * nodeB)
+{
+ char *key;
+ void *data;
+
+ assert(nodeA != NULL);
+ assert(nodeB != NULL);
key = nodeB->key;
data = nodeB->data;
-
+
nodeB->key = nodeA->key;
nodeB->data = nodeA->data;
@@ -361,98 +382,116 @@ static void swapNodes(ListNode * nodeA, ListNode * nodeB) {
nodeA->data = data;
}
-static void bubbleSort(ListNode ** nodesArray, long start, long end) {
+static void bubbleSort(ListNode ** nodesArray, long start, long end)
+{
long i;
long j;
- ListNode * node;
+ ListNode *node;
- if(start>=end) return;
+ if (start >= end)
+ return;
- for(j=start;j<end;j++) {
- for(i=end-1;i>=start;i--) {
+ for (j = start; j < end; j++) {
+ for (i = end - 1; i >= start; i--) {
node = nodesArray[i];
- if(strcmp(node->key,node->nextNode->key)>0) {
- swapNodes(node,node->nextNode);
+ if (strcmp(node->key, node->nextNode->key) > 0) {
+ swapNodes(node, node->nextNode);
}
}
}
}
-static void quickSort(ListNode ** nodesArray, long start, long end) {
- if(start>=end) return;
- else if(end-start<5) bubbleSort(nodesArray,start,end);
+static void quickSort(ListNode ** nodesArray, long start, long end)
+{
+ if (start >= end)
+ return;
+ else if (end - start < 5)
+ bubbleSort(nodesArray, start, end);
else {
long i;
- ListNode * node;
+ ListNode *node;
long pivot;
- ListNode * pivotNode;
- char * pivotKey;
+ ListNode *pivotNode;
+ char *pivotKey;
- List * startList = makeList(free, 0);
- List * endList = makeList(free, 0);
- long * startPtr = malloc(sizeof(long));
- long * endPtr = malloc(sizeof(long));
+ List *startList = makeList(free, 0);
+ List *endList = makeList(free, 0);
+ long *startPtr = malloc(sizeof(long));
+ long *endPtr = malloc(sizeof(long));
*startPtr = start;
*endPtr = end;
- insertInListWithoutKey(startList,(void *)startPtr);
- insertInListWithoutKey(endList,(void *)endPtr);
+ insertInListWithoutKey(startList, (void *)startPtr);
+ insertInListWithoutKey(endList, (void *)endPtr);
- while(startList->numberOfNodes) {
+ while (startList->numberOfNodes) {
start = *((long *)startList->lastNode->data);
end = *((long *)endList->lastNode->data);
- if(end-start<5) {
- bubbleSort(nodesArray,start,end);
- deleteNodeFromList(startList,startList->lastNode);
- deleteNodeFromList(endList,endList->lastNode);
- }
- else {
- pivot = (start+end)/2;
+ if (end - start < 5) {
+ bubbleSort(nodesArray, start, end);
+ deleteNodeFromList(startList,
+ startList->lastNode);
+ deleteNodeFromList(endList, endList->lastNode);
+ } else {
+ pivot = (start + end) / 2;
pivotNode = nodesArray[pivot];
pivotKey = pivotNode->key;
- for(i=pivot-1;i>=start;i--) {
+ for (i = pivot - 1; i >= start; i--) {
node = nodesArray[i];
- if(strcmp(node->key,pivotKey)>0) {
+ if (strcmp(node->key, pivotKey) > 0) {
pivot--;
- if(pivot>i) {
- swapNodes(node,nodesArray[pivot]);
+ if (pivot > i) {
+ swapNodes(node,
+ nodesArray
+ [pivot]);
}
- swapNodes(pivotNode,nodesArray[pivot]);
+ swapNodes(pivotNode,
+ nodesArray[pivot]);
pivotNode = nodesArray[pivot];
}
}
- for(i=pivot+1;i<=end;i++) {
+ for (i = pivot + 1; i <= end; i++) {
node = nodesArray[i];
- if(strcmp(pivotKey,node->key)>0) {
+ if (strcmp(pivotKey, node->key) > 0) {
pivot++;
- if(pivot<i) {
- swapNodes(node,nodesArray[pivot]);
+ if (pivot < i) {
+ swapNodes(node,
+ nodesArray
+ [pivot]);
}
- swapNodes(pivotNode,nodesArray[pivot]);
+ swapNodes(pivotNode,
+ nodesArray[pivot]);
pivotNode = nodesArray[pivot];
}
}
- deleteNodeFromList(startList,startList->lastNode);
- deleteNodeFromList(endList,endList->lastNode);
+ deleteNodeFromList(startList,
+ startList->lastNode);
+ deleteNodeFromList(endList, endList->lastNode);
- if(pivot-1-start>0) {
+ if (pivot - 1 - start > 0) {
startPtr = malloc(sizeof(long));
endPtr = malloc(sizeof(long));
*startPtr = start;
- *endPtr = pivot-1;
- insertInListWithoutKey(startList,(void *)startPtr);
- insertInListWithoutKey(endList,(void *)endPtr);
+ *endPtr = pivot - 1;
+ insertInListWithoutKey(startList,
+ (void *)
+ startPtr);
+ insertInListWithoutKey(endList,
+ (void *)endPtr);
}
- if(end-pivot-1>0) {
+ if (end - pivot - 1 > 0) {
startPtr = malloc(sizeof(long));
endPtr = malloc(sizeof(long));
- *startPtr = pivot+1;
+ *startPtr = pivot + 1;
*endPtr = end;
- insertInListWithoutKey(startList,(void *)startPtr);
- insertInListWithoutKey(endList,(void *)endPtr);
+ insertInListWithoutKey(startList,
+ (void *)
+ startPtr);
+ insertInListWithoutKey(endList,
+ (void *)endPtr);
}
}
}
@@ -462,15 +501,18 @@ static void quickSort(ListNode ** nodesArray, long start, long end) {
}
}
-void sortList(List * list) {
- assert(list!=NULL);
+void sortList(List * list)
+{
+ assert(list != NULL);
list->sorted = 1;
- if(list->numberOfNodes<2) return;
-
- if(list->nodesArray) freeListNodesArray(list);
+ if (list->numberOfNodes < 2)
+ return;
+
+ if (list->nodesArray)
+ freeListNodesArray(list);
makeListNodesArray(list);
- quickSort(list->nodesArray,0,list->numberOfNodes-1);
+ quickSort(list->nodesArray, 0, list->numberOfNodes - 1);
}