dictionary.c

来自「SRI international 发布的OAA框架软件」· C语言 代码 · 共 290 行

#ifndef lint
/*static char dictionary_c_rcsid[] = "$Header: /home/zuma1/OAA/CVSRepository/oaa2/src/oaalib/c/src/dictionary.c,v 1.11 2002/09/25 21:44:23 agno Exp $";*/
#endif /*lint*/


#include "dictionary.h"
#include "libicl.h"
#ifdef _WINDOWS
#include <stdlib.h>
#endif

#include <stdio.h>
#include <stdlib.h>

/****************************************************************************
 * Definition for utility dictionary type and functions for manipulating it
 ****************************************************************************/

/**
 * Create a new dictionary that uses _compar() to determine equivalence of
 * keys and _keyfree() to free keys (called by the dict_remove functions).
 */
DICTIONARY *dict_new(int (*_compar)(void *, void *), void (*_keyfree)(void *)) {
  DICTIONARY *newdict = (DICTIONARY *)malloc(sizeof(DICTIONARY));

  newdict->size = 0;
  newdict->capacity = INIT_CAPACITY;
  newdict->compar = _compar;
  newdict->keyfree = _keyfree;

  if(!(newdict->key = (void *)calloc(INIT_CAPACITY, sizeof(void*)))) {
    return NULL;
  }
  if(!(newdict->value = (void *)calloc(INIT_CAPACITY, sizeof(void*)))) {
    return NULL;
  }
  return newdict;
}
/**
 * Expand dictionary capacity by one increment.
 * Returns size of new dictionary.
 */
int dict_expand_capacity(DICTIONARY *dict) {
  void **newkey, **newval;
  int newcap, i, n;

  if(!dict)     /* null passed in, return error */
    return -1;
  newcap = dict->capacity + INIT_CAPACITY;
  if(!(newkey = (void *)calloc(newcap, sizeof(void*))))
    return dict->capacity;
  if(!(newval = (void *)calloc(newcap, sizeof(void*))))
    return dict->capacity;
  for(i=0, n=dict->size; i<n; i++) {
    newkey[i] = dict->key[i];
    newval[i] = dict->value[i];
  }
  free(dict->key);
  free(dict->value);
  dict->key = newkey;
  dict->value = newval;
  return(dict->capacity = newcap);
}
/**
 * Uses compar() to compare keys and return the corresponding value.
 */
void *dict_get(DICTIONARY *d, void *key) {
  int i, n;

  for(i=0, n=d->size; i<n; i++) {
    if(d->compar(key, d->key[i]) == 1) {
      return d->value[i];
    }
  }
  return NULL;
}

/**
 * Return the nth key and value in the list in variables key and value.
 * Return 1 if there is a value and 0 if not.
 */
int dict_get_nth(DICTIONARY *d, void **key, void **value, int n) {
  if((n >= 0) && (n < d->size)) {
    *key = d->key[n];
    *value = d->value[n];
    return 1;
  }
  return 0;
}

/**
 * Return the index assocated with this key or -1 if it doesn't exist.
 */
int dict_index_for_key(DICTIONARY *d, void *key) {
  int i,n;

  for(i=0, n=d->size; i<n; i++) {
    if(d->compar(key, d->key[i]) == 1) {
      return i;
    }
  }
  return -1;
}

/**
 * Add a key/value pair to a dictionary.  If the key already exists, the value
 * is replaced with this one and the old value is returned
 */
void *dict_put(DICTIONARY *d, void *key, void *value) {
  int oldsize, index;
  void *ret = NULL;

  if(!d) return ret;
  oldsize = d->size;
  /* Check to see if this is a new key */
  if((index = dict_index_for_key(d, key)) < 0) {
    /* Check capacity and expand if neccessary */
    if(oldsize >= d->capacity)
      if(dict_expand_capacity(d) <= oldsize)
        return NULL;
    /* add key/value pair at end */
    d->key[oldsize] = key;
    d->value[oldsize] = value;
    d->size++;
  } else { /* must be an existing key */
    ret = d->value[index];
    d->value[index] = value;
  }
  return ret;
}

/**
 * Add a key/value pair to a dictionary.  With this function, the dictionary
 * acts more like a vector in that it may add more than one value with the
 * same key to the table.  Returns the new value
 */
void *dict_put_nonunique(DICTIONARY *d, void *key, void *value) {
  int oldsize;
  void *ret = NULL;

  if(!d) return ret;
  oldsize = d->size;
  /* Check capacity and expand if neccessary */
  if(oldsize >= d->capacity)
    if(dict_expand_capacity(d) <= oldsize)
      return NULL;
  /* add key/value pair at end */
  d->key[oldsize] = key;
  d->value[oldsize] = value;
  d->size++;
  return value;
}

/**
 * Remove the first occurance of a key and it's associated value.
 * Call d->keyfree() to free the key.  Return the associated value.
 */
void *dict_remove(DICTIONARY *d, void *key) {
  void *ret = NULL;
  int index, i, n;

  if(!d) return ret;
  index = dict_index_for_key(d, key);
  if(index >= 0) {
    /* remember the return value */
    ret = d->value[index];
    /* free the key */
    if (d->keyfree)
      d->keyfree(d->key[index]);

    /* shift the remaining contents up */
    for(i=index+1, n=d->size; i<n; i++) {
      d->key[i-1] = d->key[i];
      d->value[i-1] = d->value[i];
    }
    d->size--;
  }
  CHECK_LEAKS();
  return ret;
}

/**
 * Remove the entry specified by this key/value pair.
 * Call d->keyfree() to free the key.  Return the associated value.
 *
 * <p><b>Warning</b> -- this function assumes that the same comparison function is
 * used for both keys and values.  this will be true when they are both
 * ICL_Terms.</p>
 */
void *dict_remove_specific(DICTIONARY *d, void *key, void *value) {
  void *ret = NULL;
  int index = -1, i, n;

  if(!d) return ret;
  for(i=0, n=d->size; i<n; i++) {
    if((d->compar(key, d->key[i]) == 1) &&
       (d->compar(value, d->value[i]) == 1)) {

      /* remember the correct index and return value */
      index = i;
      ret = d->value[index];

      /* free the key */
      if (d->keyfree)
        d->keyfree(d->key[index]);
      break;
    }
  }
  if(index >= 0) {
    /* shift the remaining contents up */
    for(i=index+1, n=d->size; i<n; i++) {
      d->key[i-1] = d->key[i];
      d->value[i-1] = d->value[i];
    }
    d->size--;
  }
  return ret;
}

/**
 * Remove all occurances of a key and it's associated values.
 * Return the number of key/value pairs removed.
 * Allocate an array (values) and set it to contain the values removed.
 *
 * <p><b>NOTE:<b> "values" must be freed by the caller!<p>
 */
void **dict_remove_all(DICTIONARY *d, void *key, int *num_removed) {
  int index, i, n, num_found = 0;
  void **_values = NULL;

  if(!d) {
    if (num_removed) {
      *num_removed = num_found;
    }
    return _values;
  }

  index = dict_index_for_key(d, key);
  while(index >= 0) {
    num_found++;

    /* Allocate space for and remember the return value */
    _values = (void *)realloc(_values, sizeof(void*) * num_found);
    _values[num_found-1] = d->value[index];

    /* Free the key */
    d->keyfree(d->key[index]);

    /* shift the remaining contents up */
    for(i=index+1, n=d->size; i<n; i++) {
      d->key[i-1] = d->key[i];
      d->value[i-1] = d->value[i];
    }
    d->size--;
    index = dict_index_for_key(d, key);
  }
  if (num_removed)
    *num_removed = num_found;
  return _values;
}

/**
 * Free the dictionary but not the contents.
 */
void dict_free(DICTIONARY *d) {
  if(!d) return;
  free(d->key);
  free(d->value);
  free(d);
}

/**
 * @defgroup Dictionary Dictionary
 *
 * Definition for utility dictionary type and functions for manipulating it.
 *
 * @{
 */

/**
 * @file dictionary.h
 */

/**
 * @file dictionary.c
 * Definition for utility dictionary type and functions for manipulating it.
 */

/** @} */