diff options
Diffstat (limited to '')
| -rw-r--r-- | src/list.c | 426 |
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); } |