source: branches/1.2/packages/vizservers/nanovis/Chain.cpp @ 3589

Last change on this file since 3589 was 2923, checked in by ldelgass, 8 years ago

style fixes

  • 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
30typedef int (QSortCompareProc) (const void *, const void *);
31
32/**
33 * Removes all the links from the chain, freeing the memory for each
34 * link.  Memory pointed to by the link (clientData) is not freed.  It's
35 * the caller's responsibility to deallocate it.
36 */
37void
38Chain::reset()
39{
40    ChainLink *oldPtr;
41    ChainLink *linkPtr = _head;
42
43    while (linkPtr != NULL) {
44        oldPtr = linkPtr;
45        linkPtr = linkPtr->next();
46        delete oldPtr;
47    }
48    init();
49}
50
51/**
52 * Inserts a link after another link.  If afterPtr is NULL, then the new
53 * link is prepended to the beginning of the chain.
54 */
55void
56Chain::linkAfter(ChainLink *linkPtr, ChainLink *afterPtr)
57{
58    if (_head == NULL) {
59        _tail = _head = linkPtr;
60    } else {
61        if (afterPtr == NULL) {
62            /* Prepend to the front of the chain */
63            linkPtr->_next = _head;
64            linkPtr->_prev = NULL;
65            _head->_prev = linkPtr;
66            _head = linkPtr;
67        } else {
68            linkPtr->_next = afterPtr->next();
69            linkPtr->_prev = afterPtr;
70            if (afterPtr == _tail) {
71                _tail = linkPtr;
72            } else {
73                afterPtr->next()->_prev = linkPtr;
74            }
75            afterPtr->_next = linkPtr;
76        }
77    }
78    _nLinks++;
79}
80
81/**
82 * Inserts a new link preceding a given link in a chain.  If beforePtr is
83 * NULL, then the new link is placed at the beginning of the list.
84 *
85 * \param linkPtr New entry to be inserted
86 * \param beforePtr Entry to link before
87 */
88void
89Chain::linkBefore(ChainLink *linkPtr,
90                  ChainLink *beforePtr)
91{
92    if (_head == NULL) {
93        _tail = _head = linkPtr;
94    } else {
95        if (beforePtr == NULL) {
96            // Append to the end of the chain.
97            linkPtr->_next = NULL;
98            linkPtr->_prev = _tail;
99            _tail->_next = linkPtr;
100            _tail = linkPtr;
101        } else {
102            linkPtr->_prev = beforePtr->prev();
103            linkPtr->_next = beforePtr;
104            if (beforePtr == _head) {
105                _head = linkPtr;
106            } else {
107                beforePtr->prev()->_next = linkPtr;
108            }
109            beforePtr->_prev = linkPtr;
110        }
111    }
112    _nLinks++;
113}
114
115/**
116 * Unlinks a link from the chain. The link is not deallocated,
117 * but only removed from the chain.
118 */
119void
120Chain::unlink(ChainLink *linkPtr)
121{
122    bool unlinked;              /* Indicates if the link is actually removed
123                                 * from the chain. */
124
125    unlinked = false;
126    if (_head == linkPtr) {
127        _head = linkPtr->next();
128        unlinked = true;
129    }
130    if (_tail == linkPtr) {
131        _tail = linkPtr->prev();
132        unlinked = true;
133    }
134    if (linkPtr->next() != NULL) {
135        linkPtr->next()->_prev = linkPtr->prev();
136        unlinked = true;
137    }
138    if (linkPtr->prev() != NULL) {
139        linkPtr->prev()->_next = linkPtr->next();
140        unlinked = true;
141    }
142    if (unlinked) {
143        _nLinks--;
144    }
145    linkPtr->_prev = linkPtr->_next = NULL;
146}
147
148/**
149 * Unlinks and frees the given link from the chain.  It's assumed that
150 * the link belong to the chain. No error checking is performed to verify
151 * this.
152 */
153void
154Chain::deleteLink(ChainLink *linkPtr)
155{
156    unlink(linkPtr);
157    delete linkPtr;
158}
159
160/**
161 * Creates and new link with the given data and appends it to the end of
162 * the chain.
163 *
164 * \return a pointer to the link created.
165 */
166ChainLink *
167Chain::append(void *clientData)
168{
169    ChainLink *linkPtr;
170
171    linkPtr = new ChainLink(clientData);
172    linkBefore(linkPtr, (ChainLink *)NULL);
173    return linkPtr;
174}
175
176/**
177 * Creates and new link with the given data and prepends it to beginning
178 * of the chain.
179 *
180 * \return a pointer to the link created.
181 */
182ChainLink  *
183Chain::prepend(void *clientData)
184{
185    ChainLink *linkPtr;
186
187    linkPtr = new ChainLink(clientData);
188    linkAfter(linkPtr, (ChainLink *)NULL);
189    return linkPtr;
190}
191
192/**
193 * Find the link at the given position in the chain.
194 *
195 * \param position Index of link to select from front or back of the chain.
196 *
197 * \return  the pointer to the link, if that numbered link
198 * exists. Otherwise NULL.
199 */
200ChainLink *
201Chain::getNthLink(long position)
202{
203    ChainLink *linkPtr;
204
205    for (linkPtr = _head; linkPtr != NULL; linkPtr = linkPtr->next()) {
206        if (position == 0) {
207            return linkPtr;
208        }
209        position--;
210    }
211    return NULL;
212}
213
214/**
215 * Sorts the chain according to the given comparison routine. 
216 *
217 * Side Effects:
218 *   The chain is reordered.
219 */
220void
221Chain::sort(ChainCompareProc *proc)
222{
223    ChainLink *linkPtr;
224    long i;
225
226    if (_nLinks < 2) {
227        return;
228    }
229    ChainLink **linkArr = new ChainLink *[_nLinks + 1];
230    if (linkArr == NULL) {
231        return;                 /* Out of memory. */
232    }
233    i = 0;
234    for (linkPtr = _head; linkPtr != NULL; linkPtr = linkPtr->next()) { 
235        linkArr[i++] = linkPtr;
236    }
237    qsort((char *)linkArr, _nLinks, sizeof(ChainLink *), 
238          (QSortCompareProc *)proc);
239
240    /* Rethread the chain. */
241    linkPtr = linkArr[0];
242    _head = linkPtr;
243    linkPtr->_prev = NULL;
244    for (i = 1; i < _nLinks; i++) {
245        linkPtr->_next = linkArr[i];
246        linkPtr->next()->_prev = linkPtr;
247        linkPtr = linkPtr->next();
248    }
249    _tail = linkPtr;
250    linkPtr->_next = NULL;
251    delete [] linkArr;
252}
Note: See TracBrowser for help on using the repository browser.