← Back to branch summary

~ubuntu-branches/ubuntu/utopic/gridengine/utopic

« back to all changes in this revision

Viewing changes to source/libs/cull/cull_hash.c

  • Committer: Bazaar Package Importer
  • Author(s): Mark Hymers
  • Date: 2008-06-25 22:36:13 UTC
  • Revision ID: james.westby@ubuntu.com-20080625223613-tvd9xlhuoct9kyhm
Tags: upstream-6.2~beta2
Import upstream version 6.2~beta2

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/libs/cull/cull_hash.c
 
1
/*___INFO__MARK_BEGIN__*/
 
2
/*************************************************************************
 
3
 * 
 
4
 *  The Contents of this file are made available subject to the terms of
 
5
 *  the Sun Industry Standards Source License Version 1.2
 
6
 * 
 
7
 *  Sun Microsystems Inc., March, 2001
 
8
 * 
 
9
 * 
 
10
 *  Sun Industry Standards Source License Version 1.2
 
11
 *  =================================================
 
12
 *  The contents of this file are subject to the Sun Industry Standards
 
13
 *  Source License Version 1.2 (the "License"); You may not use this file
 
14
 *  except in compliance with the License. You may obtain a copy of the
 
15
 *  License at http://gridengine.sunsource.net/Gridengine_SISSL_license.html
 
16
 * 
 
17
 *  Software provided under this License is provided on an "AS IS" basis,
 
18
 *  WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING,
 
19
 *  WITHOUT LIMITATION, WARRANTIES THAT THE SOFTWARE IS FREE OF DEFECTS,
 
20
 *  MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE, OR NON-INFRINGING.
 
21
 *  See the License for the specific provisions governing your rights and
 
22
 *  obligations concerning the Software.
 
23
 * 
 
24
 *   The Initial Developer of the Original Code is: Sun Microsystems, Inc.
 
25
 * 
 
26
 *   Copyright: 2001 by Sun Microsystems, Inc.
 
27
 * 
 
28
 *   All Rights Reserved.
 
29
 * 
 
30
 ************************************************************************/
 
31
/*___INFO__MARK_END__*/
 
32
 
 
33
#include <stdio.h>
 
34
#include <stdlib.h>
 
35
 
 
36
/* do not compile in monitoring code */
 
37
#ifndef NO_SGE_COMPILE_DEBUG
 
38
#define NO_SGE_COMPILE_DEBUG
 
39
#endif
 
40
 
 
41
#include "sgermon.h"
 
42
#include "sge_log.h"
 
43
#include "msg_cull.h"
 
44
 
 
45
#include "cull_list.h"
 
46
#include "cull_hash.h"
 
47
#include "cull_listP.h"
 
48
#include "cull_multitypeP.h"
 
49
#include "cull_multitype.h"
 
50
#include "sge_string.h"
 
51
#include "sge_hostname.h"
 
52
 
 
53
/****** cull/hash/--CULL_Hashtable **********************************************
 
54
*  NAME
 
55
*     htable -- Hashtable extensions for cull lists 
 
56
*
 
57
*  SYNOPSIS
 
58
*     cull_htable cull_hash_create(const lDescr *descr, int size);
 
59
*
 
60
*     void cull_hash_new(lList *lp, int name, bool unique);
 
61
*
 
62
*     void cull_hash_insert(const lListElem *ep, const int pos, );
 
63
*
 
64
*     void cull_hash_remove(const lListElem *ep, const int pos);
 
65
*
 
66
*     void cull_hash_elem(const lListElem *ep);
 
67
*
 
68
*     lListElem *cull_hash_first(const lList *lp, const int pos, 
 
69
*                         const void *key, const void **iterator);
 
70
*
 
71
*     lListElem *cull_hash_next(const lList *lp, const int pos, 
 
72
*                         const void *key, const void **iterator);
 
73
*
 
74
*     void cull_hash_free_descr(lDescr *descr);
 
75
*
 
76
*  FUNCTION
 
77
*     This module provides an abstraction layer between cull and 
 
78
*     the hash table implementation in libuti. It provides the 
 
79
*     necessary functions to use hash tables from libuti for cull lists.
 
80
*
 
81
*     The functions defined in this module implement hash tables with 
 
82
*     non unique keys, provide wrapper functions for hash insert, remove 
 
83
*     and search that are aware of the non unique hash implementation, 
 
84
*     functions that deal with the necessary extensions to the cull list
 
85
*     descriptor objects etc.
 
86
*
 
87
*  SEE ALSO
 
88
*     uti/hash/--Hashtable
 
89
*     cull/hash/cull_hash_create()
 
90
*     cull/hash/cull_hash_new()
 
91
*     cull/hash/cull_hash_insert()
 
92
*     cull/hash/cull_hash_remove()
 
93
*     cull/hash/cull_hash_elem()
 
94
*******************************************************************************/
 
95
 
 
96
/****** cull/hash/-CULL_Hashtable_Defines ****************************************************
 
97
*  NAME
 
98
*     Defines -- Constants for the cull hash implementation
 
99
*
 
100
*  SYNOPSIS
 
101
*     #define MIN_CULL_HASH_SIZE 4
 
102
*
 
103
*  FUNCTION
 
104
*     Provides constants to be used in the hash table implementation 
 
105
*     for cull lists.
 
106
*
 
107
*     MIN_CULL_HASH_SIZE - minimum size of a hash table. When a new 
 
108
*                          hash table is created, it will have the size 
 
109
*                          2^MIN_CULL_HASH_SIZE
 
110
*******************************************************************************/
 
111
#define MIN_CULL_HASH_SIZE 4
 
112
 
 
113
/****** cull/hash/-CULL_Hashtable_Typedefs ***************************************************
 
114
*  NAME
 
115
*     Typedefs -- Typedefs for cull hash implementation 
 
116
*
 
117
*  SYNOPSIS
 
118
*     typedef struct _non_unique_hash non_unique_hash;
 
119
*     
 
120
*     struct _non_unique_hash {
 
121
*        non_unique_hash *next;
 
122
*        const void *data;
 
123
*     };
 
124
*
 
125
*  FUNCTION
 
126
*     Internal data structure to handle hash tables with non unique 
 
127
*     keys. The hash table (from libuti) in this case will not store 
 
128
*     a pointer to the cull object itself, but a pointer to a list of 
 
129
*     cull objects. This list is implemented using the non_unique_hash 
 
130
*     structures.
 
131
*
 
132
*  SEE ALSO
 
133
*     uti/hash/--Hashtable
 
134
*******************************************************************************/
 
135
typedef struct _non_unique_hash non_unique_hash;
 
136
 
 
137
typedef struct non_unique_header {
 
138
   non_unique_hash *first;
 
139
   non_unique_hash *last;
 
140
} non_unique_header;
 
141
 
 
142
struct _non_unique_hash {
 
143
   non_unique_hash *prev;
 
144
   non_unique_hash *next;
 
145
   const void *data;
 
146
};
 
147
 
 
148
struct _cull_htable {
 
149
   htable ht;       /* hashtable for keys */
 
150
   htable nuht;     /* hashtable for lookup of non unique object references */
 
151
};
 
152
 
 
153
/****** cull/hash/cull_hash_create() *******************************************
 
154
*  NAME
 
155
*     cull_hash_create() -- create a new hash table
 
156
*
 
157
*  SYNOPSIS
 
158
*     cull_htable cull_hash_create(const lDescr *descr, int size) 
 
159
*
 
160
*  FUNCTION
 
161
*     Creates a new hash table for a certain descriptor and returns the 
 
162
*     hash description (lHash) for it.
 
163
*     The initial size of the hashtable can be specified.
 
164
*     This allows for optimization of the hashtable, as resize operations
 
165
*     can be minimized when the final hashtable size is known at creation time,
 
166
*     e.g. when copying complete lists.
 
167
*
 
168
*  INPUTS
 
169
*     const lDescr *descr - descriptor for the data field in a 
 
170
*                           cull object.
 
171
*     int size            - initial size of hashtable will be 2^size
 
172
*
 
173
*  RESULT
 
174
*     cull_htable - initialized hash description
 
175
*******************************************************************************/
 
176
cull_htable cull_hash_create(const lDescr *descr, int size)
 
177
{
 
178
   htable ht   = NULL;   /* hash table for keys */
 
179
   htable nuht = NULL;   /* hash table for non unique access */
 
180
   cull_htable ret = NULL;
 
181
 
 
182
   /* if no size is given, use default value */
 
183
   if (size == 0) {
 
184
      size = MIN_CULL_HASH_SIZE;
 
185
   }
 
186
 
 
187
   /* create hash table for object keys */
 
188
   switch(mt_get_type(descr->mt)) {
 
189
      case lStringT:
 
190
         ht = sge_htable_create(size, dup_func_string, 
 
191
                                hash_func_string, hash_compare_string);
 
192
         break;
 
193
      case lHostT:
 
194
         ht = sge_htable_create(size, dup_func_string, 
 
195
                                hash_func_string, hash_compare_string);
 
196
         break;
 
197
      case lUlongT:
 
198
         ht = sge_htable_create(size, dup_func_u_long32, 
 
199
                                hash_func_u_long32, hash_compare_u_long32);
 
200
         break;
 
201
      default:
 
202
         unknownType("cull_create_hash");
 
203
         ht = NULL;
 
204
         break;
 
205
   }
 
206
 
 
207
   /* (optionally) create hash table for non unique hash access */
 
208
   if (ht != NULL) {
 
209
      if (!mt_is_unique(descr->mt)) {
 
210
         nuht = sge_htable_create(size, dup_func_pointer, 
 
211
                                  hash_func_pointer, hash_compare_pointer);
 
212
         if (nuht == NULL) {
 
213
            sge_htable_destroy(ht);
 
214
            ht = NULL;
 
215
         }
 
216
      }
 
217
   }
 
218
 
 
219
   /* hashtables OK? Then create cull_htable */
 
220
   if (ht != NULL) {
 
221
      ret = (cull_htable)malloc(sizeof(struct _cull_htable));
 
222
 
 
223
      /* malloc error? destroy hashtables */
 
224
      if (ret == NULL) {
 
225
         sge_htable_destroy(ht);
 
226
         if (nuht != NULL) {
 
227
            sge_htable_destroy(nuht);
 
228
         }
 
229
      } else {
 
230
         ret->ht = ht;
 
231
         ret->nuht = nuht;
 
232
      }
 
233
   }
 
234
 
 
235
   return ret;
 
236
}
 
237
 
 
238
/****** cull/hash/cull_hash_create_hashtables() ********************************
 
239
*  NAME
 
240
*     cull_hash_create_hashtables() -- create all hashtables on a list
 
241
*
 
242
*  SYNOPSIS
 
243
*     void cull_hash_create_hashtables(lList *lp) 
 
244
*
 
245
*  FUNCTION
 
246
*     Creates all hashtables for an empty list.
 
247
*
 
248
*  INPUTS
 
249
*     lList *lp - initialized list structure
 
250
*
 
251
*  NOTES
 
252
*     If the list already contains elements, these elements are not 
 
253
*     inserted into the hash lists.
 
254
*******************************************************************************/
 
255
void cull_hash_create_hashtables(lList *lp) 
 
256
{
 
257
   if(lp != NULL) {
 
258
      int i, size;
 
259
      const lListElem *ep;
 
260
      lDescr * descr = lp->descr;
 
261
 
 
262
      /* compute final size of hashtables when all elements are inserted */
 
263
      size = hash_compute_size(lGetNumberOfElem(lp));
 
264
 
 
265
      /* create hashtables, pass final size */
 
266
      for(i = 0; descr[i].mt != lEndT; i++) {
 
267
         if(mt_do_hashing(descr[i].mt) && descr[i].ht == NULL) {
 
268
            descr[i].ht = cull_hash_create(&descr[i], size);
 
269
         }
 
270
      }
 
271
   
 
272
      /* create hash entries for all objects */
 
273
      for_each (ep, lp) {
 
274
         cull_hash_elem(ep);
 
275
      }
 
276
   }
 
277
}
 
278
 
 
279
/****** cull/hash/cull_hash_insert() *******************************************
 
280
*  NAME
 
281
*     cull_hash_insert() -- insert a new element in a hash table
 
282
*
 
283
*  SYNOPSIS
 
284
*     void cull_hash_insert(const lListElem *ep, const int pos) 
 
285
*
 
286
*  FUNCTION
 
287
*     Inserts ep into the hash list for data field at position pos.
 
288
*     A hash key will be computed. The element will be inserted
 
289
*     in the corresponding hash table considering unique/non unique
 
290
*     hash storage.
 
291
*
 
292
*  INPUTS
 
293
*     const lListElem *ep - the cull object to be stored in a hash list
 
294
*     const int pos       - describes the data field of the objects that
 
295
*                           is to be hashed
 
296
*******************************************************************************/
 
297
void cull_hash_insert(const lListElem *ep, void *key, cull_htable ht, bool unique)
 
298
{
 
299
   if(ht == NULL || ep == NULL || key == NULL) {
 
300
      return;
 
301
   }
 
302
 
 
303
   if (unique) {
 
304
      sge_htable_store(ht->ht, key, ep);
 
305
   } else {
 
306
      union {
 
307
         non_unique_header *l;
 
308
         void *p;
 
309
      } head; 
 
310
 
 
311
      union {
 
312
         non_unique_hash *l;
 
313
         void *p;
 
314
      } nuh;
 
315
 
 
316
      head.l = NULL;
 
317
      nuh.l = NULL;
 
318
 
 
319
      /* do we already have a list of elements with this key? */
 
320
      if(sge_htable_lookup(ht->ht, key, (const void **) &head.p) == True) {
 
321
         /* We only have something to do if ep isn't already stored */
 
322
         if (sge_htable_lookup(ht->nuht, &ep, (const void **)&nuh.p) == False) {
 
323
            nuh.p = (non_unique_hash *)malloc(sizeof(non_unique_hash));
 
324
            nuh.l->data = ep;
 
325
            nuh.l->prev = head.l->last;
 
326
            nuh.l->next = NULL;
 
327
            nuh.l->prev->next = nuh.p;
 
328
            head.l->last = nuh.p;
 
329
            sge_htable_store(ht->nuht, &ep, nuh.p);
 
330
         }
 
331
      } else { /* no list of non unique elements for this key, create new */
 
332
         head.p = (non_unique_header *)malloc(sizeof(non_unique_header));
 
333
         nuh.p = (non_unique_hash *)malloc(sizeof(non_unique_hash));
 
334
         head.l->first = nuh.p;
 
335
         head.l->last = nuh.p;
 
336
         nuh.l->prev = NULL;
 
337
         nuh.l->next = NULL;
 
338
         nuh.l->data = ep;
 
339
         sge_htable_store(ht->ht, key, head.p);
 
340
         sge_htable_store(ht->nuht, &ep, nuh.p);
 
341
      }
 
342
   }
 
343
}
 
344
 
 
345
/****** cull/hash/cull_hash_remove() *******************************************
 
346
*  NAME
 
347
*     cull_hash_remove() -- remove a cull object from a hash list
 
348
*
 
349
*  SYNOPSIS
 
350
*     void cull_hash_remove(const lListElem *ep, const int pos) 
 
351
*
 
352
*  FUNCTION
 
353
*     Removes ep from a hash table for data field specified by pos.
 
354
*
 
355
*  INPUTS
 
356
*     const lListElem *ep - the cull object to be removed
 
357
*     const int pos       - position of the data field 
 
358
*******************************************************************************/
 
359
void cull_hash_remove(const lListElem *ep, const int pos)
 
360
{
 
361
   char host_key[CL_MAXHOSTLEN+1];
 
362
   cull_htable ht;
 
363
   void *key;
 
364
 
 
365
   if(ep == NULL || pos < 0) {
 
366
      return;
 
367
   }
 
368
 
 
369
   ht = ep->descr[pos].ht;
 
370
   
 
371
 
 
372
   if(ht == NULL) {
 
373
      return;
 
374
   }
 
375
 
 
376
   key = cull_hash_key(ep, pos, host_key);
 
377
   if(key != NULL) {
 
378
      if(mt_is_unique(ep->descr[pos].mt)) {
 
379
        sge_htable_delete(ht->ht, key);
 
380
      } else {
 
381
         union {
 
382
            non_unique_header *l;
 
383
            void *p;
 
384
         } head;
 
385
         union {
 
386
            non_unique_hash *l;
 
387
            void *p;
 
388
         } nuh;
 
389
 
 
390
         head.l = NULL;
 
391
         nuh.l = NULL;
 
392
 
 
393
         /* search element in key hashtable */
 
394
         if(sge_htable_lookup(ht->ht, key, (const void **)&head.p) == True) {
 
395
            /* search element in non unique access hashtable */
 
396
            if (sge_htable_lookup(ht->nuht, &ep, (const void **)&nuh.p) == True) {
 
397
               if (head.l->first == nuh.p) {
 
398
                  head.l->first = nuh.l->next;
 
399
                  if (head.l->last == nuh.p) {
 
400
                     head.l->last = NULL;
 
401
                  } else {
 
402
                     head.l->first->prev = NULL;
 
403
                  }
 
404
               } else if (head.l->last == nuh.p) {
 
405
                  head.l->last = nuh.l->prev;
 
406
                  head.l->last->next = NULL;
 
407
               } else {
 
408
                  nuh.l->prev->next = nuh.l->next;
 
409
                  nuh.l->next->prev = nuh.l->prev;
 
410
               }
 
411
               
 
412
               sge_htable_delete(ht->nuht, &ep);
 
413
               free(nuh.p); nuh.p = NULL; /* JG: TODO: use FREE */
 
414
            } else {
 
415
             /* JG: TODO: error output */
 
416
            }
 
417
 
 
418
            if (head.l->first == NULL && head.l->last == NULL) {
 
419
               free(head.p); head.p = NULL;
 
420
               sge_htable_delete(ht->ht, key);
 
421
            }
 
422
         }   
 
423
      }
 
424
   }   
 
425
}
 
426
 
 
427
/****** cull/hash/cull_hash_elem() *********************************************
 
428
*  NAME
 
429
*     cull_hash_elem() -- insert cull object into associated hash tables
 
430
*
 
431
*  SYNOPSIS
 
432
*     void cull_hash_elem(const lListElem *ep) 
 
433
*
 
434
*  FUNCTION
 
435
*     Insert the cull element ep into all hash tables that are 
 
436
*     defined for the cull list ep is member of.
 
437
*
 
438
*  INPUTS
 
439
*     const lListElem *ep - the cull object to be hashed
 
440
*******************************************************************************/
 
441
void cull_hash_elem(const lListElem *ep) {
 
442
   int i;
 
443
   lDescr *descr;
 
444
   char host_key[CL_MAXHOSTLEN];
 
445
  
 
446
   if(ep == NULL) {
 
447
      return;
 
448
   }
 
449
 
 
450
   descr = ep->descr;
 
451
  
 
452
   for(i = 0; descr[i].mt != lEndT; i++) {
 
453
      if(descr[i].ht != NULL) {
 
454
         cull_hash_insert(ep, cull_hash_key(ep, i, host_key), descr[i].ht, 
 
455
                          mt_is_unique(descr[i].mt));
 
456
      }
 
457
   }
 
458
}
 
459
 
 
460
/****** cull/hash/cull_hash_first() *******************************************
 
461
*  NAME
 
462
*     cull_hash_first() -- find first object for a certain key
 
463
*
 
464
*  SYNOPSIS
 
465
*     lListElem* cull_hash_first(const lList *lp, const int pos, 
 
466
*                                const void  *key, 
 
467
*                                const void **iterator) 
 
468
*
 
469
*  FUNCTION
 
470
*     Searches for key in the hash table for data field described by 
 
471
*     pos in the cull list lp.
 
472
*     If an element is found, it is returned.
 
473
*     If the hash table uses non unique hash keys, iterator returns the 
 
474
*     necessary data for consecutive calls of cull_hash_next() returning
 
475
*     objects with the same hash key.
 
476
*
 
477
*  INPUTS
 
478
*     const lList *lp       - the cull list to search
 
479
*     const int pos         - position of the data field for key
 
480
*     const void *key       - the key to use for the search
 
481
*     const void **iterator - iterator for calls of cull_hash_next
 
482
*
 
483
*  RESULT
 
484
*     lListElem* - first object found matching key, 
 
485
*                  if no object found: NULL
 
486
*
 
487
*  SEE ALSO
 
488
*     cull/hash/cull_hash_next()
 
489
******************************************************************************/
 
490
lListElem *cull_hash_first(cull_htable ht, const void *key, bool unique, 
 
491
                           const void **iterator)
 
492
{
 
493
   union {
 
494
      lListElem *l;
 
495
      void *p;
 
496
   } ep;
 
497
   ep.l = NULL;
 
498
 
 
499
   if (iterator == NULL) {
 
500
      return NULL;
 
501
   }
 
502
 
 
503
   if(ht == NULL || key == NULL) {
 
504
      *iterator = NULL;
 
505
      return NULL;
 
506
   }
 
507
 
 
508
   if (unique) {
 
509
      *iterator = NULL;
 
510
      if (sge_htable_lookup(ht->ht, key, (const void **)&ep.p) == True) {
 
511
         return ep.p;
 
512
      } else {
 
513
         return NULL;
 
514
      }
 
515
   } else {
 
516
      union {
 
517
         non_unique_header *l;
 
518
         void *p;
 
519
      } head;
 
520
      head.l = NULL;
 
521
 
 
522
      if (sge_htable_lookup(ht->ht, key, (const void **)&head.p) == True) {
 
523
         ep.p = (lListElem *)head.l->first->data;
 
524
         *iterator = head.l->first;
 
525
         return ep.p;
 
526
      } else {
 
527
         *iterator = NULL;
 
528
         return NULL;
 
529
      }
 
530
   }
 
531
}
 
532
 
 
533
/****** cull/hash/cull_hash_next() *********************************************
 
534
*  NAME
 
535
*     cull_hash_next() -- find next object matching a key
 
536
*
 
537
*  SYNOPSIS
 
538
*     lListElem* cull_hash_next(const lList *lp, const int pos, 
 
539
*                               const void *key, const void **iterator) 
 
540
*
 
541
*  FUNCTION
 
542
*     Returns the next object matching the same key as a previous call
 
543
*     to cull_hash_first or cull_hash_next.
 
544
*
 
545
*  INPUTS
 
546
*     const lList *lp       - the cull list to search
 
547
*     const int pos         - position of the data field for key
 
548
*     const void *key       - the key to use for the search
 
549
*     const void **iterator - iterator to use for the search.
 
550
*
 
551
*  RESULT
 
552
*     lListElem* - object if found, else NULL
 
553
*
 
554
*  NOTES
 
555
*     The order in which objects with the same key are returned is not
 
556
*     defined.
 
557
*
 
558
*  SEE ALSO
 
559
*     cull/hash/cull_hash_first()
 
560
*******************************************************************************/
 
561
lListElem *cull_hash_next(cull_htable ht, const void **iterator)
 
562
{
 
563
   lListElem *ep = NULL;
 
564
   non_unique_hash *nuh = (non_unique_hash *)*iterator;
 
565
  
 
566
   if (ht == NULL) {
 
567
      return NULL;
 
568
   }
 
569
 
 
570
   nuh = nuh->next;
 
571
   if(nuh != NULL) {
 
572
      ep = (lListElem *)nuh->data;
 
573
      *iterator = nuh;
 
574
   } else {
 
575
      *iterator = NULL;
 
576
   }
 
577
 
 
578
   return ep;
 
579
}
 
580
 
 
581
/****** cull/hash/cull_hash_delete_non_unique_chain() *************************
 
582
*  NAME
 
583
*     cull_hash_delete_non_unique_chain() -- del list of non unique obj.
 
584
*
 
585
*  SYNOPSIS
 
586
*     void cull_hash_delete_non_unique_chain(cull_htable table, 
 
587
*                                            const void *key, 
 
588
*                                            const void **data) 
 
589
*
 
590
*  FUNCTION
 
591
*     For objects that are stored in a hash table with non unique keys, 
 
592
*     for each key a linked list of objects is created.
 
593
*     This function deletes this linked list for each key in the hash 
 
594
*     table. It is designed to be called by the function 
 
595
*     sge_htable_for_each from the libuti hash implementation.
 
596
*
 
597
*  INPUTS
 
598
*     cull_htable table   - hash table in which to delete/free a sublist
 
599
*     const void *key   - key of the list to be freed 
 
600
*     const void **data - pointer to the sublist
 
601
*
 
602
*  SEE ALSO
 
603
*     uti/hash/sge_htable_for_each()
 
604
******************************************************************************/
 
605
void cull_hash_delete_non_unique_chain(htable table, const void *key, 
 
606
                                       const void **data)
 
607
{
 
608
   non_unique_header *head = (non_unique_header *)*data;
 
609
   if (head != NULL) {
 
610
      non_unique_hash *nuh = head->first;
 
611
      while(nuh != NULL) {
 
612
         non_unique_hash *del = nuh;
 
613
         nuh = nuh->next;
 
614
         free(del);
 
615
      }
 
616
      free(head);
 
617
   }
 
618
}
 
619
 
 
620
/****** cull/hash/cull_hash_free_descr() **************************************
 
621
*  NAME
 
622
*     cull_hash_free_descr() -- free the hash contents of a cull descr
 
623
*
 
624
*  SYNOPSIS
 
625
*     void cull_hash_free_descr(lDescr *descr) 
 
626
*
 
627
*  FUNCTION
 
628
*     Frees the memory used by the hashing information in a cull 
 
629
*     descriptor (lDescr). If a hash table is still associated to 
 
630
*     the descriptor, it is also deleted.
 
631
*
 
632
*  INPUTS
 
633
*     lDescr *descr - descriptor to free 
 
634
*
 
635
*  SEE ALSO
 
636
*     cull/hash/cull_hash_delete_non_unique()
 
637
*     uti/hash/sge_htable_destroy()
 
638
******************************************************************************/
 
639
void cull_hash_free_descr(lDescr *descr)
 
640
{
 
641
   int i;
 
642
   for(i = 0; descr[i].mt != lEndT; i++) {
 
643
      cull_htable ht = descr[i].ht;
 
644
      if (ht != NULL) {
 
645
         if(!mt_is_unique(descr[i].mt)) {
 
646
            /* delete chain of non unique elements */
 
647
            sge_htable_for_each(ht->ht, cull_hash_delete_non_unique_chain);
 
648
            sge_htable_destroy(ht->nuht);
 
649
         }
 
650
         sge_htable_destroy(ht->ht);
 
651
         free(ht);
 
652
         descr[i].ht = NULL;
 
653
      }
 
654
   }
 
655
}
 
656
 
 
657
 
 
658
/****** cull/hash/cull_hash_new_check() ****************************************
 
659
*  NAME
 
660
*     cull_hash_new() -- create new hash table, if it does not yet exist
 
661
*
 
662
*  SYNOPSIS
 
663
*     int cull_hash_new_check(lList *lp, int nm, bool unique) 
 
664
*
 
665
*  FUNCTION
 
666
*     Usually hash tables are defined in the object type definition
 
667
*     for each object type in libs/gdi.
 
668
*
 
669
*     There are cases where for a certain application additional hash 
 
670
*     tables shall be defined to speed up certain access methods.
 
671
*
 
672
*     cull_hash_new_check can be used to create a hash table for a list
 
673
*     on the contents of a certain field.
 
674
*     If it already exist, nothing is done.
 
675
*
 
676
*     The caller can choose whether the field contents have to be
 
677
*     unique within the list or not.
 
678
*
 
679
*  INPUTS
 
680
*     lList *lp   - the list to hold the new hash table
 
681
*     int nm      - the field on which to create the hash table 
 
682
*     bool unique - unique contents or not 
 
683
*
 
684
*  RESULT
 
685
*     int - 1 on success, else 0
 
686
*
 
687
*  EXAMPLE
 
688
*     create a non unique hash index on the job owner for a job list
 
689
*     cull_hash_new_check(job_list, JB_owner, false);
 
690
*
 
691
*  SEE ALSO
 
692
*     cull/hash/cull_hash_new()
 
693
*
 
694
*******************************************************************************/
 
695
int cull_hash_new_check(lList *lp, int nm, bool unique)
 
696
{
 
697
   const lDescr *descr = lGetListDescr(lp);
 
698
   int pos = lGetPosInDescr(descr, nm);
 
699
  
 
700
   if (descr != NULL && pos >= 0) {
 
701
      if (descr[pos].ht == NULL)  {
 
702
         return cull_hash_new(lp, nm, unique);
 
703
      }
 
704
   }
 
705
 
 
706
   return 1;
 
707
}
 
708
 
 
709
/****** cull/hash/cull_hash_new() **********************************************
 
710
*  NAME
 
711
*     cull_hash_new() -- create new hash table
 
712
*
 
713
*  SYNOPSIS
 
714
*     int cull_hash_new(lList *lp, int nm, int unique) 
 
715
*
 
716
*  FUNCTION
 
717
*     Usually hash tables are defined in the object type definition
 
718
*     for each object type in libs/gdi.
 
719
*
 
720
*     There are cases where for a certain application additional hash 
 
721
*     tables shall be defined to speed up certain access methods.
 
722
*
 
723
*     cull_hash_new can be used to create a hash table for a list
 
724
*     on the contents of a certain field.
 
725
*     The caller can choose whether the field contents have to be
 
726
*     unique within the list or not.
 
727
*
 
728
*  INPUTS
 
729
*     lList *lp  - the list to hold the new hash table
 
730
*     int nm     - the field on which to create the hash table 
 
731
*     bool unique - unique contents or not 
 
732
*
 
733
*  RESULT
 
734
*     int - 1 on success, else 0
 
735
*
 
736
*  EXAMPLE
 
737
*     create a non unique hash index on the job owner for a job list
 
738
*     cull_hash_new(job_list, JB_owner, 0);
 
739
*
 
740
*******************************************************************************/
 
741
int cull_hash_new(lList *lp, int nm, bool unique)
 
742
{
 
743
   lDescr *descr;
 
744
   lListElem *ep;
 
745
   int pos, size;
 
746
   char host_key[CL_MAXHOSTLEN];
 
747
 
 
748
   DENTER(CULL_LAYER, "cull_hash_new");
 
749
 
 
750
   if(lp == NULL) {
 
751
      DEXIT;
 
752
      return 0;
 
753
   }
 
754
 
 
755
   descr = lp->descr;
 
756
 
 
757
   pos = lGetPosInDescr(descr, nm);
 
758
 
 
759
   if(pos < 0) {
 
760
      CRITICAL((SGE_EVENT, MSG_CULL_GETELEMSTRERRORXRUNTIMETYPE_S , lNm2Str(nm)));
 
761
      DEXIT;
 
762
      return 0;
 
763
   }
 
764
 
 
765
   if(descr[pos].ht != NULL) {
 
766
      WARNING((SGE_EVENT, MSG_CULL_HASHTABLEALREADYEXISTS_S, lNm2Str(nm)));
 
767
      DEXIT;
 
768
      return 0;
 
769
   }
 
770
 
 
771
   /* copy hashing information */
 
772
   descr[pos].mt |= CULL_HASH;
 
773
   if(unique) {
 
774
      descr[pos].mt |= CULL_UNIQUE;
 
775
   }
 
776
 
 
777
   size = hash_compute_size(lGetNumberOfElem(lp));
 
778
 
 
779
   descr[pos].ht = cull_hash_create(&descr[pos], size);
 
780
 
 
781
   if (descr[pos].ht == NULL) {
 
782
      DEXIT;
 
783
      return 0;
 
784
   }
 
785
 
 
786
   /* insert all elements into the new hash table */
 
787
   for_each(ep, lp) {
 
788
      cull_hash_insert(ep, cull_hash_key(ep, pos, host_key), descr[pos].ht, 
 
789
                       unique);
 
790
   }
 
791
 
 
792
   DEXIT;
 
793
   return 1;
 
794
}
 
795
 
 
796
void *cull_hash_key(const lListElem *ep, int pos, char *host_key)
 
797
{
 
798
   void *key = NULL;
 
799
 
 
800
   lDescr *descr = &(ep->descr[pos]);
 
801
 
 
802
   switch(mt_get_type(descr->mt)) {
 
803
      case lUlongT:
 
804
         key = (void *)&(ep->cont[pos].ul);
 
805
         break;
 
806
 
 
807
      case lStringT:
 
808
         key = ep->cont[pos].str;
 
809
         break;
 
810
  
 
811
      case lHostT:
 
812
         if (ep->cont[pos].host != NULL && host_key != NULL) {
 
813
            sge_hostcpy(host_key,ep->cont[pos].host);
 
814
            sge_strtoupper(host_key, CL_MAXHOSTLEN);
 
815
            key = host_key;
 
816
         }
 
817
         break;
 
818
 
 
819
      default:
 
820
         unknownType("cull_hash_key");
 
821
         key = NULL;
 
822
         break;
 
823
   }
 
824
 
 
825
   return key;
 
826
}
 
827
 
 
828
 
 
829
const char *
 
830
cull_hash_statistics(cull_htable ht, dstring *buffer)
 
831
{
 
832
   const char *ret = NULL;
 
833
 
 
834
   sge_dstring_clear(buffer);
 
835
 
 
836
   if (ht != NULL) {
 
837
      sge_dstring_copy_string(buffer, "Keys:\n");
 
838
      ret = sge_htable_statistics(ht->ht, buffer);
 
839
      
 
840
      if (ht->nuht != NULL) {
 
841
         sge_dstring_append(buffer, "\nNon Unique Hash Access:\n");
 
842
         ret = sge_htable_statistics(ht->nuht, buffer);
 
843
      }
 
844
   } else {
 
845
      ret = sge_dstring_copy_string(buffer, "no hash table");
 
846
   }
 
847
   
 
848
   return ret;
 
849
}
 
850