← Back to branch summary

~ubuntu-branches/ubuntu/precise/torque/precise-updates

« back to all changes in this revision

Viewing changes to src/lib/Libutils/u_tree.c

  • Committer: Bazaar Package Importer
  • Author(s): Dominique Belhachemi
  • Date: 2010-05-17 20:56:46 UTC
  • mto: This revision was merged to the branch mainline in revision 8.
  • Revision ID: james.westby@ubuntu.com-20100517205646-yjsoqs5r1s9xpnu9
Tags: upstream-2.4.8+dfsg
Import upstream version 2.4.8+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/lib/Libutils/u_tree.c
 
1
#include "utils.h"
 
2
 
 
3
extern int LOGLEVEL;
 
4
 
 
5
/**
 
6
 * inserts the key into the tree if it isn't there already
 
7
 * @param key - the key we are inserting (input)
 
8
 * @param nodep - what the new node's nodep should be (optional input)
 
9
 * @param rootp - the address of the tree's root
 
10
 * NOTE:  tinsert cannot report failure 
 
11
*/
 
12
 
 
13
void tinsert(
 
14
 
 
15
  const u_long   key, /* I */
 
16
  struct pbsnode  *nodep, /* I (optional) */  
 
17
  tree         **rootp) /* I */
 
18
 
 
19
  {
 
20
  register tree *q;
 
21
 
 
22
  if (rootp == NULL)
 
23
    {
 
24
    /* invalid tree address - failure */
 
25
 
 
26
    return;
 
27
    }
 
28
 
 
29
  while (*rootp != NULL)
 
30
    {
 
31
    /* Knuth's T1: */
 
32
 
 
33
    if (key == (*rootp)->key) /* T2: */
 
34
      {
 
35
      /* key already exists */
 
36
 
 
37
      return;   /* we found it! */
 
38
      }
 
39
 
 
40
    rootp = (key < (*rootp)->key) ?
 
41
 
 
42
            &(*rootp)->left : /* T3: follow left branch */
 
43
            &(*rootp)->right; /* T4: follow right branch */
 
44
    }
 
45
 
 
46
  /* create new tree node */
 
47
 
 
48
  q = (tree *)malloc(sizeof(tree)); /* T5: key not found */
 
49
 
 
50
  if (q == NULL)
 
51
    {
 
52
    /* cannot allocate memory - failure */
 
53
 
 
54
    return;
 
55
    }
 
56
 
 
57
  /* make new tree */
 
58
  /* link new node to old */
 
59
  *rootp = q;
 
60
  /* initialize new tree node */
 
61
  q->key = key;   
 
62
  q->left = NULL;
 
63
  q->right = NULL;
 
64
  /* if nodep is null then this doesn't do anything */
 
65
  q->nodep = nodep;
 
66
 
 
67
  /* success */
 
68
 
 
69
  return;
 
70
  }  /* END tinsert() */
 
71
 
 
72
 
 
73
 
 
74
 
 
75
/** 
 
76
 * delete the node with the given key 
 
77
 * @param key - the key of the node to be deleted
 
78
 * @param rootp - the address of the root of the tree
 
79
*/
 
80
 
 
81
void *tdelete(
 
82
 
 
83
  const u_long   key, /* I */
 
84
  tree         **rootp) /* I */
 
85
 
 
86
  {
 
87
  tree  *p;
 
88
  register tree *q;
 
89
  register tree *r;
 
90
 
 
91
  if (LOGLEVEL >= 6)
 
92
    {
 
93
    sprintf(log_buffer, "deleting key %lu",
 
94
            key);
 
95
 
 
96
    log_record(
 
97
      PBSEVENT_SCHED,
 
98
      PBS_EVENTCLASS_REQUEST,
 
99
      "tdelete",
 
100
      log_buffer);
 
101
    }
 
102
 
 
103
  if ((rootp == NULL) || ((p = *rootp) == NULL))
 
104
    {
 
105
    return(NULL);
 
106
    }
 
107
 
 
108
  while (key != (*rootp)->key)
 
109
    {
 
110
    p = *rootp;
 
111
 
 
112
    rootp = (key < (*rootp)->key) ?
 
113
            &(*rootp)->left :  /* left branch */
 
114
            &(*rootp)->right;  /* right branch */
 
115
 
 
116
    if (*rootp == NULL)
 
117
      {
 
118
      return(NULL);  /* key not found */
 
119
      }
 
120
    }
 
121
 
 
122
  r = (*rootp)->right;    /* D1: */
 
123
 
 
124
  if ((q = (*rootp)->left) == NULL)  /* Left */
 
125
    {
 
126
    q = r;
 
127
    }
 
128
  else if (r != NULL)
 
129
    {
 
130
    /* Right is null? */
 
131
 
 
132
    if (r->left == NULL)
 
133
      {
 
134
      /* D2: Find successor */
 
135
      r->left = q;
 
136
 
 
137
      q = r;
 
138
      }
 
139
    else
 
140
      {
 
141
      /* D3: Find (struct tree_t *)0 link */
 
142
 
 
143
      for (q = r->left;q->left != NULL;q = r->left)
 
144
        {
 
145
        r = q;
 
146
        }
 
147
 
 
148
      r->left = q->right;
 
149
 
 
150
      q->left = (*rootp)->left;
 
151
      q->right = (*rootp)->right;
 
152
      }
 
153
    }
 
154
 
 
155
  free((struct tree_t *)*rootp);     /* D4: Free node */
 
156
 
 
157
  *rootp = q;                         /* link parent to new node */
 
158
 
 
159
  return(p);
 
160
  }  /* END tdelete() */
 
161
 
 
162
 
 
163
/*
 
164
 * Tree search generalized from Knuth (6.2.2) Algorithm T just like
 
165
 * the AT&T man page says.
 
166
 *
 
167
 * The tree_t structure is for internal use only, lint doesn't grok it.
 
168
 *
 
169
 * Written by reading the System V Interface Definition, not the code.
 
170
 *
 
171
 * Totally public domain.
 
172
 */
 
173
/*LINTLIBRARY*/
 
174
 
 
175
/** 
 
176
 * finds a pointer to the specified node in the tree
 
177
 * @param key - the key of the node to find
 
178
 * @param rootp - the address of the tree's root
 
179
 * @return a pointer to the node with the specified key or NULL if not found
 
180
 *
 
181
 * NOTE: on the mom nodep is never used, but it expects a non-NULL value or
 
182
 * else it thinks the key wasn't found
 
183
 * WARNING: this means that pointer can't be used on the mom and that you 
 
184
 * should always use 
 
185
*/
 
186
 
 
187
struct pbsnode *tfind(
 
188
 
 
189
        const u_long   key, /* I */
 
190
        tree         **rootp) /* I / O */
 
191
 
 
192
  {
 
193
  if (rootp == NULL)
 
194
    {
 
195
    return(NULL);
 
196
    }
 
197
 
 
198
  while (*rootp != NULL)
 
199
    {
 
200
    /* Knuth's T1: */
 
201
 
 
202
    if (key == (*rootp)->key) /* T2: */
 
203
      {
 
204
      /* found */
 
205
 
 
206
      /* this if logic prevents mom errors, see above note */
 
207
      if ((*rootp)->nodep != NULL)
 
208
        return((*rootp)->nodep);
 
209
      else
 
210
        return((struct pbsnode *)1);
 
211
      }
 
212
 
 
213
    rootp = (key < (*rootp)->key) ?
 
214
 
 
215
            &(*rootp)->left : /* T3: follow left branch */
 
216
            &(*rootp)->right; /* T4: follow right branch */
 
217
    }
 
218
 
 
219
  return(NULL);
 
220
  }  /* END tfind() */
 
221
 
 
222
 
 
223
 
 
224
 
 
225
/** 
 
226
 * lists all of the keys in the tree
 
227
 * NOTE:  recursive.  Buf not initialized
 
228
 * @param rootp - the root node of the tree
 
229
 * @param Buf - the output buffer
 
230
 * @param BufSize - the size of the output buffer 
 
231
 * @return 1 if rootp or Buf are NULL, -1 if the buffer is too small, -1 otherwise
 
232
*/
 
233
 
 
234
int tlist(
 
235
 
 
236
  tree *rootp,   /* I */
 
237
  char *Buf,     /* O (modified) */
 
238
  int   BufSize) /* I */
 
239
 
 
240
  {
 
241
  char tmpLine[32];
 
242
 
 
243
  int  BSize;
 
244
 
 
245
  /* check for bad inputs */
 
246
  if ((rootp == NULL) || (Buf == NULL))
 
247
    {
 
248
    /* empty tree - failure */
 
249
 
 
250
    return(1);
 
251
    }
 
252
 
 
253
  if (BufSize <= 16)
 
254
    {
 
255
    /* inadequate space to append data */
 
256
 
 
257
    return(-1);
 
258
    }
 
259
 
 
260
  BSize = BufSize;
 
261
 
 
262
  if (rootp->left != NULL)
 
263
    {
 
264
    tlist(rootp->left, Buf, BSize);
 
265
 
 
266
    BSize -= strlen(Buf);
 
267
    }
 
268
 
 
269
  if (rootp->right != NULL)
 
270
    {
 
271
    tlist(rootp->right, Buf, BSize);
 
272
 
 
273
    BSize -= strlen(Buf);
 
274
    }
 
275
 
 
276
  if (BSize <= 16)
 
277
    {
 
278
    /* inadequate space to append data */
 
279
 
 
280
    return(-1);
 
281
    }
 
282
 
 
283
  sprintf(tmpLine, "%ld.%ld.%ld.%ld",
 
284
 
 
285
          (rootp->key & 0xff000000) >> 24,
 
286
          (rootp->key & 0x00ff0000) >> 16,
 
287
          (rootp->key & 0x0000ff00) >> 8,
 
288
          (rootp->key & 0x000000ff));
 
289
 
 
290
  if ((Buf[0] != '\0') && (BSize > 1))
 
291
    {
 
292
    strcat(Buf, ",");
 
293
 
 
294
    BSize--;
 
295
    }
 
296
 
 
297
  if (BSize > (int)strlen(tmpLine))
 
298
    {
 
299
    strcat(Buf, tmpLine);
 
300
    }
 
301
 
 
302
  return(-1);
 
303
  }  /* END tlist() */
 
304
 
 
305
 
 
306
 
 
307
 
 
308
/**
 
309
 * frees the tree from memory
 
310
 * @param rootp - the address of the root of the tree
 
311
*/
 
312
void tfree(
 
313
 
 
314
  tree **rootp) /* I */
 
315
 
 
316
  {
 
317
  if (rootp == NULL || *rootp == NULL)
 
318
    {
 
319
    return;
 
320
    }
 
321
 
 
322
  tfree(&(*rootp)->left);
 
323
 
 
324
  tfree(&(*rootp)->right);
 
325
 
 
326
  free(*rootp);
 
327
 
 
328
  *rootp = NULL;
 
329
 
 
330
  return;
 
331
  }
 
332
 
 
333