File: rdf_hash_memory.c

package info (click to toggle)
redland 1.0.7-1
  • links: PTS, VCS
  • area: main
  • in suites: lenny
  • size: 27,592 kB
  • ctags: 12,328
  • sloc: ansic: 79,017; xml: 25,115; sh: 10,162; yacc: 5,985; lex: 3,682; makefile: 3,260; perl: 2,814; cpp: 59
file content (1066 lines) | stat: -rw-r--r-- 27,132 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
/* -*- Mode: c; c-basic-offset: 2 -*-
 *
 * rdf_hash_memory.c - RDF Hash In Memory Implementation
 *
 * $Id: rdf_hash_memory.c 12583 2007-09-21 11:19:32Z laalto $
 *
 * Copyright (C) 2000-2006, David Beckett http://purl.org/net/dajobe/
 * Copyright (C) 2000-2004, University of Bristol, UK http://www.bristol.ac.uk/
 * 
 * This package is Free Software and part of Redland http://librdf.org/
 * 
 * It is licensed under the following three licenses as alternatives:
 *   1. GNU Lesser General Public License (LGPL) V2.1 or any newer version
 *   2. GNU General Public License (GPL) V2 or any newer version
 *   3. Apache License, V2.0 or any newer version
 * 
 * You may not use this file except in compliance with at least one of
 * the above three licenses.
 * 
 * See LICENSE.html or LICENSE.txt at the top of this package for the
 * complete terms and further detail along with the license texts for
 * the licenses in COPYING.LIB, COPYING and LICENSE-2.0.txt respectively.
 * 
 * 
 */


#ifdef HAVE_CONFIG_H
#include <rdf_config.h>
#endif

#ifdef WIN32
#include <win32_rdf_config.h>
#endif

#include <stdio.h>
#include <string.h>
#include <stdarg.h>
#include <sys/types.h>

#ifdef HAVE_STDLIB_H
#include <stdlib.h> /* for abort() as used in errors */
#endif

#include <redland.h>
#include <rdf_types.h>


/* private structures */
struct librdf_hash_memory_node_value_s
{
  struct librdf_hash_memory_node_value_s* next;
  void *value;
  size_t value_len;
};
typedef struct librdf_hash_memory_node_value_s librdf_hash_memory_node_value;


struct librdf_hash_memory_node_s
{
  struct librdf_hash_memory_node_s* next;
  void *key;
  size_t key_len;
  u32 hash_key;
  librdf_hash_memory_node_value *values;
  int values_count;
};
typedef struct librdf_hash_memory_node_s librdf_hash_memory_node;


typedef struct
{
  /* the hash object */
  librdf_hash* hash;
  /* An array pointing to a list of nodes (buckets) */
  librdf_hash_memory_node** nodes;
  /* this many buckets used */
  int size;
  /* this many keys */
  int keys;
  /* this many values */
  int values;
  /* total array size */
  int capacity;

  /* array load factor expressed out of 1000.
   * Always true: (size/capacity * 1000) < load_factor,
   * or in the code: size * 1000 < load_factor * capacity
   */
  int load_factor;
} librdf_hash_memory_context;



/* default load_factor out of 1000 */
static const int librdf_hash_default_load_factor=750;

/* starting capacity - MUST BE POWER OF 2 */
static const int librdf_hash_initial_capacity=8;


/* prototypes for local functions */
static librdf_hash_memory_node* librdf_hash_memory_find_node(librdf_hash_memory_context* hash, void *key, size_t key_len, int *bucket, librdf_hash_memory_node** prev);
static void librdf_free_hash_memory_node(librdf_hash_memory_node* node);
static int librdf_hash_memory_expand_size(librdf_hash_memory_context* hash);

/* Implementing the hash cursor */
static int librdf_hash_memory_cursor_init(void *cursor_context, void *hash_context);
static int librdf_hash_memory_cursor_get(void* context, librdf_hash_datum* key, librdf_hash_datum* value, unsigned int flags);
static void librdf_hash_memory_cursor_finish(void* context);




/* functions implementing the API */

static int librdf_hash_memory_create(librdf_hash* new_hash, void* context);
static int librdf_hash_memory_destroy(void* context);
static int librdf_hash_memory_open(void* context, const char *identifier, int mode, int is_writable, int is_new, librdf_hash* options);
static int librdf_hash_memory_close(void* context);
static int librdf_hash_memory_clone(librdf_hash* new_hash, void *new_context, char *new_identifier, void* old_context);
static int librdf_hash_memory_values_count(void *context);
static int librdf_hash_memory_put(void* context, librdf_hash_datum *key, librdf_hash_datum *data);
static int librdf_hash_memory_exists(void* context, librdf_hash_datum *key, librdf_hash_datum *value);
static int librdf_hash_memory_delete_key(void* context, librdf_hash_datum *key);
static int librdf_hash_memory_delete_key_value(void* context, librdf_hash_datum *key, librdf_hash_datum *value);
static int librdf_hash_memory_sync(void* context);
static int librdf_hash_memory_get_fd(void* context);

static void librdf_hash_memory_register_factory(librdf_hash_factory *factory);




/*
 * perldelta 5.8.0 says under *Performance Enhancements*
 *
 *   Hashes now use Bob Jenkins "One-at-a-Time" hashing key algorithm
 *   http://burtleburtle.net/bob/hash/doobs.html  This algorithm is
 *   reasonably fast while producing a much better spread of values
 *   than the old hashing algorithm ...
 *
 * Changed here to hash the string backwards to help do URIs better
 *
 */

#define ONE_AT_A_TIME_HASH(hash,str,len) \
     do { \
        register const unsigned char *c_oneat = (unsigned char*)str+len-1; \
        register int i_oneat = len; \
        register u32 hash_oneat = 0; \
        while (i_oneat--) { \
            hash_oneat += *c_oneat--; \
            hash_oneat += (hash_oneat << 10); \
            hash_oneat ^= (hash_oneat >> 6); \
        } \
        hash_oneat += (hash_oneat << 3); \
        hash_oneat ^= (hash_oneat >> 11); \
        (hash) = (hash_oneat + (hash_oneat << 15)); \
    } while(0)



/* helper functions */


/**
 * librdf_hash_memory_find_node:
 * @hash: the memory hash context
 * @key: key string
 * @key_len: key string length
 * @user_bucket: pointer to store bucket
 * @prev: pointer to store previous node
 *
 * Find the node for the given key or value.
 * 
 * If value is not NULL and value_len is non 0, the value will also be
 * compared in the search.
 *
 * If user_bucket is not NULL, the bucket used will be returned.  if
 * prev is no NULL, the previous node in the list will be returned.
 * 
 * Return value: #librdf_hash_memory_node of content or NULL on failure
 **/
static librdf_hash_memory_node*
librdf_hash_memory_find_node(librdf_hash_memory_context* hash, 
			     void *key, size_t key_len,
			     int *user_bucket,
			     librdf_hash_memory_node** prev) 
{
  librdf_hash_memory_node* node;
  int bucket;
  u32 hash_key;

  /* empty hash */
  if(!hash->capacity)
    return NULL;
  
  ONE_AT_A_TIME_HASH(hash_key, key, key_len);

  if(prev)
    *prev=NULL;

  /* find slot in table */
  bucket=hash_key & (hash->capacity - 1);
  if(user_bucket)
    *user_bucket=bucket;

  /* check if there is a list present */ 
  node=hash->nodes[bucket];
  if(!node)
    /* no list there */
    return NULL;
    
  /* walk the list */
  while(node) {
    if(key_len == node->key_len && !memcmp(key, node->key, key_len))
      break;
    if(prev)
      *prev=node;
    node=node->next;
  }

  return node;
}


static void
librdf_free_hash_memory_node(librdf_hash_memory_node* node) 
{
  if(node->key)
    LIBRDF_FREE(cstring, node->key);
  if(node->values) {
    librdf_hash_memory_node_value *vnode, *next;

    /* Empty the list of values */
    for(vnode=node->values; vnode; vnode=next) {
      next=vnode->next;
      if(vnode->value)
        LIBRDF_FREE(cstring, vnode->value);
      LIBRDF_FREE(librdf_hash_memory_node_value, vnode);
    }
  }
  LIBRDF_FREE(librdf_hash_memory_node, node);
}


static int
librdf_hash_memory_expand_size(librdf_hash_memory_context* hash) {
  int required_capacity=0;
  librdf_hash_memory_node **new_nodes;
  int i;

  if (hash->capacity) {
    /* big enough */
    if((1000 * hash->keys) < (hash->load_factor * hash->capacity))
      return 0;
    /* grow hash (keeping it a power of two) */
    required_capacity=hash->capacity << 1;
  } else {
    required_capacity=librdf_hash_initial_capacity;
  }

  /* allocate new table */
  new_nodes=(librdf_hash_memory_node**)LIBRDF_CALLOC(librdf_hash_memory_nodes, 
						     required_capacity,
						     sizeof(librdf_hash_memory_node*));
  if(!new_nodes)
    return 1;


  /* it is a new hash empty hash - we are done */
  if(!hash->size) {
    hash->capacity=required_capacity;
    hash->nodes=new_nodes;
    return 0;
  }
  

  for(i=0; i<hash->capacity; i++) {
    librdf_hash_memory_node *node=hash->nodes[i];
      
    /* walk all attached nodes */
    while(node) {
      librdf_hash_memory_node *next;
      int bucket;

      next=node->next;
      /* find slot in new table */
      bucket=node->hash_key & (required_capacity - 1);
      node->next=new_nodes[bucket];
      new_nodes[bucket]=node;

      node=next;
    }
  }

  /* now free old table */
  LIBRDF_FREE(librdf_hash_memory_nodes, hash->nodes);

  /* attach new one */
  hash->capacity=required_capacity;
  hash->nodes=new_nodes;

  return 0;
}



/* functions implementing hash api */

/**
 * librdf_hash_memory_create:
 * @hash: #librdf_hash hash
 * @context: memory hash contxt
 *
 * Create a new memory hash.
 * 
 * Return value: non 0 on failure
 **/
static int
librdf_hash_memory_create(librdf_hash* hash, void* context) 
{
  librdf_hash_memory_context* hcontext=(librdf_hash_memory_context*)context;

  hcontext->hash=hash;
  hcontext->load_factor=librdf_hash_default_load_factor;
  return librdf_hash_memory_expand_size(hcontext);
}


/**
 * librdf_hash_memory_destroy:
 * @context: memory hash context
 *
 * Destroy a memory hash.
 * 
 * Return value: non 0 on failure
 **/
static int
librdf_hash_memory_destroy(void* context) 
{
  librdf_hash_memory_context* hcontext=(librdf_hash_memory_context*)context;

  if(hcontext->nodes) {
    int i;
  
    for(i=0; i<hcontext->capacity; i++) {
      librdf_hash_memory_node *node=hcontext->nodes[i];
      
      /* this entry is used */
      if(node) {
        librdf_hash_memory_node *next;
        /* free all attached nodes */
        while(node) {
          next=node->next;
          librdf_free_hash_memory_node(node);
          node=next;
        }
      }
    }
    LIBRDF_FREE(librdf_hash_memory_nodes, hcontext->nodes);
  }

  return 0;
}


/**
 * librdf_hash_memory_open:
 * @context: memory hash context
 * @identifier: identifier - not used
 * @mode: access mode - not used
 * @is_writable: is hash writable? - not used
 * @is_new: is hash new? - not used
 * @options: #librdf_hash of options - not used
 *
 * Open memory hash with given parameters.
 * 
 * Return value: non 0 on failure
 **/
static int
librdf_hash_memory_open(void* context, const char *identifier,
                        int mode, int is_writable, int is_new,
                        librdf_hash* options) 
{
  /* NOP */
  return 0;
}


/**
 * librdf_hash_memory_close:
 * @context: memory hash context
 *
 * Close the hash.
 * 
 * Return value: non 0 on failure
 **/
static int
librdf_hash_memory_close(void* context) 
{
  /* NOP */
  return 0;
}


static int
librdf_hash_memory_clone(librdf_hash *hash, void* context, char *new_identifer,
                         void *old_context) 
{
  librdf_hash_memory_context* hcontext=(librdf_hash_memory_context*)context;
  librdf_hash_memory_context* old_hcontext=(librdf_hash_memory_context*)old_context;
  librdf_hash_datum *key, *value;
  librdf_iterator *iterator;
  int status=0;
  
  /* copy data fields that might change */
  hcontext->hash=hash;
  hcontext->load_factor=old_hcontext->load_factor;

  /* Don't need to deal with new_identifier - not used for memory hashes */

  /* Use higher level functions to iterator this data
   * on the other hand, maybe this is a good idea since that
   * code is tested and works
   */

  key=librdf_new_hash_datum(hash->world, NULL, 0);
  value=librdf_new_hash_datum(hash->world, NULL, 0);

  iterator=librdf_hash_get_all(old_hcontext->hash, key, value);
  while(!librdf_iterator_end(iterator)) {
    librdf_hash_datum* k= (librdf_hash_datum*)librdf_iterator_get_key(iterator);
    librdf_hash_datum* v= (librdf_hash_datum*)librdf_iterator_get_value(iterator);

    if(librdf_hash_memory_put(hcontext, k, v)) {
      status=1;
      break;
    }
    librdf_iterator_next(iterator);
  }
  if(iterator)
    librdf_free_iterator(iterator);

  librdf_free_hash_datum(value);
  librdf_free_hash_datum(key);

  return status;
}


/**
 * librdf_hash_memory_values_count:
 * @context: memory hash cursor context
 *
 * Get the number of values in the hash.
 * 
 * Return value: number of values in the hash or <0 on failure
 **/
static int
librdf_hash_memory_values_count(void *context) 
{
  librdf_hash_memory_context* hash=(librdf_hash_memory_context*)context;

  return hash->values;
}



typedef struct {
  librdf_hash_memory_context* hash;
  int current_bucket;
  librdf_hash_memory_node* current_node;
  librdf_hash_memory_node_value *current_value;
} librdf_hash_memory_cursor_context;



/**
 * librdf_hash_memory_cursor_init:
 * @cursor_context: hash cursor context
 * @hash_context: hash to operate over
 *
 * Initialise a new hash cursor.
 * 
 * Return value: non 0 on failure
 **/
int
librdf_hash_memory_cursor_init(void *cursor_context, void *hash_context) 
{
  librdf_hash_memory_cursor_context *cursor=(librdf_hash_memory_cursor_context*)cursor_context;

  cursor->hash = (librdf_hash_memory_context*)hash_context;
  return 0;
}


/**
 * librdf_hash_memory_cursor_get:
 * @context: memory hash cursor context
 * @key: pointer to key to use
 * @value: pointer to value to use
 * @flags: flags
 *
 * Retrieve a hash value for the given key.
 * 
 * Return value: non 0 on failure
 **/
static int
librdf_hash_memory_cursor_get(void* context, 
                              librdf_hash_datum *key,
                              librdf_hash_datum *value,
                              unsigned int flags)
{
  librdf_hash_memory_cursor_context *cursor=(librdf_hash_memory_cursor_context*)context;
  librdf_hash_memory_node_value *vnode=NULL;
  librdf_hash_memory_node *node;
  

  /* First step, make sure cursor->current_node points to a valid node,
     if possible */

  /* Move to start of hash if necessary  */
  if(flags == LIBRDF_HASH_CURSOR_FIRST) {
    int i;
    
    cursor->current_node=NULL;
    /* find first used bucket (with keys) */
    cursor->current_bucket=0;

    for(i=0; i< cursor->hash->capacity; i++)
      if((cursor->current_node=cursor->hash->nodes[i])) {
        cursor->current_bucket=i;
        break;
      }

    if(cursor->current_node)
      cursor->current_value=cursor->current_node->values;
  }

  /* If still have no current node, try to find it from the key */
  if(!cursor->current_node && key && key->data) {
    cursor->current_node=librdf_hash_memory_find_node(cursor->hash,
                                                      (char*)key->data,
                                                      key->size,
                                                      NULL, NULL);
    if(cursor->current_node)
      cursor->current_value=cursor->current_node->values;
  }


  /* If still have no node, failed */
  if(!cursor->current_node)
    return 1;

  /* Check for end of values */

  switch(flags) {
    case LIBRDF_HASH_CURSOR_SET:
      /* If key does not exist, failed above, so test if there are values */

      /* FALLTHROUGH */
    case LIBRDF_HASH_CURSOR_NEXT_VALUE:
      /* If want values and have reached end of values list, end */
      if(!cursor->current_value)
        return 1;
      break;
      
    case LIBRDF_HASH_CURSOR_FIRST:
    case LIBRDF_HASH_CURSOR_NEXT:
      /* If have reached last bucket, end */
      if(cursor->current_bucket >= cursor->hash->capacity)
        return 1;
      
      break;
    default:
      librdf_log(cursor->hash->hash->world,
                 0, LIBRDF_LOG_ERROR, LIBRDF_FROM_HASH, NULL,
                 "Unknown hash method flag %d", flags);
      return 1;
  }
  

  /* Ok, there is data, retrieve it */

  switch(flags) {
    case LIBRDF_HASH_CURSOR_SET:

      /* FALLTHROUGH */
    case LIBRDF_HASH_CURSOR_NEXT_VALUE:
      vnode=cursor->current_value;
      
      /* copy value */
      value->data=vnode->value;
      value->size=vnode->value_len;
      
      /* move on */
      cursor->current_value=vnode->next;
      break;
      
    case LIBRDF_HASH_CURSOR_FIRST:
    case LIBRDF_HASH_CURSOR_NEXT:
      node=cursor->current_node;

      /* get key */
      key->data= node->key;
      key->size= node->key_len;

      /* if want values, walk through them */
      if(value) {
        vnode=cursor->current_value;
        
        /* get value */
        value->data=vnode->value;
        value->size=vnode->value_len;

        /* move on */
        cursor->current_value=vnode->next;
        
        /* stop here if there are more values, otherwise need next
         * key & values so drop through and move to the next node
         */
        if(cursor->current_value)
          break;
      }
      
      /* move on to next node in current bucket */
      if(!(node=cursor->current_node->next)) {
        int i;
        
        /* end of list - move to next used bucket */
        for(i=cursor->current_bucket+1; i< cursor->hash->capacity; i++)
          if((node=cursor->hash->nodes[i])) {
            cursor->current_bucket=i;
            break;
          }
        
      }
      
      if((cursor->current_node=node))
        cursor->current_value=node->values;
      
      break;
    default:
      librdf_log(cursor->hash->hash->world,
                 0, LIBRDF_LOG_ERROR, LIBRDF_FROM_HASH, NULL,
                 "Unknown hash method flag %d", flags);
      return 1;
  }
  

  return 0;
}


/**
 * librdf_hash_memory_cursor_finished:
 * @context: hash memory get iterator context
 *
 * Finish the serialisation of the hash memory get.
 *
 **/
static void
librdf_hash_memory_cursor_finish(void* context)
{
/* librdf_hash_memory_cursor_context *cursor=(librdf_hash_memory_cursor_context*)context; */

}


/**
 * librdf_hash_memory_put:
 * @context: memory hash context
 * @key: pointer to key to store
 * @value: pointer to value to store
 *
 * - Store a key/value pair in the hash.
 * 
 * Return value: non 0 on failure
 **/
static int
librdf_hash_memory_put(void* context, librdf_hash_datum *key, 
		       librdf_hash_datum *value) 
{
  librdf_hash_memory_context* hash=(librdf_hash_memory_context*)context;
  librdf_hash_memory_node *node;
  librdf_hash_memory_node_value *vnode;
  u32 hash_key;
  void *new_key=NULL;
  void *new_value;
  int bucket= (-1);
  int is_new_node;

  /* ensure there is enough space in the hash */
  if (librdf_hash_memory_expand_size(hash))
    return 1;
  
  /* find node for key */
  node=librdf_hash_memory_find_node(hash,
				    key->data, key->size,
				    NULL, NULL);

  is_new_node=(node == NULL);
  
  /* not found - new key */
  if(is_new_node) {
    ONE_AT_A_TIME_HASH(hash_key, key->data, key->size);

    bucket=hash_key & (hash->capacity - 1);

    /* allocate new node */
    node=(librdf_hash_memory_node*)LIBRDF_CALLOC(librdf_hash_memory_node, 1,
                                                 sizeof(librdf_hash_memory_node));
    if(!node)
      return 1;

    node->hash_key=hash_key;
    
    /* allocate key for new node */
    new_key=LIBRDF_MALLOC(cstring, key->size);
    if(!new_key) {
      LIBRDF_FREE(librdf_hash_memory_node, node);
      return 1;
    }

    /* copy new key */
    memcpy(new_key, key->data, key->size);
    node->key=new_key;
    node->key_len=key->size;
  }
  
  
  /* always allocate new value */
  new_value=LIBRDF_MALLOC(cstring, value->size);
  if(!new_value) {
    if(is_new_node) {
      LIBRDF_FREE(cstring, new_key);
      LIBRDF_FREE(librdf_hash_memory_node, node);
    }
    return 1;
  }

  /* always allocate new librdf_hash_memory_node_value */
  vnode=(librdf_hash_memory_node_value*)LIBRDF_CALLOC(librdf_hash_memory_node_value, 1, sizeof(librdf_hash_memory_node_value));
  if(!vnode) {
    LIBRDF_FREE(cstring, new_value);
    if(is_new_node) {
      LIBRDF_FREE(cstring, new_key);
      LIBRDF_FREE(librdf_hash_memory_node, node);
    }
    return 1;
  }

  /* if we get here, all allocations succeeded */


  /* put new value node in list */
  vnode->next=node->values;
  node->values=vnode;

  /* note that in counter */
  node->values_count++;
 
  /* copy new value */
  memcpy(new_value, value->data, value->size);
  vnode->value=new_value;
  vnode->value_len=value->size;


  /* now update buckets and hash counts */
  if(is_new_node) {
    node->next=hash->nodes[bucket];
    hash->nodes[bucket]=node;
  
    hash->keys++;
  }
  

  hash->values++;

  /* Only increase bucket count use when previous value was NULL */
  if(!node->next)
    hash->size++;

  return 0;
}


/**
 * librdf_hash_memory_exists:
 * @context: memory hash context
 * @key: key
 * @value: value
 *
 * Test the existence of a key in the hash.
 * 
 * Return value: >0 if the key/value exists in the hash, 0 if not, <0 on failure
 **/
static int
librdf_hash_memory_exists(void* context, 
                          librdf_hash_datum *key, librdf_hash_datum *value)
{
  librdf_hash_memory_context* hash=(librdf_hash_memory_context*)context;
  librdf_hash_memory_node* node;
  librdf_hash_memory_node_value *vnode;
  
  node=librdf_hash_memory_find_node(hash,
				    (char*)key->data, key->size,
				    NULL, NULL);
  /* key not found */
  if(!node)
    return 0;
  
  /* no value wanted */
  if(!value)
    return 1;

  /* search for value in list of values */
  for(vnode=node->values; vnode; vnode=vnode->next) {
    if(value->size == vnode->value_len && 
       !memcmp(value->data, vnode->value, value->size))
      break;
  }

  return (vnode != NULL);
}



/**
 * librdf_hash_memory_delete_key_value:
 * @context: memory hash context
 * @key: pointer to key to delete
 * @value: pointer to value to delete
 *
 * - Delete a key/value pair from the hash.
 * 
 * Return value: non 0 on failure
 **/
static int
librdf_hash_memory_delete_key_value(void* context, librdf_hash_datum *key,
                                    librdf_hash_datum *value)
{
  librdf_hash_memory_context* hash=(librdf_hash_memory_context*)context;
  librdf_hash_memory_node *node, *prev, *next;
  librdf_hash_memory_node_value *vnode, *vprev;
  int bucket;
  
  node=librdf_hash_memory_find_node(hash, 
				    (char*)key->data, key->size,
				    &bucket, &prev);
  /* key not found anywhere */
  if(!node)
    return 1;

  /* search for value in list of values */
  vnode=node->values;
  vprev=NULL;
  while(vnode) {
    if(value->size == vnode->value_len && 
       !memcmp(value->data, vnode->value, value->size))
      break;
    vprev=vnode;
    vnode=vnode->next;
  }

  /* key/value combination not found */
  if(!vnode)
    return 1;

  /* found - delete it from list */
  if(!vprev) {
    /* at start of list so delete from there */
    node->values=vnode->next;
  } else
    vprev->next=vnode->next;

  /* free value and value node */
  if(vnode->value)
    LIBRDF_FREE(librdf_hash_memory_node_value, vnode->value);
  LIBRDF_FREE(librdf_hash_memory_node_value, vnode);

  /* update hash counts */
  hash->values--;

  /* check if last value was removed */
  if(node->values)
    /* no, so return success */
    return 0;
  

  /* yes - all values gone so need to delete entire key node */

  if(!prev) {
    /* is at start of list, so delete from there */
    if(!(hash->nodes[bucket]=node->next))
      /* hash bucket occupancy is one less if bucket is now empty */
      hash->size--;
    next=NULL;
  } else
    next=prev->next=node->next;
  
  /* free node */
  librdf_free_hash_memory_node(node);
  
  /* see if there are remaining values for this key */
  if(!next) {
    /* no - so was last value for that key, reduce key count */
    hash->keys--;
  } else {
    int found=0;
    
    node=next;
    while(node) {
      if(key->size == node->key_len && !memcmp(key, node->key, key->size)){
        found=1;
        break;
      }
      node=node->next;
    }
    
    /* no further key values found - so was last value for that key */
    if(!found)
      hash->keys--;
  }

  return 0;
}


/**
 * librdf_hash_memory_delete_key:
 * @context: memory hash context
 * @key: pointer to key to delete
 *
 * - Delete a key and all its values from the hash.
 * 
 * Return value: non 0 on failure
 **/
static int
librdf_hash_memory_delete_key(void* context, librdf_hash_datum *key) 
{
  librdf_hash_memory_context* hash=(librdf_hash_memory_context*)context;
  librdf_hash_memory_node *node, *prev;
  int bucket;
  
  node=librdf_hash_memory_find_node(hash, 
				    (char*)key->data, key->size,
				    &bucket, &prev);
  /* not found anywhere */
  if(!node)
    return 1;

  /* search list from here */
  if(!prev) {
    /* is at start of list, so delete from there */
    if(!(hash->nodes[bucket]=node->next))
      /* hash bucket occupancy is one less if bucket is now empty */
      hash->size--;
  } else
    prev->next=node->next;

  /* update hash counts */
  hash->keys--;
  hash->values-= node->values_count;
  
  /* free node */
  librdf_free_hash_memory_node(node);
  return 0;
}


/**
 * librdf_hash_memory_sync:
 * @context: memory hash context
 *
 * Flush the hash to disk.
 * 
 * Not used
 * 
 * Return value: 0
 **/
static int
librdf_hash_memory_sync(void* context) 
{
  /* Not applicable */
  return 0;
}


/**
 * librdf_hash_memory_get_fd:
 * @context: memory hash context
 *
 * Get the file descriptor representing the hash.
 * 
 * Not used
 * 
 * Return value: -1
 **/
static int
librdf_hash_memory_get_fd(void* context) 
{
  /* Not applicable */
  return -1;
}


/* local function to register memory hash functions */

/**
 * librdf_hash_memory_register_factory:
 * @factory: hash factory prototype
 *
 * Register the memory hash module with the hash factory.
 * 
 **/
static void
librdf_hash_memory_register_factory(librdf_hash_factory *factory) 
{
  factory->context_length = sizeof(librdf_hash_memory_context);
  factory->cursor_context_length = sizeof(librdf_hash_memory_cursor_context);
  
  factory->create  = librdf_hash_memory_create;
  factory->destroy = librdf_hash_memory_destroy;

  factory->open    = librdf_hash_memory_open;
  factory->close   = librdf_hash_memory_close;
  factory->clone   = librdf_hash_memory_clone;

  factory->values_count = librdf_hash_memory_values_count;

  factory->put     = librdf_hash_memory_put;
  factory->exists  = librdf_hash_memory_exists;
  factory->delete_key  = librdf_hash_memory_delete_key;
  factory->delete_key_value  = librdf_hash_memory_delete_key_value;
  factory->sync    = librdf_hash_memory_sync;
  factory->get_fd  = librdf_hash_memory_get_fd;

  factory->cursor_init   = librdf_hash_memory_cursor_init;
  factory->cursor_get    = librdf_hash_memory_cursor_get;
  factory->cursor_finish = librdf_hash_memory_cursor_finish;
}

/**
 * librdf_init_hash_memory:
 * @world: redland world object
 *
 * Initialise the memory hash module.
 * 
 * Initialises the memory hash module and sets the default hash load factor.
 *
 * The recommended and current default value is 0.75, i.e. 750/1000.  
 * To use the default value (whatever it is) use a value less than 0.
 **/
void
librdf_init_hash_memory(librdf_world *world) 
{
  /* use default load factor */
  if(world->hash_load_factor <= 0 || world->hash_load_factor > 999)
    world->hash_load_factor=librdf_hash_default_load_factor;

  librdf_hash_register_factory(world,
                               "memory", &librdf_hash_memory_register_factory);
}