dictionary.c

Go to the documentation of this file.

/*
 * Copyright (C) 2006  SRI International
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 *
 * SRI International: 333 Ravenswood Ave, Menlo Park, CA 94025
 */

#ifndef lint
/*static char dictionary_c_rcsid[] = "$Header: /home/zuma1/OAA/CVSRepository/oaa2/src/oaalib/c/src/dictionary.c,v 1.12 2006/10/29 22:12:13 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
 ****************************************************************************/

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;
}
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);
}
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;
}

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;
}

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;
}

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;
}

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;
}

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;
}

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;
}

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;
}

void dict_free(DICTIONARY *d) {
  if(!d) return;
  free(d->key);
  free(d->value);
  free(d);
}

---