lib/dlist.c File Reference

#include "common.h"
#include "dlist.h"

Include dependency graph for dlist.c:

Go to the source code of this file.

Data Structures

struct  dlSorter

Functions

void dlListInit (struct dlList *dl)
dlList * newDlList ()
void dlListReset (struct dlList *dl)
void freeDlList (struct dlList **pList)
void freeDlListAndVals (struct dlList **pList)
void dlInsertBetween (struct dlNode *before, struct dlNode *after, struct dlNode *newNode)
void dlAddBefore (struct dlNode *anchor, struct dlNode *newNode)
void dlAddAfter (struct dlNode *anchor, struct dlNode *newNode)
void dlAddHead (struct dlList *list, struct dlNode *newNode)
void dlAddTail (struct dlList *list, struct dlNode *newNode)
dlNode * dlAddValBefore (struct dlNode *anchor, void *val)
dlNode * dlAddValAfter (struct dlNode *anchor, void *val)
dlNode * dlAddValHead (struct dlList *list, void *val)
dlNode * dlAddValTail (struct dlList *list, void *val)
void dlRemove (struct dlNode *node)
void dlRemoveHead (struct dlList *list)
void dlRemoveTail (struct dlList *list)
dlNode * dlPopHead (struct dlList *list)
dlNode * dlPopTail (struct dlList *list)
void dlDelete (struct dlNode **nodePtr)
int dlCount (struct dlList *list)
static int dlNodeCmp (const void *elem1, const void *elem2)
void dlSort (struct dlList *list, int(*compare)(const void *elem1, const void *elem2))
boolean dlEmpty (struct dlList *list)
dlNode * dlGetBeforeHead (struct dlList *list)
dlNode * dlGetAfterTail (struct dlList *list)
void * dlListToSlList (struct dlList *dList)
void dlCat (struct dlList *a, struct dlList *b)
dlNode * dlValInList (struct dlList *list, void *val)

Variables

static char const rcsid [] = "$Id: dlist.c,v 1.11 2005/07/04 18:44:09 markd Exp $"
static int(*) compareFunc (const void *elem1, const void *elem2)

Function Documentation

void dlAddAfter ( struct dlNode *  anchor,
struct dlNode *  newNode 
)

Definition at line 82 of file dlist.c.

References dlInsertBetween(), and dlNode::next.

Referenced by dlAddValAfter().

00084 {
00085 dlInsertBetween(anchor, anchor->next, newNode);
00086 }

Here is the call graph for this function:

Here is the caller graph for this function:

void dlAddBefore ( struct dlNode *  anchor,
struct dlNode *  newNode 
)

Definition at line 76 of file dlist.c.

References dlInsertBetween(), and dlNode::prev.

Referenced by dlAddValBefore().

00078 {
00079 dlInsertBetween(anchor->prev, anchor, newNode);
00080 }

Here is the call graph for this function:

Here is the caller graph for this function:

void dlAddHead ( struct dlList *  list,
struct dlNode *  newNode 
)

Definition at line 88 of file dlist.c.

References dlInsertBetween(), dlList::head, and dlNode::prev.

Referenced by carefulAlloc(), and dlAddValHead().

00090 {
00091 struct dlNode *head = list->head;
00092 dlInsertBetween(head->prev, head, newNode);
00093 }

Here is the call graph for this function:

Here is the caller graph for this function:

void dlAddTail ( struct dlList *  list,
struct dlNode *  newNode 
)

Definition at line 95 of file dlist.c.

References dlInsertBetween(), dlNode::next, and dlList::tail.

Referenced by boxFindClumps(), dlAddValTail(), dlCat(), dlSort(), kdTreeMake(), memTrackerAlloc(), memTrackerRealloc(), mergeContigs(), mergeIntoAdjacentClusters(), and splitList().

00097 {
00098 struct dlNode *tail = list->tail;
00099 dlInsertBetween(tail, tail->next, newNode);
00100 }

Here is the call graph for this function:

Here is the caller graph for this function:

struct dlNode* dlAddValAfter ( struct dlNode *  anchor,
void *  val 
) [read]

Definition at line 111 of file dlist.c.

References AllocA, dlAddAfter(), and dlNode::val.

00113 {
00114 struct dlNode *node = AllocA(struct dlNode);
00115 node->val = val;
00116 dlAddAfter(anchor, node);
00117 return node;
00118 }

Here is the call graph for this function:

struct dlNode* dlAddValBefore ( struct dlNode *  anchor,
void *  val 
) [read]

Definition at line 102 of file dlist.c.

References AllocA, dlAddBefore(), and dlNode::val.

00104 {
00105 struct dlNode *node = AllocA(struct dlNode);
00106 node->val = val;
00107 dlAddBefore(anchor, node);
00108 return node;
00109 }

Here is the call graph for this function:

struct dlNode* dlAddValHead ( struct dlList *  list,
void *  val 
) [read]

Definition at line 120 of file dlist.c.

References AllocA, dlAddHead(), and dlNode::val.

00122 {
00123 struct dlNode *node = AllocA(struct dlNode);
00124 node->val = val;
00125 dlAddHead(list, node);
00126 return node;
00127 }

Here is the call graph for this function:

struct dlNode* dlAddValTail ( struct dlList *  list,
void *  val 
) [read]

Definition at line 129 of file dlist.c.

References AllocA, dlAddTail(), and dlNode::val.

Referenced by dgConnectWithVal(), dgConstrainedPriorityOrder(), dgFindPath(), mergeContigs(), synQueuePut(), and xStitch().

00131 {
00132 struct dlNode *node = AllocA(struct dlNode);
00133 node->val = val;
00134 dlAddTail(list, node);
00135 return node;
00136 }

Here is the call graph for this function:

Here is the caller graph for this function:

void dlCat ( struct dlList *  a,
struct dlList *  b 
)

Definition at line 285 of file dlist.c.

References dlAddTail(), and dlPopHead().

00287 {
00288 struct dlNode *node;
00289 while ((node = dlPopHead(b)) != NULL)
00290     dlAddTail(a, node);
00291 }

Here is the call graph for this function:

int dlCount ( struct dlList *  list  ) 

Definition at line 192 of file dlist.c.

References dlList::head, and slCount().

Referenced by bfGraphFromRangeGraph(), carefulCountBlocksAllocated(), dlSort(), mergeContigs(), mergeWithinCluster(), and synQueueSize().

00194 {
00195 return slCount(list->head) - 1;
00196 }

Here is the call graph for this function:

Here is the caller graph for this function:

void dlDelete ( struct dlNode **  nodePtr  ) 

Definition at line 181 of file dlist.c.

References dlRemove(), and freeMem().

00183 {
00184 struct dlNode *node = *nodePtr;
00185 if (node != NULL)
00186     {
00187     dlRemove(node);
00188     freeMem(node);
00189     }
00190 }

Here is the call graph for this function:

boolean dlEmpty ( struct dlList *  list  ) 

Definition at line 247 of file dlist.c.

References dlIsEmpty.

Referenced by dgConstrainedPriorityOrder(), dlGetAfterTail(), dlGetBeforeHead(), and synQueueGet().

00249 {
00250 return dlIsEmpty(list);
00251 }

Here is the caller graph for this function:

struct dlNode* dlGetAfterTail ( struct dlList *  list  )  [read]

Definition at line 262 of file dlist.c.

References dlEmpty(), dlNode::next, and dlList::tail.

00264 {
00265 if (dlEmpty(list))
00266     return list->tail;
00267 else
00268     return list->tail->next;
00269 }

Here is the call graph for this function:

struct dlNode* dlGetBeforeHead ( struct dlList *  list  )  [read]

Definition at line 253 of file dlist.c.

References dlEmpty(), dlList::head, and dlNode::prev.

00255 {
00256 if (dlEmpty(list))
00257     return list->head;
00258 else
00259     return list->head->prev;
00260 }

Here is the call graph for this function:

void dlInsertBetween ( struct dlNode *  before,
struct dlNode *  after,
struct dlNode *  newNode 
)

Definition at line 68 of file dlist.c.

References dlNode::next, and dlNode::prev.

Referenced by dlAddAfter(), dlAddBefore(), dlAddHead(), and dlAddTail().

00069 {
00070 before->next = newNode; 
00071 newNode->prev = before; 
00072 newNode->next = after;  
00073 after->prev = newNode; 
00074 }

Here is the caller graph for this function:

void dlListInit ( struct dlList *  dl  ) 

Definition at line 10 of file dlist.c.

References dlList::head, dlList::nullMiddle, and dlList::tail.

Referenced by boxFindClumps(), dlSort(), kdTreeMake(), and splitList().

00012 {
00013 dl->head = (struct dlNode *)(&dl->nullMiddle);
00014 dl->nullMiddle = NULL;
00015 dl->tail = (struct dlNode *)(&dl->head);
00016 }

Here is the caller graph for this function:

void dlListReset ( struct dlList *  dl  ) 

Definition at line 28 of file dlist.c.

References freeMem(), dlList::head, dlNode::next, dlList::nullMiddle, and dlList::tail.

Referenced by freeDlList().

00030 {
00031 struct dlNode *node, *next;
00032 for (node = dl->head; node->next != NULL; node = next)
00033     {
00034     next = node->next;
00035     freeMem(node);
00036     }
00037 dl->head = (struct dlNode *)(&dl->nullMiddle);
00038 dl->nullMiddle = NULL;
00039 dl->tail = (struct dlNode *)(&dl->head);
00040 }

Here is the call graph for this function:

Here is the caller graph for this function:

void* dlListToSlList ( struct dlList *  dList  ) 

Definition at line 271 of file dlist.c.

References dlNode::prev, slAddHead, dlList::tail, and dlNode::val.

00273 {
00274 struct slList *list = NULL, *el;
00275 struct dlNode *node;
00276 
00277 for (node = dList->tail; node->prev != NULL; node = node->prev)
00278     {
00279     el = node->val;
00280     slAddHead(&list, el);
00281     }
00282 return list;
00283 }

static int dlNodeCmp ( const void *  elem1,
const void *  elem2 
) [static]

Definition at line 208 of file dlist.c.

References compareFunc, dlSorter::node, and dlNode::val.

Referenced by dlSort().

00210 {
00211 struct dlSorter *a = (struct dlSorter *)elem1;
00212 struct dlSorter *b = (struct dlSorter *)elem2;
00213 return compareFunc(&a->node->val, &b->node->val);
00214 }

Here is the caller graph for this function:

struct dlNode* dlPopHead ( struct dlList *  list  )  [read]

Definition at line 161 of file dlist.c.

References dlRemove(), dlList::head, and dlNode::next.

Referenced by dgFindPath(), dlCat(), mergeContigs(), synQueueGet(), and synQueueGrab().

00163 {
00164 struct dlNode *node = list->head;
00165 if (node->next == NULL)
00166     return NULL;
00167 dlRemove(node);
00168 return node;
00169 }

Here is the call graph for this function:

Here is the caller graph for this function:

struct dlNode* dlPopTail ( struct dlList *  list  )  [read]

Definition at line 171 of file dlist.c.

References dlRemove(), dlNode::prev, and dlList::tail.

00173 {
00174 struct dlNode *node = list->tail;
00175 if (node->prev == NULL)
00176     return NULL;
00177 dlRemove(node);
00178 return node;
00179 }

Here is the call graph for this function:

void dlRemove ( struct dlNode *  node  ) 

Definition at line 138 of file dlist.c.

References dlNode::next, and dlNode::prev.

Referenced by carefulFree(), clusterRemoveEncompassed(), contigRemoveEncompassed(), dgConstrainedPriorityOrder(), dgDisconnect(), dlDelete(), dlPopHead(), dlPopTail(), dlRemoveHead(), dlRemoveTail(), memTrackerFree(), memTrackerRealloc(), mergeClusters(), mergeContigs(), mergeWithinCluster(), and splitList().

00140 {
00141 struct dlNode *before = node->prev;
00142 struct dlNode *after = node->next;
00143 before->next = after;
00144 after->prev = before;
00145 node->prev = NULL;
00146 node->next = NULL;
00147 }

Here is the caller graph for this function:

void dlRemoveHead ( struct dlList *  list  ) 

Definition at line 149 of file dlist.c.

References dlRemove(), and dlList::head.

00151 {
00152 dlRemove(list->head);
00153 }

Here is the call graph for this function:

void dlRemoveTail ( struct dlList *  list  ) 

Definition at line 155 of file dlist.c.

References dlRemove(), and dlList::tail.

00157 {
00158 dlRemove(list->tail);
00159 }

Here is the call graph for this function:

void dlSort ( struct dlList *  list,
int(*)(const void *elem1, const void *elem2)  compare 
)

Definition at line 216 of file dlist.c.

References compareFunc, dlAddTail(), dlCount(), dlListInit(), dlNodeCmp(), freeMem(), dlList::head, needLargeMem(), and dlNode::next.

Referenced by dgConstrainedPriorityOrder(), kdTreeMake(), and mergeContigs().

00222 {
00223 int len = dlCount(list);
00224 
00225 if (len > 1)
00226     {
00227     /* Move val's onto an array, sort, and then put back into list. */
00228     struct dlSorter *sorter = needLargeMem(len * sizeof(sorter[0])), *s;
00229     struct dlNode *node;
00230     int i;
00231 
00232     for (i=0, node = list->head; i<len; ++i, node = node->next)
00233         {
00234         s = &sorter[i];
00235         s->node = node;
00236         }
00237     compareFunc = compare;
00238     qsort(sorter, len, sizeof(sorter[0]), dlNodeCmp);
00239     dlListInit(list);
00240     for (i=0; i<len; ++i)
00241         dlAddTail(list, sorter[i].node);
00242     freeMem(sorter);
00243     }
00244 }

Here is the call graph for this function:

Here is the caller graph for this function:

struct dlNode* dlValInList ( struct dlList *  list,
void *  val 
) [read]

Definition at line 293 of file dlist.c.

References dlEnd, dlList::head, dlNode::next, and dlNode::val.

00295 {
00296 struct dlNode *node;
00297 for (node = list->head; !dlEnd(node); node = node->next)
00298     if (node->val == val)
00299         return node;
00300 return NULL;
00301 }

void freeDlList ( struct dlList **  pList  ) 

Definition at line 42 of file dlist.c.

References dlListReset(), and freez().

Referenced by dgConstrainedPriorityOrder(), dgFindPath(), freeContigList(), freeDlListAndVals(), and mergeContigs().

00044 {
00045 struct dlList *list = *pList;
00046 if (list != NULL)
00047     {
00048     dlListReset(list);
00049     freez(pList);
00050     }
00051 }

Here is the call graph for this function:

Here is the caller graph for this function:

void freeDlListAndVals ( struct dlList **  pList  ) 

Definition at line 53 of file dlist.c.

References freeDlList(), freeMem(), dlList::head, dlNode::next, and dlNode::val.

Referenced by dgFree(), and mergeContigs().

00056 {
00057 struct dlList *list = *pList;
00058 if (list != NULL)
00059     {
00060     struct dlNode *node;
00061     for (node = list->head; node->next != NULL; node = node->next)
00062         freeMem(node->val);
00063     freeDlList(pList);
00064     }
00065 }

Here is the call graph for this function:

Here is the caller graph for this function:

struct dlList* newDlList (  )  [read]

Definition at line 18 of file dlist.c.

References AllocVar, dlList::head, dlList::nullMiddle, and dlList::tail.

Referenced by carefulMemInit(), dgConstrainedPriorityOrder(), dgFindPath(), dgNew(), finishContigs(), mergeContigs(), and xStitch().

00020 {
00021 struct dlList *dl;
00022 AllocVar(dl);
00023 dl->head = (struct dlNode *)(&dl->nullMiddle);
00024 dl->tail = (struct dlNode *)(&dl->head);
00025 return dl;
00026 }

Here is the caller graph for this function:

Variable Documentation

int(*) compareFunc(const void *elem1, const void *elem2) [static]

Definition at line 205 of file dlist.c.

Referenced by dlNodeCmp(), dlSort(), and quickHeapBalanceWithChildren().

char const rcsid[] = "$Id: dlist.c,v 1.11 2005/07/04 18:44:09 markd Exp $" [static]

Definition at line 8 of file dlist.c.

Generated on Tue Dec 25 19:44:07 2007 for blat by  doxygen 1.5.2