Wolfgang Thallergcc16 merge934c3885 months agoHistory
294 lines · 7.6 KB · C
RawDownload
/* Hash tables for Objective C internal structures   Copyright (C) 1993-2026 Free Software Foundation, Inc. This file is part of GCC. GCC is free software; you can redistribute it and/or modifyit under the terms of the GNU General Public License as published bythe Free Software Foundation; either version 3, or (at your option)any later version. GCC is distributed in the hope that it will be useful,but WITHOUT ANY WARRANTY; without even the implied warranty ofMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See theGNU General Public License for more details. Under Section 7 of GPL version 3, you are granted additionalpermissions described in the GCC Runtime Library Exception, version3.1, as published by the Free Software Foundation. You should have received a copy of the GNU General Public License anda copy of the GCC Runtime Library Exception along with this program;see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see<http://www.gnu.org/licenses/>.  */ #include "objc-private/common.h"#include <assert.h>               /* For assert.  */ #include "objc/runtime.h"         /* For objc_calloc.  */#include "objc-private/hash.h" /* These two macros determine when a hash table is full and   by how much it should be expanded respectively.    These equations are percentages.  */#define FULLNESS(cache) \   ((((cache)->size * 75) / 100) <= (cache)->used)#define EXPANSION(cache) \  ((cache)->size * 2) cache_ptrobjc_hash_new (unsigned int size, hash_func_type hash_func,	       compare_func_type compare_func){  cache_ptr cache;   /* Pass me a value greater than 0 and a power of 2.  */  assert (size);  assert (! (size & (size - 1)));   /* Allocate the cache structure.  calloc insures its initialization     for default values.  */  cache = (cache_ptr) objc_calloc (1, sizeof (struct cache));  assert (cache);   /* Allocate the array of buckets for the cache.  calloc initializes     all of the pointers to NULL.  */  cache->node_table    = (node_ptr *) objc_calloc (size, sizeof (node_ptr));  assert (cache->node_table);   cache->size  = size;   /* This should work for all processor architectures (?).  */  cache->mask = (size - 1);	  /* Store the hashing function so that codes can be computed.  */  cache->hash_func = hash_func;   /* Store the function that compares hash keys to determine if they     are equal.  */  cache->compare_func = compare_func;   return cache;}  voidobjc_hash_delete (cache_ptr cache){  node_ptr node;  node_ptr next_node;  unsigned int i;   /* Purge all key/value pairs from the table.  */  /* Step through the nodes one by one and remove every node WITHOUT     using objc_hash_next. this makes objc_hash_delete much more     efficient. */  for (i = 0; i < cache->size; i++)    {      if ((node = cache->node_table[i]))	{	  /* An entry in the hash table has been found.  Now step	     through the nodes next in the list and free them.  */	  while ((next_node = node->next))	    {	      objc_hash_remove (cache,node->key);	      node = next_node;	    }	  objc_hash_remove (cache,node->key);	}    }   /* Release the array of nodes and the cache itself.  */  objc_free(cache->node_table);  objc_free(cache);}  voidobjc_hash_add (cache_ptr *cachep, const void *key, void *value){  size_t indx = (*(*cachep)->hash_func) (*cachep, key);  node_ptr node = (node_ptr) objc_calloc (1, sizeof (struct cache_node));   assert (node);   /* Initialize the new node.  */  node->key    = key;  node->value  = value;  node->next  = (*cachep)->node_table[indx];   /* Debugging.  Check the list for another key.  */#ifdef DEBUG  {    node_ptr node1 = (*cachep)->node_table[indx];    while (node1)      {	assert (node1->key != key);	node1 = node1->next;      }  }#endif   /* Install the node as the first element on the list.  */  (*cachep)->node_table[indx] = node;   /* Bump the number of entries in the cache.  */  ++(*cachep)->used;    /* Check the hash table's fullness.  We're going to expand if it is     above the fullness level.  */  if (FULLNESS (*cachep))    {      /* The hash table has reached its fullness level.  Time to	 expand it. 	 I'm using a slow method here but is built on other primitive	 functions thereby increasing its correctness.  */      node_ptr node1 = NULL;      cache_ptr new = objc_hash_new (EXPANSION (*cachep),				     (*cachep)->hash_func,				     (*cachep)->compare_func);            DEBUG_PRINTF ("Expanding cache %#x from %d to %d\n",		    (int) *cachep, (*cachep)->size, new->size);            /* Copy the nodes from the first hash table to the new one.  */      while ((node1 = objc_hash_next (*cachep, node1)))	objc_hash_add (&new, node1->key, node1->value);            /* Trash the old cache.  */      objc_hash_delete (*cachep);            /* Return a pointer to the new hash table.  */      *cachep = new;    }} voidobjc_hash_remove (cache_ptr cache, const void *key){  size_t indx = (*cache->hash_func) (cache, key);  node_ptr node = cache->node_table[indx];   /* We assume there is an entry in the table.  Error if it is     not.  */  assert (node);   /* Special case.  First element is the key/value pair to be     removed.  */  if ((*cache->compare_func) (node->key, key))    {      cache->node_table[indx] = node->next;      objc_free(node);    }  else    {      /* Otherwise, find the hash entry.  */      node_ptr prev = node;      BOOL removed = NO;      do	{	  if ((*cache->compare_func) (node->key, key))	    {	      prev->next = node->next, removed = YES;	      objc_free(node);	    }	  else	    prev = node, node = node->next;	}      while (!removed && node);      assert (removed);    }    /* Decrement the number of entries in the hash table.  */  --cache->used;}  node_ptrobjc_hash_next (cache_ptr cache, node_ptr node){  /* If the scan is being started then reset the last node visitied     pointer and bucket index.  */  if (!node)    cache->last_bucket  = 0;    /* If there is a node visited last then check for another entry in     the same bucket.  Otherwise step to the next bucket.  */  if (node)    {      if (node->next)	{	  /* There is a node which follows the last node returned.	     Step to that node and return it.  */	  return node->next;	}      else	++cache->last_bucket;  }   /* If the list isn't exhausted then search the buckets for other     nodes.  */  if (cache->last_bucket < cache->size)    {      /*  Scan the remainder of the buckets looking for an entry at	  the head of the list.  Return the first item found.  */      while (cache->last_bucket < cache->size)	if (cache->node_table[cache->last_bucket])	  return cache->node_table[cache->last_bucket];	else	  ++cache->last_bucket;            /* No further nodes were found in the hash table.  */      return NULL;    }  else    return NULL;}  /* Given KEY, return corresponding value for it in CACHE.  Return NULL   if the KEY is not recorded.  */void *objc_hash_value_for_key (cache_ptr cache, const void *key){  node_ptr node = cache->node_table[(*cache->hash_func) (cache, key)];  void *retval = NULL;   if (node)    do      {	if ((*cache->compare_func) (node->key, key))	  {	    retval = node->value;	    break;	  }	else	  node = node->next;      }    while (! retval && node);    return retval;} /* Given KEY, return YES if it exists in the CACHE.  Return NO if it   does not */BOOLobjc_hash_is_key_in_hash (cache_ptr cache, const void *key){  node_ptr node = cache->node_table[(*cache->hash_func) (cache, key)];    if (node)    do      {	if ((*cache->compare_func)(node->key, key))	  return YES;	else	  node = node->next;      }    while (node);   return NO;}

Keyboard shortcuts

General

Show keyboard shortcuts
?
Focus the current search
/

Issues and pull requests

Open filters
f

Issues, pull requests and Inbox

Select next item
j↓
Select previous item
k↑
Open selected item
Enter
Dismiss filters or clear selection
Esc

Repository code

Go to file
t