source: nanovis/branches/1.1/Chain.cpp @ 5393

Last change on this file since 5393 was 4889, checked in by ldelgass, 9 years ago

Merge r3611:3618 from trunk

  • Property svn:eol-style set to native
File size: 6.1 KB
Line 
1/* -*- mode: c++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2/* The module implements a generic linked list package.
3 *
4 * Copyright 1991-2004 George A Howlett.
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining
7 * a copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sublicense, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 */
25#include <stdlib.h>
26#include <stdio.h>
27
28#include "Chain.h"
29
30using namespace nv;
31
32typedef int (QSortCompareProc) (const void *, const void *);
33
34/**
35 * Removes all the links from the chain, freeing the memory for each
36 * link.  Memory pointed to by the link (clientData) is not freed.  It's
37 * the caller's responsibility to deallocate it.
38 */
39void
40Chain::reset()
41{
42    ChainLink *oldPtr;
43    ChainLink *linkPtr = _head;
44
45    while (linkPtr != NULL) {
46        oldPtr = linkPtr;
47        linkPtr = linkPtr->next();
48        delete oldPtr;
49    }
50    init();
51}
52
53/**
54 * Inserts a link after another link.  If afterPtr is NULL, then the new
55 * link is prepended to the beginning of the chain.
56 */
57void
58Chain::linkAfter(ChainLink *linkPtr, ChainLink *afterPtr)
59{
60    if (_head == NULL) {
61        _tail = _head = linkPtr;
62    } else {
63        if (afterPtr == NULL) {
64            /* Prepend to the front of the chain */
65            linkPtr->_next = _head;
66            linkPtr->_prev = NULL;
67            _head->_prev = linkPtr;
68            _head = linkPtr;
69        } else {
70            linkPtr->_next = afterPtr->next();
71            linkPtr->_prev = afterPtr;
72            if (afterPtr == _tail) {
73                _tail = linkPtr;
74            } else {
75                afterPtr->next()->_prev = linkPtr;
76            }
77            afterPtr->_next = linkPtr;
78        }
79    }
80    _nLinks++;
81}
82
83/**
84 * Inserts a new link preceding a given link in a chain.  If beforePtr is
85 * NULL, then the new link is placed at the beginning of the list.
86 *
87 * \param linkPtr New entry to be inserted
88 * \param beforePtr Entry to link before
89 */
90void
91Chain::linkBefore(ChainLink *linkPtr,
92                  ChainLink *beforePtr)
93{
94    if (_head == NULL) {
95        _tail = _head = linkPtr;
96    } else {
97        if (beforePtr == NULL) {
98            // Append to the end of the chain.
99            linkPtr->_next = NULL;
100            linkPtr->_prev = _tail;
101            _tail->_next = linkPtr;
102            _tail = linkPtr;
103        } else {
104            linkPtr->_prev = beforePtr->prev();
105            linkPtr->_next = beforePtr;
106            if (beforePtr == _head) {
107                _head = linkPtr;
108            } else {
109                beforePtr->prev()->_next = linkPtr;
110            }
111            beforePtr->_prev = linkPtr;
112        }
113    }
114    _nLinks++;
115}
116
117/**
118 * Unlinks a link from the chain. The link is not deallocated,
119 * but only removed from the chain.
120 */
121void
122Chain::unlink(ChainLink *linkPtr)
123{
124    bool unlinked;              /* Indicates if the link is actually removed
125                                 * from the chain. */
126
127    unlinked = false;
128    if (_head == linkPtr) {
129        _head = linkPtr->next();
130        unlinked = true;
131    }
132    if (_tail == linkPtr) {
133        _tail = linkPtr->prev();
134        unlinked = true;
135    }
136    if (linkPtr->next() != NULL) {
137        linkPtr->next()->_prev = linkPtr->prev();
138        unlinked = true;
139    }
140    if (linkPtr->prev() != NULL) {
141        linkPtr->prev()->_next = linkPtr->next();
142        unlinked = true;
143    }
144    if (unlinked) {
145        _nLinks--;
146    }
147    linkPtr->_prev = linkPtr->_next = NULL;
148}
149
150/**
151 * Unlinks and frees the given link from the chain.  It's assumed that
152 * the link belong to the chain. No error checking is performed to verify
153 * this.
154 */
155void
156Chain::deleteLink(ChainLink *linkPtr)
157{
158    unlink(linkPtr);
159    delete linkPtr;
160}
161
162/**
163 * Creates and new link with the given data and appends it to the end of
164 * the chain.
165 *
166 * \return a pointer to the link created.
167 */
168ChainLink *
169Chain::append(void *clientData)
170{
171    ChainLink *linkPtr;
172
173    linkPtr = new ChainLink(clientData);
174    linkBefore(linkPtr, (ChainLink *)NULL);
175    return linkPtr;
176}
177
178/**
179 * Creates and new link with the given data and prepends it to beginning
180 * of the chain.
181 *
182 * \return a pointer to the link created.
183 */
184ChainLink  *
185Chain::prepend(void *clientData)
186{
187    ChainLink *linkPtr;
188
189    linkPtr = new ChainLink(clientData);
190    linkAfter(linkPtr, (ChainLink *)NULL);
191    return linkPtr;
192}
193
194/**
195 * Find the link at the given position in the chain.
196 *
197 * \param position Index of link to select from front or back of the chain.
198 *
199 * \return  the pointer to the link, if that numbered link
200 * exists. Otherwise NULL.
201 */
202ChainLink *
203Chain::getNthLink(long position)
204{
205    ChainLink *linkPtr;
206
207    for (linkPtr = _head; linkPtr != NULL; linkPtr = linkPtr->next()) {
208        if (position == 0) {
209            return linkPtr;
210        }
211        position--;
212    }
213    return NULL;
214}
215
216/**
217 * Sorts the chain according to the given comparison routine. 
218 *
219 * Side Effects:
220 *   The chain is reordered.
221 */
222void
223Chain::sort(ChainCompareProc *proc)
224{
225    ChainLink *linkPtr;
226    long i;
227
228    if (_nLinks < 2) {
229        return;
230    }
231    ChainLink **linkArr = new ChainLink *[_nLinks + 1];
232    if (linkArr == NULL) {
233        return;                 /* Out of memory. */
234    }
235    i = 0;
236    for (linkPtr = _head; linkPtr != NULL; linkPtr = linkPtr->next()) {
237        linkArr[i++] = linkPtr;
238    }
239    qsort((char *)linkArr, _nLinks, sizeof(ChainLink *),
240          (QSortCompareProc *)proc);
241
242    /* Rethread the chain. */
243    linkPtr = linkArr[0];
244    _head = linkPtr;
245    linkPtr->_prev = NULL;
246    for (i = 1; i < _nLinks; i++) {
247        linkPtr->_next = linkArr[i];
248        linkPtr->next()->_prev = linkPtr;
249        linkPtr = linkPtr->next();
250    }
251    _tail = linkPtr;
252    linkPtr->_next = NULL;
253    delete [] linkArr;
254}
Note: See TracBrowser for help on using the repository browser.